[NOIP2014] 普及组-白红宇

[NOIP2014] 普及组

阅读量：6717 次

发布时间：2019-06-25

本文共 3031 字，大约阅读时间需要 10 分钟。

模拟。

将所有“两个不同数之和”装进桶里，扫描原数组记录满足条件的数的个数。

1 /*by SilverN*/ 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 const int mxn=20010; 9 int read(){10     int x=0,f=1;char ch=getchar();11     while(ch<'0' || ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}12     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}13     return x*f;14 }15 int n;16 int a[mxn];17 int cnt[mxn];18 int main(){19     int i,j;20     n=read();21     for(i=1;i<=n;i++){22         a[i]=read();23     }24     for(i=1;i

珠心算测验

暴力。

因为L<=100，所以分子和分母都从1循环到100，暴力判断即可。

1 /*by SilverN*/ 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 int read(){ 9     int x=0,f=1;char ch=getchar();10     while(ch<'0' || ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}11     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}12     return x*f;13 }14 int gcd(int a,int b){15     if(!b)return a;16     return gcd(b,a%b);17 }18 int a,b,L;19 int ra=100,rb=1;20 int main(){21     int i,j;22     a=read();b=read();L=read();23     for(i=1;i<=L;i++)24      for(j=1;j<=L;j++){25          if(gcd(i,j)!=1)continue;26          if(i*b>=j*a && i*rb

比例简化

O(n^2)循环会超时。

可以计算出最外围一圈数的个数，每次拆掉一圈数，到了目标数所在的圈再暴力查找。

1 /*by SilverN*/ 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 using namespace std; 9 int n;10 int main(){11 int i,j;12 cin>>n>>i>>j;13 long long ans=0;14 int eg=min(min(n-i,i-1),min(n-j,j-1));15 for(int k=0;k

螺旋矩阵

暴力DFS选择的行，然后在所选行上DP。

DP时需要前缀和优化。

1 /*by SilverN*/ 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 using namespace std; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}12 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}13 return x*f;14 }15 int f[17][17];16 int n,m,r,c;17 int mp[17][17];18 int ans=1e9;19 //bool vis[17];20 int use[17];21 int ds[17];//行之间的差值 22 int cs[17][17];//列之间的差值 23 void DP(){24 memset(cs,0,sizeof cs);25 memset(ds,0,sizeof ds);26 memset(f,0x3f,sizeof f);27 int i,j;28 for(i=1;i
            
             r){61 /* printf("use:");62 for(int i=1;i<=r;i++)printf("%d ",use[i]);63 printf("\n");*/64 DP();return;65 }66 int lim=n-(r-dep);67 for(int i=pos;i<=lim;i++){68 use[dep]=i;69 DFS(dep+1,i+1);70 }71 return;72 }73 int main(){74 int i,j;75 n=read();m=read();r=read();c=read();76 for(i=1;i<=n;i++)77 for(j=1;j<=m;j++)78 mp[i][j]=read();79 DFS(1,1);80 // use[1]=4;use[2]=5;DP();81 82 83 printf("%d\n",ans);84 return 0;85 }