WORIA

https://codeforces.com/contest/1278 B. A and B   题意：用正负1到正负n凑出x，每对正负只能且必须选正或负，问最小的n。 观察发现用1到n可以凑出 [(−(1+n)⋅n)/2,(1+n)⋅n/2][(-(1+n)\cdot n)/2,(1+n)\cdot n/2][(−(1+n)⋅n)/2,(1+n)⋅n/2] 的与两端点奇偶性相同的所有数，那就先二分找到，在看如果奇偶性不对，就+1. 123456789101112131415161718192021222324#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1e8 + 10;const int INF = 0x3f3f3f3f;typedef pair<int, int>pii;int T;vector<ll>vc;int main() { cin >> T; for (int i = 0; i < 100000; i ...

http://codeforces.com/contest/1260/problem/C B. Obtain Two Zeroes   题意：两个整数 a,b,(a,b≥0)a,b,(a,b\geq 0)a,b,(a,b≥0)，每次 a−=xa-=xa−=x 且 b−=2xb-=2xb−=2x 或 a−=2xa-=2xa−=2x 且 b−=xb-=xb−=x，xxx 为正整数。问任意次操作后能否使 a，b都等于0. 把所有对a减x的操作合并为减x，所有对b减x的操作合并为减y。 则 a=x+2y,b=2x+ya=x+2y,b=2x+ya=x+2y,b=2x+y。 a+b=3⋅(x+y)a+b=3\cdot (x+y)a+b=3⋅(x+y)。即 a+ba+ba+b 为 3 的倍数。 但由于有 a=1，b=8这样的情况，还要一步。 x=3⋅(2b−a)≥0x=3\cdot (2b-a)\geq 0x=3⋅(2b−a)≥0，所以 2b−a≥02b-a\geq 02b−a≥0。同理，2a−b≥02a-b\geq 02a−b≥0。 12345678910111213141516171819#in ...

http://codeforces.com/contest/1207 B. Square Filling   题意：一个nm的01矩阵，要求在一个初始为0的nm矩阵中操作，每次选一个2*2的正方形置为1，问能否得到和给定矩阵一样的矩阵。 遍历，贪心地判断如果当前位置的正方形内都是1，则置为1，最后看如果两个矩阵不同，则不行。 1234567891011121314151617181920212223242526272829303132333435363738394041#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;int n, m;int a[100][100], b[100][100];typedef pair<int, int> pii;vector<pii>vc;int cal() { int ans = 0; for (int i = 1; i <= ...

http://codeforces.com/contest/1202 A. You Are Given Two Binary Strings…   题意：给定二进制下两个数，把第二个数左移k位，与第一个数相加，再把数字倒过来，要求字典序最小，求k。 第二个数最低位的1要和第一个数对应位置之前的1对齐。再移位只会增大位数。 1234567891011121314151617181920212223242526#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;int T;char s[N], t[N];int main() { cin >> T; while (T--) { scanf("%s", s); scanf("%s", t); int n = strlen(s), m = strlen(t); int p; for ...

https://codeforces.com/contest/1197 D. Yet Another Subarray Problem   题意：给定一个数组，和m，k。问所有区间的 ∑i=lrai−k⌈r−l+1m⌉\sum\limits_{i=l}^{r} a_i - k \lceil \frac{r - l + 1}{m} \rceili=l∑r​ai​−k⌈mr−l+1​⌉ 的最大值。1≤n≤3⋅105,1≤m≤10,1≤k≤1091 \le n \le 3 \cdot 10^5, 1 \le m \le 10, 1 \le k \le 10^91≤n≤3⋅105,1≤m≤10,1≤k≤109 dp 从m的范围应该要想到对m的模作为dp的一维。 dp[i][j]dp[i][j]dp[i][j] 表示以 i 为右端点，长度对m的模为 j 的区间的最大值。 则当模从0变为1时，⌈r−l+1m⌉\lceil \frac{r - l + 1}{m} \rceil⌈mr−l+1​⌉ 的值+1，这时的值为模为0时的值 -k。 其它时候直接+a[i]。 转移方程为： dp[i][j]=dp[ ...

https://codeforces.com/contest/1187 C. Vasya And Array   题意：有一个数组，已知某几个区间非递减，某几个不是非递减，要求构造出这个数组。 构造 要尽可能地构造出尽量多的不是非递减的区间，所以在满足非递减区间的基础上，其它都安排为递减。 设vis[i]表示第i位大于等于第i-1位，则所有已知非递减的区间除左端点外都vis=1. 从前往后遍历，遇到vis=1的就设置该位等于前一位，否则等于前一位-1。 1234567891011121314151617181920212223242526272829303132333435#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const ll mod = 1e9 + 7;const int N = 2e5 + 10;int n, m;typedef pair<int, int& ...

