囧。。。

       哎。。。最近比较懒。。已经懒到贴代码了。。所以弄了个马甲叫nimendongde然后密码是123456A了题之后就可以直接看了。。。
不过被人盗了T_T。。。。
囧掉了。。。发现SkyDrive这个网盘很方便啊T_T。。。以后有神马东西就传上去好了T_T。。

[Sdoi2009]Bill的挑战

[Sdoi2009]Bill的挑战

Time Limit:4000MS Memory Limit:65536K
Total Submit:33 Accepted:11
Case Time Limit:1000MS

Description

Input

本题包含多组数据。
第一行:一个整数T,表示数据的个数。
对于每组数据:
第一行:两个整数,N和K(含义如题目表述)。
接下来N行:每行一个字符串。

Output

1
2 1
a?
?b

Sample Input

Sample Output

Source

Day2
俄。。这个题目也只要知道方法就很好做了。。而这种方法在TC上出现。。
设Ret[Set]表示“跟”Set集合中字符串匹配的数量。。
注意是跟,不是刚好跟。。所以可以扫描一边搞出来。。
算出所有Ret[Set]
再用Ans[Set]表示刚好跟Set集合中字符串匹配的数量
那么Ans[Set]=Ret[Set]-(Ans[a] )(Set 是a的真子集)..
从大到小算出Ans[Set]再统计就可以了T_T。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define All(x) x.begin(),x.end()
using namespace std;
const int maxn=15,maxL=50,mod=1000003;
int T,N,K;
string A[maxn];
bool C[maxn];
int Ret[1<<maxn];
void Calc_Ret()
{
    static char Fixed[maxL];
    memset(Fixed,0,sizeof Fixed);
    int Set=0;
    int ret=1;
    rep(i,N)if(C[i])
    {
        Set|=1<<i;
        rep(j,A[i].size())
        if(A[i][j]!=’?’)
        {
            if(Fixed[j]&&A[i][j]!=Fixed[j])
            {
                ret=0;
            }
            else
            {
                Fixed[j]=A[i][j];
            }
        }
    }
    rep(j,A[0].size())if(!Fixed[j])ret*=26,ret%=mod;
    Ret[Set]=ret;
}
void Generate_Ways(int str)
{
    if(str==N)
    {
        Calc_Ret();
        return;
    }
    //D choose A[str]
    C[str]=false;
    Generate_Ways(str+1);
    //choose A[str];
    C[str]=true;
    Generate_Ways(str+1);
}
void Calc_Ans()
{
    int Ans=0;
    for(int i=(1<<N)-1;i>=0;i–)
    {
        for(int subset=(i-1)&i;subset>0;subset=(subset-1)&i)
            Ret[subset]=(Ret[subset]-Ret[i]+mod)%mod;
        if(i)Ret[0]=(Ret[0]-Ret[i]+mod)%mod;
    }
    rep(i,(1<<N))
    {
        int cnt=0;
        rep(j,N)if(i>>j&1)cnt++;
        if(cnt==K)Ans+=Ret[i],Ans%=mod;
    }
    cout<<Ans<<endl;
}
void Input_Data()
{
    cin>>N>>K;
    rep(i,N)cin>>A[i];
}
int main()
{
    //freopen("in","r",stdin);
    cin>>T;
    rep(i,T)
    {
        Input_Data();
        Generate_Ways(0);
        Calc_Ans();
    }
}

对于30%的数据,T ≤ 5,M ≤ 5,字符串长度≤ 20;对于70%的数据,T ≤ 5,M ≤ 13,字符串长度≤ 30;对于100%的数据,T ≤ 5,M ≤ 15,字符串长度≤ 50。50

[Sdoi2008]Cave 洞穴勘测

[Sdoi2008]Cave 洞穴勘测

Time Limit:10000MS Memory Limit:265536K
Total Submit:19 Accepted:6
Case Time Limit:1000MS

Description

