@Scarlet 2017-01-07T06:16:35.000000Z 字数 16404 阅读 1192

# NOIP泛做

NOIP 解题报告

## 2015年

### 神奇的幻方

#include<bits/stdc++.h>int a[50][50],n;int main(){    scanf("%d",&n);    int nx=1,ny=(n+1)/2;    a[nx][ny]=1;    for (int i=2;i<=n*n;a[nx][ny]=i,i++)        if (nx==1&&ny!=n)nx=n,ny++;3        else        if (ny==n&&nx!=1)ny=1,nx--;        else        if (nx==1&&ny==n)nx++;        else        if (nx!=1&&ny!=n)            if (a[nx-1][ny+1])nx++;            else nx--,ny++;    for (int i=1;i<=n;i++,puts(""))        for (int j=1;j<=n;j++)            printf("%d ",a[i][j]);} 

### 信息传递

#include<bits/stdc++.h>using namespace std;#define maxn 200010#define INF 2000000000int dep[maxn],vis[maxn],f[maxn],l=0,ans=INF,n;int main(){    scanf("%d",&n);    for (int i=1;i<=n;i++)        scanf("%d",&f[i]);    for (int i=1;i<=n;i++)        if (!vis[i])        {            int j=i,st=1;l++;            while (!vis[f[j]])            {                dep[j]=st;                vis[j]=l;                st++;                j=f[j];            }            dep[j]=st;            vis[j]=l;            if (vis[j]==vis[f[j]]) ans=min(ans,dep[j]-dep[f[j]]+1);        }    printf("%d",ans);}

### 跳石头

#include<bits/stdc++.h>#define maxn 50010int l,n,k,p[maxn],L,R,mid,ans;int check(int x){    int k1=0,l=0;    for (int i=1;i<=n;i++)        if (p[i]-p[l]<x) k1++;        else l=i;    if (p[n+1]-p[l]<x) k1++;    if (k1>k) return 0;    return 1;}int main(){    scanf("%d%d%d",&l,&n,&k);    for (int i=1;i<=n;i++)        scanf("%d",&p[i]);    p[0]=0;    p[n+1]=l;    L=1,R=l;    while (L<=R)    {        mid=L+R>>1;        if (!check(mid)) R=mid-1;        else ans=mid,L=mid+1;    }    printf("%d",ans);    return 0;}

### 子串

#include<bits/stdc++.h>#define maxn 1005#define maxm 205#define mod 1000000007using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int f[2][maxn][maxm],g[2][maxn][maxm],n,m,k;char a[maxn],b[maxm],ans;int main(){    scanf("%d%d%d%s%s",&n,&m,&k,a+1,b+1);    for(int i=0;i<=n;i++)g[0][i][0]=1;    int cr=1;    for(int K=1;K<=k;K++,cr^=1)    {        memset(f[cr],0,sizeof(f[cr]));        memset(g[cr],0,sizeof(g[cr]));        for(int i=1;i<=n;i++)            for(int j=1;j<=m;j++)            {                if(a[i]==b[j])f[cr][i][j]=(f[cr][i-1][j-1]+g[cr^1][i-1][j-1])%mod;//接续上一段或者新起一段                g[cr][i][j]=(g[cr][i-1][j]+f[cr][i][j])%mod;//维护前缀和            }    }    printf("%d\n",g[cr^1][n][m]);    return 0;}

### 运输计划

