2017 CCPC杭州题解

2017CCPC杭州题目PDF

Problem A. Super-palindrome

题解：

　　给你一个字符串，每一步可以将一个字符替换为另一个字符，问你最少多少步可以使得，该字符串任意奇数子串为回文串，偶数子串为回文串。

满足上面条件一定是ababab这种形式，所以我们只要找到数量最多的两种字符用n-numa-numb得到ans1,有可能一种字符的数量过多，这时候我们只要把所有字符都变成这种字符就行了。得到n-numa,ans2;

在ans1和ans2中去最小值就是答案了；

参考代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=;

int T,a[maxn];

char s[maxn];

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s",s+);

        int len=strlen(s+),ans=;

        for(int i=;i<=len;++i) a[i]=s[i]-'a'+;

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

        {

            for(int j=;j<=;++j)

            {

                int sum=;

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

                {

                    if((k&)&&a[k]==i) ++sum;

                    if(!(k&)&&a[k]==j) ++sum;

                }

                ans=max(ans,sum);

            }

        }

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

        {

            int sum=;

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

                if(a[k]==i) sum++;

            ans=max(ans,sum);

        }

        printf("%d\n",len-ans);

    }

    return ;

}

Problem B. Master of Phi

　　公式化简；

参考代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod=;

int quick_pow(int a,int b){int ans=;while(b) {if(b&) ans=1LL*a*ans%mod;a=1LL*a*a%mod;b>>=;} return ans;}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int m;

        scanf("%d",&m);

        LL ans=;

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

        {

            int p,q;

            scanf("%d%d",&p,&q);

            ans=1LL*ans*(quick_pow(p,q)+1LL*quick_pow(p,q-)*(p-)%mod*q%mod)%mod;

        }

        printf("%lld\n",ans);

    }

}

Problem C. Hakase and Nano

题解：

　　给你n对石头，每堆a[i]个，一个d,d==1时表示Hakase先手，d==2时表示Nano先手，每次从一堆中拿任意个石头，至少拿一个；但是这是一个不平等博弈，就是Hakase可以连续拿两次，而Nano只能连续拿一次。问你Hakase是否可以取胜。

　　首先如果d==1,那么只有当所有堆石头的数量都为1且数量%3==1的时候Hakase才必败，其他情况都是必胜。

d==2的时候，因为N想赢所以肯定想转换到上述H会输的状态，所以H在n是3的倍数，且有n-1个数为1时会输（这时N只需从不是1的那堆石子里拿掉一些石子使状态变为1 1 1），或者n是3的倍数余1，且n个数为1时会输（此时N只需拿掉一堆石子，H就到了必输态），或者n是3的倍数余1，且n-1个数为1时会输（此时N只需拿掉一堆不是1的石子，H就到了必输态）。

参考代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int T,n,d,x;

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        int cnt=;

        scanf("%d%d",&n,&d);

        for(int i=;i<=n;++i) scanf("%d",&x),cnt+=(x==);

        if(d==)

        {

            if(cnt==n&&n%==) puts("No");

            else puts("Yes");

        }

        else

        {

            if(n%==&&cnt>=n-) puts("No");

            else if(n%==&&cnt==n-) puts("No");

            else puts("Yes");

        }

    }

    return ;

}

Problem D. Master of Random

题解：

　　给你一棵树，每个节点有个权值，现在这个树是随机的，现在随即选择一颗子树，问你这棵子树的节点权值和的期望为多少；

　　我们考虑对于一颗子树上面的点，他到子树的根必定在他到整个树的根的路径上面，然后，我们考虑每次添加一个节点，他要么是子树根节点，要么自己单独型号才能一个子树。

参考代码：

#include<bits/stdc++.h>

using namespace std;

#define mod 998244353

typedef long long ll;

const int maxn=1e5+;

int T,n;

ll num,sum,ans,a[maxn],f[maxn];

ll qpow(ll x,ll y)

{

    ll res=;

    while(y)

    {

        if(y&) res=res*x%mod;

        x=x*x%mod;

        y>>=;

    }

    return res;

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        sum=;ans=;

        num=qpow(n,mod-);

        for(int i=;i<=n;i++) scanf("%lld",a+i);

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

        {

              f[i]=(sum*qpow(i-,mod-)%mod+)%mod;

              sum=(sum+f[i])%mod;

              ans=(ans+a[i]*f[i]%mod)%mod;

        }

        ans=(ans*num)%mod;

        printf("%lld\n",ans);

    }

      return ;

}

Problem E. Master of Subgraph

题解：

　　题目给你一个树图，然后每个节点一个权值a[i],给你一个m,对于x=1~m :问你该树图里面是否有连通子图的值为x,输出x对应取值下的答案(0/1);

　　我们考虑点分治，用bitset维护经过每个点的链的权值和。

参考代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;

const int maxn=3e3+;

const int maxm=1e5+;

bitset<maxm> bit[maxn],ans;

int T,n,m,w[maxn];

vector<int> g[maxn];

int root,mx[maxn],siz[maxn],S;

bool vis[maxn];

void getroot(int u,int fa)

