noip2011模拟题准备

来源：蜘蛛抓取(WebSpider) 时间：2011-10-14 09:56 标签： noip2011模拟题
& & 分析：& & 首先有一个不断快排的做法，好像会超时。& & 正解是归并。& & 先快排一次。& & 之后就是归并排序。& & 先将胜利的人加上1分，并放入一个win数组。& & 将失败的人放入一个lose数组里。& & 最后归并到原数组中。& & 这个题原本想到了正解，但是倒在了细节上。。& & 代码：& & #include&iostream&
#include&cstdio&
#include&algorithm&
int n,r,q,i,j,
struct node
}a[200010],w[100010],l[100010];
bool cmp(node a,node b)
if (a.s==b.s) return a.ii&b.
return a.s&b.s;
int main()
freopen("swiss.in","r",stdin);
freopen("swiss.out","w",stdout);
cin&&n&&r&&q; n*=2;
for ( i=1;i&=n;++i) scanf("%d",&a[i].s),a[i].ii=i;
for ( j=1;j&=n;++j) scanf("%d",&a[j].p);
sort(a+1,a+1+n,cmp);
for ( ji=1;ji&=r;ji++)
int wi=1,lo=1;
for ( i=1;i&=n;i+=2)
if (a[i].p&a[i+1].p) w[wi++]=a[i+1],l[lo++]=a[i];
else if (a[i].p&a[i+1].p)l[lo++]=a[i+1],w[wi++]=a[i];
wi--;lo--;
for ( i=1;i&=n/2;i++) w[i].s++;
int x=1,y=1;
while( x&=n/2 && y&=n/2)
if (w[x].s&l[y].s) a[++i]=w[x++];
if (w[x].s&l[y].s) a[++i]=l[y++];
if (w[x].s==l[y].s&&w[x].ii&l[y].ii) a[++i]=l[y++];
if (w[x].s==l[y].s&&w[x].ii&l[y].ii) a[++i]=w[x++];
if (x&n/2)
while (y&=n/2) a[++i]=l[y++];
else while (x&=n/2) a[++i]=w[x++];
printf("%d",a[q].ii);
声明：该文章系网友上传分享，此内容仅代表网友个人经验或观点，不代表本网站立场和观点；若未进行原创声明，则表明该文章系转载自互联网；若该文章内容涉嫌侵权，请及时向
上一篇：下一篇：
相关经验教程
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.002 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.002 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.003 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.004 收益
的原创经验被浏览，获得 ￥0.005 收益NOIP2011初赛提高组参考解答_yuejun_南通教育博客
NOIP2011初赛提高组参考解答
算法与编程
阅读(4000)&&
发表于 11:01:41&&
5.& C300+400=700B
7A[1..n]i&jA[i]&A[j],A[i]A[j]3
&&& a数I1a[i]ni
21 2 5 13 34
457344&& 213*7
m*n0-1m=2n72n-11012^(n-1)002^(n-1)122n-2*2=22n-1,nn*22n-1213*7.
f(n)=4n/(n-1)*f(n-1)& (1012)
f(n)=n*22n-1
1①ans.num[i+j-1]&&&&&&&& ②ans.num[i]:=ans.num[i] mod 10
③a.num[i]+b.num[i]&&&&& ④ans.num[i] mod 2
⑤inc(ans.len)&&&&&&&&&& ⑥a.len&b.len
⑦ord(‘0’)或48&&&&&&&& ⑧times(middle,middle),target
此题为简单高精度运算的大杂烩，加减乘除几乎全有。
乘法中要注意的是i位乘以j位的数据结果加到i+j-1位里，乘完以后再考虑进位；
加法是对应位相加，可以同步处理进位。
除法本题只是除以2，一位一位除2的时候，余数的情况要先处理。
另外还有一个比较两个以数组形式存储的大数据大小的子程序over，先从长度来考虑，谁长谁大，相等长度时从高位向低位依次比较，只要出现有大的情况就认为它大。
2．①inc(num)&&&&&&&&&&&&&& &&& ②j:=i
③solve(left,j-1,deep+1)&&&& ④solve(j+1,right,deep+1)
deepmaxdeepmaxdeepdeepsum1;
deep=maxdeepsum1
博客分类……
&&友情链接
@2005－.cn, all rights reserved
主办单位：南通市教育局 &&
承办单位： &&
技术支持 &&相关文章：&&&&&&
最新添加资讯
24小时热门资讯
附近好友搜索You are here:
CCF NOIP2011提高组一等奖名单公示
CCF NOIP2011
—————————————————————
NOI报名系统noip2011普及组复赛解题思路要标准程序与基本思路,最好带注释,（第一题可以不讲）,
第二题：var
wz,wz1,tot,i:
assign(input,'stat.in');
assign(output,'stat.out');
reset(input);
rewrite(output);begin
close(input);
close(output);function upp(ss:char):begin
upp:=chr(ord(ss)-32);begin
readln(s);
for i:=1 to length(s) do
if ord(s[i])>96 then
s[i]:=upp(s[i]);begin
while not eof do
if st=' ' then begin
if s1=s then begin
if wz=-1 then wz:=wz1;
inc(wz1,length(s1)+1);
else begin
if ord(st)>96 then st:=upp(st);
if s1=s then begin
if wz=-1 then wz:=wz1;
inc(wz1,length(s1)+1);
if tot>0 then writeln(tot,' ',wz)
else writeln('-1');beginend.第三题：题目分析：首先,由于每轮比赛的次序都是由上一轮比赛完后的比分决定的,因此对于普及组的同学来说仅能使用模拟的方法来解决.容易想到的是每一轮模拟完以后快排一次,用这样的方法,时间复杂度为O((2n)*log 2n*R),根据数据范围可知这种思路仅能解决50%的数据.因此我们需要一种更有效的方式.分析题意后可以发现,对于每一轮比赛过后,每一位选手都会有一种状态,赢了或者输了,而每一位选手比赛前都是有序的,那么对于所有在该轮比赛中赢了或者是输了的选手,都是有序的.即每轮比赛后,我们可以以O(N)的效率获得胜负选手的有序队列,对于两组有序序列,容易想到将两组数列归并,归并的效率为O(N),这样,完成一轮比赛的效率从O((2n)*log 2n*R)缩减至O(NR),根据数据范围,这样的程序是能够在1秒内出解的.第四题：转后缀表达式＋dp,个人认为递推
为您推荐：
其他类似问题
扫描下载二维码

我要回帖

更多关于 noip2011模拟题 的文章

 

随机推荐