WORIA

https://codeforces.com/contest/1323 C. Unusual Competitions   题意：括号序列，每次可以选一段，内部自由调整，花费为这段的长度，问调整成正确序列的最小花费。 直接贪心找错的一段调整。如果右括号左边的左括号不够的话一定是要调整的，就看调整到哪里。 1234567891011121314151617181920212223242526#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1e6 + 10;const int INF = 0x3f3f3f3f;int n;int sum, l, r;char s[N];int ans;int main() { scanf("%d", &n); scanf("%s", s + 1); for (int i = 1; s[i]; i++) { sum += (s[i] == '(' ? 1 ...

http://codeforces.com/contest/1321 B. Journey Planning   题意：给定一个数组，要求找到一个子序列，满足每个元素的值的差等于坐标的差，要求序列总和最大。 对于每个满足条件的序列，它们的第一个元素的下标一定确定了，所以用map维护类似并查集一样，最后找map里的最大值。 123456789101112131415161718192021#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1e4+ 10;const int INF = 0x3f3f3f3f;map<int, ll>mp;int n;int main() { cin >> n; for (int i = 0; i < n; i++) { int x; scanf("%d", &x); mp[x - i] += x; } ll ans = 0; for (auto p ...

http://codeforces.com/contest/1314 A. Recommendations   题意：有n个数，要求所有数不能相同，并给出了每个数+1所需的值，问最小花费。 并查集，贪心 容易得到要求所有数的最终位置乘以花费的和最小，可以贪心，因为花费大的多移动一个大于花费少的多移动一个。 把花费从大到小排序，遍历时遇到相同的数说明要移动了，并且一定是移动后遇到的那个，移动到连续块的最大值处，而连续块可以并查集维护最大值，每次把移完的值x与x+1合并，这样由于每次都一定是移到最大，所以每次都是更新最大值。 1234567891011121314151617181920212223242526#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 2e5 + 10;map<ll, ll>par;ll find(ll x) { if (!par.count(x))par[x] = x; re ...

http://codeforces.com/contest/1313 B. Different Rules   题意：两场比赛，每场有个名次，最终名次为两场名次之和的排名，等于总名次小于等于自己的人数。问最多，最少多少名。 构造，贪心 由于同分都算自己前面，所以最多就是尽量凑和自己同分。最少就是尽量凑比自己多一分。 12345678910111213141516#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 2e5 + 10;int T;int n, a, b;int main() { cin >> T; while (T--) { cin >> n >> a >> b; int y = max(0, a + b - n); cout << min(n, y + 1) << ' ' << ...

http://codeforces.com/contest/1307 C. Cow and Message   题意：给一个串S，其中有等差数列位置的子序列为密码，问等差数列位置出现最多的序列是什么，只要给出最多的出现次数。 如果一个大于2位的序列出现多次，一定有长度为2的序列出现次数只多不少，所以出现次数最多的一定是长度为2的序列，或者长度为1的序列。 只有26个字母，两位串，直接枚举就好了，遍历每一位同时更新。 12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 1e6 + 10;char s[N];ll cnt[100][100], b[100];ll ans;int main() { scanf("%s", s); for (int i = 0; s[i]; i++) { int c = s[i] - ...

http://codeforces.com/contest/1304 D. Shortest and Longest LIS   题意：有一个排列，给出了每个元素与它后面一个元素的大小关系，要求构造出这个序列，满足大小关系且最长上升子序列最大/最小。 构造 考虑如何填小于的位置，要最长，显然是从左到右，从小到大填，然后剩下的位置从从大到小填。 要最短，就从后向前，从小到大填小于号，再从大到小填剩下的。 1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<int, int>pii;const int INF = 0x3f3f3f3f;const int N = 1e6 + 10;int T, n;char s[N];int ans1[N], ans2[N];int main() { cin >> T; while ...

http://codeforces.com/contest/1301 C. Ayoub’s function   题意：已知一个n位的01串中有k个1，问最多有几个子串中至少有1个1. 反面考虑有几个串只有0。每一段长度为a的连续的0会有 a⋅(a+1)2\frac{a\cdot(a+1)}{2}2a⋅(a+1)​ 个只有0的串，把所有连续0结果加起来就是总的只有0的串。 相当于最小化 a⋅(a+1)+(n−a)⋅(n−a+1)=2⋅(a2−na)+n2+na\cdot (a+1)+(n-a)\cdot (n-a+1)=2\cdot(a^2-na)+n^2+na⋅(a+1)+(n−a)⋅(n−a+1)=2⋅(a2−na)+n2+n，当 a=n2a=\frac{n}{2}a=2n​ 时最小，可得尽量分散时最小。 123456789101112131415161718192021222324#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<int, int>pii; ...

http://codeforces.com/contest/1300 C. Anu Has a Function   题意：定义 f(x,y)=(x∣y)−yf(x, y) = (x | y) - yf(x,y)=(x∣y)−y，重排给定数列 [a1,a2,…,an][a_1, a_2, \dots, a_n][a1​,a2​,…,an​]，使得 f(f(…f(f(a1,a2),a3),…an−1),an)f(f(\dots f(f(a_1, a_2), a_3), \dots a_{n-1}), a_n)f(f(…f(f(a1​,a2​),a3​),…an−1​),an​) 最大。 这个函数的作用就是从x中扣掉y里有1的位。 所以实际上只有第一个x对结果有影响，确定了第一个之后其它的顺序无所谓。 第一个里如果某一位有1而其它也存在数这一位为1，那么这个1必定被抠掉，仅当只有第一个数在这一位是1，它才会留到最后。所以就要找到最大的能留到最后的位。就是从大到小遍历找到某一位只有一个数在该位为1。其他的随便排。 123456789101112131415161718192021222324 ...

B. Array Sharpening   题意：给定一个非负数列，每次操作选一个正数-1，问任意次操作后能否变成一个单峰凸函数。 若有奇数个，从两端开始从零递增，判断每个数初始大于终值。 若有偶数个，判断完还要判断中间两个能否大于个数除2，否则没法出现峰值。 123456789101112131415161718192021222324252627282930313233343536373839#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 T;int n;int a[maxn];int main() { cin >> T; while (T--) { cin >> n; bool flg = 1; for (int i = 1; i <= n; i++)
...

http://codeforces.com/contest/1293 D. Aroma’s Search   题意：平面上有几个数据点，(ax⋅xi−1+bx,ay⋅yi−1+by)(a_x \cdot x_{i-1} + b_x, a_y \cdot y_{i-1} + b_y)(ax​⋅xi−1​+bx​,ay​⋅yi−1​+by​)，且 (x0,y0)(x_0,y_0)(x0​,y0​) ,ax,ay,bx,bya_x,a_y,b_x,b_yax​,ay​,bx​,by​ 给定，问在给定总距离内从起始点最多走过几个数据点，距离为曼哈顿距离。 可以发现 (xi,yi)(x_i,y_i)(xi​,yi​) 是指数级增长的，所以总的点数一定不多，试一下发现只有几十个，那就直接暴力枚举从起始点先走到一个数据点，再从这个数据点走向其它点，由于是曼哈顿距离，所以如果两个数据点能互相到达，那么一定可以经过所有中间点。 则枚举起始数据点，和终止数据点，若两者可达，则经过点数为两者中间所有点。 1234567891011121314151617181920212223242526272829303 ...