首页 > 代码库 > 10.23 noip模拟试题

10.23 noip模拟试题

尼玛蛋pdf好难粘

直接写了

T1

/*开始写wa了 我真弱2333 关于p的排序规则不只是差值 为了字典序最小 还要拍别的*/#include<cstdio>#include<algorithm>#define maxn 100010#define inf 1e7#define mem(a,b) for(int i=0;i<=n;i++)a[i]=b[i];using namespace std;int n,m,ans=inf,k;char s[maxn],r[maxn],l[maxn];struct node{    int c,o;}p[maxn];int cmp(const node &x,const node &y){    if(x.c!=y.c)return x.c<y.c;//差值优先     int i=x.o,j=y.o;    if(s[i]==s[j]){//相等的特盘         if(s[i]-0<k)return i>j;        else return i<j;    }    return s[i]>s[j];//优先改数大的 大的大的大的 话说这sort的cmp不能写很多if好像 会慢死 }int Abs(int x){    return x>0?x:-x;}int Cmp(){    for(int i=1;i<=n;i++){        if(l[i]<r[i])return 1;        if(l[i]>r[i])return 0;    }}int main(){    freopen("number.in","r",stdin);    freopen("number.out","w",stdout);    scanf("%d%d%s",&n,&m,s+1);    for(k=0;k<=9;k++){        for(int i=1;i<=n;i++){            p[i].c=Abs(s[i]-0-k);            p[i].o=i;        }        sort(p+1,p+1+n,cmp);        int mx=0;        for(int i=1;i<=m;i++)            mx+=p[i].c;        if(mx<ans){            ans=mx;mem(r,s);            for(int i=1;i<=m;i++)                r[p[i].o]=k+0;        }        else if(ans==mx){            ans=mx;mem(l,s);            for(int i=1;i<=m;i++)                l[p[i].o]=k+0;            if(Cmp())mem(r,l);        }    }    printf("%d\n",ans);    for(int i=1;i<=n;i++)        printf("%c",r[i]);    return 0;}

T2

/*1 S=a1 c=a2-a12 S=a1 c=a3-a13 S=a2 c=a3-a2我晕 还带验证合法性 尼玛SP个毛啊 wo de da an dui a */#include<cstdio>#define maxn 200010using namespace std;int n,a[maxn],S,c,A[maxn],B[maxn],cnt;bool f[maxn];int init(){    int x=0,f=1;char s=getchar();    while(s<0||s>9){if(s==-)f=-1;s=getchar();}    while(s>=0&&s<=9){x=x*10+s-0;s=getchar();}    return x*f;}void Clear(){    cnt=0;    for(int i=0;i<=n;i++)        f[i]=A[i]=B[i]=0;}bool Judge(){    int now=a[S];    for(int i=S;i<=n;i++)        if(a[i]==now){            f[i]=1;now+=c;B[++B[0]]=a[i];            A[0]=0;int falg=0;            for(int j=1;j<=n;j++)                if(!f[j])A[++A[0]]=a[j];            if(A[0]<=1||B[0]<=1)continue;            int C=A[2]-A[1];            for(int j=3;j<=A[0];j++)                if(A[j]-A[j-1]!=C){                    falg=1;break;                }            if(falg==0)return 1;        }}void Printf(){    printf("%d ",B[0]);    for(int i=1;i<B[0];i++)        printf("%d ",B[i]);    printf("%d\n",B[B[0]]);    printf("%d ",A[0]);    for(int i=1;i<A[0];i++)        printf("%d ",A[i]);    printf("%d\n",A[A[0]]);}int main(){    freopen("progression.in","r",stdin);    freopen("progression.out","w",stdout);    n=init();    for(int i=1;i<=n;i++)        a[i]=init();    S=1;c=a[2]-a[1];    if(Judge()){Printf();return 0;}    Clear();S=1;c=a[3]-a[1];    if(Judge()){Printf();return 0;}    Clear();S=2;c=a[3]-a[2];    if(Judge()){Printf();return 0;}    printf("No solution\n");    return 0;}
T3
/*我尼玛今天刚意识到 这样Dfs是O(m)的啊 啊 啊 很自信地暴力 华丽的T了*/#include<cstdio>#define maxm 10010#define maxn 510using namespace std;int n,m,Q,num,head[maxn],f[maxn],cnt,l,r;struct node{    int o,v,pre;}e[maxm*2];int init(){    int x=0,f=1;char s=getchar();    while(s<0||s>9){if(s==-)f=-1;s=getchar();}    while(s>=0&&s<=9){x=x*10+s-0;s=getchar();}    return x*f;}void Add(int from,int to,int x){    num++;e[num].v=to;    e[num].o=x;    e[num].pre=head[from];    head[from]=num;}void Dfs(int x){    for(int i=head[x];i;i=e[i].pre){//O()O()O()O        if((e[i].o>=l&&e[i].o<=r)||f[e[i].v])continue;        f[e[i].v]=1;Dfs(e[i].v);    }}int main(){    freopen("network5.in","r",stdin);    freopen("network.out","w",stdout);    n=init();m=init();int u,v;    for(int i=1;i<=m;i++){        u=init();v=init();        Add(u,v,i);Add(v,u,i);    }    Q=init();    while(Q--){        for(int i=1;i<=n;i++)f[i]=0;        l=init();r=init();cnt=0;        for(int i=1;i<=n;i++)            if(f[i]==0){                f[i]=1;cnt++;Dfs(i);            }        printf("%d\n",cnt);    }    return 0;}
/*并茶几~边老多老多  有很多很多虚的渣的没用的 因为不能用的是一段区间 所以能用的就是 前缀 后缀预处理统计出有贡献的边们然后Q次询问就成了每次O(n) */#include<cstdio>#define maxm 10010#define maxn 510#define Cf for(int i=0;i<=n;i++)fa[i]=iusing namespace std;int n,m,Q,A[maxm],B[maxm],fa[maxn];struct node{    int u,v;}p[maxm];int init(){    int x=0,f=1;char s=getchar();    while(s<0||s>9){if(s==-)f=-1;s=getchar();}    while(s>=0&&s<=9){x=x*10+s-0;s=getchar();}    return x*f;}int find(int x){    if(x!=fa[x])return fa[x]=find(fa[x]);    return fa[x];}int main(){    freopen("network.in","r",stdin);    freopen("network.out","w",stdout);    n=init();m=init();int u,v;Cf;    for(int i=1;i<=m;i++){        u=init();v=init();        p[i].u=u;p[i].v=v;    }    for(int i=1;i<=m;i++){        int r1=find(p[i].u);        int r2=find(p[i].v);        if(r1!=r2){            fa[r2]=r1;A[++A[0]]=i;        }    }    Cf;    for(int i=m;i>=1;i--){        int r1=find(p[i].u);        int r2=find(p[i].v);        if(r1!=r2){            fa[r2]=r1;B[++B[0]]=i;        }    }    Q=init();    while(Q--){        Cf;int l,r,cnt=0;        l=init();r=init();        for(int i=1;i<=A[0];i++){            if(A[i]>=l)break;            int r1=find(p[A[i]].u);            int r2=find(p[A[i]].v);            if(r1!=r2){                fa[r2]=r1;cnt++;            }        }        for(int i=1;i<=B[0];i++){            if(B[i]<=r)break;            int r1=find(p[B[i]].u);            int r2=find(p[B[i]].v);            if(r1!=r2){                fa[r2]=r1;cnt++;            }        }        printf("%d\n",n-cnt);    }    return 0;}

 

10.23 noip模拟试题