注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

NOIP2013题解(含400AC代码)  

2014-02-17 22:09:20|  分类: noip |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
抱歉各位OIER,最近很忙,没写题解,也没修改考试的程序,不过今天搞好了,分享下,(*^__^*) 嘻嘻……!

1.计数问题:
 此题简单模拟,几率一下即可,水题不解释。
C++代码如下:
#include <cstdio>
using namespace std;
int main()
{
    int x,n,ans=0;
    scanf("%d%d",&n,&x);
    for (int i=1;i<=n;i++) 
    {
        for (int j=i;j>0;j /=10)
         if (j %10==x) ans++;
     }
printf("%d",ans);
return 0;
}

2.表达式求值:不要想复杂,+相当于隔开符,遇到乘号便相乘到X,遇到加号便相乘并加入到ans中,数字直接用MOD 10000来方便条件,XX=XX*10+ORD(A[I]);O(N);
代码如下:
var l,x,xx,ans,i:longint; s:ansistring; begin readln(s); s:=s+'+'; l:=length(s);ans:=0;x:=1;xx:=0; for i:=1 to l do begin if s[i]='+' then begin ans:=(ans+(xx*x)mod 10000)mod 10000; xx:=0;x:=1; end else if s[i]='*' then begin x:=(x*xx)mod 10000;xx:=0;end else xx:=(xx*10+ord(s[i])-48)mod 10000; end; writeln(ans); end.

3.小朋友的数字:此题80分很水,纯最大字段和+开INT64。100分需要运用到同余公式:
(a+b)mod P=a mod p+b mod p;所以也轻松解决,注意负数可不能MOD,大于0可以,因为显存上升序列。
AC代码如下:var i,j,k,l,m,a1,n,p:Longint;
ans,tmp:Int64; a:array[0..1000001]of int64; flag:boolean; begin readln(n,p); for i:=1 to n do read(a[i]); readln; tmp:=0;ans:=-(1 shl 60); for i:=1 to n do begin inc(tmp,a[i]); if tmp>ans then ans:=tmp; if tmp<0 then tmp:=0; a[i]:=ans; end; a1:=a[1]; ans:=a1+a[1]; for i:=2 to n-1 do begin tmp:=ans; if a[i]>0 then begin ans:=(tmp+a[i])mod p; if a[i]>abs(a1)then flag:=true; end; end; if (not(flag))and(ans<a1)then ans:=a1; if (n=1) then ans:=a1; writeln(ans mod p); end.

4.车站分级:此题难度较大,想到》=转到《就变得很简单了,就是A>B,B>C,让你求阶级嘛,一看就知道是3;处理起来FOLYED、DFS即可。但推荐一种更重要的算法:拓扑排序。因为是有向图并且无环,按照拓扑建立即可满分.记过测试,O(kN2),k为较大系数《500;
哥的C++代码如下:
#include<cstdio> #include<cstring> using namespace std; bool map[1010][1010];int a[1100],ru[1100];bool num[1100]; int k,i,j,n,m,p,ans; int main() { scanf("%d%d",&n,&m); for (i=1;i<=m;i++) { memset(num,false,sizeof(num)); scanf("%d",&p); for (j=1;j<=p;j++) {scanf("%d",&a[j]);num[a[j]]=true;} for (j=a[1]+1;j<=a[p]-1;j++) if (num[j]==false) for (k=1;k<=p;k++){ if (map[a[k]][j]==false){ map[a[k]][j]=true; ru[j]++;} } }; ans=0;memset(num,false,sizeof(num)); while (3<4) { k=0; for (j=1;j<=n;j++) if ((ru[j]==0)and(num[j]==false)) { k++;a[k]=j;num[j]=true; } if (k==0) break; ans++; for (i=1;i<=k;i++) for (j=1;j<=n;j++) if (map[a[i]][j]) { map[a[i]][j]=false; ru[j]--; } } printf("%d",ans); scanf("\n"); return 0; }

  评论这张
 
阅读(53)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018