首页 > 代码库 > Codeforces Round #215 (Div. 1)
Codeforces Round #215 (Div. 1)
A Sereja and Algorithm
题意：给定有x,y,z组成的字符串，每次询问某一段s[l, r]能否变成变成zyxzyx的循环体。
分析：
分析每一段x,y,z数目是否满足构成循环体，当然长度<3的要特判。
代码：
1 #include <bits/stdc++.h> 2 #define in freopen("solve_in.txt", "r", stdin); 3 #define pb push_back 4 5 using namespace std; 6 typedef long long LL; 7 8 const int maxn = (int)1e5 + 100; 9 char s[maxn];10 int cnt[maxn][3];11 int main() {12 13 int m;14 scanf("%s", s+1);15 scanf("%d", &m);16 int len = strlen(s+1);17 for(int i = 1; i <= len; i++) {18 for(int k = 0; k < 3; k++)19 cnt[i][k] = cnt[i-1][k];20 cnt[i][s[i]-‘x‘]++;21 }22 for(int i = 0; i < m; i++) {23 int l, r;24 scanf("%d%d", &l, &r);25 int a = cnt[r][0]-cnt[l-1][0];26 int b = cnt[r][1]-cnt[l-1][1];27 int c = cnt[r][2]-cnt[l-1][2];28 int tmp = r-l+1;29 if(tmp < 3)30 puts("YES");31 else {32 33 if(tmp%3 == 0) {34 if(a == b && b == c)35 puts("YES");36 else puts("NO");37 } else if(tmp%3 == 1) {38 if((a == b && c - b == 1) || (b == c && a-b == 1) || (a == c &&b -a == 1))39 puts("YES");40 else puts("NO");41 } else {42 if((a == b && a-c == 1) || (b == c && b-a==1) || (a == c && a-b == 1))43 puts("YES");44 else puts("NO");45 }46 }47 }48 return 0;49 }
B Sereja ans Anagrams
题意：给定2个数组，a[1...n]，以及b[1...m]问能否从a中等间隔的选取m个数，使得这m个数与b中各个整数数目对应相等。
分析：
容易知道由于是等间隔p的出现，所以可以将a[1..n]的数按间隔分成p组，每次添加一个数时，看相应的组m个数形成的序列是否和b中数的数目对应相等，每次添加，减少一个数，最多改变2个数的数目，看是不是所有的数的数目都满足与在b中的相等。感觉和单调队列类似。
代码：
1 #include <bits/stdc++.h> 2 #define in freopen("solve_in.txt", "r", stdin); 3 #define pb push_back 4 5 using namespace std; 6 typedef long long LL; 7 typedef map<int, int> MPII; 8 9 const int maxn = 2*(int)1e5;10 int n, m, p;11 MPII mps, mx[maxn];12 vector<int> ans;13 int a[maxn], b[maxn];14 int sat[maxn];15 queue<int> q[maxn];16 17 int main() {18 19 scanf("%d%d%d", &n, &m, &p);20 for(int i = 0; i < n; i++) {21 scanf("%d", a+i);22 }23 int dif = 0;24 for(int i = 0; i < m; i++) {25 int t;26 scanf("%d", &t);27 if(mps[t] == 0)28 dif++;29 mps[t]++;30 }31 for(int i = 0; i < n; i++) {32 int di = i%p;33 if(q[di].size() >= m) {34 int u = q[di].front();35 q[di].pop();36 if(mx[di][u] == mps[u])37 sat[di]--;38 else if(mx[di][u] == mps[u]+1)39 sat[di]++;40 mx[di][u]--;41 }42 int u = a[i];43 q[di].push(a[i]);44 if(mx[di][u] == mps[u])45 sat[di]--;46 else if(mx[di][u] == mps[u]-1)47 sat[di]++;48 mx[di][u]++;49 if(sat[di] == dif)50 ans.pb(i-(m-1)*p);51 }52 cout<<ans.size()<<endl;53 for(int i = 0; i < ans.size(); i++) {54 printf("%d%c", ans[i]+1, i == ans.size()-1?‘\n‘:‘ ‘);55 }56 return 0;57 }
C Sereja and the Arrangement of Numbers
题意：n个位置，从m不同的数中选一些数去填充，构成一个数组，数组中出现的任何两个数一定要在数组中至少连续出现一次，每个数都有一个代价，要求选出的数总代价最大！
分析：首先肯定的是选出代价尽量大的数，那么就要确定n个位置最多放多少个不同的数，做的时候其实是想到了完全图的，但是没继续想下去。由于任何两个数都要相邻出现，所以肯定是满足完全图关系的，但是如果将相邻关系看做一条边的话，n个位置n-1条边，而且这n-1条边是能够从左走到右，也就是构成一个半欧拉图。
半欧拉图：最多有两个点度数为奇数。对于偶数个节点完全图，每个点度数为奇数，添加一条边能够使得两个点度数变为偶数，所以最少需要添加(点数/2-1)条边构成半欧拉图，因为最终还是允许两个点度数为奇数。奇数个结点完全图，度数为偶数，所以不需要添加边了。
这样根据，图中n-1条边二分最多能放置的结点数，得到数组中最多出现多少个不同的数，贪心选取最大就行了。
代码：
1 #include <bits/stdc++.h> 2 #define in freopen("solve_in.txt", "r", stdin); 3 #define pb push_back 4 5 using namespace std; 6 typedef long long LL; 7 typedef map<int, int> MPII; 8 const int maxn = (int)1e5 + 100; 9 10 int w[maxn];11 int getAns(int lim, int r){12 int l = 1;13 while(l < r){14 int mid((l+r+1)>>1);15 int tmp;16 if(mid&1){17 tmp = ((LL)mid*(mid-1)>>1);18 if(tmp <= lim)19 l = mid;20 else r = mid-1;21 }22 else {23 tmp = ((LL)mid*(mid-1)/2+mid/2-1);24 if(tmp <= lim)25 l = mid;26 else r = mid-1;27 }28 }29 return l;30 }31 int main(){32 33 int n, m;34 scanf("%d%d", &n, &m);35 for(int i(0); i != m; i++){36 scanf("%*d%d", w+i);37 }38 sort(w, w+m, greater<int> ());39 n = getAns(n-1, m);40 LL ans = 0;41 for(int i = 0; i != n; i++)42 ans += w[i];43 cout<<ans<<endl;44 return 0;45 }
Codeforces Round #215 (Div. 1)