A.注意两个问题，一个是必须是排好序，也就是abc位置不能颠倒，其次就是a，b不能没有。 利用is_sorted可以快速解决第一个问题。
#include<cstdio> #include<iostream> #include<string> #include<algorithm> using namespace std; int main() { string str;int cnt[3]={0}; cin>>str; for(auto a:str) cnt[a-'a']++; if(is_sorted(str.begin(),str.end())&&cnt[0]&&cnt[1]&&(cnt[2]==cnt[0]||cnt[2]==cnt[1])) cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0; }B. 我们为了使两个数列上对应位置的数之差最小，可以考虑维护一个堆，里面存着两个数列每个位置之差的绝对值——因为可加可减，平方的时候正负并没有区别。然后，每次把当前最大的差拿出来减1，然后丢回堆里即可。注意，如果堆顶的元素变成了0而k1+k2还没用完的话，那么就必须特判了。
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cmath> using namespace std; int main() { int a[1005],b[1005],k1,k2,i,j,k,num[1005],n; cin>>n>>k1>>k2; for(i=1;i<=n;i++){ scanf("%d",&a[i]); } for(i=1;i<=n;i++)scanf("%d",&b[i]); priority_queue<int>que; for(i=1;i<=n;i++){ num[i]=abs(a[i]-b[i]);que.push(num[i]); } for(i=1;i<=k1+k2;i++){ j=que.top();que.pop(); if(j==0){ if(abs(k1+k2-i+1)&1) cout<<1<<endl; else cout<<0<<endl; return 0; } j-=1;que.push(j); } long long ans=0; while(!que.empty()){ j=que.top();que.pop();ans+=(long long)j*j; } cout<<ans<<endl; return 0; }C. 首先，注意一个事实——题目没有要求构造的数列中数字各异，那么是肯定不可能无解的：2^32次方就超过x的上限了。 然后，其实我们可以发现一个通用的构造方法——我们知道，任何一个数都可以表示成若干个2的幂次方之和，那么当然也可以表示成若干个2的幂次方-1 之和。那么，我们需要的x就可以这么构造了： 假设x=2^a1-1+2^a2-1+…+2^an-1,那么我们就可以构造n堆数，每堆数中有n个相同的数，堆与堆之间数相差d，这样一定能满足题目要求。
#include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<cstring> using namespace std; typedef long long ll; int main() { int x,d,i,j; vector<ll>v; cin>>x>>d; ll val=1; while(x){ for(i=0;x>=(1<<i);i++){//加和起来正好是2^(i+1) -1 v.push_back(val); x-=(1<<i); } val+=d; } cout<<v.size()<<endl; for(ll i:v) cout<<i<<' '; cout<<endl; return 0; }D. 这题很容易的一个想法就是直接去模拟，然而数据范围之大决定了这是不可能的。事实上，我们只需要维护每一层的移位信息即可——有点类似于线段树的lazytag，先记录下来，问询的时候再进行影响。 可以发现，如果只是对节点进行移位的话，那么因为更深的层也都跟着移了，所有没啥影响。但是如果只是移数值的话，那么更深的层相当于要反向移回相应的长度。此外就是不少细节了。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; typedef long long ll; ll shift[100]; void shi(int ceng,ll k) { ll mod=1LL<<ceng;//计算出这一层总的数字的个数 k%=mod;//一定要记得先mod后加,不然似乎会爆long long shift[ceng]=(shift[ceng]+k+mod)%mod;//计算出这一层新的移位情况,因为可能左移导致 //负,所有先加mod后取模 } int main() { ll q,t,k,x,i,j; cin>>q; while(q--){ scanf("%lld%lld",&t,&x); int be=0; for(;x>>be;be++);be--;//计算层数 if(t<3){ scanf("%lld",&k); if(t==2){ shi(be,k);//如果是对节点进行移位,直接移即可 } else{ shi(be,k);shi(be+1,-k*2);//若只是对数值移位,则下一层也会受影响 } } else{ for(;be>=0;be--){ cout<<x<<' '; x+=shift[be];//输出后加上本层的移位影响 if(x>=(1LL<<(be+1)))x-=(1LL<<be);//如果超过了本层的总数,当然要减去 x>>=1;//算出父节点对应数值 } cout<<endl; } } return 0; }F. 做法非常机智：对于每个点维护一个set，比如读入一条边 x,y,z，就在点x的set里 找权值
#include<cstdio> #include<iostream> #include<set> #include<algorithm> using namespace std; int n,m,v,u,w,ans=0;//pair中第一位保存边长,第2位保存这条边终点处使用这条边后的边数和 set<pair<int,int>>a[100100];//set中pair只按第一个键值排序 int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)a[i].insert({-1,0});//初始全部加入一个不会影响结果的pair while(m--){ scanf("%d%d%d",&v,&u,&w); auto it=a[v].lower_bound({w,-1});//寻找权值<w的最大位置 it--; int d=it->second+1;//如果这条边可以加入,那么终点处的如果用了这条边,最大边数自然就是上个点的边数+1; it=a[u].lower_bound({w+1,-1}); it--; if(it->second>=d)continue;//如果终点在边=w甚至更小时的边数已经>=d,那么这条边显然没有加进去的意义 while(1){ it=a[u].lower_bound({w,-1});//把终点处所有边>=w而边数<=d的全部删除,他们没有存在的意义 if(it==a[u].end())break;//显然边数相等时边越小越优 if(it->second>d)break; a[u].erase(it); } a[u].insert({w,d});//插入此边 } for(int i=1;i<=n;i++){ auto it=a[i].end(); it--; ans=max(ans,it->second); } printf("%d\n",ans); return 0; }