#include<bits/stdc++.h>#define maxn 300010#define maxm 600010using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}#define AE(u,v,w) E[Si]=(Ed){u,v,w},nxt[Si]=idx[u],idx[u]=Si++struct Ed{int u,v,w;}E[maxm];int idx[maxn],nxt[maxm],Si=1;int n,m,v[maxn],fa[maxn],siz[maxn],top[maxn],id[maxn],son[maxn],dep[maxn],dis[maxn],cnt=0;int que[maxn];int dfs(int x,int f){    int re=1,w=0,t;    for(int i=idx[x];i;i=nxt[i])        if(E[i].v!=f)        {            fa[E[i].v]=x;dep[E[i].v]=dep[x]+1;dis[E[i].v]=dis[x]+E[i].w;            re+=t=dfs(E[i].v,x);if(t>w)w=t,son[x]=E[i].v;        }    return re;}void dfs2(int x,int tp){    top[x]=tp;id[x]=cnt++;    if(son[x])dfs2(son[x],tp);    for(int i=idx[x];i;i=nxt[i])        if(E[i].v!=son[x]&&E[i].v!=fa[x])dfs2(E[i].v,E[i].v);}struct poi{int u,v,lca,w;}Q[maxn];int lca(int x,int y)//这里采用了稍快的树剖求lca，改成倍增的话就不超过NOIP范围了。{    for(;top[x]^top[y];x=fa[top[x]])        if(dep[top[x]]<dep[top[y]])swap(x,y);    return dep[x]<dep[y]?x:y;}int f[maxn],L,ha[maxn],www,cc;int calc(int x,int f){    int tmp=ha[x];    for(int i=idx[x];i;i=nxt[i])        if(E[i].v!=f)            tmp+=calc(E[i].v,x);//前缀和还原信息    tmp>=cc?www=max(www,dis[x]-dis[f]):0;    return tmp;}int check(int x){    cc=0;    for(int i=1;i<=m;i++)        if(Q[i].w>x)cc++;    if(f[cc])return f[cc]>=L-x;//记录部分答案进行优化    memset(ha,0,sizeof(ha));    for(int i=1;i<=m;i++)        if(Q[i].w>x)ha[Q[i].u]++,ha[Q[i].v]++,ha[Q[i].lca]-=2;//差分记录信息    www=0;    calc(1,0);    f[cc]=www;    return www>=L-x;}int main(){    n=read(),m=read();    for(int i=1,a,b,w;i<n;i++)a=read(),b=read(),w=read(),AE(a,b,w),AE(b,a,w);    dfs(1,0);    dfs2(1,1);    int ans,l=0,r=0;    for(int i=1,a,b;i<=m;i++)a=read(),b=read(),Q[i]=(poi){a,b,lca(a,b),0},Q[i].w=dis[a]+dis[b]-dis[Q[i].lca]*2,r=max(r,Q[i].w);    L=r;    for(;l<r;)    {        int mid=l+r>>1;        if(check(mid))r=mid;        else l=mid+1;    }    printf("%d\n",l);    return 0;}

## 2014年

### 生活大爆炸版石头剪刀布

#include<bits/stdc++.h>#define maxn 210using namespace std;int score[5][2]={{0,0,1,1,0},                 {1,0,0,1,0},                 {0,1,0,0,1},                 {0,0,1,0,1},                 {1,1,0,0,0}};int a[maxn],b[maxn];int main(){    int n,na,nb,sa=0,sb=0;    scanf("%d%d%d",&n,&na,&nb);    for (int i=1;i<=na;i++)        scanf("%d",&a[i]);    for (int i=1;i<=nb;i++)        scanf("%d",&b[i]);    for (int i=1;i<=n;i++)    {        int u=a[1+(i-1)%na],v=b[1+(i-1)%nb];        sa+=score[u][v];        sb+=score[v][u];    }    printf("%d %d",sa,sb);    return 0;}

### 联合权值

$\sum_{sym}$ 是对称求和）

