POI 2003

POI 2003 OI 解题报告

Sequences without Stammers

题意：用最少的字符种数构造长度为$n$的字符串使得没有连续重复子串

不是很懂，似乎>=5的情况下可以用三种字符无限构造。

贴一个poi的std：

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
using namespace std;
int i,l,n;
bool t[32769],c,d;
int main()
{
    scanf("%d",&n);
    for(l=1,c=0;l<=32768;t[l]=c,l*=2,c=!c)
    if (n==1) puts("1\na");
    if (n==2) puts("2d\nab");
    if (n==3) puts("2\baba");
    if (n>=4)
    {
        puts("3");
        for(c=0,d=1,i=1;i<=n;i++)
        {
            printf("%c",(c==d?'a':(c?'b':'c')));
            l=1+((i+1)^i);
            if(l>=65536)l>>=16;
            c=d;d^=t[l];    
        }
        puts("");
    }
    return 0;
}

Chocolate (Stage I)

题意：一块$n*m$的巧克力，横切第$i$刀需要$x_i$的价格，竖切第$j$刀需要$y_i$的价格，求最小价值。

贪心，假设价值从大到小切是最优的。模拟即可。

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

Numerals of Przesmyks (Stage I) (0/100)

Printed-Circuit Boards (Stage I) (0/100)

Smugglers (Stage I)

题意：物品1通过一系列特技变化变成物品i，再变回物品1，试最小化特价代价+v[i]/2

嘛，一看就是一道最短路。是找一个经过1和v[i]的有向最小环，事实上求出正反边的最短路取个min就好了。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 5010
#define maxm 200010
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,m;
#define AE(u,v,w,idx) E[Si]=(Ed){u,v,w},nxt[Si]=idx[u],idx[u]=Si++
struct Ed{int u,v,w;}E[maxm];
int a[maxn],i1[maxn],i2[maxn],nxt[maxm],Si=1,q[maxm],d[maxn],e[maxn],v[maxn],ans;
queue<int>Q;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    m=read();
    for(int u,v,w;m--;)u=read(),v=read(),w=read(),AE(u,v,w,i1),AE(v,u,w,i2);
    memset(d,63,sizeof(d));Q.push(1);d[1]=0;v[1]=1;
    for(;!Q.empty();)
    {
        int u=Q.front();Q.pop();v[u]=0;
        for(int i=i1[u];i;i=nxt[i])
            if(d[u]+E[i].w<d[E[i].v])
            {
                d[E[i].v]=d[u]+E[i].w;
                if(!v[E[i].v])
                    v[E[i].v]=1,Q.push(E[i].v);
            }
    }
    memset(e,63,sizeof(e));Q.push(1);e[1]=0;v[1]=1;
    for(;!Q.empty();)
    {
        int u=Q.front();Q.pop();v[u]=0;
        for(int i=i2[u];i;i=nxt[i])
            if(e[u]+E[i].w<e[E[i].v])
            {
                e[E[i].v]=e[u]+E[i].w;
                if(!v[E[i].v])
                    v[E[i].v]=1,Q.push(E[i].v);
            }
    }
    ans=1e9;
    for(int i=1;i<=n;i++)
        ans=min(ans,d[i]+e[i]+a[i]/2);
    printf("%d\n",ans);
    return 0;
}

Mastermind II (Stage II - day 0) (0/100)

Motorways (Stage II - day 1) (0/100)

Trinomial (Stage II - day 1)

题意：计算$(x^2+x+1)^n$的$i$次项系数对$3$取模

在lbn187的帮助下拿到了伪std。
可还是不知道是怎么回事，好神啊，为什么求$C(2n,m)*(m\% 2+1)$就行了呢？
不是很懂啊

/*
    Author:Scarlet
*/
#include<stdio.h>
int f[3]={1,1,2};long long n,m,t;
int C(int n,int m){return m>n?0:f[n]*f[m]*f[n-m]%3;}
int L(long long n,long long m){return m?C(n%3,m%3)*L(n/3,m/3)%3:1;}
int main()
{
    for(scanf("%lld",&t);t--;)
    {
        scanf("%lld%lld",&n,&m);
        printf("%d\n",L(2*n,m)*(m%2+1)%3);
    }
}