辉辉热衷于洞穴勘测。某天,他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测,辉辉发现这片区域由n个洞穴(分别编号为1到n)以及若干通道组成,并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来,那么这两个洞穴就是连通的,按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。
洞穴都十分坚固无法破坏,然而通道不太稳定,时常因为外界影响而发生改变,比如,根据有关仪器的监测结果,123号洞穴和127号洞穴之间有时会出现一条通道,有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示:
如果监测到洞穴u和洞穴v之间出现了一条通道,终端机上会显示一条指令 Connect u v
如果监测到洞穴u和洞穴v之间的通道被毁,终端机上会显示一条指令 Destroy u v
经过长期的艰苦卓绝的手工推算,辉辉发现一个奇怪的现象:无论通道怎么改变,任意时刻任意两个洞穴之间至多只有一条路径。因而,辉辉坚信这是由于某种本质规律的支配导致的。因而,辉辉更加夜以继日地坚守在终端机之前,试图通过通道的改变情况来研究这条本质规律。
然而,终于有一天,辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸(终端机也足够坚固无法破坏),转而求助于你,说道:“你老兄把这程序写写吧”。
辉辉希望能随时通过终端机发出指令 Query u v,向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。
已知在第一条指令显示之前,JSZX洞穴群中没有任何通道存在。

Input