#include<bits/stdc++.h>#define maxn 200010#define mod 10007using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int mx[maxn][3],s1[maxn],s2[maxn],ans1,ans2;int n,u[maxn],v[maxn],w[maxn];int main(){    n=read();    for(int i=1;i<n;i++)        u[i]=read(),v[i]=read();    for(int i=1;i<=n;i++)w[i]=read();    for(int i=1;i<n;i++)    {        s1[u[i]]+=w[v[i]],s1[v[i]]+=w[u[i]],        s2[u[i]]+=w[v[i]]*w[v[i]]%mod,s2[v[i]]+=w[u[i]]*w[u[i]]%mod;        if(w[v[i]]>mx[u[i]][0])mx[u[i]][4]=mx[u[i]][0],mx[u[i]][0]=w[v[i]];        else if(w[v[i]]>mx[u[i]][5])mx[u[i]][6]=w[v[i]];        if(w[u[i]]>mx[v[i]][0])mx[v[i]][7]=mx[v[i]][0],mx[v[i]][0]=w[u[i]];        else if(w[u[i]]>mx[v[i]][8])mx[v[i]][9]=w[u[i]];    }    for(int i=1;i<=n;i++)        ans1=max(ans1,mx[i][0]*mx[i][10]),s1[i]%=mod,ans2+=(s1[i]*s1[i]-s2[i])%mod;    printf("%d %d",ans1,(ans2%mod+mod)%mod);}

### 飞扬的小鸟

#include<bits/stdc++.h>#define maxn 10010using namespace std;int x[maxn],y[maxn],p,l[maxn],h[maxn];int f[maxn],g[maxn];int main(){    int n,m,k;    scanf("%d%d%d",&n,&m,&k);    for (int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]),l[i]=m+1;    for (int i=1;i<=k;i++)scanf("%d",&p),scanf("%d%d",&h[p],&l[p]);    int i;    for (i=1;i<=n;i++)    {        for (int j=1;j<=m;j++)g[j]=f[j],f[j]=1e9;        for (int j=1,k=0;j<=m;j++)f[k=min(j+x[i],m)]=min(f[k],min(g[j],f[j])+1);        for (int j=h[i]+1;j<l[i];j++)if (j+y[i]<=m) f[j]=min(f[j],g[j+y[i]]);        int k=0,j;        for (k=0,j=1;j<=m;k|=f[j++]<1e9) if (j<=h[i]||j>=l[i])f[j]=1e9;        if (!k) break;    }    int ans=0;    if (i<=n){for (int j=1;j<i;j++)if (l[j]<=m) ans++;return printf("0\n%d",ans),0;}    ans=1e9;    for (int i=1;i<=m;i++)ans=min(ans,f[i]);    printf("1\n%d",ans);}

### 无线网络发射器选址

$n$小得浑身难受，大力模拟即可。

#include<bits/stdc++.h>using namespace std;const int maxn = 600;int d, n,w[maxn][maxn],x,y,z;int cnt = 0, ans = 0;int get(int x, int y){    int sum = 0;    for(int i = x-d; i <= x+d; ++i)        for(int j = y-d; j <= y+d; ++j)            if (i >=0 && j >=0)               sum += w[i][j];    return sum;}int main() {    scanf("%d%d", &d, &n);    for(int i = 1; i <= n; i++){        scanf("%d%d%d",&x,&y,&z);        w[x][y] = z;    }    for(int i = 0; i <= 128; i++)        for(int j = 0; j <= 128; j++) {            int x = get(i, j);            if(x > ans)ans = x,cnt = 1;            else if(x == ans)cnt++;    }    printf("%d %d\n", cnt, ans);    return 0;}

### 寻找道路

#include<bits/stdc++.h>using namespace std;#define maxn 600000struct Edge {    int v,next;}e[maxn];int first[maxn],d[maxn],u1[maxn], u2[maxn],en;bool mark[maxn];int n, m;int s, t;void add(int u, int v) {    en++;    e[en].v = v;    e[en].next = first[u];    first[u] = en;}void bfs(int u, int flag) {    memset(d, -1, sizeof(d));    queue<int> q;    q.push(u);    d[u] = 0;    while(!q.empty()) {        int x = q.front();        q.pop();        for(int j = first[x]; j > 0; j = e[j].next)        if (j % 2 == flag && !mark[e[j].v]) {            int v = e[j].v;            if(d[v] == -1) {                d[v] = d[x] + 1;                q.push(v);            }        }    }    return ;}int main() {    memset(first, -1, sizeof(first));    scanf("%d%d", &n, &m);    en = 0;     for(int i = 1; i <= m; i++) {        scanf("%d%d", &u1[i], &u2[i]);        add(u1[i],u2[i]);        add(u2[i],u1[i]);    }    scanf("%d%d", &s, &t);    bfs(t, 0);    for(int i = 1; i <= m; i++)        if(d[u2[i]] == -1)            mark[u1[i]] = true;    bfs(s, 1);    printf("%d\n", d[t]);    return 0;}

