站酷网官网网址,网页设计与制作实例教程,中文版本wordpress,安平县建设局网站题目暂时是AC#xff0c;现在是Hack阶段#xff0c;代码仅供参考。 A. Recovering a Small String
题目给出的n都可以由字母来组成#xff0c;比如4可以是aab#xff0c;字母里面排第一个和第二个#xff0c;即1124。但是会歧义#xff0c;比如aba为1214#xff0c;也是…题目暂时是AC现在是Hack阶段代码仅供参考。 A. Recovering a Small String
题目给出的n都可以由字母来组成比如4可以是aab字母里面排第一个和第二个即1124。但是会歧义比如aba为1214也是4答案就不唯一输出字典序最小的那三个字母。
直接枚举。
#include bits/stdc.h
//#define int long long
#define per(i,j,k) for(int (i)(j);(i)(k);(i))
#define rep(i,j,k) for(int (i)(j);(i)(k);--(i))
#define fr first
#define se second
#define endl \n
using namespace std;int n;void solve(){cinn;per(i,a,z){per(j,a,z){per(k,a,z){int tii-a1;int tjj-a1;int tkk-a1;if(titjtkn){cout(char)i(char)j(char)kendl;return;}}}}
}void init(){}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t;cint;while(t--)solve(),init();return 0;
} B. Make Equal
你可以任选序列中的两个数 i j让 a[i] 减去 1~a[i] 的任意值 加到 a[j] 上面这个操作可以无限执行问是否可以让序列的每个数都相等。也可以不执行操作
关键要想到每个数都要相等的话那么每个数都要变成序列的平均值然后模拟就行了。
#include bits/stdc.h
#define int long long
#define per(i,j,k) for(int (i)(j);(i)(k);(i))
#define rep(i,j,k) for(int (i)(j);(i)(k);--(i))
#define fr first
#define se second
#define endl \n
using namespace std;
const int N2e55;int n,a[N],sum;void no(){coutNOendl;
}void yes(){coutYESendl;
}void solve(){cinn;per(i,1,n)cina[i],suma[i];if(sum%n!0)return no();sum/n;//每一个都要是sum的平均值int nowtake0;per(i,1,n){if(a[i]sum)continue;else if(a[i]sum){if(nowtakesum-a[i]){nowtake-sum-a[i];}else return no();}else if(a[i]sum){nowtakea[i]-sum;}}if(nowtake)return no();else return yes();
}void init(){sum0;
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t;cint;while(t--)solve(),init();return 0;
} C. Make Equal Again
给你一个序列A你可以选择任意一个连续区间全部变成任意一个数比如[2,2,9,10]选择3~4全部变成2就会变成[2,2,2,2]这个操作你只能执行一次问你将序列A中的每个数都相等至少要改变几个数。
从答案入手最大范围是 l1rn就是全部修改然后看看 l 和 r 能不能往里面变让答案更小。
显然可以分类讨论。
如果a[l] a[r]那就是要改中间的部分。
如果a[l] ! a[r]那就是要改左边或者右边更短的那一截。
#include bits/stdc.h
#define int long long
#define per(i,j,k) for(int (i)(j);(i)(k);(i))
#define rep(i,j,k) for(int (i)(j);(i)(k);--(i))
#define fr first
#define se second
#define endl \n
using namespace std;
const int N2e55;int n,a[N];void solve(){cinn;per(i,1,n)cina[i];int l1,rn;if(a[l]!a[r]){while(a[l]a[1])l;while(a[r]a[n])r--;coutmin(n-l1,r)endl;}else{while(a[l]a[1])l;while(a[r]a[n])r--;if(lr)coutr-l1endl;else cout0endl;}
}void init(){per(i,1,n)a[i]0;
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t;cint;while(t--)solve(),init();return 0;
} 补题D. Divisible Pairs
对于序列中 i j 的两个数如果有 (a[i]a[j])%x0 并且 (a[i]-a[j])%y0 那么称之为一个漂亮对问你有几个漂亮对。
朴素算法很容易写出来但是这道题的范围要求复杂度小于等于nlogn。
n^2过不了。
per(i,1,n){per(j,i1,n){if((a[i]a[j])%x0 and (a[i]-a[j])%y0){ans;}}}循环显然没有可以改进的空间了所以我们需要对判断条件入手。
(a[i]a[j])%x0 and (a[i]-a[j])%y0
也就是箭头根据模运算律展开
1、(a[i]a[j])%x0 - (a[i]%xa[j]%x)%x02、(a[i]-a[j])%y0 - (a[i]%y-a[j]%y)%y0
最终可以得到下面两个条件
1、a[i]%x a[j]%x x 或者 a[i]%x a[j]%x 02、a[i]%y 和 a[j]%y 的余数相等
所以只需要把每个数对x和y取余之后保留下来再去匹配条件就可以了。
#include bits/stdc.h
#define int long long
#define per(i,j,k) for(int (i)(j);(i)(k);(i))
#define rep(i,j,k) for(int (i)(j);(i)(k);--(i))
#define fr first
#define se second
#define endl \n
using namespace std;
const int N2e55;int n,x,y,tmp,ans;mappairint,int,intf;void solve(){cinnxy;per(i,1,n){cintmp;int ltmp%x,rtmp%y;ansf[{x-l,r}];if(l0)ansf[{0,r}];f[{l,r}];}coutansendl;
}void init(){f.clear();ans0;
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t;cint;while(t--)solve(),init();return 0;
} E. Anna and the Valentines Day Gift
博弈论主要难度在于读题和代码细节。
Anna和Sasha在玩游戏Anna先手开始第一回合。
Anna回合的操作选择一个数翻转。如255变成552。250变成52去掉开头的0
Sasha回合的操作选择两个数拼接成一个数方向任意。如255,10变成25510或者10255
如果轮到Sasha的时候无法找出两个数那么游戏结束。
若最后留下来的那一个数10^m那么Sasha胜利否则Anna胜利。
问两个人都执行他们的最优操作最后谁会胜利。 对于Anna来说最优的操作是让结尾0最多的数翻转才会减少最终拼接数的位数。
对于Sasha来说拼接的意义就是让结尾0最多的数不能被翻转。
那么处理一下输入保留一下总位数和结尾0的数量排个序模拟。
#include bits/stdc.h
//#define int long long
#define per(i,j,k) for(int (i)(j);(i)(k);(i))
#define rep(i,j,k) for(int (i)(j);(i)(k);--(i))
#define fr first
#define se second
#define endl \n
using namespace std;
const int N2e55,M2e65;int n,tmp,m;
vectorpairint,intv;//几位数,结尾几个0void solve(){cinnm;per(i,1,n){cintmp;int cnt0,cntz0;bool flagtrue;while(tmp){int bittmp%10;if(bit!0)flagfalse;if(flag)cntz;//记录结尾0的数量cnt;//记录位数tmp/10;}v.push_back({cnt,cntz});}sort(v.begin(),v.end(),[](pairint,inta,pairint,intb){return a.seb.se;});//根据结尾0的数量降序排序,每次都对结尾0最多的进行操作int all0;//算一下最后总位数会剩下多少,用来和10^m的m比较bool Annatrue;per(i,0,v.size()-1){if(Anna){Annafalse;v[i].fr-v[i].se;//总位数减去结尾0的数量}else {Annatrue;//Sasha回合保护一个结尾所以不用变}allv[i].fr;//累计总位数}if(allm1){//m是1后面有几个0总位数是m1coutSashaendl;}else coutAnnaendl;
}void init(){v.clear();
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t;cint;while(t--)solve(),init();return 0;
}
