WORIA

http://codeforces.com/contest/1285 D. Dr. Evil Underscores   题意：给定一个数组，求出 XXX 使得 max⁡1≤i≤n(ai⊕X)\underset{1 \leq i \leq n}{\max} (a_i \oplus X)1≤i≤nmax​(ai​⊕X)，要求输出结果。 对于二进制下某一位，如果既有1又有0，那么不管X取什么，最大值这一位一定为1.否则，一定为0。但是在为1的情况下又分X为0还是1，可能会导致不同的后续结果，所以要dfs搜下去，主要是要知道复杂度是够的，这就是一棵完全二叉树，一共最多n个叶子，log⁡n\log nlogn 层，复杂度是 O(n)O(n)O(n) 的。 12345678910111213141516171819202122232425262728293031#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<int, int> pii;const int INF = 0 ...

http://codeforces.com/contest/1287 B. Hyperset   题意：给出n个字符串，要求若三个字符串每一列的三个字母都不同或者都相同，则可以放一起，求最多凑出几个集合。 若已知两个字符串，则第三个字符串就是确定的。map找到即可。 1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<int, int> pii;const int INF = 0x3f3f3f3f;const int maxn = 1e5 + 10;int n, k;map<string,int>mp;string s[maxn];int ans;int vis[30];char oth(char a, char b) { int x = 'S' - 'A', y = & ...

http://codeforces.com/contest/1269 B. Modulo Equality   题意：给定 a,ba,ba,b 两个数组，求最小的 XXX ，使得 (a[i]+X)mod  m(a[i]+X)\mod m(a[i]+X)modm 与 bbb 的某个排列一一对应。 没法暴力枚举 XXX，所以考虑枚举减小枚举的范围，枚举 bbb 中的数，作为与 a[1]a[1]a[1] 对应的 b[1]b[1]b[1]，可以得到唯一的 XXX，再验证 XXX 是否满足其它 a[i],b[j]a[i],b[j]a[i],b[j] 都有对应。 123456789101112131415161718192021222324#include<bits/stdc++.h>using namespace std;const int INF = 0x3f3f3f3f;int n, m;vector<int> a, b;int main(){ scanf("%d%d", &n, &m); a.resize(n), b.r ...

http://codeforces.com/contest/1271 C. Shawarma Tent   题意：直角坐标系上有一个起始点，和其他点，从起始点到其它点只能经过与最短路径长度相等的路径，现要在整个坐标系上找出一个点，使得从起始点到其他点的路径覆盖该点次数最多。 易证起始点的上下左右四个点一定至少有一个满足条件。因为其它满足条件的点一定有一条路径通过这四个点中的一个，则可以等价过去。 则枚举判断即可。 1234567891011121314151617181920212223242526272829303132333435#include <bits/stdc++.h>using namespace std;#define ll long longtypedef pair<int,int> pii;const int INF=0x3f3f3f3f;const int maxn=1e6+10;int n;ll sx,sy;ll x[maxn],y[maxn];ll dx[]{-1,1,0,0};ll dy[]{0,0,-1 ...

E. Editor http://codeforces.com/contest/1263/problem/E 题意：给定一串操作序列，包含’L’，‘R’即左右移动光标，’(‘，’)'， ‘a-z’，表示给当前光标赋值。要求在每一次操作完成后给出当前序列是否对括号合法，即左右括号匹配，若匹配，则给出括号的最大深度。 线段树+前缀和 维护每个点的前缀和，线段树维护区间内点的前缀的最大和最小值。 当且仅当线段树整个区间的前缀和最小值为 0 并且整个序列的前缀和为 0 时合法。 若合法，则括号最大深度为线段树整个区间的最大值。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include <bits/stdc++.h>using namespace std;#define ll l ...

https://codeforces.com/contest/1243 B2. Character Swap (Hard Version)   题意：给定两个字符串s，t，每次可以在两个字符串中各选一个位置，再字符串间交换，最终要使两个字符串相同。操作数不要求最少，但要小于2n。 贪心构造 挨个遍历过去，如果两个字符串当前位置i不同，则先在s串中找到和s[i]相同的j，交换s[j],t[i]；若找不到，则在t中找和s[i]相同的j，先交换s[j],t[j]，再交换s[j],t[i]。 在每个位置最多交换2次，总共不超过2n。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;const ll mod = 1e9 + ...

http://codeforces.com/contest/1236 C. Labs   题意：把 1到 n2n^2n2 分成n组，组间连边，且只有从大数向小数连有向边，要求最大化两组之间边数的最小值。 直接猜蛇形构造。 12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;int n;int a[310][310];int main() { scanf("%d", &n); int p = 1, ad = 1; for (int i = 1; i <= n * n; i++) { int t = (i - 1) / n + 1; a[p][t] = i; if (p == n && (t & 1) || p == 1 && (!(t & ...

https://codeforces.com/contest/1228 C. Primes and Multiplication   题意：定义 g(x,y)g(x,y)g(x,y) 为最大能整除x的y的幂次，f(x,y)f(x,y)f(x,y) 为所有x的质因数k的 g(y,k)g(y,k)g(y,k) 值的乘积。例如：f(30,70)=g(70,2)⋅g(70,3)⋅g(70,5)=21⋅30⋅51=10f(30, 70) = g(70, 2) \cdot g(70, 3) \cdot g(70, 5) = 2^1 \cdot 3^0 \cdot 5^1 = 10f(30,70)=g(70,2)⋅g(70,3)⋅g(70,5)=21⋅30⋅51=10，求 f(x,1)⋅f(x,2)⋅…⋅f(x,n) mod (109+7)f(x, 1) \cdot f(x, 2) \cdot \ldots \cdot f(x, n) \bmod{(10^{9} + 7)}f(x,1)⋅f(x,2)⋅…⋅f(x,n)mod(109+7)，(2≤x≤109,1≤n≤1018)(2 \le x \le ...

A. Yellow Cards   最多的话，先淘汰k值小的人。最少的话，先每个人扣k-1分，最后如果n还有，则剩多少就淘汰多少人。 123456789101112131415161718192021222324#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn = 1e4 + 5;const int INF = 0x3f3f3f3f;int a1, a2, k1, k2, n;int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> a1 >> a2 >> k1 >> k2 >> n; if (k1 > k2) { swap(a1, a2); swap(k1, k2); } int ansmax, ansmin; int num1 = min(a1, n / k1); ansmax ...

http://codeforces.com/contest/1209 B. Koala and Lights   题意：n个灯，从第b[i]秒开始变，周期为a[i]，问最多有几个灯同时亮。 数字不大，直接枚举时间，周期很小。 123456789101112131415161718192021222324252627#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;int n;int a[N], b[N], c[110][1010];char s[N];int main() { scanf("%d", &n); scanf("%s", s + 1); for (int i = 1; i <= n; i++)scanf("%d%d", &a[i], &b[i]); int ans = 0; for (int ...