### 解方程

#include<bits/stdc++.h>#define maxn 110#define R 4#define G getchar()using namespace std;int a[10010],A[110],P[4]={10007,11003,12007,13001},N,H[110][11],L,ans=0,V,p,X,sum,x,n,m,W;bool C[1000010];char ch;int main(){    scanf("%d%d\n",&n,&m);    for (int i=0;i<=n;i++)    {        L=0,ch=G;        if (ch=='-') N=-1;        else a[L++]=ch-48,N=1;        ch=G;        while (ch<=57&&ch>=48)            a[L++]=ch-48,ch=G;        scanf("\n");        for (int p=0;p<R;p++)        {            W=0;            for (int w=0;w<L;w++)W=(W*10+a[w])%P[p];            H[i][p]=(P[p]+W*N)%P[p];        }     }    for (int i=1;i<=m;i++)    {        V=1;        if (C[i]) continue;        for (int j=0;j<R;j++)        {            p=P[j],x=i%p,sum=0,X=1;            for (int k=0;k<=n;k++) sum=(sum+X*H[k][j])%p,X=(X*x)%p;             if (sum)            {                for (int k=i;k<=m;k+=P[j])C[k]=1;                V=0;break;            }        }        if (V) A[++ans]=i;    }    printf("%d\n",ans);    for (int i=1;i<=ans;i++)        printf("%d\n",A[i]);    return 0;}

## 2013年

### 转圈游戏

#include<bits/stdc++.h>#define maxn 1000using namespace std;typedef long long LL;LL mod,r;LL Pow(LL x,LL y){    LL r=1;    for(;y;y>>=1,x=x*x%mod)if(y&1)r=r*x%mod;    return r;}int main(){    LL m,k,x;    scanf("%lld%lld%lld%lld",&mod,&m,&k,&x);    LL p=(Pow(10,k)*(m%mod))%mod;    printf("%lld",(p+(x%mod))%mod);     return 0;}

### 火柴排队

#include<bits/stdc++.h>#define maxn 100010using namespace std;int a[maxn],b[maxn],c[maxn];int u[maxn],s[maxn],t[maxn],n,w;long long sum=0;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int cmp(int a,int b){return u[a]<u[b];}struct poi{int s,t;}A[maxn];inline bool cmpp(const poi &a,const poi &b){return a.s<b.s;}void add(int x){for(;x<=n;x+=x&-x)c[x]++;}int ask(int x){for(w=0;x;x-=x&-x)w+=c[x];return w;}int main(){    n=read();    for(int i=0;i<n;i++)s[i]=t[i]=i;    for(int i=0;i<n;i++)u[i]=read();sort(s,s+n,cmp);    for(int i=0;i<n;i++)u[i]=read();sort(t,t+n,cmp);    for(int i=0;i<n;i++)A[i]=(poi){s[i],t[i]};    sort(A,A+n,cmpp);    sum=1ll*n*(n-1)>>1;    for(int i=0;i<n;i++)sum=sum-ask(A[i].t+1),add(A[i].t+1);    printf("%lld",sum%99999997);    return 0;}

### 货车运输

