Codeforces Round #253 (Div. 1)

在进行作弊活动的情况下A了4T

A 爆搜每次选什么。用位运算优化。时间复杂度O(10!*n)由于剪枝常数较小。

#include<cstdio>
using namespace std;
const char c[]={'R','G','B','Y','W'};
int ans,ss[11],ff[11],n,kn[110],us[11],vs[11],f[110],i,g[266],j,v;
char s[100];
void dfs(int x)
{
	int i,j,vv[110];
	if(x>=ans)return;
	for(i=1;i<=n;i++)if(kn[i]^(1<<f[i]))break;
	if(i>n){ans=x;return;}
	for(i=1;i<=n;i++)vv[i]=kn[i];
	for(i=0;i<5;i++)if(!us[i])
	{
		us[i]=1;
		for(j=1;j<=n;j++)
			if(f[j]/5==i)kn[j]&=ff[i];
			else kn[j]&=~ff[i];
		dfs(x+1);us[i]=0;
		for(j=1;j<=n;j++)kn[j]=vv[j];
	}for(i=0;i<5;i++)if(!vs[i])
	{
		vs[i]=1;
		for(j=1;j<=n;j++)
			if(f[j]%5==i)kn[j]&=ss[i];
			else kn[j]&=~ss[i];
		dfs(x+1);vs[i]=0;
		for(j=1;j<=n;j++)kn[j]=vv[j];
	}
}
int main()
{
	scanf("%d",&n);ans=10;
	for(i=0;i<5;i++)g[c[i]]=i;
	for(i=1;i<=n;i++)
	{
		scanf("%s",&s);
		f[i]=g[s[0]]*5+s[1]-'1';
		v|=1<<f[i];
	}for(i=1;i<=n;i++)kn[i]=v;
	for(i=0;i<5;i++)
		for(j=0;j<5;j++)
			ss[i]|=1<<j*5+i,ff[i]|=1<<i*5+j;
	dfs(0);printf("%d\n",ans);
}

B 贪心。先排序，从大到小选。正确性的证明推一推就能推出来。时间复杂度O(nlogn)

#include<cstdio>
#include<algorithm>
#define eps 1e-10
using namespace std;
int n,i,j,l,ln;
double a[110],x,y;
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%lf",&a[i]);
	sort(a+1,a+n+1);x=0;y=1;
	for(;n;n--)
	{
		if(x*(1-a[n])+y*a[n]<x)break;
		x=x*(1-a[n])+y*a[n];y=y*(1-a[n]);
	}printf("%.10lf\n",x);
}

C 考虑如果有一个位置，他的左右都大于等于他，那么一定要先取掉他。把所有可以取的都取完后得到一个先单调增后单调减的序列。然后一个对于这个序列而言，取任意一个东西不可能让别的值变大。所以把每个点两边的最小值求个sigma就好了。一定可以构造出取的方案。时间复杂度O(nlogn)。

#include<cstdio>
#include<algorithm>
#define N 500010
using namespace std;
int n,i,sg[N],xg[N],a[N],f[N],u,use[N];
long long ans;
bool cmp(int x,int y){return a[x]<a[y];}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		sg[i]=i-1;xg[i]=i+1;
		scanf("%d",&a[i]),f[i]=i;
	}sort(f+1,f+n+1,cmp);
	for(i=1;i<=n;i++)
	{
		u=f[i];
		if(a[sg[u]]>=a[u]&&a[xg[u]]>=a[u])
		{
			use[u]=1;
			ans+=min(a[sg[u]],a[xg[u]]);
			xg[sg[u]]=xg[u];sg[xg[u]]=sg[u];
		}
	}for(i=n;i>=1;i--)
	{
		u=f[i];if(use[u])continue;
		ans+=min(a[sg[u]],a[xg[u]]);
	}printf("%I64d\n",ans);
}

D 这题以前做过的。直接暴力向上跳就好了。均摊时间复杂度O(nlogn)。

#include<cstdio>
#include<algorithm>
using namespace std;
int i,n,fa[1000010],tot[1000010],t,s,max1[1000010],max2[1000010],ff;
int main()
{
    scanf("%d",&n);
    for(i=2;i<=n+1;i++)
    {
        scanf("%d",&fa[i]);tot[i]=1;
        for(t=i;t>1;t=s)
        {
            s=fa[t];if(tot[t]>tot[max1[s]])
                max2[s]=max1[s],max1[s]=t;else
            if(tot[t]>tot[max2[s]]&&t!=max1[s])max2[s]=t;
            ff=max(tot[max1[s]],tot[max2[s]]+1);
            if(ff>tot[s])tot[s]=ff;else break;
        }printf("%d ",tot[max1[1]]);
    }
}

E 看了题解还是不会做。。那个经典问题怎么做啊。。