Codeforec Contest 460

#codeforce

题目链接在这里

A. Vasya and Socks

初始共有n个,之后每m天多一个,其中发的那个第二天才能用,每天消耗一个,问能维持多少天?

直接模拟就可以,不过能写出推导式子更好。
我是这么理解的,以第二个例子n = 9, m = 3为例:
○ ○ ● ○ ○ ● ○ ○ ● ○ ○ ● ○
空心○ 表示从一开始就有,实心● 表示后来发的。
假设最后共使用了s天,于是有
s / m + n = s
最后的 = 后来发的 + 最开始的, 但是当天发的是没法当天用的,因此如果s是m的倍数,s需要减1。
注s的推导: 假设s = p * m + q,可以得到p = n / (m - 1), q = n % (m - 1),所以s = n * m / (m - 1)

int main()
{
    int n,m;
    cin >> n >> m;
    int s = n * m / (m - 1);
    if (s % m == 0)
        --s;
    cout << s << endl;
    return 0;
}

B. Little Dima and Equation

给定一个公式,x = b * s(x) ** a + c
a,b,c给定,s(x)表示x十进制的各位和,**表示求幂,注意x的范围: 0←x→1e9,1e9单循环都会比较耗时。
因此暴力是不行的。
那就再看s(x)的范围,x最多是9个9,可以得到:0←x→81,循环一边得到结果即可。

int main()
{
    LL a,b,c;
    vector<LL> ans;
    cin >> a >> b >> c;

    for (int i = 0; i <= 81; ++i)
    {
        LL x = 1;
        for (int j = 0; j < a; ++j)
            x *= i;
        x = b * x + c;
        LL y = x;
        int j = 0;
        while (y)
        {
            j += (y%10);
            y /= 10;
        }
        if (i == j && x < 1e9 && x > 0)
            ans.push_back(x);
    }

    cout << ans.size() << endl;
    sort(ans.begin(), ans.end());
    for (vector<LL>::iterator iter = ans.begin(); iter != ans.end(); ++iter)
    {
        cout << *iter << " ";
    }
    if (!ans.empty())
    cout << endl;

    return 0;
}

C. Present

有n朵花,每次浇连续的w朵,被浇的花会长高1,问m天后最低的那朵最高是多高?
注意范围:1 ≤ w ≤ n ≤ 1e5; 1 ≤ m ≤ 1e5
套两层循环,比如

for i : 1 to m  
    for j : 1 to n  

就会超时,更直接的思路是直接二分求结果。
注意二分的结束条件,关于二分的一篇笔记
数组water_cnt记录对第i朵花实际浇了多少次可以到希望的高度。
scurr维护了浇到当前花的次数(包括之前和当前花的次数,即water_cnt[i - w + 1] + … + water_cnt[i])
对下朵花,只要减去water_cnt[i - w + 1]就可以了,计算完后加上water_cnt[i + 1]就可以更新scurr。
这样计算当前花在前面浇花过程中浇了多少次了,更简单一些。

int main()
{
    LL n,m,w, ans = 0;
    cin >> n >> m >> w;
    LL a[100000] = {0};
    LL water_cnt[100000] = {0};
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    LL low = 1, high = 1e10;
    while (low < high) {
        LL mid = (low + high + 1) >> 1;
        LL scurr = 0;//记录前面有多少次浇到了当前花,即[current - w + 1,current]共浇了多少次。
        LL x = 0;

        //compute x,x是浇花要浇到至少mid高度,所需要的天数
        //water_cnt记录实际浇的次数
        for (int i = 0; i < n; ++i) {
            water_cnt[i] = 0;
            scurr -= i >= w ? water_cnt[i - w] : 0;//i - w的花浇不到当前花,去掉后就是前面浇花时,浇到了当前花的次数

            LL water_needed = mid - a[i];//需要浇多少
            if (scurr < water_needed) {
                water_cnt[i] = water_needed - scurr;//相减实际浇多少就可以到mid高度了
                scurr += water_cnt[i];//更新供下朵花使用该值
                x += water_cnt[i];
                if (x > m) {
                    break;
                }
            }
        }


        if (x <= m)
        {
            low = mid;
        }
        else
        {
            high = mid - 1;
        }
    }

    cout << low << endl;
    return 0;
}

D. Little Victor and Set

给定一个范围[l,r],从其中选取数字,使得所有数字异或的值最小。数字的个数1 <= x <= k。
范围是:1 ≤ l ≤ r ≤ 1e12; 1 ≤ k ≤ min(1e6, r - l + 1)。

求解这道题目,关于异或,有几个知识点:

