@Scarlet 2017-01-12T12:06:34.000000Z 字数 7637 阅读 1193

# POI 1997

POI 1997 OI 解题报告

## The Number of Symmetrical Choices (Stage I)

f[x][y]为从$x$走到$y$的回文路径的方案数，则

a[x]==a[y]，则f[x][y]=sum(f[i][j])($x→i$有边，$j→y$有边)
a[x]!=a[y]，则f[x][y]=0

From Claris

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 666#define maxm 2333using namespace std;#define AE(u,v) to[Si]=v,nxt[Si]=i1[u],i1[u]=Si++,to[Si]=u,nxt[Si]=i2[v],i2[v]=Si++int i1[maxn],i2[maxn],nxt[maxm],to[maxm],Si;int v[maxn][maxn],f[maxn][maxn];int n,m,st[2][maxn],en[2][maxn],a[maxn];char s[maxn];int F(int x,int y){    if(v[x][y])return f[x][y];    v[x][y]=1;    if(a[x]!=a[y])return 0;    for(int i=i1[x];i+1;i=nxt[i])        for(int j=i2[y];j+1;j=nxt[j])            f[x][y]+=F(to[i],to[j]);    return f[x][y];}int main(){    memset(i1,-1,sizeof(i1));    memset(i2,-1,sizeof(i2));    scanf("%d",&n);m=2;    for(int k=0;k<2;k++)        for(int i=1;i<=n;i++)        {            st[k][i]=m+1;            scanf("%s",s+1);            int l=strlen(s+1);            for(int j=1;j<l;j++)                AE(m+j,m+j+1);            for(int j=1;j<=l;j++)a[m+j]=s[j]-'a'+1;            en[k][i]=m+=l;        }    for(int i=1;i<n;i++)    {        AE(en[0][i],st[0][i+1]);        AE(en[0][i],st[1][i+1]);        AE(en[1][i],st[0][i+1]);        AE(en[1][i],st[1][i+1]);    }    AE(1,st[0][3]);    AE(1,st[1][4]);    AE(en[0][n],2);    AE(en[1][n],2);    for(int i=1;i<=m;i++)    {        v[i][i]=f[i][i]=1;        for(int j=i1[i];j+1;j=nxt[j])        {            v[i][to[j]]=1;            if(a[i]==a[to[j]])f[i][to[j]]=1;        }    }    printf("%d",F(1,2));    return 0;}

## Cheap Travels (Stage I)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 1010using 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[maxn],p[maxn];struct poi{int d,p;}a[maxn];inline bool cmp(const poi &a,const poi &b){return a.d<b.d;}void out(int x){    if(a[x].d==0)return;    out(p[x]);printf("%d ",a[x].d);}int main(){    int m=read(),n=read();    for(int i=1;i<=n;i++)        a[i].d=read(),a[i].p=read();    a[++n].d=m;    sort(a+1,a+1+n,cmp);    memset(f,0x7f7f7f7f,sizeof(f));f[0]=0;    for(int i=1;i<=n;f[i]+=a[i].p*10000+1,i++)        for(int j=0;j<i;j++)            if(a[i].d-a[j].d<=800)                if(f[j]<f[i])f[i]=f[j],p[i]=j;    out(p[n]);puts("");    memset(f,0x7f7f7f7f,sizeof(f));f[0]=0;    for(int i=1;i<=n;f[i]+=a[i].p+10000,i++)        for(int j=0;j<i;j++)            if(a[i].d-a[j].d<=800)                if(f[j]<f[i])f[i]=f[j],p[i]=j;    out(p[n]);puts("");    return 0;}

## XOR Gates (Stage I)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 110#define maxm 3210using 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) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++int idx[maxm],nxt[maxm*2],to[maxm*2],Si,n,m,k;bitset<101>w[maxm],fin;int vis[maxm];void dfs(int x){    vis[x]=1;    for(int i=idx[x];i+1;i=nxt[i])        {            if(!vis[to[i]])dfs(to[i]);            w[x]^=w[to[i]];        }}int f[maxn][2],g[maxn],ans;int dfs(int N,bool top,bool s){    if(N>=n)return s;    if(!top&&f[N][s]+1)return f[N][s];    int ans=0,t=top?g[N]:1;    for(int i=0;i<=t;i++)        ans+=dfs(N+1,top&(i==t),s^(fin[N]&i));    if(!top)f[N][s]=ans;    return ans;}void add(int x){    int a=read();    if(a<0)w[x][-a-1]=w[x][-a-1]^1;    else AE(x,a-1);}int main(){    memset(idx,-1,sizeof(idx));    n=read(),m=read(),k=read()-1;    for(int i=0;i<m;i++)add(i),add(i);    dfs(k);ans=0;fin=w[k];    for(int i=0;i<n;i++)scanf("%1d",&g[i]),ans^=fin[i]&g[i];    memset(f,-1,sizeof(f));    ans-=dfs(0,1,0);    for(int i=0;i<n;i++)scanf("%1d",&g[i]);    memset(f,-1,sizeof(f));    ans+=dfs(0,1,0);    printf("%d\n",ans);    return 0;}

