noip2014 普及组

珠心算测验 题目传送门

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int n,w[107],sum[100007],ans;
int main()
{
    n=read();
    for(int i=1;i<=n;i++) w[i]=read(),sum[w[i]]++;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++) if(sum[w[i]+w[j]]) ans++,sum[w[i]+w[j]]--;
    }
    printf("%d
",ans);
    return 0;
}

螺旋矩阵 题目传送门

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=30007;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int n,x,y;
int dfs(int n,int x,int y){
    if(x!=1&&x!=n&&y!=1&&y!=n) return 4*(n-1)+dfs(n-2,x-1,y-1);
    if(x==1) return y;
    if(y==n) return n-1+x;
    if(x==n) return 2*(n-1)+(n-y+1);
    return 3*(n-1)+(n-x+1);
}
int main()
{
    n=read(); x=read(); y=read();
    printf("%d
",dfs(n,x,y));
    return 0;
}

比例简化 题目传送门

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int a,b,w;
int ans1,ans2;
double mn=inf;
int gcd(int x,int y){
    int p;
    while(y){
        p=x%y;
        x=y;
        y=p;
    }
    return x;
}
int main()
{
    a=read(); b=read(); w=read();
    double h=1.0*a/b;
    for(int i=1;i<=w;i++)
        for(int j=1;j<=w;j++) if(gcd(i,j)==1){
            double now=1.0*i/j;
            if(now>=h&&now-h<mn) mn=now-h,ans1=i,ans2=j;
        }
    printf("%d %d
",ans1,ans2);
    return 0;
}

子矩阵  题目传送门

这是道dp题 因为状态数太多 所以我们可以枚举行数来降幂 预处理一波行列差就可以实现了 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=1e9;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int n,m,r,c,cnt,ans=inf;
int s[25][25],f[25][25],h[25],w[25][25],l[25];
void dp(){
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i][j]=inf,h[i]=0,w[i][j]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=c;j++){
            if(j>=2) h[i]+=abs(s[i][l[j]]-s[i][l[j-1]]);
            f[i][0]=0; f[i][1]=h[i];
            for(int k=i+1;k<=n;k++) w[i][k]+=abs(s[k][l[j]]-s[i][l[j]]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=2;j<=min(r,i);j++){
             for(int k=1;k<i;k++) f[i][j]=min(f[i][j],f[k][j-1]+w[k][i]);
             f[i][j]+=h[i];
        }
        ans=min(ans,f[i][r]);
    }
}
int main()
{
    n=read(); m=read(); r=read(); c=read();
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      s[i][j]=read();
    for(int k=1;k<(1<<m);k++){
        cnt=0;
        for(int i=0;i<m;i++) if((1<<i)&k){
            l[++cnt]=i+1;
            if(cnt>c) break;
            if(cnt+(m-i-1)<c) break;
        }
        if(cnt==c) dp();
    }
    printf("%d
",ans);
    return 0;
}