------------恢复内容开始------------
地址：http://codeforces.com/contest/1311
A. Add Odd or Subtract Even
题意：给定ab两个数，每次操作可以将a增加任意一个奇数或是减少任意一个偶数。问最少几次使两个数字相等
解析：分情况讨论即可。a==b,a>b,a<b，一步到位或者需要加一步？
#include<iostream> #include<cstdio> #include<stack> #include<cstring> #include<string> #include<algorithm> using namespace std; const int maxn=1e5+10; typedef long long ll; int last,cur,ext[maxn]; char s[maxn]; int main() { int t; cin>>t; while(t--) { ll a,b; cin>>a>>b; if(a==b) cout<<"0"<<endl; else if(a>b) { if((a-b)%2==0) cout<<"1"<<endl; else cout<<"2"<<endl; } else { if((a-b)%2==0) cout<<"2"<<endl; else cout<<"1"<<endl; } } }
B. WeirdSort
题意：n个数，m个可更换坐标。对m中的坐标x，可以在数组中进行a[x]和a[x+1]的交换，交换可以任意次，问是否可以把数组变为不递减数组？
解析：需要明确一点就是，在这m个可更换坐标中，我们一定可以把这些相邻数变成非递减的，而达到这一目标后，数组里如果还存在其他递减数字而且无法修改，那么就输出NO。所以，我们while(1)里面对他们进行交换，直到换到这种情形：可交换点与其相邻里已经不存在递减了，就break掉。出循环后，再遍历一遍，如果严格非递减，就YES，否则就是NO！
#include<iostream> #include<cstdio> #include<stack> #include<cstring> #include<string> #include<algorithm> using namespace std; const int maxn=105; int a[maxn],vis[maxn]; int main() { int t; cin>>t; while(t--) { memset(vis,0,sizeof(vis)); int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=m;i++) { int x; cin>>x; vis[x]=1; } while(1) { int k=0; for(int i=1;i<n;i++) { if(vis[i]&&a[i]>a[i+1]) { swap(a[i],a[i+1]); k=1; } } if(!k) break; } int ok=0; for(int i=1;i<n;i++) { if(a[i]>a[i+1]) { ok=1;break; } } if(ok) cout<<"NO"<<endl; else cout<<"YES"<<endl; // for(int i=1;i<=n;i++) // cout<<a[i]<<" "; // cout<<endl; } }
C. Perform the Combo
题意：长为n的字符串，m个错误操作坐标点，如果到错误坐标点，就从头重新读取，然后接着读直到下一个错误点，再重复之前的操作。比如说abcd，3,4,就是:abcabcdabcd。输出a~z各个字母的出现次数。
解析：暴力T了，这数据妥妥的T啊，但是控制不住想试试，耽误了思路。赛后看题解，原来前缀和可以解决这个问题。对于原字符串，不管怎么读错，结尾肯定是一个完整的字符串，所以我们先用num[]数组记下原字符串各字母出现的次数。对于一个字母的出现次数，取决于它的后面字母出现的次数，a[i]循环一次，它的前面所有字母都要+1，所以从后往前记录前缀，累加即可:arr[i]+=arr[i+1]。这个arr[]，就是记录的每个字母循环次数，也就是出现次数(这里面不包括原字符串)。而这个arr前缀初始化，就是对于每个错误操作arr[x]++。具体看代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 2e5+10; int ar[maxn],num[maxn]; int main() { int t; cin>>t; while(t--) { int n,m; memset(num,0,sizeof(num)); memset(ar,0,sizeof(ar)); cin>>n>>m; string s; cin>>s; for(int i=1;i<=m;i++) { int x; cin>>x;x--; ar[x]++; } int len=s.length(); for(int i=0;i<len;i++) { num[s[i]-97]++; } for(int i=len-1;i>=0;i--) { ar[i]+=ar[i+1]; num[s[i]-97]+=ar[i]; } for(int i=0;i<26;i++) { if(i<25) cout<<num[i]<<" "; else cout<<num[i]<<endl; } } }
------------恢复内容结束------------
Codeforces Round #624 (Div. 3)
原文：https://www.cnblogs.com/liyexin/p/12367525.html