拉了CF583和CF486的两套div2题目
还是先贴宏定义部分
#define MAXN 1000000+5
#define MOD 1000000007
#define PI (acos(-1.0))
#define EPS 1e-6
#define MMT(s,a) memset(s, a, sizeof s)
#define GO(i,a,b) for(int i = (a); i < (b); ++i)
#define GOE(i,a,b) for(int i = (a); i <= (b); ++i)
#define OG(i,a,b) for(int i = (a); i > (b); --i)
#define OGE(i,a,b) for(int i = (a); i >= (b); --i)
A - Asphalting Roads(CF-583A)
题意就是n条水平路，n条竖直路，构成井字形状。然后第i天会到(xi,yi)这个路口，如果这个路口得两条路都没有被染色，就输出这天并把两个路口都染上颜色，否则跳到下一天。
输出所有可以染色得天数。
题目思路：标记遍历即可
1 1 int main(){ 2 2 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 3 3 int n,x,y; 4 4 cin>>n; 5 5 int mp1[55] = {0},mp2[55] = {0}; 6 6 GO(i,0,n*n){ 7 7 cin>>x>>y; 8 8 if(mp1[x] == 0 && mp2[y] == 0){ 9 9 cout << i+1 << " "; 1010 mp1[x] = mp2[y] = 1; 1111 } 1212 } 1313 cout << endl; 1414 1515 return 0; 1616 }
B - Robot's Task(CF-583B)
题意就是最开始从左往右走，如果现在值Num比a[i]大，则Num+1，否则跳过他，走到尽头如果有数没有经过，则转向再次走，已经走过的地方不能再走。
Num初始值为0，问至少转向几次。
思路：模拟即可
1 1 int main(){ 2 2 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 3 3 int n; 4 4 int a[1005] = {0},vis[1005] = {0}; 5 5 cin>>n; 6 6 GOE(i,1,n){ 7 7 cin>>a[i]; 8 8 } 9 9 bool flag = true; 1010 int cnt = n,ans = 0,num = 0; 1111 while(cnt > 0){ 1212 if(flag){ 1313 GOE(i,1,n){ 1414 if(!vis[i] && num >= a[i]){ 1515 vis[i] = 1; 1616 num++; 1717 cnt--; 1818 } 1919 } 2020 } 2121 else{ 2222 OGE(i,n,1){ 2323 if(!vis[i] && num >= a[i]){ 2424 vis[i] = 1; 2525 num++; 2626 cnt--; 2727 } 2828 } 2929 } 3030 flag = !flag; 3131 if(cnt > 0) 3232 ans++; 3333 } 3434 cout << ans << endl; 3535 3636 return 0; 3737 }
C - GCD Table(CF-583C)
给你一个打乱了的GCD表，问是哪些值构成的。
思路：这n个数一定就是对角线上的数，直接降序排列然后暴力找，每次找到的最大的数一定是其中一个数，然后求出它与已经求出的所有数的gcd在队列中去掉两个这个gcd数，保证所有大于等于下一个数字的gcd一定都被去掉了，剩下的最大的又是要找的数。
额外定义
template<typename T>
using maxHeap = priority_queue<T, vector<T>, less<T> >;
template<typename T>
inline T gcd(T a, T b){ return b==0 ? a : gcd(b,a%b); }
代码
1 1 int main(){ 2 2 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 3 3 int n,k = 0,temp,num; 4 4 int a[250050],b[250050]; 5 5 cin>>n; 6 6 GOE(i,1,n*n){ 7 7 cin>>a[i]; 8 8 } 9 9 sort(a+1,a+1+n*n); 1010 maxHeap<int> q; 1111 OG(i,n*n,0){ 1212 if(!q.empty()) 1313 temp = q.top(); 1414 else 1515 temp = 0; 1616 if(a[i] == temp){ 1717 q.pop(); 1818 continue; 1919 } 2020 GO(j,0,k){ 2121 num = gcd(b[j],a[i]); 2222 q.push(num); 2323 q.push(num); 2424 } 2525 b[k++] = a[i]; 2626 } 2727 GO(i,0,k) 2828 cout << b[i] << " "; 2929 cout << endl; 3030 3131 return 0; 3232 }
F - Calculating Function(CF-486A)
题意就是按照他给的公式输出F(n)；
思路：可以推出n为偶数是F(n) = n/2,否则F(n) = n/2 - n;
代码
1 1 int main(){ 2 2 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 3 3 ll n; 4 4 cin>>n; 5 5 if (n&1) 6 6 cout << n/2 - n << endl; 7 7 else 8 8 cout << n/2 << endl; 9 9 1010 return 0; 1111 }
G - OR in Matrix(CF-486B)
题目就是说bij为i行和j列的值OR操作的结果，现在给你操作后的表，要你求操作前的表。
思路：如果bij = 0，则证明i行和j列全是0，如果是1，则证明i行和j列必须有一个1，所以先把所有值设为1，按照题目把某些行列变为0，再判断一遍是否满足题意即可
代码
1 1 int main(){ 2 2 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 3 3 int n,m; 4 4 int a[105][105],b[105][105]; 5 5 fill(b[0],b[0]+105*105,1); 6 6 cin>>n>>m; 7 7 GOE(i,1,n){ 8 8 GOE(j,1,m){ 9 9 cin>>a[i][j]; 1010 if(a[i][j] == 0){ 1111 GOE(ii,1,n) 1212 b[ii][j] = 0; 1313 GOE(jj,1,m) 1414 b[i][jj] = 0; 1515 } 1616 } 1717 } 1818 1919 GOE(i,1,n){ 2020 GOE(j,1,m){ 2121 if(a[i][j] == 1){ 2222 int flag = 0; 2323 GOE(ii,1,n){ 2424 if(b[ii][j] == 1){ 2525 flag = 1; 2626 break; 2727 } 2828 } 2929 GOE(jj,1,m){ 3030 if(b[i][jj] == 1){ 3131 flag = 1; 3232 break; 3333 } 3434 } 3535 if(!flag){ 3636 cout << "NO" << endl; 3737 exit(0); 3838 } 3939 } 4040 } 4141 } 4242 4343 cout << "YES" << endl; 4444 GOE(i,1,n){ 4545 GOE(j,1,m) 4646 cout << b[i][j] << " "; 4747 cout << endl; 4848 } 4949 5050 return 0; 5151 }
H - Palindrome Transformation(CF-486C)
题意就是4种操作，最开始在k位置操作，问最少操作多少次使得原串变成回文串。
思路：因为是对称的，我们先不要管最开始在哪个位置，遍历即可，当a[i] != a[n-i-1]时候，我们再想是变a[i]还是变另一个，然后答案加上这个值。同时往容器中加上从k走到i远还是走到n-i-1近。
最后排序，答案加上最远距离于最近距离之差再加上这两者距离k最近的距离即可。
为什么只需要不需要管k的位置，因为k无论在哪里，我们都需要把所有不符合的字符走到，所以这里得花掉最远距离和最近距离的差，同时我们最开始在k，需要走到最近的位置开始遍历上一段距离，所以最终答案就是
ans = 每个不合格字符的操作次数 + 不合格字符的区间长度 + 从k位置走到这个区间的某一端点的距离；
因为不管你的k是否在这个区间内，都需要遍历一遍这个区间。
1 1 int main(){ 2 2 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 3 3 int n,k; 4 4 string s; 5 5 vector<int> q; 6 6 cin>>n>>k>>s; 7 7 int len = n/2,ans = 0; 8 8 GO(i,0,len){ 9 9 if(s[i] != s[n-1-i]){ 1010 int tp = abs(s[i] - s[n-1-i]); 1111 tp = min(tp,26-tp); 1212 ans += tp; 1313 if(tp) 1414 q.PB((abs(i+1-k) < abs(n-i-k)) ? i+1 : n-i); 1515 } 1616 } 1717 int cnt = q.size(); 1818 if(q.empty()) 1919 cout << ans << endl; 2020 else{ 2121 sort(q.begin(),q.end()); 2222 ans += q[cnt-1] - q[0] + min(abs(q[cnt-1]-k),abs(q[0]-k)); 2323 cout << ans << endl; 2424 } 2525 return 0; 2626 }
D题E题时间关系暂时不补了。