首页 > 代码库 > [NOIP2013] 普及组
[NOIP2013] 普及组
计数问题
纯模拟
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 int main(){ 5 int n,x; 6 cin>>n>>x; 7 int i,c=0; 8 for(i=1;i<=n;i++){ 9 int a=i;10 while(a!=0){11 if(a%10==x)c++;12 a/=10;13 }14 }15 cout<<c;16 return 0;17 }
表达式求值
模拟计算，扫一遍出解
1 /*NOIP2013普及组t2 洛谷P1981 表达式求值*/ 2 /**/ 3 #include<algorithm> 4 #include<iostream> 5 #include<cstring> 6 #include<cstdio> 7 #include<cmath> 8 using namespace std; 9 char last;10 char c;11 int x=0;12 int a=0,b=1;13 int sum=0;14 int main(){15 int i,j;16 bool flag=1;17 do{18 if(cin>>c);19 else{20 flag=0;21 c=‘+‘;22 }23 if(c>=‘0‘ && c<=‘9‘)x=x*10+c-‘0‘;24 else{25 a=x;26 x=0;27 }28 if(c==‘*‘){29 last=1;30 b=(a*b)%10000;31 }32 if(c==‘+‘){33 if(last){34 a=(a*b)%10000;35 sum=(sum+a)%10000;36 b=1;37 last=0;38 }39 else sum+=a;40 }41 42 }while(flag==1);43 printf("%d",sum%10000);44 return 0;45 }
小朋友的数字
线性DP
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 const long long inf=1000000005; 7 int n,p,a[1000500]; 8 9 long long su[1000500]={0};//特征值 10 long long scoremx=-inf;//前排最大分数 11 long long dmx=-inf;12 long long ans=-inf;13 int sum1(){14 int i,j;15 long long s=0;16 long long mx=-inf;17 for(i=1;i<=n;i++){18 if(s+a[i]>mx)mx=s+a[i];19 su[i]=mx;20 if(s+a[i]>0) s+=a[i];21 else s=0;22 }23 //24 for(i=1;i<=n;i++){25 su[i]%=p<<1;26 }27 return 0;28 }29 int main(){30 int i,j;31 scanf("%d%d",&n,&p);32 for(i=1;i<=n;i++)scanf("%d",&a[i]);33 sum1();34 long long score;35 //136 scoremx=su[1];37 score=su[1];38 dmx=score+su[1];39 //end40 for(i=2;i<=n;i++){41 score=dmx;42 if(dmx>scoremx)scoremx=dmx;43 if(su[i]+score>dmx)dmx=su[i]+score;44 }45 printf("%d",scoremx%p);46 return 0;47 }
车站分级
从已知的低级站向高级站连边，跑拓扑排序得出层级关系
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 int n,m; 8 int a;//[第i趟车次的停靠站数] 9 int s[2000];//[第i趟车次停靠的站] 10 int mp[1200][1200]={0};11 int book[1200];12 int r[1200],c[1200]; 13 int st[1200];14 int ans=0;15 void rd(){16 scanf("%d%d",&n,&m);17 int i,j,k;18 for(i=1;i<=m;i++){19 memset(book,0,sizeof(book));20 scanf("%d",&a);21 for(j=1;j<=a;j++){22 scanf("%d",&s[j]);23 book[s[j]]=1;24 }25 for(k=s[1];k<=s[a];k++)//遍历从始发站到终点站26 {27 if(!book[k])28 for(j=1;j<=a;j++)29 if(!mp[k][s[j]])//从低级连到高级可过，从高级连到低级超时 30 {31 mp[k][s[j]]=1;32 r[s[j]]++;}33 }34 35 }36 }37 int main(){38 // freopen("level.in","r",stdin);39 // freopen("level.out","w",stdout);40 rd();41 int i,j;42 int top=0;43 memset(book,0,sizeof(book));44 while(1){45 ans++;46 top=0;47 for(i=1;i<=n;i++)48 if(!r[i] && !book[i])49 {50 top++;51 st[top]=i;52 book[i]=1;53 }54 55 if(!top)break;56 for(j=1;j<=n;j++)57 for(i=1;i<=top;i++){58 if(mp[st[i]][j]){59 mp[st[i]][j]=0;60 r[j]--;61 }62 } 63 if(!top)break;64 } 65 66 printf("%d",ans-1);67 68 69 return 0;70 }
[NOIP2013] 普及组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。