https://codeforces.com/contest/1175 E. Minimal Segment Cover   题意：在一条直线上给定了 n 个区间，m次询问，每次给出一个区间，问至少需要多少个区间能够覆盖询问区间。注意是覆盖区间中的所有实数点，不只是整数点。 倍增 这种问题好像是经典的倍增。 mx[i][j]mx[i][j]mx[i][j] 表示从坐标 iii ，经过 2j2^j2j 个区间，最远到达的坐标。 可以通过二分来确定，但是由于进制数可以贪心，所以只要贪心地从大到小遍历 jjj ，每当 mx[i][j]<ymx[i][j]<ymx[i][j]<y 时跳 jjj。注意由于不是小于等于并且在同一个区间内也要跳，所以最后还要跳一次 mx[i][0]mx[i][0]mx[i][0]。 可以通过dp得到 mx[i][0]mx[i][0]mx[i][0]，对于每个区间，左端点 mx[i][0]=max(mx[i][0],r)mx[i][0]=max(mx[i][0],r)mx[i][0]=max(mx[i][0],r)，再遍历坐标，mx[i][0]=ma ...

https://codeforces.com/contest/1167 E. Range Deleting   题意：给定一个长为n，且每个数都小于等于x的数列a，设 f(l,r)f(l,r)f(l,r) 为删除数值大小在 [l,r][l,r][l,r] 的数之后剩下的数列，问有多少对 l,r 满足 f(l,r)f(l,r)f(l,r) 非递减。 设 L 为最大的满足1到L非递减的数。 R 为最小的满足R到x非递减的数。 则 l，r 必定位于如下位置。 所以只要先处理出 L，R ，再枚举 l ，找到对应的最小的 r，从 r 到 x 这一段都是可以与当前 l 配对的。 而最小的 r 必须要 r+1 最小出现的位置大于 l-1 最大出现的位置，也就是删除 l，r后 l -1 和 r+1 要能拼起来。可以二分找到大于 l-1 的最小的 r+1。 由于有一些数没有在数列中出现过，所以可以放在任意位置，为了使答案最大，在不同时候要放在不同位置，所以用 vi[i] 记录是否不在数列中。 1234567891011121314151617181920212223242526272829303132 ...

https://acm.ecnu.edu.cn/contest/363/ D. 一！二！三！   题意：给定 L,R,0≤L≤R≤1018L,R,0\le L\le R\le 10^{18}L,R,0≤L≤R≤1018，求满足 x⊕3x=2xx\oplus 3x=2xx⊕3x=2x 的 xxx 的个数。 数位dp 看到这数据范围就要想到数位 dp。 首先推式子。 左右同时异或上 xxx，得到 3x=x⊕2x3x=x\oplus 2x3x=x⊕2x，即 x⊕2x=x+2xx\oplus2x=x+2xx⊕2x=x+2x。 我们知道 x+y=x⊕y+((x&y)<<1)x+y=x\oplus y+((x\&y)<<1)x+y=x⊕y+((x&y)<<1)，所以 x+2x=x⊕2x+((x&2x)<<1)x+2x=x\oplus 2x+((x\&2x)<<1)x+2x=x⊕2x+((x&2x)<<1)，所以 x⊕2x+((x&2x)<<1)=x⊕2xx\o ...

https://acm.ecnu.edu.cn/contest/362/ A. 棋局   题意：在一个 n∗mn*mn∗m，1≤n,m≤101\le n,m\le 101≤n,m≤10 的棋盘上，每格有 a[i][j]a[i][j]a[i][j] 和 b[i][j]b[i][j]b[i][j]，两人轮流下棋，仅当该位置没有棋子且该位置左侧和上方所有格子内都有棋子，才可以在该位置落子。最终，先手方的分数为占有的格子的 aaa 值之和，后手方的分数为占有的格子的 bbb 值之和，问双方都最优的情况下最终先手方与后手方的分数差。 MinMax博弈+哈希/轮廓线dp 两种做法。 第一种 哈希。 本题最关键的一点是，由于落子的格子必须上方和左方都放满了，所以棋盘上一定是每一行的棋子数递增，第一行最多，第二行其次，以此类推。且每一行都是放满了一个前缀。 这就限制了实际上可行的状态数非常少，少到可以直接暴力dfs枚举。 数组 p[i]p[i]p[i] 记录下第 iii 行有几个棋子，哈希存起来，dfs。 本来MinMax是要分当前是先手方还是后手方讨论的，但是因为这里只要求差值，所以换了一个人操作， ...