Codeforces Round #418 (Div.2)
A. An abandoned sentiment from past
题意:给你一个含有n个数的序列,其中有k个数为0,再给你k个数,让你将序列中的0用这k个数代替,每个数只能用一次,问你能不能使替代后的n个数不是递增的,能则输出Yes,否则输出No
将k个数从大到小排列,依次代替0,再判断是否递增即可
#include#include #include #include using namespace std; int main(){ int n,k; int a[105],b[105]; cin>>n>>k; for(int i=0;i >a[i]; for(int i=0;i >b[i]; sort(b,b+k); int j=k-1; for(int i=0;i a[i+1]){ cout<<"Yes"<
题意:有三个序列a,b,p,均含有n个整数其中p为标准序列是1到n的整数(不重复),而a和b中有且只有1个元素和p不同,a、b序列至少有一个元素不同(最多两个),给你序列a和b,让你求p
a和b中要么一个元素不同,要么两个元素不同, 注意p中的元素各不相同用个数组记录a和b中已经相同的元素,若a和b只有一个元素不同,则将其改为未出现的元素即可,若有两个元素不同,则要考虑可能有一个元素在a或b里重复,再修改即可
#include#include #include #include using namespace std; int c[1005]; int x,y,z,d,e,f; int main(){ int n; int a[1005],b[1005]; cin>>n; for(int i=0;i >a[i]; for(int i=0;i >b[i]; int k=0; for(int i=0;i C. An impassioned circulation of affection
由于q很大,n很小,所以应该考虑预处理原字符串,对于每个字符c,计算从第i(i<=n)个字符到第j(i<=j<=n)个字符中与c不同的字符的个数ans,更新dp[c][ans]=max(dp[c][ans],j-i+1),这个dp数组表示什么呢,表示恰好修改ans个字符后的序列中最多含有的连续个c字符数,这和最后的答案有区别,因为有的不用修改ans次就能有相同的答案,故需再更新一下$dp[c][i]=max(dp[c][i-1],dp[c][i])$.
#include#include #include #include #include #define MAXN 1005 #define MAXM 30005 using namespace std; int dp[1505][1505],d[1505][1005]; string s; int main(){ int l; cin>>l; for(int i=1;i<=l;i++){ cin>>s[i]; } for(int k='a';k<='z';k++) for(int i=1;i<=l;i++){ int ans=0; for(int j=i;j<=l;j++){ if(s[j]!=k) ans++; dp[k][ans]=max(dp[k][ans],j-i+1); } } for(int k='a';k<='z';k++) for(int i=1;i<=l;i++) dp[k][i]=max(dp[k][i-1],dp[k][i]); int n; cin>>n; for(int i=0;i >b>>a; cout<