#include<bits/stdc++.h>#define maxm 70010#define maxn 10010#define INF 2000000000using namespace std;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}struct Ed{int u,v,w;}E[maxm];int r[maxm],n,m,f[maxn];int GF(int x){return f[x]==x?x:f[x]=GF(f[x]);}int cmp(int a,int b){return E[a].w>E[b].w;}int nxt[maxm],idx[maxn],Si;#define AE(u,v,w) E[Si]=(Ed){u,v,w},nxt[Si]=idx[u],idx[u]=Si++int p[maxn][14];//以i跳2^j格的点int w[maxn][14];//跳的范围内最小边权int h[maxn];//每点深度int dfs(int u){    for(int j=1;j<14;j++)        p[u][j]=p[p[u][j-1]][j-1],w[u][j]=min(w[u][j-1],w[p[u][j-1]][j-1]);    for(int i=idx[u];i+1;i=nxt[i])        if(!h[E[i].v])            h[E[i].v]=h[u]+1,p[E[i].v][0]=u,w[E[i].v][0]=E[i].w,dfs(E[i].v);}int LCA(int a,int b){    int ans=INF;    if(GF(a)!=GF(b))return-1;    if(h[a]<h[b])swap(a,b);    for(int t=h[a]-h[b],j=0;t;t>>=1,j++)        if(t&1)ans=min(ans,w[a][j]),a=p[a][j];    if(a==b)return ans;    for(int j=13;j>=0;j--)        if(p[a][j]^p[b][j])            ans=min(ans,w[a][j]),a=p[a][j],ans=min(ans,w[b][j]),b=p[b][j];    ans=min(ans,w[a][0]);    return min(ans,w[b][0]);}int main(){    n=read(),m=read();    for(int i=1;i<=n;i++)f[i]=i;    for(int i=0;i<m;i++)r[i]=i;    for(int i=0,u,v,w;i<m;i++)u=read(),v=read(),w=read(),E[i]=(Ed){u,v,w};    sort(r,r+m,cmp);    memset(idx,-1,sizeof(idx));Si=m;    for(int i=0;i<m;i++)    {        Ed&e=E[r[i]];        int x=GF(e.u),y=GF(e.v);        if(x!=y)f[x]=y,AE(e.u,e.v,e.w),AE(e.v,e.u,e.w);    }    h[1]=1;dfs(1);    int q=read();    for(int i=1;i<=q;i++)        printf("%d\n",LCA(read(),read()));    return 0;}

### 积木大赛

#include<bits/stdc++.h>int n,l,r,s;int main(){    scanf("%d",&n);    for(;n--;l=r)        scanf("%d",&r),r>l?s+=r-l:0;    printf("%d",s);}

### 花匠

#include<bits/stdc++.h>#define maxn 100010int a[maxn],n,ans=2;int sqn(int a){return a>0?a:-1;}int main(){    scanf("%d%d",&n,&a[1]);    for(int i=2;i<=n;i++)    {        scanf("%d",&a[i]);        if (a[i]==a[i-1])i--,n--;    }    for(int i=2;i<=n-1;i++)        if (sqn(a[i]-a[i-1])*sqn(a[i+1]-a[i])<0)ans++;    printf("%d",min(ans,n));    return 0;}

## 2012年

### Vigenère密码

#include<bits/stdc++.h>#define maxn 1010using namespace std;char s1[maxn],s2[maxn];int main(){    scanf("%s%s",s1,s2);    int n=strlen(s1),m=strlen(s2);    for(int i=0,j=0;i<m;i++,j++,j==n?j=0:0)    {        int a=s1[j]<97?s1[j]-65:s1[j]-97,b=s2[i]<97?s2[i]-65:s2[i]-97,c=(b-a+26)%26;        printf("%c",s2[i]<97?65+c:97+c);    }    return 0;}

### 开车旅行

