(A)
咕咕咕
const int N=55;
char s[N];int n;
int main(){
scanf("%s",s+1),n=strlen(s+1);
s[n-7]=' ',printf("%s
",s+1);
return 0;
}
(B)
咕咕咕
//quming
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
multiset<int>s;int n,m;
typedef multiset<int>::iterator IT;
int main(){
scanf("%d",&n);
for(R int i=1,x;i<=n;++i)scanf("%d",&x),s.insert(x);
IT it;
scanf("%d",&m);
for(R int i=1,x;i<=m;++i){
scanf("%d",&x);
it=s.lower_bound(x);
if(it==s.end()||(*it)!=x)return puts("NO"),0;
s.erase(it);
}
puts("YES");
return 0;
}
(C)
如果两个点之间距离为(d)，那么每一次显然可以中间随便连一条边使得(d=d-3+1)，所以两个点在最终的图中有边当且仅当它们的距离为奇数。那么如果图中有奇环最终可以变成完全图，否则的话黑白染色，黑点白点之间互相可以连边
//quming
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct eg{int v,nx;}e[N<<1];int head[N],tot;
inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}
ll res;int cnt[2],dis[N],deg[N],n,m,fl;
void dfs(int u,int d){
dis[u]=d,++cnt[d];
go(u)if(dis[v]==-1)dfs(v,d^1);
else if(dis[v]!=d^1)fl=1;
}
int main(){
scanf("%d%d",&n,&m);
for(R int i=1,u,v;i<=m;++i){
scanf("%d%d",&u,&v),add(u,v),add(v,u);
++deg[u],++deg[v];
}
memset(dis,-1,(n+1)<<2);
dfs(1,0);
if(fl)return printf("%lld
",(1ll*n*(n-1)>>1)-m),0;
fp(i,1,n)res+=cnt[dis[i]^1]-deg[i];
printf("%lld
",res>>1);
return 0;
}
(D)
考虑最终的序列，一个(1)一定是由一开始的(11111...101)或者(101...111)转移而来的，且假设有(k)个(1)，那么贡献就是(k-1)，我们记形如这样的串为好的，那么所有好的串的串长总和是(O(n))的，那么预处理一下直接(dp)就行了
//quming
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=5e5+5;
char s[N];int las[N],f[N],n;
int main(){
scanf("%d%s",&n,s+1);
fp(i,1,n)las[i]=(s[i]=='1'?las[i-1]:i);
fp(i,1,n){
f[i]=f[i-1];
if(s[i]=='1'&&las[i]&&s[las[i]-1]=='1'){
R int x=las[i],y=las[x-1];
cmax(f[i],f[x-2]+i-x);
if(i==x+1)fp(j,y,x-2)cmax(f[i],f[j]+x-1-j);
}
}
printf("%d
",f[n]);
return 0;
}
(E)
首先发现蓝球永远在红球的左边，且如果现在需要选一个红球，一定是把一个(s)或(t)放到红球的开头是最优的
那么我们枚举给(Snuke)的球中开头的连续蓝球的个数，然后设(g_{i,j})表示还剩(i)个蓝球和(j)个红球，且给(Snuke)的序列中开头第一个必须是红球的方案数
考虑(g)，那么(t)必须得放在红球的开头，即(i+1)这个位置，然后选了总共(j)个球之后，这个(t)就没有用了
考虑选完(j)个球之后，发现仍然是一个类似的问题，只不过此时只有一个(s)可以放了
于是我们分别定义(e_{i,j})表示(i)蓝(j)红，必须红开，(f_{i,j})表示(i)蓝(j)红，有一个(s)可以放，转移的时候，对于(e)就枚举前(j)个里有多少个蓝，对于(f)就枚举开头的蓝的个数，那么转移方程就是
[egin{aligned}
&e_{i,j}=sum_{kleq i}{j-1choose k}\
&f_{i,j}=sum_{kleq i}e_{i-k,j}\
&g_{i,j}=sum_{kleq i}{j-1choose k}f_{i-k,k}\
&h_{i,j}=sum_{kleq i}g_{i-k,j}\
end{aligned}
]
(e,f)的转移可以前缀和优化掉，不过(g)不行。我们发现我们最终要求的答案是(h_{n,m})，所以只需要考虑那些(j=m)的(g)就可以了
于是复杂度为(O(n^2))
//quming
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int P=1e9+7;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
R int res=1;
for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
return res;
}
const int N=2005;
int e[N][N],f[N][N],g[N][N],h[N][N],cs[N][N],sb[N][N],n,m;
void init(){
fp(i,0,max(n,m)){
cs[i][0]=1;
fp(j,1,i)cs[i][j]=add(cs[i-1][j],cs[i-1][j-1]);
sb[i][0]=1;fp(j,1,n)sb[i][j]=add(sb[i][j-1],cs[i][j]);
}
fp(i,0,n)fp(j,1,m)e[i][j]=sb[j-1][i];
e[0][0]=1;
fp(i,1,n)fp(j,0,m)upd(e[i][j],e[i-1][j]);
fp(i,0,n)fp(j,0,m)f[i][j]=e[i][j];
fp(i,0,n)fp(k,0,i)upd(g[i][m],mul(cs[m-1][k],f[i-k][k]));
g[0][0]=1;
fp(k,0,n)upd(h[n][m],g[n-k][m]);
}
int main(){
// freopen("testdata.in","r",stdin);
scanf("%d%d",&n,&m);
init();
printf("%d
",h[n][m]);
return 0;
}
(F)
每一次把当前最小的和最大的子串依次拼接，然后把这个新的字符串插入集合中，一直到集合中只剩下一个元素为止
//quming
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
struct node{
string s;int c;
inline node(R string ss,R int cc):s(ss),c(cc){}
inline bool operator <(const node &b)const{return s<b.s;}
};set<node>s;
int x,y,z;
int main(){
scanf("%d%d%d",&x,&y,&z);
if(x)s.insert(node("a",x));
if(y)s.insert(node("b",y));
if(z)s.insert(node("c",z));
while(2333){
if(s.size()==1){
node p=*s.begin();
fp(i,1,p.c)cout<<p.s;
puts("");
return 0;
}
R node p=*s.begin(),q=*--s.end();
s.erase(s.begin()),s.erase(--s.end());
R int k=min(p.c,q.c);s.insert(node(p.s+q.s,k));
if(p.c-k)s.insert(node(p.s,p.c-k));
if(q.c-k)s.insert(node(q.s,q.c-k));
}
return 0;
}