CODE FESTIVAL 2017 qual B 题解

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

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

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

A - XXFESTIVAL

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

#include<bits/stdc++.h>

using namespace std;

char s[1005];

int main()

{

	scanf("%s",s);

	int n=strlen(s);

	for(int i=0;i<n-8;i++)

	{

		putchar(s[i]);

	}

	cout<<endl;

	return 0;

}

B - Problem Set

题意：

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

n,m<=200000

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

#include<bits/stdc++.h>

#define N 200005

using namespace std;

int n,m;

map<int,int>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<m)

	{

		puts("NO");

	}

	else

	{

		for(int i=n;i>=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<bits/stdc++.h>

#define N 200005

using 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<<ans<<endl;

	return 0;

}

D - 101 to 010

题意：

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

N<=500000

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

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

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

分段的话DP一下就好了。

#include<bits/stdc++.h>

#define N 500005

using 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<<f[n]<<endl;

	return 0;

}

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<bits/stdc++.h>

#define N 2005

using 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<N;i++)

    {

        c[i][0]=s[i][0]=1;

        w[i][0]=i+1;

        for(int j=1;j<=i;j++)

        {

            c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;

            s[i][j]=(s[i][j-1]+c[i][j])%p;

            w[i][j]=1LL*c[i][j]*(i-j+1)%p;

            (w[i][j]+=w[i][j-1])%=p;

        }

    }

    cin>>A>>B;

    int ans=1;

    for(int i=0;i<A;i++)

    {

        for(int j=0;j<=A-i;j++)

        {

            if(A-i-j==0){ans++;continue;}

            if(j+B-1<A-i)continue;

            int q=0;

            if(j>=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<<ans%p<<endl;

    return 0;

}

F - Largest Smallest Cyclic Shift

题意：

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

输出最小表示。

X+Y+Z<=50

参考CF上某神犇的解法。

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

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

#include<bits/stdc++.h>

using namespace std;

int a,b,c;

multiset<string>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;

}

巴特西