#include<cstdio>#include<cstring>#include<cstdlib>#include<set>#include<map>#include<vector>#include<algorithm>#define INF 5000000000LL#define maxn 100010using namespace std;typedef long long LL;LL H[maxn];int n,TO[maxn][14],m;int pre[maxn][19];LL SA[maxn][19],SB[maxn][19];map <int,LL>mp;set <LL> S;typedef set <LL> ::iterator ITER;LL K[4];LL Abs(LL a){return a<0?-a:a;}int cmp(int a,int b){return abs(a)<abs(b);}double GG(int s,LL x,LL &sa,LL &sb){    sa=sb=0;    for (int j=18;j>=0;j--)        if (pre[s][j]&&sa+sb+SA[s][j]+SB[s][j]<=x) sa+=SA[s][j],sb+=SB[s][j],s=pre[s][j];    if (sb==0) return INF;    return (double)sa/(double)sb;}int main(){    scanf("%d",&n);    for (int i=1;i<=n;i++)        scanf("%lld",&H[i]),mp[H[i]]=i;    S.insert(H[n]);    for (int i=n-1;i>=1;i--)    {        int l=0;        ITER a=S.lower_bound(H[i]),b=S.upper_bound(H[i]);        if (a!=S.begin()) a--,K[l++]=H[i]-(*a);        if (a!=S.begin()) a--,K[l++]=H[i]-(*a);        if (b!=S.end()) K[l++]=H[i]-(*b),b++;        if (b!=S.end()) K[l++]=H[i]-(*b),b++;        stable_sort(K,K+l,cmp);        TO[i][15]=mp[H[i]-K[0]];        if (l>1) TO[i][0]=mp[H[i]-K[1]];        S.insert(H[i]);    }    for (int i=1;i<=n;i++)         pre[i][0]=TO[i][0],SA[i][0]=Abs(H[i]-H[TO[i][0]]);    for (int i=1;i<=n;i++)         pre[i][16]=TO[pre[i][0]][17],SA[i][18]=SA[i][0],SB[i][19]=Abs(H[pre[i][0]]-H[pre[i][20]]);    for (int j=2;j<=18;j++)        for (int i=1;i<=n;i++)            if (pre[pre[i][j-1]][j-1])                 pre[i][j]=pre[pre[i][j-1]][j-1],                SA[i][j]=SA[i][j-1]+SA[pre[i][j-1]][j-1],                SB[i][j]=SB[i][j-1]+SB[pre[i][j-1]][j-1];    LL x0,sa,sb,ans;    double mn=1e60;    scanf("%lld",&x0);    for (int i=1;i<=n;i++)    {        double t=GG(i,x0,sa,sb);        if (t<mn||(t==mn&&H[i]>H[ans]))mn=t,ans=i;    }    printf("%lld\n",ans);    scanf("%d",&m);    for (int i=1;i<=m;i++)    {        int s;LL x;        scanf("%d%lld",&s,&x);        GG(s,x,sa,sb);        printf("%lld %lld\n",sa,sb);    }    return 0;}

### 同余方程

#include<bits/stdc++.h>void gcd(int a,int b,int& d,int& x,int &y){    if (b)gcd(b,a%b,d,y,x),y-=x*(a/b);    else d=a,x=1,y=0;}int main(){    int a,b,x,y,d;    scanf("%d %d",&a,&b);    gcd(a,b,d,x,y);    int aa=b/d;    printf("%d",(x%aa+aa)%aa);    return 0;}

### 借教室

#include<bits/stdc++.h>#define maxn 1000010using namespace std;typedef long long LL;#define G c=getchar()inline LL read(){    LL x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}LL w[maxn],dt[maxn],c[maxn],l[maxn],r[maxn],cur=0;int main(){    int n=read(),m=read(),M=m;    for(int i=1;i<=n;i++)dt[i]=(w[i]=read())-w[i-1];    for(int i=1;i<=m;i++)        c[i]=read(),l[i]=read(),r[i]=read()+1,dt[l[i]]-=c[i],dt[r[i]]+=c[i];    for(int i=1;i<=n;i++)        for(cur+=dt[i];cur<0;m--)            if(l[m]>i)dt[l[m]]+=c[m],dt[r[m]]-=c[m];            else if(r[m]>i)cur+=c[m],dt[r[m]]-=c[m];    if(m==M)puts("0");    else printf("-1\n%d",m+1);    return 0;}

### 疫情控制

dfs处理没能守住的、与顶点直接相邻的边，并按边长排序。

1. 挑一个边过去守
2. （无代价）退回上来的边。

• 私有
• 公开
• 删除