Codeforces Round 895 (Div. 3)

A. Two Vessels

求出目标水位，然后计算倒水的次数向上取整即可

void solve(){
   db a, b, c; cin >> a >> b >> c;
   print(int(ceil((max(a, b) - (abs(b + a) / 2)) / c)));
}

B. The Corridor or There and Back Again

对于每个可能被激活的陷阱，计算该陷阱激活后可以走到的最右边的距离，答案就是所有最远距离里的最小值

void solve(){
   int n; cin >> n;
   int ans = inf;
   while (n--){
        int a, b; cin >> a >> b;
        ans = min(ans, a + (b - 1) / 2);
   }
   print(ans);
}

trap是在刚进入时激活的，所以可以移动的步数是b - 1

C. Non-coprime Split

预处理sqrt(1e7)内的质数，然后对于每个l，r，去扫描一遍质数数组，对于每个质数做计算看是否存在符合条件的结果。

vi primes;
void PreProcess(){
    primes = sievePrimes(4444);        //函数模板
}
 
void solve(){
    int l, r; cin >> l >> r;
    liter(prime, primes){
        int a = (l / prime - 1)* prime, b = (r / prime - 1) * prime;//如果除以Prime后不减1，可能会出现：l==r且l被prime整除，则prime + l > r。r%prime >= 0，但是没有 - 1，导致prime + b> r
        if (a > 1 && prime + a >= l && prime + 1 <= r){print(prime, a);return;}
        else if (b > 1 && prime + b >= l && prime + b<= r){print(prime, b); return;}
    }
    print(-1);
}

一开始读错题了，以为a，b都要在l，r区间内。

第一种算法预处理了1e7的质数，TLE。

第二种算法尝试用2与[l, r]之间的偶数进行匹配， WA。

第三种算法对每个质数尝试找到一个解，AC。

为什么在寻找含有prime的因子时一定要被prime除了以后将结果-1，而且这种方法一定正确？

因为r/prime - 1>=1必须成立，才可能有解。如果这个式子不成立，说明r最多只能包含一个当前的prime，不可能包含第二个也含有prime的因子。比如r= 5, r/2-1 = 1，可以包含2，2。r = 3, r/2 -1 = 0，r范围内只能包含一个2，不可能包含第二个2出来。

所以也可以这么理解，先将r降为当前prime最大整数倍r = r / prime * prime，然后看r中是否包含了至少2个prime，即r / prime >= 2。这两个条件都满足，则一定有解。

至于为什么要计算L，因为做题时没有想到L的计算是非必须的。只要单独的把R拿出来进行计算，L最后只用来做大小的比较即可，代码也可以AC。

如果按L来计算的话，应该是这样的：L = L / prime  + (L % prime != 0)，然后再判断L是否小于R，L中是否包含了至少2个prime即可。

D. Plus Minus Permutation

统计x下标出现的次数，y下标出现的次数，以及两者同时出现的次数。

贪心策略：将从n开始计数的大的数放到x的下标上，从1开始计数的小的数放到y的下标上，其他的数无所谓。因为位置最多只能有n个，所以这种放置策略一定正确。

void solve(){
    ll n, x, y; cin >> n >> x >> y;
    ll x1 = n / x, y1 = n / y, z = n / lcm(x, y);//x和y的最小公倍数
    x1 -= z, y1 -= z;
    ll r = n, l = 1;
    ll a = (r - x1 + 1 + r) * (x1) / 2;
    ll b = (y1 + l) * y1 / 2;
    print(a - b);
}

一开始居然看成了把加减法看成了乘数法qaq
 

E. Data Structures Fan

给长度为n的字符串01序列和长度为n的数组，将数组按字符串中为0还是为1分成两部分。q个询问，每个询问可能是将区间LR中的数取反，或者询问数组中所有字符串对应位置为0或者为1的异或和。

预处理一个前缀异或和，以及数组中1的异或和，数组中0的异或和。区间修改时将两个异或结果与区间异或和[L, R]做一次运算即可。

void solve(){
    int n; cin >> n;
     vi a(n + 1); LITER(x, a) cin >> x;
     string s; cin >> s;
     s = ' ' + s;
     vi prefix(n + 1);
     int z = 0, o = 0;
     lfor (i, 1, n){
        prefix[i] = prefix[i - 1] ^ a[i];
        if (s[i] == '1'){o ^= a[i];}
        else z ^= a[i];
     }
     int q; cin >> q;
     vi ans;
     while (q--){
        int c; cin >> c;
        if (c == 2){
            int d; cin >> d;
            ans.pb(d == 0 ? z : o);
        }
        else{
            int l, r; cin >> l >> r;
            o ^= prefix[r] ^ prefix[l - 1];
            z ^= prefix[r] ^ prefix[l - 1];
        }
     }
     print(ans);
}

算法正确性的保证在于：区间取反说明区间中的0都变成了1，1 都变成了0。如果[L, R]中有新的数变成了1，那么1一定要跟他们做运算（增加这些数到结果中），如果有1变成了0，那么1也要跟他们做运算（从结果中消除这部分数），对于0同理。

写完E题已经晚上11点半，洗洗睡了。等有机会FG再见