当前位置：首页 > news >正文

noip2014 普及组

news 来源：原创 2024/5/17 17:22:43

珠心算测验题目传送门

#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\n",ans);
    return 0;
}

View Code

螺旋矩阵题目传送门

#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\n",dfs(n,x,y));
    return 0;
}

View Code

比例简化题目传送门

#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\n",ans1,ans2);
    return 0;
}

View Code

子矩阵题目传送门

这是道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\n",ans);
    return 0;
}