失踪人口回归。撒花\^o^/

说来真是惭愧，NOI之后就没怎么刷过题，就写了几道集训队作业题，打了几场比赛还烂的不行，atcoder至今是蓝名=.=

以后还是多更一些博客吧，我可不想清华集训的时候就退役

 

A - XXFESTIVAL

题意：输入XXFESTIVAL,输出XX。。。

#include
     
      using namespace std;char s[1005];int main(){	scanf("%s",s);	int n=strlen(s);	for(int i=0;i
     

　　

B - Problem Set

题意：

有n个人，每人有个值di，m个问题，每个问题有个值ti，一个人可以解决值相同的问题，问能不能全部解决。

n,m<=200000

 

用个map每次在里边查就行了。

#include
     
      #define N 200005using namespace std;int n,m;map
      
       mp;int a[N],b[N];int main(){	cin>>n;	for(int i=1;i<=n;i++)scanf("%d",&a[i]),mp[a[i]]++;	cin>>m;	for(int i=1;i<=m;i++)	{		scanf("%d",&b[i]);		if(mp[b[i]]<=0)		{			puts("NO");			return 0;		}		mp[b[i]]-=1;	}	puts("YES");	return 0;	sort(a+1,a+n+1);	sort(b+1,b+m+1);	if(n
       
        =n-m+1;i--)		{			if(b[m-n+i]>a[i])			{				puts("NO");				return 0;			}		}		puts("YES");	}	return 0;}
       
      
     

　　

 

C - 3 Steps

题意：

给一个连通图，如果一个点u能走三条边到达v，并且uv之间没有边，那么可以在他们之间连一条边，不停的连，问最多能连几条边。

2≤N≤105

 

把这张图黑白染色，如果不是二分图，那么所有边都可以连上，否则只能在黑白点之间连边。

证明的话，显然一个白点走三步只能到一个黑点，连完边之后依然是个二分图，一点一点连的话显然所有能连的边都能连上。

#include
     
      #define N 200005using namespace std;int n,m;int head[N],ver[N],nxt[N],tot;void add(int a,int b){	tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;return ;}int v[N],flag,tt1,tt2;void dfs(int x,int c){	if(c)tt1++;	else tt2++;	v[x]=c;	for(int i=head[x];i;i=nxt[i])	{		if(v[ver[i]]==-1)dfs(ver[i],c^1);		else if(v[ver[i]]!=(c^1))		{			flag=1;		}	}}int main(){	cin>>n>>m;	int t1,t2;	for(int i=1;i<=m;i++)	{		scanf("%d%d",&t1,&t2);		add(t1,t2);add(t2,t1);	}	memset(v,-1,sizeof(v));	dfs(1,1);long long  ans;	if(flag)	{		ans=1LL*n*(n-1)/2-m;	}	else	{		ans=1LL*tt1*tt2-m;	}	cout<
      
       <
      
     

　　

 

D - 101 to 010

题意：

有一个01序列，每次可以选出其中的一个101，变成010，问最优策略下能操作几次。

N<=500000

 

这题比赛的时候做了一年。。。

把101->010看做一次反应，我们发现对于发生需要有先后顺序的反应的一段只能长成1011111....或....1111101。

这样我们可以把序列分成很多段，每一段自己反应。

分段的话DP一下就好了。

#include
     
      #define N 500005using namespace std;int n,a[N],f[N],g[N],l[N],h[N],p[N],q[N];char s[N];int main(){	cin>>n;scanf("%s",s+1);	for(int i=1;i<=n;i++)a[i]=s[i]-'0';	memset(g,0xcf,sizeof(g));	memset(l,0xcf,sizeof(l));	memset(h,0xcf,sizeof(h));	memset(p,0xcf,sizeof(p));	memset(q,0xcf,sizeof(q));	for(int i=1;i<=n;i++)	{		if(a[i]==1)		{			g[i]=f[i-1];			h[i]=max(f[i-1],h[i-1])+1;			l[i]=max(q[i-1],l[i-1])+1;			f[i]=p[i-1];		}		else		{			p[i]=h[i-1];			q[i]=g[i-1];		}		f[i]=max(f[i],max(f[i-1],l[i]));	}	cout<
      
       <
      
     

　　

 

E - Popping Balls

题意：

有A个红球和B个蓝球排成一列，蓝球排在红球后。

可以选择一个s和t，s,t<=A+B

每次从第一个，或第s个，或第t个位置取出一个球。

问对于所有的s和t，最后的取出序列V有多少种，颜色相同的球没有区别。

A,B<=2000

 

这题做了十年。。。

我们先枚举V的开头有多少个红球，假设是i个，那么我们贪心的把t(不妨让t>s)设为A-i+1,因为t越小越好，第i+1个必须是蓝球。

再枚举取到剩下t-1个球时还有多少个红球j，此时还有A-i-j个蓝球。

从开始到达这个状态的方案数是$C_{B-1}^{B-1-(A-i-j)}$(之后又取走了B-1个球，其中有B-1-(A-i-j)个蓝球)。

之后的问题变为有A个红球和B个蓝球，只能选一个s，问取完的方案数。

大概是$$\sum_{k=0}^{j}\sum_{l=0}^{j-k}C_{A-i-j-1}^{l}$$

就是组合数某一行的前缀和的前缀和。

#include
     
      #define N 2005using namespace std;int c[N][N],s[N][N],w[N][N];const int p = 1000000007;int A,B;int main(){    for(int i=0;i
      
       >A>>B;    int ans=1;    for(int i=0;i
       
        =A-i-j-1)            {                q=w[A-i-j-1][A-i-j-1]+1LL*(j-A+i+j+1)*s[A-i-j-1][A-i-j-1]%p;                q%=p;            }            else            {                q=w[A-i-j-1][j]-1LL*(A-i-j-1-j)*s[A-i-j-1][j]%p;                q=(q+p)%p;            }            ans=(ans+1LL*c[B-1][A-i-j]*q%p)%p;        }    }    cout<
        
         <
        
       
      
     

　　

 

F - Largest Smallest Cyclic Shift

题意：

给出X个‘a’，Y个'b'，Z个‘c’，让你排列成一个字符串，使得最小表示最大。

输出最小表示。

X+Y+Z<=50

 

参考CF上某神犇的解法。

先把所有字母放到一个multiset<string>里，每回取出最小的字符串和最大的字符串拼在一起放回去，知道只剩一个字符串，输出。

贪心嘛，一个字符串太小了肯定要用大的往后拽，正确性大概YY一下就好了。

#include
     
      using namespace std;int a,b,c;multiset
      
       s;int main(){    cin>>a>>b>>c;    for(int i=1;i<=a;i++)s.insert("a");    for(int i=1;i<=b;i++)s.insert("b");    for(int i=1;i<=c;i++)s.insert("c");    while(s.size()>1)    {        string ss=(*s.begin())+(*s.rbegin());        s.erase(s.begin());        s.erase(--s.end());        s.insert(ss);    }    cout<<(*s.begin());    return 0;}