{

    siz[u]=;mx[u]=;

    for(int i=,len=g[u].size();i<len;++i)

    {

        int v=g[u][i];

        if(v==fa || vis[v]) continue;

        getroot(v,u);

        siz[u]+=siz[v];

        mx[u]=max(mx[u],siz[v]);

    }

    mx[u]=max(mx[u],S-mx[u]);

    if(mx[u]<mx[root]) root=u;

}

void calc(int u,int fa)

{

    siz[u]=;bit[u]<<=w[u];

    for(int i=,len=g[u].size();i<len;++i)

    {

        int v=g[u][i];

        if(vis[v]||v==fa) continue;

        bit[v]=bit[u];

        calc(v,u);

        bit[u]|=bit[v];

        siz[u]+=siz[v];

    }

}

void solve(int u)

{

    vis[u]=true;

    bit[u].reset();bit[u].set();

    calc(u,);

    ans|=bit[u];

    for(int i=,len=g[u].size();i<len;++i)

    {

        int v=g[u][i];

        if(vis[v]) continue;

        root=; S=siz[v];

        getroot(v,);

        solve(root);

    }

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        ans.reset();

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;++i) g[i].clear(),vis[i]=;

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

        {

            int u,v;

            scanf("%d%d",&u,&v);

            g[u].push_back(v);

            g[v].push_back(u);

        }

        for(int i=;i<=n;++i) scanf("%d",w+i);

        S=n; root=;mx[]=INF;

        getroot(,);

        solve();

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

            printf("%d",(int)ans[i]);

        puts("");

    }

    return ;

}

Problem J. Master of GCD

题意：

　　给出T组数据（1 <= T <= 10）,每组数据中，有两个数n（1 <= n <= 10^5）和 m (1 <= m <= 10^5)。其中 n 表示有n个由1组成的数， m表示下面给出m组数据，每组数据由 p，q，k 组成。表示区间p 到 q，增大k倍（k 等于2 或者 3）.输出这n个数最终的最大公约数。由于数据比较大，因此需要mod 998244353。
　　差分一下，维护2的次幂和3的次幂；

参考代码：

#include<bits/stdc++.h>

using namespace std;

#define mod 998244353

typedef long long ll;

const int maxn=1e5+;

int T,n,m;

ll x[maxn],y[maxn];

ll qpow(ll x,ll y)

{

    ll res=;

    while(y)

    {

        if(y&) res=res*x%mod;

        x=x*x%mod;

        y>>=;

    }

    return res;

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;++i) x[i]=y[i]=;

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

        {

            int l,r,xx;

            scanf("%d%d%d",&l,&r,&xx);

            if(xx==) x[l]++,x[r+]--;

            else y[l]++,y[r+]--;

        }

        for(int i=;i<=n;++i) x[i]+=x[i-],y[i]+=y[i-];

        ll ans1=x[],ans2=y[];

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

            ans1=min(ans1,x[i]),ans2=min(ans2,y[i]);

        ll ans=qpow(,ans1)*qpow(,ans2)%mod;

        printf("%lld\n",ans);

    }

    return ;

}

Problem K. Master of Sequence

题解：

参考代码：

#include<bits/stdc++.h>

#define mod 998244353

const int maxn=1e6+;

using namespace std;

typedef long long ll;

struct node{

    ll a,b;

} p[maxn];

int T,n,m,num[][],cnt[];

ll s;

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        s=;

        memset(num,,sizeof num);

        memset(cnt,,sizeof cnt);

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;++i) scanf("%d",&p[i].a);

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

        {

            scanf("%d",&p[i].b);

            s+=(p[i].b/p[i].a);

            cnt[p[i].a]++;

            num[p[i].a][p[i].b%p[i].a]++;

        }

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

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

                num[i][j]+=num[i][j+];

        while(m--)

        {

            int ty,y,z;

            scanf("%d",&ty);

            if(ty==)

            {

                scanf("%d%d",&y,&z);

                for(int i=p[y].b%p[y].a;i>=;--i) num[p[y].a][i]--;

                s-=(p[y].b/p[y].a);

                cnt[p[y].a]--;

                p[y].a=z;

                s+=(p[y].b/p[y].a);

                cnt[z]++;

                for(int i=p[y].b%z;i>=;--i) num[z][i]++;

            }

            else if(ty==)

            {

                scanf("%d%d",&y,&z);

                for(int i=p[y].b%p[y].a;i>=;--i) num[p[y].a][i]--;

                s-=(p[y].b/p[y].a);

                p[y].b=z;

                s+=(p[y].b/p[y].a);

                for(int i=p[y].b%p[y].a;i>=;--i) num[p[y].a][i]++;

            }

            else

            {

                ll k;

                scanf("%lld",&k);

                ll l=,r=1e13,ans;

                while(l<=r)

                {

                    ll mid=l+r>>;

                    ll sum=-s;

                    for(int i=;i<=;++i) sum+=mid/i*cnt[i]-num[i][mid%i+];

                    if(sum>=k) r=mid-,ans=mid;

                    else l=mid+;

                }

                printf("%lld\n",ans);

            }

        }

    }

    return ;

}

巴特西

2017 CCPC杭州题解

最新文章

热门文章

巴特西

2017 CCPC杭州 题解

最新文章

热门文章

2017 CCPC杭州题解