## Airports (Stage II - day 0)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 505using 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 n;struct poi{int i,d;}a[maxn];inline bool cmp(const poi &a,const poi &b){return a.d<b.d;}int main(){    n=read();    for(int i=1;i<=n;i++)        a[i]=(poi){i,read()};    for(int i=n,j;i>=1;i--)        for(sort(a+1,a+1+i,cmp),j=i-1;j>=i-a[i].d;j--)            printf("%d %d\n",a[i].i,a[j].i),a[j].d--;    return 0;}

## Addon (Stage II - day 1)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 20010using 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 a[maxn],x,n,aa;bitset<maxn>f,b;vector<int>ans;int main(){    n=read();    for(int i=1;i<=n;i++)b[read()]=1;    for(int i=1,j;i<=10000;i++)        if(b[i])        {            if(aa=i,!f[i])                for(ans.push_back(i),f[i]=1,j=0;(1<<j)<=10000/i;j++)                    f|=(f<<(i<<j));        }        else        if(f[i])        {            for(printf("%d\n",aa),j=0;j<ans.size();j++)                printf("%d\n",ans[j]);            return 0;        }    return 0;}

## Genotypes (Stage II - day 1)

/*    Author:Scarlet*/#pragma GCC optimize ("O2")#include<bits/stdc++.h>#define maxn 102using namespace std;int f[maxn][maxn],e[maxn][maxn],g[maxn],T,m,n;char S[maxn];inline void dp(const int &i,const int &j,int const &c){    for(int k=i;k<j;k++)        for(int q=f[i][k];q;q^=q&-q)            if(f[k+1][j]&e[c][__builtin_ctz(q&-q)]){f[i][j]|=1<<c;return;}}int main(){    scanf("%d",&m);    for(int i=1;i<=m;i++)        scanf("%s",S),e[S[0]-'A'][S[1]-'A']|=1<<S[2]-'A';    scanf("%d",&T);    for(;T--;)    {        scanf("%s",S+1);int n=strlen(S+1);        memset(f,0,sizeof(f));memset(g,0x7f7f7f,sizeof(g));g[0]=0;        for(int i=1;i<=n;i++)f[i][i]|=1<<S[i]-'A';        for(int L=1;L<n;L++)            for(int i=1;i+L<=n;i++)                for(int c=0;c<26;c++)                    dp(i,i+L,c);        for(int i=1;i<=n;i++)            for(int j=1;j<=i;j++)                if(f[j][i]&(1<<18))g[i]=min(g[i],g[j-1]+1);        if(g[n]<=n)printf("%d\n",g[n]);else puts("NIE");    }    return 0;}

## Monochromatic Triangles (Stage III - day 1)

/*    Author:Scarlet*/#include<bits/stdc++.h>int n,m,ans,i,d[1001];int main(){    scanf("%d%d",&n,&m);    for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),d[x]++,d[y]++;     for(int i=1;i<=n;i++)ans+=(d[i]*(n-1-d[i]));    printf("%d\n",n*(n-1)*(n-2)/6-ans/2);}

## Lecture Halls Reservation (Stage III - day 2)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 30010#define maxm 10010using 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) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++int idx[maxn],nxt[maxm],to[maxm],Si=1,f[maxn],mx;int main(){    int n=read();    for(int i=1,x,y;i<=n;i++)        x=read(),y=read(),AE(y,x),mx=max(mx,y);    for(int i=1;f[i]=f[i-1],i<=mx;i++)        for(int j=idx[i];j;j=nxt[j])            f[i]=max(f[i],f[to[j]]+i-to[j]);    printf("%d",f[mx]);    return 0;}

Next：POI 2003

• 私有
• 公开
• 删除