您的位置: 首页  >  IT文章  >  2017CCPC杭州(ABCDJ)

2017CCPC杭州(ABCDJ)

分类: IT文章 • 2025-02-04 12:20:01

所有的题目在这里<---

待补...

Problem A. HDU6264:Super-palindrome

题意：

　　题目定义了一个超级回文串，这个串满足：它的任一奇数长度的串都是回文串。

　　现在给你一个字符串，问你把它变成超级回文串需要多少次操作。每次操作可以把一个字符变成其他任一字符。

题解：

　　显然，一个串只有符合　整个串奇数位字符都相同，偶数位字符都相同，奇数位偶数位字符不一定要相同(包含了字符全相同的情况)时满足超级回文。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100+10;
const int INF = 1e9+10;
const ll mod = 998244353;
int main(){
    int T;
    scanf("%d",&T);
    for (int t = 1; t <= T; ++t) {
        string s;
        cin >> s;
        int a1[300]={0},a2[300]={0};
        int l = s.length(),num1=0,num2=0;
        for (int i = 0; i < l; ++i) {
            if (i%2) num2 = max(num2,++a2[s[i]]);
            else num1 = max(num1,++a1[s[i]]);
        }
        printf("%d
",(l/2-num1)+(l-l/2-num2));
    }
    return 0;
}
View Code

Problem B.HDU6265:Master of Phi

题意：

　　求 2017CCPC杭州(ABCDJ)

题解：

2017CCPC杭州(ABCDJ)

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000+10;
const int INF = 1e9+10;
const ll mod = 998244353;
ll qp(ll a, ll b){
    ll ans = 1;
    while (b) {
        if (b&1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    int T,n;
    scanf("%d",&T);
    while (T--) {
        ll ans = 1,p,q;
        scanf("%d",&n);
        for (int i = 0; i < n; i++){
            scanf("%lld%lld",&p,&q);
            ans=(ans*(qp(p,q)+((p-1)*q%mod)*qp(p,q-1)%mod))%mod;
        }
        printf("%lld
",ans);
    }
    return 0;
}
View Code

 

Problem C.HDU6266:Hakase and Nano

题意：

　　有n堆石子，每次可以选择任意一堆从中取至少一个石子，谁最后取完谁赢。

　　Hakase取两次，Nano取一次，两个人轮流取。问 Hakase是否能赢。

题解：

　　一堆石子如果只有一个，那么一次就取走了一堆，堆数减少；否则这一堆可以有剩余，堆数可以不变。

　　当 Hakase先取石子时，只有在每堆石子数量都为1且堆数是3的倍数时 Hakase会输，其余情况都会赢。

　　当 Nano先取石子时，Nano拿了第一次之后，就相当于成了Hakase先手。所以要使Hakase输需要使Nano拿了第一次之后每堆石子数量都为1且剩下的堆数是三的倍数，否则Hakase赢。这时有3种情况：

　　1.每堆石子都为1，且　堆数-1　是3的倍数。

　　2.只有一堆石子数量不为1，Nano将这堆石子全拿走，剩下 n-1堆石子数量全为1，且 n-1 是3的倍数。

　　3.只有一堆石子数量不为1，Nano将这堆石子剩一个，剩下 n 堆石子数量全为1，且 n 是3的倍数。

　　只有以上4种情况输出No，否则都是Yes。判断一下就行了。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100+10;
const int INF = 1e9+10;
const ll mod = 998244353;
int main(){
    int T,n,d,x;
    scanf("%d",&T);
    while (T--){
        int num = 0;
        scanf("%d%d",&n,&d);
        for (int i = 0; i < n; ++i) {
            scanf("%d",&x);
            if (x == 1) num++;
        }
        bool fg = 1;
        if (n == num) {
            num %= 3;
            if (d == 1 && !num) fg = 0;
            else if (d == 2 && num == 1) fg = 0;
        } else if (n == num+1) {
            if (d == 2&&((n%3)==0||(num%3)==0)) fg = 0;
        }
        printf("%s
",fg?"Yes":"No");
    }
    return 0;
}
View Code

Problem D. HDU6267Master of Random

题意：

　　之前没看到样例二的解释，然后搞了很久才弄懂题目意思...

　　有一颗树节点由0~n-1编号，0为根节点，其余点i的父节点随机在(0,i-1)中选一个，问所有情况下所有子树的和除以子树个数后的答案。

　　答案可能很大需要mod 998244353。

题解：

　　看懂题意之后就很好做了。

　　我们可以先把由1~4个节点组成的符合条件的树先画出来：

　　2017CCPC杭州(ABCDJ)

　　显然我们能发现，当节点数量为n时，节点0~n-1分别被计算了：

　　0 : (n-1)!
　　1 : (n-1)! + (n-1)!/1　
       2 : (n-1)! + (n-1)!/1 +(n-1)!/2
　　......
　　n-1 : (n-1)! + (n-1)!/1 +(n-1)!/2+...+(n-1)!/(n-1)

　　那么我们能得到所有的子树和和为(n-1)! * a[0] + ((n-1)! + (n-1)!/1) * a[1] + ... + ( (n-1)! + (n-1)!/1 +(n-1)!/2+...+(n-1)!/(n-1) ) * a[n-1]

　　子树个数为 (n-1)! * n  (树的排列方式数 * 节点数)
　　因为有除法取摸，所以要用到逆元　a^(mod-2)
 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000+10;
const int INF = 1e9+10;
const ll mod = 998244353;
ll pq(ll a, ll b){
    ll ans = 1;
    while (b) {
        if (b&1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
ll ive(ll x) {
    return pq(x,mod-2);
}
int main() {
    int T,n;
    scanf("%d",&T);
    while (T--) {
        ll fm = 1, x;
        scanf("%d%lld",&n,&x);
        for (ll i = 1; i < n; i++){
            fm = (fm*i)%mod;
        }
        ll num = fm, ans = (fm * x) % mod;
        for (int i = 1; i < n; ++i) {
            scanf("%lld",&x);
            num = (num + fm*ive(i))%mod;
            ans = (ans + num*x%mod)%mod;
        }
        fm = (fm*n)%mod;
        printf("%lld
",ans*ive(fm)%mod);
    }
    return 0;
}
View Code

Problem J. HDU6273:Master of GCD

题意：

　　一开始有n个全为1的数，每次操作你选择一个区间[l,r]和一个x，将这个区间内的每个数更新为乘以x之后的值，x只能是2或者3。问m次操作之后，所有数的最大公约数是多少。

题解：

　　一开始所有数都为1，然后对每个区间的数进行乘法运算，那么所有数的最大公约数就是他们乘的同一个数的最小次方的乘积。

　　例如：假设3个1，第一个乘了2次2和3次3，第二一个乘了3次2和2次3，第三个乘了4次2和1次3。那么他们的最大公约数为2的2次方与3的1次方的乘积。

　　那么我们只需要记录一下每个数乘了几次2和3就行了。一开始用的树状数组，后来发现可以直接用前缀和。算结果时用快速幂取模即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int INF = 1e9+10;
const ll mod = 998244353;
ll num2[N],num3[N];
int T,n,m;
int lowbit(int x){
    return x&(-x);
}
void update(int id,ll *a, ll x) {
    while (id <= n) {
        a[id] +=x;
        id += lowbit(id);
    }
}

ll query(int id, ll *a) {
    ll r = 0;
    while (id > 0) {
        r += a[id];
        id -= lowbit(id);
    }
    return r;
}
ll pq(ll a, ll b) {
    ll r = 1;
    while (b) {
        if (b&1) r = (r*a) % mod;
        a = (a*a) % mod;
        b>>=1;
    }
    return r;
}
int main()
{
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        memset(num2,0,sizeof(num2));
        memset(num3,0, sizeof(num3));
        for (int i = 0; i < m; ++i) {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            if (x == 2){
                update(l,num2,1);
                update(r+1,num2,-1);
            }else {
                update(l,num3,1);
                update(r+1,num3,-1);
            }
        }
        ll n2 = query(1,num2),n3 = query(1,num3);
        for (int i = 2; i <= n; i++) {
            n2 = min(n2,query(i,num2));
            n3 = min(n3,query(i,num3));
        }
        printf("%lld
",(pq(2,n2)*pq(3,n3))%mod);
    }
    return 0;
}
树状数组 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000+10;
const int INF = 1e9+10;
const ll mod = 998244353;
int a[2][N];
ll pq(ll a, ll b){
    ll ans = 1;
    while (b) {
        if (b&1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    int T,n,m;
    scanf("%d",&T);
    while (T--){
        scanf("%d%d",&n,&m);
        memset(a,0,sizeof(a));
        for (int i = 0; i < m; ++i) {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            a[x-2][l]++;
            a[x-2][r+1]--;
        }
        ll n2, n3, sum2 , sum3;
        n2 = sum2 = a[0][1];
        n3 = sum3 = a[1][1];
        for (int i = 2; i <= n; ++i) {
            sum2 += a[0][i];
            n2 = min(sum2,n2);
            sum3 += a[1][i];
            n3 = min(sum3,n3);
        }
        printf("%lld
",(pq(2,n2) * pq(3,n3))%mod);
    }
    return 0;
}
前缀和

相关推荐