Tiles (Stage II - day 2)

题意：一个字符串$S$，$k$和$l$同时是它的循环节$S$，求$S$的最多不同字符数。

当$n<=k+l-gcd(k,l)$时，答案是$k+l-n$
否则为$gcd(k,l)$

证明？分类讨论，找出最小循环节即可。

为了能顺理成章的出题提高自己的姿势水平还是简单写一下吧。

证明：
假设这是一个从$0$开始的无限长度的字符串$S$。

因为$k,l$都是$S$循环节，所以$S_0=S_k=S_l=S_{kx+ly}(x,y\in \mathbb{Z},kx+ly>=0)$

也就是说，$S$事实上是一个以$d=gcd(k,l)$为最小循环节的字符串，这个最小循环节内的字符可以随意钦点，所以答案是$d$。
但上述情况是建立在$S$足够长的前提下的。

好比一辆电梯每次只能移动$k$或$l$层，这个电梯最终能到达的楼层与总层数直接相关。好在我们有个定理：当$n\geq k+l-d$时，电梯可以在任意$id(i\in \mathbb{N})$层停止。

那么原题也是同理，当$n\geq k+l-d$，最小循环节就是$d$，也就是答案。否则通过手算得到答案为$k+l-n$

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 501
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;
}
const int MAXN = 510;
struct HugeInt
{
    int len, s[MAXN];
    HugeInt ()
    {
        memset(s, 0, sizeof(s));
        len = 1;
    }
    HugeInt (int num) { *this = num; }
    HugeInt (const char *num) { *this = num; }
    HugeInt operator = (const int num)
    {
        char s[MAXN];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }
    HugeInt operator = (const char *num)
    {
        if(len==1&&num[0]==0)return *this;
        for(int i = 0; num[i] == '0'; num++) ;  //去前导0
        len = strlen(num);
        for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
        return *this;
    }
    HugeInt operator + (const HugeInt &b) const //+
    {
        HugeInt c;
        c.len = 0;
        for(int i = 0, g = 0; g || i < max(len, b.len); i++)
        {
            int x = g;
            if(i < len) x += s[i];
            if(i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    HugeInt operator += (const HugeInt &b)
    {
        *this = *this + b;
        return *this;
    }
    void clean()
    {
        while(len > 1 && !s[len-1]) len--;
    }
    HugeInt operator * (const HugeInt &b) //*
    {
        HugeInt c;
        c.len = len + b.len;
        for(int i = 0; i < len; i++)
        {
            for(int j = 0; j < b.len; j++)
            {
                c.s[i+j] += s[i] * b.s[j];
            }
        }
        for(int i = 0; i < c.len; i++)
        {
            c.s[i+1] += c.s[i]/10;
            c.s[i] %= 10;
        }
        c.clean();
        return c;
    }
    HugeInt operator *= (const HugeInt &b)
    {
        *this = *this * b;
        return *this;
    }
    HugeInt operator - (const HugeInt &b)
    {
        HugeInt c;
        c.len = 0;
        for(int i = 0, g = 0; i < len; i++)
        {
            int x = s[i] - g;
            if(i < b.len) x -= b.s[i];
            if(x >= 0) g = 0;
            else
            {
                g = 1;
                x += 10;
            }
            c.s[c.len++] = x;
        }
        c.clean();
        return c;
    }
    HugeInt operator -= (const HugeInt &b)
    {
        *this = *this - b;
        return *this;
    }
    HugeInt operator / (const HugeInt &b)
    {
        HugeInt c, f = 0;
        for(int i = len-1; i >= 0; i--)
        {
            f = f*10;
            f.s[0] = s[i];
            while(f >= b)
            {
                f -= b;
                c.s[i]++;
            }
        }
        c.len = len;
        c.clean();
        return c;
    }
    HugeInt operator /= (const HugeInt &b)
    {
        *this  = *this / b;
        return *this;
    }
    HugeInt operator % (const HugeInt &b)
    {
        HugeInt r = *this / b;
        r = *this - r*b;
        return r;
    }
    HugeInt operator %= (const HugeInt &b)
    {
        *this = *this % b;
        return *this;
    }
    bool operator < (const HugeInt &b)
    {
        if(len != b.len) return len < b.len;
        for(int i = len-1; i >= 0; i--)
        {
            if(s[i] != b.s[i]) return s[i] < b.s[i];
        }
        return false;
    }
    bool operator > (const HugeInt &b)
    {
        if(len != b.len) return len > b.len;
        for(int i = len-1; i >= 0; i--)
        {
            if(s[i] != b.s[i]) return s[i] > b.s[i];
        }
        return false;
    }
    bool operator == (const HugeInt &b)
    {
        return !(*this > b) && !(*this < b);
    }
    bool operator != (const HugeInt &b)
    {
        return !(*this == b);
    }
    bool operator <= (const HugeInt &b)
    {
        return *this < b || *this == b;
    }
    bool operator >= (const HugeInt &b)
    {
        return *this > b || *this == b;
    }
    string str() const
    {
        string res = "";
        for(int i = 0; i < len; i++) res = char(s[i]+'0') + res;
        return res;
    }
};
istream& operator >> (istream &in, HugeInt &x)
{
    string s;
    in >> s;
    x = s.c_str();
    return in;
}
ostream& operator << (ostream &out, const HugeInt &x)
{
    out << x.str();
    return out;
}
HugeInt Pow(HugeInt x,int y)
{
    HugeInt r=1;
    for(;y;y>>=1,x=x*x)if(y&1)r=r*x;
    return r;
}
HugeInt factorial(int x)
{
    HugeInt a=1;
    for(int i=2;i<=x;i++)
        a*=i;
    return a;
}
HugeInt k,l,d,n,g;
HugeInt gcd(HugeInt a,HugeInt b)
{
    return (b.len==1&&b.s[0]==0)?a:gcd(b,a%b);
}
int main()
{
    cin>>n>>k>>l;d=gcd(k,l);
    g=k+l-gcd(k,l);
    if(n<=g)cout<<k+l-n<<endl;
    else cout<<d<<endl;
    return 0;
}

板子贴贴没希望了。

Connections (Stage II - day 2)

题意：求图中第$k$短路

Too difficult，大概是A*特技。

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

Sums (Stage III - day 1)

题意：给定$n$个数，每次询问一个数能否表示成这$n$个数之和，一数可以多次使用

这是一个（我现在才会做的）经典问题。$mn$表示$n$个数中最小的数，那么只要考虑$\%mn$意义下每个被表示数中最小的数，用f[i]表示。
是个环状背包，所以需要在环上跑两遍。
差点被main卡常。QAQ

/*
    Author:Scarlet
*/
#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
#define maxn 50010
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 m,i,w,j,st,p,q,n,f[maxn],a[maxn/10],mn=maxn;
bool vis[maxn],cnt;
int main()
{
    n=read();
    for(i=1;i<=n;i++)a[i]=read(),mn=min(mn,a[i]);
    for(i=1;i<mn;i++)f[i]=2000000000;
    for(i=1,w,j;i<=n;i++)
        for(w=a[i]%mn,j=1;j<=2;j++,cnt^=1)
            for(st=0;vis[st]==cnt&&st<mn;st++)
                for(p=st,q=st+w>=mn?st+w-mn:st+w;vis[p]==cnt;vis[p]=cnt^1,p=q,q=q+w>=mn?q+w-mn:q+w)
                    if(f[p]+a[i]<f[q])f[q]=f[p]+a[i];
    m=read();
    for(;m--;)
    {
        i=read();
        if(i>=f[i%mn])puts("TAK");
        else puts("NIE");
    }
    return 0;
}

Monkeys (Stage III - day 2)

题意：有$n$只猴子，第一只尾巴抓住树枝，每一只猴子可能双手抓住其他猴子的尾巴，即二叉树结构，现在每秒都有猴子松开某只手，求各个猴子落地时间

看到题目第一眼认识到删边不可做，加边可做，于是就把询问倒过来，看猴子什么时候上树。

因为猴子是“一块一块”上去的，所以应该是使用并查集，当加入到1所在集合中就更新整组答案。这里采用dfs搜索联通块。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 400010
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 fa[maxn],a[maxn],n,m;
int gf(int x){return x==fa[x]?x:fa[x]=gf(fa[x]);}
#define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++
int idx[maxn],nxt[maxn],to[maxn],Si=1;
void dfs(int x,int fa,int z)
{
    a[x]=z;
    for(int i=idx[x];i;i=nxt[i])if(to[i]!=fa)dfs(to[i],x,z);
}
void uni(int x,int y,int z){
    int p=gf(x),q=gf(y);
    if(y<0||p==q)return;
    if(p==gf(1))dfs(y,x,z);else if(q==gf(1))dfs(x,y,z);else AE(x,y),AE(y,x);
    fa[p]=q;
}
int c[maxn][2],q[maxn][2],b[maxn][2];
int main()
{
    n=read(),m=read();a[1]=-1;
    for(int i=1;i<=n;i++)c[i][0]=read(),c[i][1]=read(),fa[i]=i;
    for(int i=1;i<=m;i++)q[i][0]=read(),q[i][1]=read()-1,b[q[i][0]][q[i][1]]=1;
    for(int i=1;i<=n;i++)for(int j=0;j<2;j++)if(!b[i][j])uni(i,c[i][j],-1);
    for(int i=m;i>=1;i--)uni(q[i][0],c[q[i][0]][q[i][1]],i-1);
    for(int i=1;i<=n;i++)printf("%d\n",a[i]);
    return 0;
}

Shuffle (Stage III - day 2)

题意：给定$k$和置换$b$，求一个置换$a$使得$a^k=b$

要做这个题首先我们需要知道$a^k$是什么
想象一个长度为$L$的循环，如果我们将这个循环求$k$次方，我们将会得到$Gcd(L,k)$个长度为$\frac{L}{Gcd(L,k)}$的循环
那么现在我们将$b$分解成循环，假如现在我们得到了一个长度为$L′$的循环，那么由之前的结论可以得到$L′=\frac{L}{Gcd(L,k)}$
容易证明存在一个最小的$L$满足这个$L$是所有合法的$L$的约数，且这个$L$满足对于$L′$的任意一个质因子$p$，$p$在$L$中的次数等于$p$在$L′$中的次数加上$p$在$k$中的次数
于是我们找到这个最小的$L$，将$\frac{L}{Gcd(L,k)}$个长度为$L′$的循环合并成一个循环即可

From PoPoQQQ

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
typedef long long LL;
#define maxn 1000010
using namespace std;
int a[maxn],v[maxn],n,top,k,ans[maxn];
vector<int>*st[maxn];
#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;
}
void getC(int x,vector<int> *vec)
{
    for(;;)
    {
        if(v[x])return;
        vec->push_back(x);
        v[x]=1;x=a[x];
    }
}
int cmp(vector<int>*v1,vector<int>*v2){return v1->size()<v2->size();}
int L(int x)
{
    int k=::k,re=1;
    for(int i=2;i*i<=x;i++)
        if(x%i==0)
        {
            while(x%i==0)x/=i,re*=i;
            while(k%i==0)k/=i,re*=i;    
        }
    if(x-1)
        for(re*=x;k%x==0;)
            k/=x,re*=x;
    return re;
}
int main()
{
    n=read();k=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=n;i++)
        if(!v[i])
            getC(i,st[++top]=new vector<int>);
    sort(st+1,st+top+1,cmp);
    for(int i=1;i<=top;)
    {
        static int a[maxn];
        int l=L(st[i]->size()),tmp=__gcd(l,k);
        for(int j=0;j<tmp;j++)
            for(int k=0;k<(signed)st[i+j]->size();k++)
                a[(j+(long long)k*::k)%l]=(*st[i+j])[k];
        for(int j=0;j<l;j++)
            ans[a[j]]=a[(j+1)%l];
        i+=tmp;
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
}

Next POI 2005