x ^ x = 0//异或自己为0
x ^ 0 = x//异或0为自己
(2 * x) & (2 * x + 1) = 1//对一个偶数,与+1后的奇数异或为1,以为对偶数+1,只会让最低位变1,其余位不变。 

c = r - l + 1, 可知k≤4不妨分以下几个情况讨论:

  1. c≤4 → 状态DP求解即可
  2. 如果c>4
    2.1. k == 1 → 取l
    2.2. k == 2 → ans = 1,按第三个条件取
    2.3. k == 4 → ans = 0, 按第三个条件取,取两组,则结果为0。
    2.4. k == 3 → 按第三个条件取,ans为1。然后就是看下有没有取到0的办法,比如
    3^5^6=0, 2^4^6=0
    观察可知这种数字很多,如果有我们只要构造一组即可,构造的思路如下:
    如果三个数异或为0,那么每一位组合有4种情况:
    1 0 1 0 1 1 0 0 0 1 1 0 假设我们得到三个数字x>y>z满足x^y^z=0,那么对于x最高的为1的那一位,只能是第一种情况,即这一位:
    x为1,y为1,z为0。
    比如z=101101,那么x,y的第7位应当均为1,于是有
x: 1 * * * * * *
y: 1 * * * * * *
z: 0 1 0 1 1 0 1

同时为了使得x>y,那么第6位应当x为1,y为0,注意也可以x为0,y为1,但如果是这样,就意味着更高位需要x为1,y为0才能保证x>y, 注意我们是在构造数据,因此应当x,y使得尽量小,而不是尽量大。于是有

x: 1 1 * * * * *
y: 1 0 * * * * *
z: 0 1 0 1 1 0 1

接下来的每一位,可以令x均为0,y与z相同,这样范围应该就是最小的了。于是有

x: 1 1 0 0 0 0 0
y: 1 0 0 1 1 0 1
z: 0 1 0 1 1 0 1

按照这个构造的思路,可知道z越大,则x,y越大,如果对于z=l,仍然无法找到这样的x,y那么结果为1,否则结果为0.
假设z的最高1位是j,则

x = 2 ^ (j + 1) | 2 ^ j
y = 2 ^ (j + 1) | (z & ~(2 ^ j))

关于第一种情况里的状态DP,正在整理一篇笔记,会逐步贴出。

同时1 << 34这种代码会超int,因此需要修改为LL b = 1; b << 34才能AC.

具体代码如下:

void solution_dp()
{
    const int max_state = (1 << 4);
    LL dp[max_state] = {0};
    int state = -1;
    for (int i = 0; i < max_state; ++i)
        for (int j = 0; j < c; ++j) {
            if (i & (1 << j))
                continue;
            int new_state = (1 << j) | i;
            int number_one_cnt = 0;
            int p = new_state;
            while (p)
            {
                number_one_cnt++;
                p = p & (p - 1);
            }
            dp[new_state] = dp[i] ^ (l + j);
            if (ans == -1 || dp[new_state] < ans && number_one_cnt <= k) {
                ans = dp[new_state];
                state = new_state;
            }
        }

    for (int i = 0; state; ++i) {
        if (state & 1)
            vec.push_back(l + i);
        state >>= 1;
    }
}

void solution_constructive()
{
    if (k == 1) {
        ans = l;
        vec.push_back(ans);
    }
    else if (k == 2) {
        ans = 1;
        if (l & 1)
            l++;
        vec.push_back(l);
        vec.push_back(l + 1);
    }
    else if (k == 3) {
        LL z = l;
        int max_sign = -1;
        for (LL i = 0; z; ++i) {
            max_sign = i;
            z >>= 1;
        }
        LL b = 1;
        LL x = (b << (max_sign + 1)) | (b << max_sign);//如果直接1<<max_sign会超int有可能,需要指定LL.
        if (r >= x) {
            z = l;
            ans = 0;
            LL y = (b << (max_sign + 1)) | (z & ~(b << max_sign));
            vec.push_back(x);
            vec.push_back(y);
            vec.push_back(z);
        }
        else {
            ans = 1;
            if (l & 1)
                l++;
            vec.push_back(l);
            vec.push_back(l + 1);
        }

    }
    else if (k >= 4) {
        ans = 0;
        if (l & 1)
            l++;
        vec.push_back(l);
        vec.push_back(l + 1);
        vec.push_back(l + 2);
        vec.push_back(l + 3);
    }
}

int main()
{
    cin >> l >> r >> k;
    c = r - l + 1;

    if (c <= 4) {
        solution_dp();
    }
    else {
        solution_constructive();
    }

    cout << ans << endl;
    cout << vec.size() << endl;
    for (vector<LL>::iterator iter = vec.begin(); iter != vec.end(); ++iter) {
        cout << *iter << " ";
    }
    cout << endl;

    return 0;
}