《xx,多校联考,解题报告》由会员分享，可在线阅读，更多相关《xx,多校联考,解题报告（13页珍藏版）》请在金锄头文库上搜索。
1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划XX,多校联考,解题报告Doubly-sortedGridGCJ09FinalProblemC【简要描述】给出一个N*M的方格纸，在方格内可以任意填写字母a到z，但是必须保证，任意一行从左到右字母的字典序必须保证不降，同时任意一列也必须保证字典序不降。现在一些格子已经填上了一些字母，现在要求将剩余没有填写的空格子填满，同时要使得整个方格纸上满足双调不降的要求。问总的方案数取模10007的值。SmalldatasetN,M4LargedatasetN,M10【分析与算法设计】看到这个问
2、题当然最简单的想法就是搜索了。不过，注意到每一个格子可以填26种不同的字母，所以简单考虑就可以发现，对于即使单独1*M的方格纸，可能填写的数目也将达到O(26M)的规模所以简单的搜索是绝不可行的。但是，同时我们也可以注意到，其实我们在进行搜索的时候进行了很多的重复搜索，所以我们需要尝试确立一些搜索的状态来进行记忆化搜索，或者进行递推。算法1：注意到在Small中，虽然总的方案数很多，但是注意到行数和列数都不是很大，因此我们可以尝试进行状态压缩的动态规划。沿用状态压缩动态规划的一般方法，我们记录扫描线上的状态进行转移。如有图所示，其实我们需要记录的状态仅仅是紫色格子中的字母填写情况，蓝色格子中的
3、已经填写过的字母情况我们其实就不用知道了通过紫色格子已经可以反映出蓝色格子的字母状况了。然后我们只要枚举橘红色格子填写什么字母然后进行状态的转移即可。那么考虑紫色扫描线上的点只有O(M)，相应的，状态数即为O(26M)，这在Small中，是完全可以接受的。至于一些格子已经填写了一些字母，我们只需要在转移到具体的格子然后再进行判断即可，算法并没有什么关键的转变。时间复杂度：O(NM26M)空间复杂度：O(NM+26M)期望得分：Small通过观察到在Large中，虽然N和M仍然不大，仅仅10而已，但是，考虑到26个字母的可能填写方案，显然的，仍和关于字母具体信息的扫描线记录方式都是完全行不通的。
4、我们知道，记录一个位置到底是什么字母，就需要花费26的记录代价，这是导致我们无法记录信息的关键问题。那么，我们能不能分离这一问题，并不去记录某一个位置是什么字母，而去记录每一种字母到底占了哪些位置呢？显然的！算法2：这里我们就需要利用到双调有序这一重要性质了。如果在格子(x1,y1)内的字母比(x2,y2)内的字母字典序小，那么则必然有这样的限制条件：x1x2，y1y2。所以，对于字母c1，以及恰好比其大一个字典序位置的字母c2，其分界线一定是一个从左下角到右上角的连续折线，并且任意一点只会向上，或者向右：如右图所示，我们这里标出了字母a，b，c下方的分界线，注意这里字母c所在的格子并不是连通
5、的，所以，字母c的分界线是存在一部分与b的分界线是重合的。而其实字母d的分界线是完全和字母c重合的。字母e的分界线就是整个方格的下拐折线。并且任意字典序大于e的字母的分界线都是与字母e重合的。我们不妨称这样的一条从左下角到右上角的折线为一条路径。对于两条路径P1和P2，如果满足两条路径不严格相交，并且路径P1存在一部分严格的处在在P2的上方，则我们称P10dobeginj:=tempmod10;temp:=tempdiv10;ifj=xtheninc(count);end;end;writeln(count);close(input);close(output);end.【再分析】这样虐题目是
6、会跌人品的，这段时间是非常考验人品的时候，于是就产生了下面的程序，用几个手算来说明问题：输入：输出：4204要求：1到10134每一位上含1的个数解剖之：4个位是1？1有1014种可能，前4位是0000到1013十位是1？1？前3位102种后一位10种所以有1020种可能分类讨论前2位10种后两位100种前2位1种，后两位35种分类讨论的相加得1035种前1位1种后三位1000种所以1000种后四位135种所以135种规律总结：在第i位上固定x，把原数分成两段，然后考虑ai和x大小的关系，对应了上面013的分析，不难发现：aix时，种数=*ai=x时，种数=*+ai0dobegininc(co
7、unt);bcount:=bcount-1*10;acount:=mmod10;m:=mdiv10;end;bcount+1:=bcount*10;ifx=0thendec(count);百位是1？1？千位是1？1？万位是11？以上相加得4204fori:=1tocountdobeginifaiput,);reset(input);assign(output,);rewrite(output);whilenoteolndobeginread(c);casecof+:beginadd;jisuan;flag:=false;end;*:beginadd;jisuan;flag:=true;end;
8、elsebeginval(c,k);temp:=temp*10+k;endend;end;inc(i);ai:=temp;tot:=0;ifflagthenbegininc(tot,ai*ai-1mod10000);i:=i-2;end;whilei0dobegininc(tot,ai);tot:=totmod10000;dec(i);end;writeln(tot);close(input);close(output);end.第三题：小朋友的数字(number)【本段吐槽可以无视】联赛赶上自己评职称，没随队过去，回来听说第三题难懂，赶紧瞄了下题目，孩子们啊，我不是和你们说过的吗，联赛普及组
9、就是考读题目的啊，读懂后简单有木有啊，本题就是最好的证明，再普通不过的递推了，状态转移都没有。【题目简述】给你n个数，让你求对应的n个特征值，根据特征值求分数值，题目需要输出n个分数值的最大值。【我的思路】O(n)扫描最大连续和，求出特征值，然后O(n)计算分数值，同时用更新max。这个思路有一个需要注意的地方，分数值+特征值会超过longint、int64，这里采用计算max时执行modp操作，于是就产生了如下问题：输入：5981-409-40197-96-301特征值：-409-409-分数值：-409-818-818-721-624max：-818不变-721-624最终max停留在了-
10、624，但明显-409才是最大的分数值，这个问题其实就是max初值两个-409惹的祸，必须要在后面所有特征值中判断有没有绝对值大于409的，否则max需要考虑第一个分数值，以免出现这样的错误。附上代码：vari,n,p:longint;a:array0.oflongint;f,b:array0.ofint64;max,temp:int64;flag:boolean;beginassign(input,);reset(input);assign(output,);rewrite(output);readln(n,p);fori:=1tondobeginread(ai);end;max:=-max
11、longint;fori:=1tondobegininc(temp,ai);iftempmaxthenmax:=temp;iftemp#includeintk;longlongans;intn,m,x;longlongExp(inty)if(!y)return1;if(y=1)return10%n;if(y&1)return(Exp(y1)*Exp(y1)%n)*10)%n;elsereturn(Exp(y1)*Exp(y1)%n;intmain()scanf(%d%d%d%d,&n,&m,&k,&x);ans=Exp(k);ans*=m;ans%=n;ans+=x;ans%=n;printf
12、(%lld,ans);return0;第二题：火柴排队对距离公式化简得：(ai-bi)2=(ai2-2aibi+bi2)=ai2+bi2-2aibi要求(ai-bi)2最小，就只需要aibi最大即可。这里有个贪心，当a1b,cd,且ac+bdb矛盾，所以若ab,cd，则ac+bdad+bc将此式子进行推广：当a1#include#includeusingnamespacestd;#defineMAXN#definelowbit(x)(x)+1)&x)#defineMAXstructsaverintv,t;saveraMAXN,bMAXN;boolcmp(saverx,savery)return
13、;intn,rMAXN,ans=0;inttMAXN;voidAdd(intx)for(inti=x;i=n;i+=lowbit(i)ti+;intSum(intx)intrec=0;for(;x;x-=lowbit(x)rec+=tx;returnrec;intmain()scanf(%d,&n);for(inti=0;i+n;)scanf(%d,&ai.v),ai.t=i;for(inti=0;i+n;)scanf(%d,&bi.v),bi.t=i;sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp);for(inti=0;i+n;)rai.t=bi.t;for(inti=n;i;i-)ans+=Sum(ri),Add(ri),ans%=MAX;printf(%dn,ans);return0;第三题：货车运输首先，我们可以确定
