一行超人

这博客的发表时间什么鬼  我怎么感觉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