3
17
2015
0

Codeforces Round #205 (Div. 2)

这博客的发表时间什么鬼  我怎么感觉div2 only其实和div1难度差不多

A.不说了

B.给出了2*n个两位数,要求分n个到1集合,n个到2集合。要求从1集合中取一个数x*100+2集合中去一个数y所能构成的不同的数最多。求一个方案。n<=100

题解:只出现了一次的数我们可以两边轮流放,出现了>1次的可以让他既在1集合也在2集合。这样种数之积最大。输出方案我们可以先对每种数确定<=2个元素的归属,剩下的就可以随意了Orz!!!

C.要求求一个长度为n的01串b,使得sigma(a[i]*b[i])最大  a[i]为整数。b必须小于给定的s.  n<=10W

题解:我写了DP。f[i][0]表示到第i位前面是不是贴着s过来的所得到的最大值。然后就很好写了。转移只有两行。

当然还有更简单的办法。当某一位不取1的时候肯定要把后面的全取为1.随便记录一下也可以过。

D.一个长度为n的队伍,每个人是F或M。每个时刻 如果某个M在F前面,那么下一时刻就会交换着两个人的位置。求多少时刻后队伍不会再发生改变。n<=100W

题解:Orz 还是一道很好的题的。

           1)令f[i]表示第i个F到达最终位置时的时间,那么ans=f[last F]

           2)f[i]=max(f[i-1]+1,m) m表示第i个F之前有多少个M

           这样就ok了。

E.有n个点1-n,n条有向边或者是i-i+1,或者是i到i-1.求最大反链。(意即 没有任何两个点(u,v)满足u可以到v或者v可以到u)

题解:我还是直接贴代码吧。。。直接说说不清楚。。。

int n,m,t,ans,a[maxn];
char s[maxn];
int main()
{
    scanf("%s",s);n=strlen(s);
    for0(i,n-1)if(s[i]!=s[i-1])a[++m]=1;else a[m]++;
    if(s[0]==s[n-1])a[1]+=a[m--];
    for1(i,m)if(a[i]==1)t++;else ans+=t/2+1,t=0;
    cout<<ans+t/2<<endl;
    return 0;
}

官方题解:http://codeforces.com/blog/entry/9145

 

Category: codeforces | Tags: | Read Count: 724

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com