2022 ACM-ICPC 网络赛(1) 个人题解 更新至5题

民富

A题如果i=1的时候，s=1,那cnt=1,f=f[i-2]+1。这里的f[i-2]不就RE了咩[好奇][思考]

咱比比黑

越界不一定re（）

周小乙

a题能不能用线段树写啊，写崩了昨天[大哭]

除了沉默

D题写了半天过不了，我感觉我二分写的没有问题呀
有没有大佬帮我看看问题在哪[大哭]
void init() {
        //枚举左半段1~111111111111111 的情况
        for (long long i = 0; i <= (1 << 16) - 1; i++) {
                //i必须是奇数,比如i=2  10作为左半段明显不符合
                if (i & 1) {
                        long long p = i, cnt = 0;
                        //寻找左半段1的个数
                        while (p) {
                                p &= p - 1;
                                cnt++;
                        }
                       //添加相同个数的0
                        nums.push_back(i << cnt);
                }
        }
        sort(nums.begin(), nums.end());
}
//二分
long long findVal(long long l, long long r) {
        int left = 0, right = nums.size() - 1, m;
        while (left <= right) {
                m = (left + right) / 2;
                if (nums[m] >= l && nums[m] <= r) {
                        return nums[m];
                } else if (nums[m] < l) {
                        left = m + 1;
                } else if (nums[m] > r) {
                        right = m - 1;
                }
        }
        return -1;
}
int main() {
        init();
        scanf("%d", &T);
        while (T--) {
                scanf("%ld%ld", &l, &r);
                printf("%ld\n", getVal(l, r));
        }
}

别再闹了

在一顿卡顿之后，AC了[发呆]

强者就是道理

可以

伊剑

请问K就是80*5000*5000的复杂度吗，好卡啊

曾志韦

这里不应该是如果当前点是0，对f没贡献，如果是1，我们要从这段连续的1的前边（那是一个0）递推贡献。我按这个逻辑改了这个部分，过了；可是为什么按作者的写法也能过？

夏日冰泉

为什么我这样写过不了呢，求教呜呜呜
#include<bits/stdc++.h>
using namespace std;
int mp[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        memset(mp,0,sizeof mp);
        int a,b,cnt=0;
        for(int i=1;i<=n-1;i++)
        {
            cin>>a>>b;
            mp[a]++,mp++;
        }
        for(int i=1;i<=n;i++)
            if(mp==1)cnt++;
        cout<<cnt<<endl;
    }
    return 0;
}

李健鹏

因为，n可以等于 1