OI队内测试——石门一

时间：2023-02-15 19:32:29

T1:

　　题目大意：

　　　　　　给你一个立方体，每个面上有些数字，给你一个数字K，你可以玩K轮游戏，

　　　　　　每轮你会将每个面上的数均分为4份，分给相邻的面，求K轮游戏后，上面的数字是

　　　　　　依次给你前、后、上、下、左、右的起始数字大小！

　　题解：因为轮数最大只有45，所以直接暴力模拟即可，但是可能是数据水，在通分的时候不会爆炸，也可能是我太垃圾不会算最坏情况！

　　　　　总之非高精度可以A

T2:

　　题目大意：　

　　　　给你一串由小写字母组成的字符串，希望你把它划分成一些小段，使得每一小段字符串
　　　　中的字母都不相同，并且希望分的段数尽量少。

　　　　字符串"nnsmpmn"，最少分成 3 小段："n","nsmp","mn"。 排序后输出：mn n nsmp

　　　　可能有多组解，求最小字典序的答案并输出

　　题解：DP，设F[i]表示到第i段截至的struct 存下段数，每段的字符组成即可！

T3：

　　题目大意：

　　　　你和朋友 Shary 玩一个游戏：在一个无环的、无向的图中，每个节点可以放一些糖果。

　　　　每次 Shary 可以从糖果数不少于 2 的节点上拿 2 个糖果，吃掉 1 个，并把另一个糖果放到相 邻的某个节点去。

　　　　如果在某个时候，目标节点 T 上有了糖果，游戏结束，Shary 赢。

　　　　如果你设计的初始状态，无论如何 Shary 都赢不了，则 Shary 输。 给定一个图，你能赢的方案中可以放的最多糖果数是多少？如果答案数超过 　　　　2*10^9， 只要输出-1 即可

　　题解：贪心即可，考虑它一定是一棵树，于是以这个节点T为根，先考虑一条链，我们可以证明在深度最大的放2*size+1个，其余点不放是最优的

　　　　　因为链与树无本质上的区别，所以重复上述操作即可！

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cstdio>

#define ll long long

using namespace std;

ll read()

{

    ll x=,f=; char ch;

    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;

    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');

    return x*f;

}

ll gcd(ll a,ll b){if (!b) return a; return gcd(b,a%b);

}

struct point{

    ll x,y;

    friend point operator / (point a,ll x){

        if ((a.x%x)==) {a.x/=x; return a;}

        else{

            a.y*=x;

            ll tmp=gcd(a.x,a.y);

            a.x/=tmp; a.y/=tmp; return a;

        }

    }

    friend point operator + (point a,point b){

        if (a.x==) return b;

        if (b.x==) return a;

        ll tmp=gcd(b.y,a.y); tmp=a.y/tmp*b.y;

        a.x*=(tmp/a.y); b.x*=(tmp/b.y); a.y=b.y=tmp;

        point c; c.x=a.x+b.x; c.y=;

        return (c/tmp);

    }

}a[],b[];

int main()

{

    freopen("cube.in","r",stdin);

    freopen("cube.out","w",stdout);

    point x,y;

    x.x=; x.y=;

    y.x=; y.y=;

    for (int i=; i<=; i++) a[i].x=read(),a[i].y=;

    int k=read();

    //if (k==0) {cout<<a[3].x<<endl; return;}

    for (int i=; i<=k; i++)

    {

        b[]=b[]=(a[]+a[]+a[]+a[])/;

        b[]=b[]=(a[]+a[]+a[]+a[])/;

        b[]=b[]=(a[]+a[]+a[]+a[])/;

        for (int j=; j<=; j++) a[j]=b[j];

    }

    if (a[].x==) cout<<<<endl;

    else if (a[].x%a[].y==) cout<<a[].x/a[].y<<endl;

    else cout<<a[].x<<"/"<<a[].y<<endl;

    return ;

}

/*

0 0 4 0 0 0

2

0 0 4 0 0 0

3

1 2 3 4 5 6

45

*/

T1

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cstdio>

#define N 55

using namespace std;

struct Str{int x; char s[N];};

struct P{int cnt; Str s[N];}F[N];

bool vis[N];