第一行为两个正整数n和m,分别表示洞穴的个数和终端机上出现过的指令的个数。
以下m行,依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s("Connect”、”Destroy”或者”Query”,区分大小写),之后有两个整数u和v (1≤u, v≤n且u≠v) 分别表示两个洞穴的编号。

Output

对每个Query指令,输出洞穴u和洞穴v是否互相连通:是输出”Yes”,否则输出”No”。(不含双引号)

Sample Input

Sample Output

Hint

数据说明

10%的数据满足n≤1000, m≤20000
20%的数据满足n≤2000, m≤40000
30%的数据满足n≤3000, m≤60000
40%的数据满足n≤4000, m≤80000
50%的数据满足n≤5000, m≤100000
60%的数据满足n≤6000, m≤120000
70%的数据满足n≤7000, m≤140000
80%的数据满足n≤8000, m≤160000
90%的数据满足n≤9000, m≤180000
100%的数据满足n≤10000, m≤200000

保证所有Destroy指令将摧毁的是一条存在的通道
本题输入、输出规模比较大,建议cc++选手使用scanf和printf进行IO操作以免超时

Source
俄。。对于这种裸的维护动态森林的题目也没有神马别的好办法。。要么动态树,要么朴素。。。
我一开始写了半天动态树各种TLE+WA。。。
受不鸟了决定写朴素T_T。。
结果居然可以过囧。。。。
其实就按朴素的办法来实现动态树的方法,对每个节点用F[x]表示它的父亲。。
那么我们需要一些操作。。
Mark_Root(x) 将x设为它子树的根。。这个只要将根到x的路径全部反一下就可以了。。
Find_Root(x) 找到x的根。。。只接找。。。
然后就可以差不多类。。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int maxn=10000+10;
int F[maxn],n,m;
void Clear_List()
{
    rep(i,n)F[i]=i;
}
int Find_Root(int u)
{
    while(u!=F[u])u=F[u];
    return u;
}
bool Query(int u,int v)
{
    return Find_Root(u)==Find_Root(v);
}
void Mark_Root(int u)
{
    int v=F[u],t;F[u]=u;
    while(u!=v)
    {
        t=F[v];F[v]=u;
        u=v;v=t;
    }
}
void Connect(int u,int v)
{
    Mark_Root(u);
    Mark_Root(v);
    F[v]=u;
}
void Destroy(int u,int v)
{
    Mark_Root(u);
    F[v]=v;
}
char c[100];
int main()
{
    //freopen("in","r",stdin);
    scanf("%d%d",&n,&m);int u,v;
    Clear_List();
    rep(i,m)
    {
        scanf(" ");scanf("%s%d%d",c,&u,&v);
        u–;v–;
        switch(c[0])
        {
            case ‘Q':Query(u,v)?puts("Yes"):puts("No");break;
            case ‘C':Connect(u,v);break;
            case ‘D':Destroy(u,v);break;
        }
    }
}

样例输出1 cave.outNoYesNo样例输出2 cave.outYesNo

样例输入1 cave.in200 5Query 123 127Connect 123 127Query 123 127Destroy 127 123Query 123 127样例输入2 cave.in3 5Connect 1 2Connect 3 1Query 2 3Destroy 1 3Query 2 3

样例输出1 cave.outNoYesNo样例输出2 cave.outYesNo

样例输入1 cave.in200 5Query 123 127Connect 123 127Query 123 127Destroy 127 123Query 123 127样例输入2 cave.in3 5Connect 1 2Connect 3 1Query 2 3Destroy 1 3Query 2 3

[2009国家集训队]小Z的袜子(hose)

题目上次那个有。。下面要说从fjxmlhx神牛那里知道的各种做法。。。
再结合我以前的各种做法。。有5种了T_T。。
1: 标准做法,曼哈顿最小生成树,然后遍历。。SqrtM*N+NLogN
2: 我以前的SB做法,随机一个比较小的生成树,然后遍历。。 nimendongde
3: 先将所有序列按起始点排个序,然后每次找一个结尾点的最长上升或下降序列。。
然后可以在O(N)处理掉这个序列。。每次都这么干直到没有。。
可以证明最多找SqrtM次。。所以是SqrtM*(M*LogM+N)
设一个询问左端点为l,右端点为r
设我们要计算l到r中取相同的颜色的袜子的方法数
设Ai为第i项的颜色,也就是
Size {l<=i<j<=r,Ai==Aj}
定义Ci为Size{i<j<=r,Ai==Aj}
那么我们就是要求Sum C(l..r)
4: 强大的做法来了。。我们从左往右扫描,动态维护Ci,
那么我每次加入一个点。。那些点的Ci变了呢。。就是在该点前面跟它一个颜色的点,Ci都+1了。。
那么我们可以使用树状数组来维护这个结构。。
额。。。如果一个颜色的点很多不就悲剧了么。。。
关键就是这里,如果一种颜色数量超过SqrtN。。那么我直接把这个颜色的位置存放在一个数组里。。。
那么显然可以在LogN的时间内二分出其中在l到r之间的个数。。。。
所以这些都可以忽略
然后颜色数量小于SqrtN的话,那么只要一个个更新也没事。。
复杂度N*LogN*SqrtM 常数很小。。速度很快。。。
5. 更强大的做法来了。。还是同样的考虑。。我们直接维护所有点的Ci和,不按颜色数量拆开。。
为了达成这个需要使用块状数组。。。按SqrtN分块。。每块记录这个块中所有点的Ci和。。
那么插入一个点之后,这个点之前的块的贡献和都会增加该块内与插入点同色的点的数量。。
预处理一下每个块内各种颜色的数量。。
然后询问的时候也差不多。。不过需要计算除了快之外的两端。。。
总体复杂度是N*SqrtM。。。不过空间复杂度很大而且常数也不小。。所以速度反而比第4个慢囧。。。
代码还是直接上nimendongde这个号去看吧。。
53634 是算法4
53397 是算法1
53632 是算法5
52092 是算法2
算法3没写。。

[POI2009]Lyz

[POI2009]Lyz

Time Limit:10000MS  Memory Limit:165536K
Total Submit:56 Accepted:16
Case Time Limit:2000MS

Description

初始时滑冰俱乐部有1到n号的溜冰鞋各k双。已知x号脚的人可以穿x到x+d的溜冰鞋。

有m次操作,每次包含两个数ri,xi代表来了xi个ri号脚的人。xi为负,则代表走了这么多人。

对于每次操作,输出溜冰鞋是否足够。

Input

n m k d ( 1≤n≤200,000 , 1≤m≤500,000 , 1≤k≤109 , 0≤d≤n )

ri xi ( 1≤i≤m, 1≤ri≤n-d , |xi|≤109 )

Output

对于每个操作,输出一行,TAK表示够 NIE表示不够。

Sample Input

4 4 2 1

1 3

2 3

3 3

2 -1

Sample Output

TAK

TAK

NIE

TAK

Source
额。。这个题目有二分图匹配的感觉。那么根据Hall定理,对于任何一个子集,他的临集的大小必须要大于它的大小。。
那么设ti为脚为i号的人数
对于ta到tb,它们临集的大小显然是(b-a+1+d)*k
那么需要知道是不是对任何一个连续子序列都满足这个。。
变形一下设t’a=ta-k
那么Sum(ta..b)<=(b-a+1+d)*k
<=>
Sum(t’a..b)<=d*k
。。。。可以发现只要维护t’的最大子序列和就OK了T_T。。
这显然是最简单的线段树。。
发代码也麻烦。。。我的马甲nimendongde的密码是123456.。。。
自己去看吧T_T。。

ACM的WSN,非ACMer和没读过鲁迅先生的《孔乙己》的请绕道。。

今年的regional快开始了,虽然早已退役,在此写一篇消遣。

 

        Arena的格局,是和别处不同的:是用Java做的客户端,可以随时System Test每场SRM,还可以看到挂掉的数据。喜欢做Coding的人,傍午傍晚闲得蛋疼的时候,每每花75分钟,切一场陈旧的250和500,——这是没有比赛的时候的事,有比赛的时候大家每次都把服务器挤挂——然后继续,水掉250之后趁热切掉500,倘若更NB一些,便可以留时间把1000也写一写,或者检查一下250和500有没有bug,如果1000或者准备数据,准备等会儿cha人,但一般的选手,多是铁牌男,大抵没有那么NB。只有Final拿牌的红id神牛,才提交了1000之后,又准备了各种邪恶数据,慢慢的等着cha人。

         我20岁那年起,便在学校的ACM集训队里打酱油,队长说,我样子太傻,怕切不动dp,就写点阿烦模拟吧。区域赛上的阿烦模拟,虽然没什么算法,但弯弯扭扭规则复杂的也不少。出题人往往要你会不会揣测他的英语描述是什么意思,看看你会不会用各种堆来维护状态,又要你在各种规则下面做复杂的判断和考虑,然后才开始拍码:在这种严格的时空限制下,STL里的容器和方法也很难不TLE。所以过了几天,队长说我干不了这事。幸亏帮做了个OJ有苦劳,辞退不得,便改为专门写几何这种无聊的题目了。

         我从此便整天的在各大OJ上,专切我管的题目。虽然没有什么看了解题报告还切不动的,但总觉得有些单调,有些无聊。队长一副凶脸孔,题目也没有以前那么水,教人酱油不得;只有WSN到BBS上发帖,才可以笑几声,所有至今还记得。

         WSN是进过Final却是蓝id的唯一的人。他的代码很长,缩进怪异,时常夹写看不懂的注释;一堆乱糟糟的变量命名。虽然是进过Final,可是没有拿到名次,似乎是黑马杀进去,也没有过题。他写解题报告,总是满篇的“这道题其实不难”,叫人半懂不懂的。因为他的ID是WoShenNiu,别人便从拼音拼出“我神牛”这样不靠谱的字,只好给他起个绰号,叫做WSN。WSN一到BBS上发帖,所有灌水的人都回复笑他,“WSN,你的TopCoder帐号又被封啦!”他不回答,继续回帖说“这道题其实不难的”,便贴出200来行代码。他们又故意把他的帖子顶起来,说“你一定又贴人家的模板啦!”WSN睁大眼睛说,“你怎么这样凭空污人清白……”“什么清白?我前天亲眼见你在上场SRM 1000里面贴人家费用流模板,还贴WA了”。WSN便涨红了脸,额上的青筋条条绽出,争辩道,“参考代码不能算贴……参考!……拍代码的事,能算贴么?”接连便是难懂的话,什么“其实会写”,什么“麻烦”之类,引得众人都哄笑起来:店内外充满了快活的空气。

       听人家背地里谈论,WSN原来是学计算机的,但终于没有发paper读研,又不会找工作;于是愈过愈囧,弄到将要讨饭了。幸而会写代码,便替MM做做C语言作业,换一碗饭吃。可惜他又有一样坏脾气,便是贴别人模板。写不了几行,便连人家的头文件、注释,一齐贴上。如是几次,叫他做C语言作业的MM也没有了。但他在我们OJ里,品行却比别人都好,就是从不贴别人代码;虽然间或拿模板过了题,暂时在best solutions里面排名低,但不出一月,定然自己重新写一份来刷版,多刷几次WSN的id便在很多题里排名很高。

       在这些时候,我可以附和着灌水,队长是决不责备的。而且队长见了WSN的帖子,也每每这样问他,引人发笑。WSN知道自己不能和大牛们谈算法,便只好向小白们说话,有一回他在SRM Room里问我,“你学过算法么?”我回了个省略号,他说,“学过,……我便考你一考。最大流该怎么做?”我想,整天帮人做C语言作业的人,也配考我么?便不再回复他。WSN等了许久,很恳切的说道,“不能做罢?……我教给你,记着!这些算法应该记着。将来去Regional的时候,写成模板带去。”我暗想我从来不管这类的题目,而且我们队长也从不将最大流写成模板;又好笑,又不耐烦,懒懒的答他道,“谁要你教,不是残留网络上找增广路么?”WSN显出极高兴的样子,回复了一个猥琐的笑容表情,说,“对呀对呀!……最大流有四种做法,你知道么?”我愈不耐烦了,准备退出这个Room。WSN说可以预流推进,想贴个模板出来,见我毫不热心,便又打了长长的感叹号,显出极惋惜的样子。

       有几回,几个小白看到WSN在POJ发贴,也赶热闹,把WSN的帖子顶起来。他便给他们一人发一个模板。小白们看完模板,仍然不散,回帖找他要模板。WSN着了慌,打开template的文件夹看了看,又回帖说,“不多了,我已经不多了。”又看看自己的模板库,摇头说,“不多不多!多乎哉?不多也。”于是这帖子就在一片笑声中沉下去了。

       WSN是这样的使人快活,可是没有他,别人也便这么过。

有一天,大约是Regional前的两三天,队长正在慢慢的检查要打印的模板,忽然说,“WSN长久没有来切题了。还有19个tried but failed呢!”我才也觉得他的确长久没有来了。一个灌水的人说道,“他怎么会来?……他各个OJ都被封号了。”队长说,“哦!”“他总仍旧是贴人家模板。这一回,是自己发昏,竟贴了楼爷的代码。楼爷在Astar的代码,能贴得吗?”“后来怎么样?”“怎么样?先写取消过的题,后来是封号,很多OJ都封了他,再TopCoder也封了他。”“后来呢?”“后来没有WoShenNiu的帐号切题了。”“没有帐号了怎样呢?”“怎样?……谁晓得?许是退役了。”队长也不再问,仍然慢慢的检查他的模板。

Regional之后,秋风是一天凉比一天,看看将近初冬;我整天的挂题,也须弄点模板了。一天的下半天,没有人交题,我正在BBS上闲逛。忽然间看得一个新贴,“这道题其实不难。”这语句虽然不多了,却很眼熟。看时WoShenNiu帐号并没有解封。仔细一查看,那WSN便在OJ上注册了马甲WeiSuoNan。他几乎不再过题,代码也已经不成样子;见了我回帖求解答,又说道,“道题其实真的不难。”队长也登上OJ去看WeiSuoNan,一面说,“WSN么?你还有十九个tried but failed呢!”WSN很颓唐的答道,“这……下回再AC吧。这一回是1Y的,题不难。”队长仍然同平常一样,把WSN的帖子顶起来加亮,“WSN,你又贴人家模板了!”但他这回却不十分分辩,单说了一句“不要取笑!”“取笑?要是不贴,怎么会被封号?”WSN低声说道,“忘了密码,忘,忘……”他的语言,很像恳求队长,不要再提。此时已经聚集了几个灌水的,便和队长都笑了。我看了他的解题报告,下载了,放在集训队的群共享里。他又上传了四个附件,见都是最大流模板,原来他便用这模板刷版的。不一会,他回复完帖子,便又在路人甲们的说笑声中,用那模板又贴了几个最大流的题目。

自此以后,又长久没有看见WSN。到了Final后,队长看看OJ的统计说,“WSN还有十九个tried but failed呢!”到第二年的OJ改版,又说“WSN还有十九个tried but failed呢!”到暑假集训可是没有说,再到Regional也没有看见他。

我到现在终于没有见他交题或发帖——大约WSN的确退役了。

 

by 王老师,二零一零年八月二十六日

[NOI2007]货币兑换Cash

[NOI2007]货币兑换Cash

Time Limit:5000MS  Memory Limit:65536K
Total Submit:84 Accepted:36
Case Time Limit:1000MS

Description

Input

第一行两个正整数N、S,分别表示小Y 能预知的天数以及初始时拥有的钱数。
接下来N 行,第K 行三个实数AK、BK、RateK,意义如题目中所述

Output

只有一个实数MaxProfit,表示第N 天的操作结束时能够获得的最大的金钱
数目。答案保留3 位小数。

Sample Input

3 100
1 1 1
1 2 2
2 2 3

Sample Output

225.000

Hint

测试数据设计使得精度误差不会超过10-7。
对于40%的测试数据,满足N ≤ 10;
对于60%的测试数据,满足N ≤ 1 000;
对于100%的测试数据,满足N ≤ 100 000;

Source

我又使用随机化算法强行AC了这道题目囧。。。。
WA+TLE N次。。。累成SB囧。。。
首先转化成维护凸壳大家都知道。。
我的办法基本上就是维护一个链表的数组。。
然后根据算法导论说的可以在Sqrt(N)的时间内在这个数组里面找一个元素。。
所以插入跟维护都可以做到Sqrt(N)。。。
然后硬做。。
就A掉了囧。。。
Code:
http://www.ideone.com/8hGL1

[2009国家集训队]小Z的袜子(hose)

[2009国家集训队]小Z的袜子(hose)

Time Limit:20000MS Memory Limit:265536K
Total Submit:8 Accepted:3
Case Time Limit:2000MS

Description

作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……
具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他可能会询问多个(L,R)以方便自己选择。

Input

输入文件第一行包含两个正整数N和M。N为袜子的数量,M为小Z所提的询问的数量。
接下来一行包含N个正整数Ci,其中Ci表示第i只袜子的颜色,相同的颜色用相同的数字表示。
再接下来M行,每行两个正整数L,R表示一个询问。

Output

包含M行,对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1,否则输出的A/B必须为最简分数。(详见样例)

Sample Input

Sample Output

Source

By Mt
这个题目常规的办法神马线段树块状数组通通悲剧。。。
只能把所有询问都看成点。。然后建一个曼哈顿最小生成树。。然后遍历一下得出答案。。。
但是我太懒了。。并没有要一定是最小的生成树啊。。只要差不多就可以了。。
于是我用了随机邻图的办法。。。
就是把所有点随机一下跟它距离比较近的点。。然后建一颗最小生成树。。。
居然能过T_T。。。
Code:
http://www.ideone.com/tMos6

2/50/11/14/15【样例解释】询问1:共C(5,2)=10种可能,其中抽出两个2有1种可能,抽出两个3有3种可能,概率为(1+3)/10=4/10=2/5。询问2:共C(3,2)=3种可能,无法抽到颜色相同的袜子,概率为0/3=0/1。询问3:共C(3,2)=3种可能,均为抽出两个3,概率为3/3=1/1。注:上述C(a, b)表示组合数,组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。【数据规模和约定】30%的数据中 N,M ≤ 5000;60%的数据中 N,M ≤ 25000;100%的数据中 N,M ≤ 50000,1 ≤ L < R ≤ N,Ci ≤ N。6 41 2 3 3 3 22 61 33 51 6

codeforces#28

这次的A题题意非常不清楚。。。
看得我累死囧。。。。
状态不是很好。。。弄完了ABC之后还有点时间可以做D。。
要写线段树神马的非常繁琐。。好不容易快写完了发现一些问题。。。导致没来的及囧。。。
A
首先题目中已经说了。。。这个图形是固定的。。然后需要枚举是在奇数位还是在偶数位放rod,
那么就变成一个二分图匹配问题了。。。
B
。。。把可以互相交换的位置用无向边连起来。。只需要判断每个点跟它的目的地是否可达就可以了。。。C
这个题目挺好玩的。。枚举最大值再动态规划就可以了。。。。
设F(k)为最大时间小于k的概率。。Dp出F(k)之后
Sum(( F(i+1)-F(i) )*i)就是答案了。。。
D
看错了题目。。。又错误理解了样例。。。
导致花了N长时间写线段树。。。
我是大傻叉。。。。
最后第23囧。。。。

Page 1 of 212