传送门：http://codeforces.com/contest/998
直接找出数字出现次数最多的次数
#include<bits/stdc++.h> using namespace std; int a[106]; int main() { ios::sync_with_stdio(false); int n,maxx=-1; cin>>n; for(int i=1;i<=n;i++){ int x; cin>>x; a[x]++; maxx=max(maxx,a[x]); } cout<<maxx<<endl; return 0; }题意：构造一个01串，包含a个0和b个1，其中str[i]!=str[i+1]的个数为x个 解法：手动画一下，发现只有四种格式 当x为奇数： 000…0101…111（0的个数多于1的个数） 或者 111…1010…000（1的个数多于0的个数） 当x为偶数： 10101…111（1的个数多） 或者 01010…000（0的个数多）
#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); int a,b,x; cin>>a>>b>>x; if(x&1){ if(b<a){ for(int i=1;i<=a-(x/2+1);i++) cout<<0; int cur=0; for(int i=1;i<=x;i++) cout<<cur,cur=1-cur; for(int i=1;i<=b-(x/2);i++)cout<<1; }else{ for(int i=1;i<=b-(x/2+1);i++) cout<<1; int cur=1; for(int i=1;i<=x;i++) cout<<cur,cur=1-cur; for(int i=1;i<=a-(x/2);i++) cout<<0; } }else{ if(b<a){ int cur=0; cout<<cur; if(x/2<b) for(int i=1;i<=b-x/2;i++) cout<<1; cur=1-cur; for(int i=1;i<x;i++) cout<<cur,cur=1-cur; for(int i=1;i<=a-x/2;i++) cout<<0; }else{ int cur=1; cout<<cur; if(x/2<a) for(int i=1;i<=a-x/2;i++) cout<<0; cur=1-cur; for(int i=1;i<x;i++) cout<<cur,cur=1-cur; for(int i=1;i<=b-x/2;i++) cout<<1; } } return 0; }题意：求出序列中长度不小于k的序列值的平均值的最大值 解法：直接暴力跑一遍就行
#include<bits/stdc++.h> using namespace std; const int maxn=5e3+5; int a[maxn]; int main() { ios::sync_with_stdio(false); int n,k; cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; } double maxx=0.0; for(int len=k;len<=n;len++){ double sum=0; for(int i=1;i<=len;i++) sum+=a[i]*1.0; maxx=max(maxx,sum/(len*1.0)); for(int i=len+1;i<=n;i++){ sum+=a[i]*1.0; sum-=a[i-len]*1.0; maxx=max(maxx,sum/(len*1.0)); }; } cout<<fixed<<setprecision(10)<<maxx<<endl; return 0; }题意：给n个2的次方数，q次询问x可以用最少个数前面输入的数相加得到 解法：这题没看懂。大致就是从30迭代到0，每次从x中减去min(x>>i，cnt[i])*(1<<i)，答案加上min(x>>i，cnt[i]),如果最后x等于0怎答案是可行的，否则不可行。 在题解中发现了一个函数：__builtin_ctz
#include<bits/stdc++.h> using namespace std; int cnt[40]; int main() { ios::sync_with_stdio(false); int n,q; cin>>n>>q; for(int i=1;i<=n;i++){ int x; cin>>x; cnt[__builtin_ctz(x)]++; } while(q--){ int x; cin>>x; int sum=0; for(int i=30;i>=0;i--){ int temp=min(x>>i,cnt[i]); x-=(1<<i)*temp; sum+=temp; } if(x!=0) cout<<-1<<endl; else cout<<sum<<endl; } return 0; }题意：构造一棵节点数为n，直径为d，节点度最大为k的树 解法：用两个队列，一个存放未加入树上的节点，另一个用来存放pair表示节点的信息，其中first表示节点编号，second表示当前节点在直径上的哪个节点上。先构造直径，然后尽量让每个节点的度为k
#include<bits/stdc++.h> using namespace std; const int maxn=4e5+5; queue<int>q; queue<pair<int,int>>q2; vector<pair<int,int>>e; int deg[maxn]; int n,d,k; int main() { ios::sync_with_stdio(false); int n,d,k; cin>>n>>d>>k; d++; if(d>n){cout<<"NO"<<endl;return 0;} if(k==1&&n>2){cout<<"NO"<<endl;return 0;} if(k==2&&n!=d){cout<<"NO"<<endl;return 0;} for(int i=1;i<d;i++){//直径 e.push_back({i,i+1}); deg[i]++; deg[i+1]++; } for(int i=d+1;i<=n;i++) q.push(i); for(int i=2;i<d;i++) q2.push({i,i});//first是节点编号，second表示当前节点在直径的哪个点上 for(int i=2;i<=d-i+1;i++){ int siz=q2.size(); if(siz==0) break; for(int j=1;j<=siz;j++){ pair<int,int> t=q2.front(); q2.pop(); if(t.second>i&&t.second<d-i+1){ for(int p=deg[t.first]+1;p<=k;p++){ if(q.empty()) break; int v=q.front(); q.pop(); q2.push({v,t.second}); e.push_back({t.first,v}); deg[t.first]++; deg[v]++; } }else{ for(int p=deg[t.first]+1;p<=k;p++){ if(q.empty()) break; int v=q.front(); q.pop(); e.push_back({t.first,v}); deg[t.first]++; deg[v]++; } } } if(q.empty()) break; } //for(auto it:e) cout<<it.first<<' '<<it.second<<endl; if(e.size()==n-1){ cout<<"YES"<<endl; for(auto it:e) cout<<it.first<<' '<<it.second<<endl; }else{ cout<<"NO"<<endl; } return 0; }题意：连续相等的几个单词可以写成他们首字母的大写缩写，求经过一次缩写后整个字符串的最小长度 解法：把每个单词hash，并且hash每个单词的长度，防止出现j jj j和jj j j 这样的字符串，两个字符串hash值相同但不一样。然后就是枚举连续单词的个数，暴力匹配. ps：这个hash不能用uLL的自然溢出
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long uLL; const int maxn=305; string str[maxn]; int n; int len[maxn]; LL ha[maxn],ha2[maxn],power[100005],power2[100005]; LL base=133,base2=1e9+7,mod=1998585857; bool check(int p1,int p2,int p3,int p4) { LL h1=(ha[p4]-ha[p3-1]*power[len[p4]-len[p3-1]]%mod+mod)%mod; LL h2=(ha[p2]-ha[p1-1]*power[len[p2]-len[p1-1]]%mod+mod)%mod; //cout<<h1<<' '<<h2<<endl; if(h1==h2){ h1=ha2[p4]-ha2[p3-1]*power2[p4-p3+1]; h2=ha2[p2]-ha2[p1-1]*power2[p2-p1+1]; //cout<<h1<<' '<<h2<<endl; return h1==h2; } return false; } int main() { ios::sync_with_stdio(false); power[0]=1;power2[0]=1; for(int i=1;i<100005;i++){ power[i]=power[i-1]*base%mod; power2[i]=power2[i-1]*base2; } cin>>n; for(int i=1;i<=n;i++){ cin>>str[i]; ha[i]=ha[i-1]; ha2[i]=ha2[i-1]*base2+str[i].length(); len[i]=len[i-1]+str[i].length(); for(int j=0;j<str[i].length();j++){ ha[i]=(ha[i]*base+1LL*str[i][j])%mod; } } int ans=0; for(int l=1;l<=n;l++){ for(int i=1;i+l-1<=n;i++){ int temp=0,pos=1,cnt=0; while(pos+l-1<=n){ if(pos+l-1>=i&&pos<=i){ pos=i+l; continue; } if(check(i,i+l-1,pos,pos+l-1)){ cnt++; pos=pos+l; }else{ pos++; } } //for(int j=i;j<=i+l-1;j++) cout<<str[j]<<' ';cout<<" cnt=="<<cnt<<endl; if(cnt){ cnt++; ans=max(ans,cnt*(len[i+l-1]-len[i-1]-1)); } } } ans=len[n]+n-1-ans; cout<<ans<<endl; //system("pause"); return 0; } /* j jj jj j */