POI 1997

POI 1997 OI 解题报告

The Number of Symmetrical Choices (Stage I)

题意：每次选择a[i]或者b[i]的单词拼接，求成为回文串的方案数

新建源汇$S,T$，根据题意可以建出一个DAG
设f[x][y]为从$x$走到$y$的回文路径的方案数，则
边界条件：f[x][x]=1
对于一条边$x→y$，若a[x]==a[y]，则f[x][y]=1
转移方程为：
若a[x]==a[y]，则f[x][y]=sum(f[i][j])($x→i$有边，$j→y$有边)
若a[x]!=a[y]，则f[x][y]=0
最终答案即为f[S][T]，时间复杂度$O(L^2)$。

From Claris

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 666
#define maxm 2333
using 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;
}

Jumps (Stage I) (0/100)

Cheap Travels (Stage I)

题意：给定若干酒店的坐标和价格，每走$800km$就必须开♂房♂过♂一♂晚，求最少休息时间和最少价格

似乎是普及组DP ，f[i]表示在第$i$个酒店过♂夜的答案，单调队列 $n^2$转移即可。
可以用个双关键字dp技巧：一个数位扩大后加上另一个数位，详见代码

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 1010
using 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)

题意：给定若干个引脚和异或门的连接情况，求给定区间内有多少能使异或门输出1的情况。

因为是亦或，所以最终答案一定是若干引脚的亦或值。
因为是个DAG，所以可以用dfs求出最终结果是有哪些引脚亦或所得。这里是$O(\frac{(n+m)×n}{32})$的，用手写平衡树启发式合并不知道会不会快。
然后题目就变成，在一定区间内，若干位亦或值为$1$的数有多少个。
题目中前后给出区间范围小于$100000$，但是为了出题坑害青少年锻炼dp技巧，就写了个数位dp。
因为给的是闭区间，所以还要验证一下第一个数的合法性。这里是$O(n)$的

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 110
#define maxm 3210
using 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)

题意：给定无向图的每个点度数，构造一个没有重边、自环的图。

清新小构造。考虑每次找到最大度数的点$i$，直接将他连向剩余最大的deg[i]个。可以看出这样的构造是正确的。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 505
using 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)

题意：在给定集$S$合内选出一个数$x$和一个子集$s$，并使得$S$中小于等于$x$的所有数都能有$s$中数的和表示，能用$s$中的数之和表示且不大于$x$的数都在$S$中。最大化$x$并最小化$|s|$。

枚举了大半天题意，你妈嗨.jpg。
考虑模拟：最小的数字是一定要加入的。然后对加入的数字做一波完全背包，再加入下一个数，直到存在一个能用已知数表示但不在集合$S$的数。
看代码吧= =
加了bitset特技加速完全背包。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 20010
using 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)

题意：给定一些字符生长姿势（一个变两个），每次询问给定字符串最少能由多少“S”生长成。

暴力$O(26^2*n^3)$在main上被卡了TAT。

只要让f[i][j][c]表示i-j能否变成c，大家就都会打暴力了。
然后发现main上过不去。
学习lbn位运算加速技巧，见Code

/*
    Author:Scarlet
*/
#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
#define maxn 102
using 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;
}

Petrol (Stage II - day 2) (0/100)

Recursive Ant (Stage II - day 2) (0/100)

Credibility of Witnesses (Stage III - day 0) (0/100)

Canoes (Stage III - day 1) (0/100)

The Number of N-k-special Sets (Stage III - day 1) (0/100)

Monochromatic Triangles (Stage III - day 1)

题意：$n$个点的完全图中给定某些红色边，其余全为蓝色，求同色三角形个数。

同色三角形很难统计，但是异色三角形统计较简单。考虑到每个异色三角形必有两个点连接异色边，就能统计了。

/*
    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);
}

Ali Baba (Stage III - day 2)

像是爆搜题

Lecture Halls Reservation (Stage III - day 2)

题意：若干讲座从某天下午持续到另一天上午（即讲座结束后可以当天另起一个讲座），但学校只有一个讲座，问最多能有几天在开讲座。

傻鸡DP，f[i]表示前$i$天的答案，显然可以从前一天f[i-1]转移过来，或是从某个以$i$为结尾的讲座前转移过来。XJ8DP即可。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 30010
#define maxm 10010
using 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