int n;

char s[N];

bool operator <(Str a,Str b)

{

    for (int i=; i<=min(a.x,b.x); i++)

    {

        if (a.s[i]==b.s[i]) continue;

        if (a.s[i]<b.s[i]) return ; else return ;

    }

    return a.x<b.x?:;

}

bool operator <(P a, P b){

    if (a.cnt<b.cnt) return ;

    if (a.cnt>b.cnt) return ;

    for (int i=; i<=a.cnt; i++)

    {

        if (a.s[i]<b.s[i]) return ;

        if (b.s[i]<a.s[i]) return ;

    }

}

int read()

{

    int x=,f=; char ch;

    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;

    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');

    return x*f;

}

int main()

{

    freopen("string.in","r",stdin);

    freopen("string.out","w",stdout);

    int T=read();

    while (T--)

    {

        scanf("%s",s+); n=strlen(s+);

        for (int i=; i<=n; i++) F[i].cnt=n+;

        for (int i=; i<=n; i++)

        {

            memset(vis,,sizeof(vis));

            for (int j=i-; j>=; j--)

            {

                if (vis[s[j+]-'a']) break; vis[s[j+]-'a']=;

                P X; X=F[j]; X.cnt++;

                for (int k=j+; k<=i; k++) X.s[X.cnt].x++,X.s[X.cnt].s[k-j]=s[k];

                sort(X.s+,X.s++X.cnt);

                if (X<F[i]) F[i]=X;

            }

        }

    //    cout<<" "<<F[n].cnt<<" "<<F[n].s[]endl;

        for (int i=; i<=F[n].cnt; i++)

        {

            for (int j=; j<=F[n].s[i].x; j++)

            {

                cout<<F[n].s[i].s[j];

            }

            cout<<" ";

        }

        cout<<endl;

    }

    return ;

}

/*

2

facetiously

aaaaa

2

aba

babb

*/

T2

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cstdio>

#define inf 2e9

#define ll long long

#define N 100

using namespace std;

char ch[N];

int pre[N*N],now[N],v[N*N],tot;

int size[N],hson[N];

bool vis[N];

int n;

ll ans;

int read()

{

    int x=,f=; char ch;

    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;

    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');

    return x*f;

}

void ins(int a,int b){++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b;

}

void dfs(int x,int fa)

{

    vis[x]=; size[x]=;

    for (int p=now[x]; p; p=pre[p])

    {

        int son=v[p]; if (son==fa) continue;

        dfs(son,x); size[x]=max(size[x],size[son]+);

        if (size[son]>size[hson[x]] || hson[x]==) hson[x]=son;

    }

}

void get(int x,int fa,ll sum)

{

    //cout<<" "<<x<<" "<<fa<<" "<<sum<<endl;

    if (ans==- || sum==-) {ans=-; return ;}

    if (!hson[x]) {ans+=sum; ans=ans>inf?-:ans; return;}

    for (int p=now[x]; p; p=pre[p])

    {

        int son=v[p]; if (son==fa) continue;

        if (son==hson[x]) get(son,x,sum*+>inf?-:sum*+);

        else get(son,x,);

    }

}

int main()

{

    freopen("candy.in","r",stdin);

    freopen("candy.out","w",stdout);

    int T=read();

    while (T--)

    {

        tot=; memset(now,,sizeof(now));

        n=read(); int s=read(); s++;

        for (int i=; i<=n; i++)

        {

            scanf("%s",ch+); for (int j=; j<=n; j++) if (ch[j]=='Y') ins(i,j);

        }

        memset(vis,,sizeof(vis));

        memset(hson,,sizeof(hson));

        dfs(s,); bool bo=true; for (int i=; i<=n; i++) if (!vis[i]) bo=false;

        if (!bo) {cout<<-<<endl; continue;}

        ans=; get(s,,); printf("%lld\n",ans);

    }

    return ;

}

/*

3

3 2

NYN

YNY

NYN

4 1

NYYY

YNNN

YNNN

YNNN

7 0

NYNNNYN

YNYNYNN

NYNYNNN

NNYNNNN

NYNNNNN

YNNNNNY

NNNNNYN

*/

T3

相关文章