@Scarlet 2017-01-12T12:06:52.000000Z 字数 9897 阅读 1141

# POI 2003

POI 2003 OI 解题报告

## Sequences without Stammers

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

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

## Smugglers (Stage I)

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

## Trinomial (Stage II - day 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)

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

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

Too difficult，大概是A*特技。

## Sums (Stage III - day 1)

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

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

From PoPoQQQ

/*    Author:Scarlet*/#include<bits/stdc++.h>typedef long long LL;#define maxn 1000010using 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

• 私有
• 公开
• 删除