A - Candies and Two Sisters
题意:
有 n 颗糖, 姐姐和妹妹分, 姐姐必须比妹妹的少, 问有几种情况, 必须每人有一颗.
思路:
答案就是 (n-1)/2
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- #define il inline
- #define it register int
- #define inf 0x3f3f3f3f
- #define lowbit(x) (x)&(-x)
- #define pii pair<int,int>
- #define mak(n,m) make_pair(n,m)
- #define mem(a,b) memset(a,b,sizeof(a))
- #define mod 1000000007
- const int maxn=1e6+10;
- const int mo=1e9;
- ll ksm(ll a,ll b){if(b<0)return 0;ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;}
- int t;
- int n,m;
- int main(){
- scanf("%d",&t);
- while(t--){
- scanf("%d",&n);
- if(n<3){printf("0\n");}
- else{
- printf("%d\n",(n-1)/2);
- }
- }
- return 0;
- }
- B - Construct the String
题意:
有 n,a,b, 长度是 n 的字符串, 每 a 个字符串, 都有 b 个不同字母, 进行构造, 输出其中一个.
思路:
先构造 s 一个 a 长度, 前 b 项全不同, b 项之后跟 b 一样, 然后 a 项之后开始循环构造的 s
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- #define il inline
- #define it register int
- #define inf 0x3f3f3f3f
- #define lowbit(x) (x)&(-x)
- #define pii pair<int,int>
- #define mak(n,m) make_pair(n,m)
- #define mem(a,b) memset(a,b,sizeof(a))
- #define mod 1000000007
- const int maxn=2e3+10;
- const int mo=1e9;
- ll ksm(ll a,ll b){if(b<0)return 0;ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;}
- int t;
- int n,a,b;
- char s[maxn];
- int main(){
- scanf("%d",&t);
- while(t--){
- scanf("%d%d%d",&n,&a,&b);
- int c=0,bb=b-1;
- for(it i=0;i<a;i++){
- s[i]='a'+bb;
- if(bb!=0){
- bb--;
- }
- }
- for(it i=0;i<n;i++){
- printf("%c",s[i%a]);
- }
- printf("\n");
- }
- return 0;
- }
- C - Two Teams Composing
题意:
有 n 人, ai 代表技能, n 个人要分成两个相同数量的组合, 第一个组合技能 ai 值都不同, 第二个组合技能 ai 值都相同, 问最大的相同数量是多少.
思路:
把出现 1 次的 ai 统计 (ans), 把出现重复的 ai, 个数统计 (ge), 最大量统计 (maxx), 答案就是 max(min(ans+ge,maxx-1),min(ans+ge-1,maxx));
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- #define il inline
- #define it register int
- #define inf 0x3f3f3f3f
- #define lowbit(x) (x)&(-x)
- #define pii pair<int,int>
- #define mak(n,m) make_pair(n,m)
- #define mem(a,b) memset(a,b,sizeof(a))
- #define mod 1000000007
- const int maxn=2e5+10;
- const int mo=1e9;
- ll ksm(ll a,ll b){if(b<0)return 0;ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;}
- int t;
- int n;
- int a[maxn],cnt[maxn];
- int main(){
- scanf("%d",&t);
- while(t--){
- scanf("%d",&n);
- map<int,int>mp;int ge=0;
- for(it i=0;i<n;i++){
- scanf("%d",&a[i]);
- if(mp[a[i]]==0){
- mp[a[i]]=++ge;
- cnt[ge]=1;
- }
- else{
- cnt[mp[a[i]]]++;
- }
- }
- int ans=0,maxx=0,g1=0;
- for(it i=1;i<=ge;i++){
- if(cnt[i]==1){ans++;}
- else{g1++;}
- maxx=max(cnt[i],maxx);
- }
- int sheng=g1+ans;
- printf("%d\n",max(min(g1+ans,maxx-1),min(g1+ans-1,maxx)));
- }
- return 0;
- }
- D - Anti-Sudoku
题意:
给 9 * 9 的数独, 要求变成各行各列, 每 3*3 的格子出现 2 个相同数.
思路:
把 1 变成 2 就可以了.
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- #define il inline
- #define it register int
- #define inf 0x3f3f3f3f
- #define lowbit(x) (x)&(-x)
- #define pii pair<int,int>
- #define mak(n,m) make_pair(n,m)
- #define mem(a,b) memset(a,b,sizeof(a))
- #define mod 1000000007
- const int maxn=2e5+10;
- const int mo=1e9;
- ll ksm(ll a,ll b){if(b<0)return 0;ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;}
- int t;
- int n;
- char s[10][10];
- int main(){
- scanf("%d",&t);
- while(t--){
- for(it i=0;i<9;i++){
- scanf("%s",s[i]);//printf("\n%s\n",s[i]);
- }
- for(it i=0;i<9;i++){
- for(it j=0;j<9;j++){
- if(s[i][j]=='1'){
- s[i][j]='2';
- }//cout<<s[i][j]<<endl;
- }
- }
- for(it i=0;i<9;i++){
- printf("%s\n",s[i]);
- }
- }
- return 0;
- }
- E1 - Three Blocks Palindrome (easy version)
题意:
Let's define a three blocks palindrome as the sequence, consisting of at most two distinct elements (let these elements are a and b, a can be equal b) and is as follows: [a,a,...,a[x] ,b,b,...,b[y] ,a,a,...,a[x] ]. There x,y are integers greater than or equal to 0. For example, sequences [], [2], [1,1], [1,2,1], [1,2,2,1] and [1,1,2,1,1] are three block palindromes but [1,2,3,2,1], [1,2,1,2,1] and [1,2] are not.
Your task is to choose the maximum by length subsequence of a that is a three blocks palindrome.
给 n 长度数组 ai,ai<27,n<=2000
思路:
暴力啊, 把每个 ai 位置存下来, 然后进行判断, 具体操作看代码吧, 因为 E2 我 tle 在 10 的样例, 所以不是正确的解答思路. 待补 E2,F
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- #define il inline
- #define it register int
- #define inf 0x3f3f3f3f
- #define lowbit(x) (x)&(-x)
- #define pii pair<int,int>
- #define mak(n,m) make_pair(n,m)
- #define mem(a,b) memset(a,b,sizeof(a))
- #define mod 1000000007
- const int maxn=2e3+10;
- const int mo=1e9;
- ll ksm(ll a,ll b){if(b<0)return 0;ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;}
- int t,n,a;
- int cnt[27][maxn];
- int main(){
- scanf("%d",&t);
- while(t--){
- scanf("%d",&n);
- for(it i=0;i<=26;i++){cnt[i][0]=0;}
- for(it i=1;i<=n;i++){
- scanf("%d",&a);
- cnt[a][0]++;cnt[a][cnt[a][0]]=i;
- }
- int maxx=0;
- for(it i=1;i<=26;i++){
- maxx=max(cnt[i][0],maxx);
- }
- for(it i=1;i<=26;i++){
- for(it j=1;j<=26;j++){
- if(j==i || cnt[i][0]==0 || cnt[j][0]==0){continue;}
- int ans=0;
- for(it ii=1;ii<=cnt[i][0]/2;ii++){
- ans=ii*2;int l=cnt[i][ii],r=cnt[i][cnt[i][0]-ii+1],l1=0,r1=0;
- // cout<<l<<" "<<r<<endl;
- for(it jj=1;jj<=cnt[j][0];jj++){
- if(l<cnt[j][jj]){l1=jj;break;}
- }
- for(it jj=cnt[j][0];jj>=1;jj--){
- if(r>cnt[j][jj]){r1=jj;break;}
- }
- //cout<<i<<""<<j<<" "<<r1<<" "<<l1<<" "<<ii<<endl;
- if(l1==0 || r1==0 || r1<l1){continue;}
- ans+=r1-l1+1;maxx=max(ans,maxx);
- }
- }
- }
- printf("%d\n",maxx);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3506089.html