Codeforces Round #447 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #447 (Div. 2)
过题数：2
排名：995/11398

A. QAQ

题意

给定一个字符串 $s$，询问这个字符串中有多少个字符子序列是 "QAQ"。

输入

输入只包含一个字符串 $s~(1\leq|s|\leq100)$，且字符串中只含有大写字母。

输出

输出 "QAQ" 子序列的个数。

样例

题解

对于每一个字符 'A'，能够形成的 "QAQ" 子序列的个数，等于 'A' 左边的 'Q' 字符的数量乘上右边的 'Q' 字符的数量，'Q' 字符的数量可以预处理。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 100 + 100;
int ans;
char str[maxn];
int Left[maxn], Right[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%s", str + 1) != EOF) {
        ans = 0;
        int len = strlen(str + 1);
        Left[0] = Right[len + 1] = 0;
        for(int i = 1; i <= len; ++i) {
            Left[i] = Left[i - 1];
            if(str[i] == 'Q') {
                ++Left[i];
            }
        }
        for(int i = len; i >= 1; --i) {
            Right[i] = Right[i + 1];
            if(str[i] == 'Q') {
                ++Right[i];
            }
        }
        for(int i = 1; i <= len; ++i) {
            if(str[i] == 'A') {
                ans += Left[i] * Right[i];
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. Ralph And His Magic Field

题意

在一个 $n\times m$ 的网格中填上整数，要求每一行和每一列的整数的乘积都等于 $k$，问有多少种填数的方案。

输入

输入只包含三个整数 $n,m,k~(1\leq n,m\leq10^{18},k\in\{-1,1\})$。

输出

输出总的方案数对 $10^9+7$ 取模后的结果。

样例

题解

由 $k$ 只等于 $1$ 和 $-1$ 可以知道，填入的整数只能是 $1$ 或者 $-1$，其次，不论前面的填入的乘积是多少，最后一行或者一列的数字总能填上一个 $1$ 或者 $-1$ 来得到 $k$，因此 $n-1$ 行 $m-1$ 列的方格可以填 $-1$ 和 $1$ 的任意一种组合方式，总的方案数为 $2^{(n-1)(m-1)}$，考虑最后一个方格 $(n,m)$ 填入的数字的情况，这个位置填入的数字由第 $n$ 行的前 $m-1$ 个数字和第 $m$ 列的前 $n-1$ 行数字同时决定，当 $k=1$ 时没有任何问题，当 $k=-1$，必须保证 $n\%2=m\%2$，否则这个位置不论填什么数字都无法满足条件。最后由于 $n$ 和 $m$ 都很大，如果直接相乘会爆 long long，所以要用个欧拉降幂公式 $a^b\%p=a^{b\%\phi(p)+\phi(p)}\%p$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const LL MOD = 1000000007;
const LL phi = MOD - 1;
LL n, m, k, p;
LL fast_pow(LL res, LL n) {
    LL ans;
    for(ans = 1; n != 0; n >>= 1) {
        if((n & 1) == 1) {
            ans = (ans * res) % MOD;
        }
        res = (res * res) % MOD;
    }
    return ans;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%I64d%I64d%I64d", &n, &m, &k) != EOF) {
        if(k == -1 && n % 2 != m % 2) {
            printf("0\n");
            continue;
        }
        if(n >= phi || m >= phi || n * m >= phi) {
            p = ((n - 1) % phi) * ((m - 1) % phi) % phi + phi;
        } else {
            p = (n - 1) * (m - 1);
        }
        printf("%I64d\n", fast_pow(2, p));
    }
    return 0;
}

C. Marco and GCD Sequence

题意

对于任意一个长度为 $n$ 的整数序列，将这个序列的任意一个区间 $\gcd(a_i,a_{i+1},\cdots,a_j)$ 放入一个集合 $Set$ 中，在这个集合中，如果有两个相同的区间 $\gcd$ 的值，在集合中也只保留一个，现在给定集合 $Set$，要求构造出一个满足条件的序列。

输入

第一行为一个整数 $m~(1\leq m\leq1000)$，表示集合的大小，第二行为 $n$ 个整数 $s_1,s_2\cdots,s_m~(1\leq s_i\leq10^6)$，给出的数字一定是按升序排列的。

输出

如果可以构造出这样的序列，就输出这个序列，第一行为一个整数 $n~(1\leq n\leq4000)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq10^6)$，如果有多解输出任意一个，否则输出 $-1$。数据保证如果存在解，解的序列个数一定有不超过 $4000$ 的，且 $a_i$ 一定可以不超过 $10^6$.

样例

题解

首先判断给出的所有数字的最大公约数是否等于最小的数字，如果不等于，则输出 $-1$，否则将原序列的所有数字输出，并且隔一个插入一个最小的数字，就能满足任意一个长度大于 $1$ 的区间的 $\gcd$ 都等于最小的数字。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 1000000 + 100;
int n, cnt;
int ans[maxn], num[maxn];
int gcd(int x, int y) {
    return (y == 0? x: gcd(y, x % y));
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        cnt = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
        }
        int Gcd = num[1];
        for(int i = 2; i <= n; ++i) {
            Gcd = gcd(Gcd, num[i]);
        }
        if(Gcd != num[1]) {
            printf("-1\n");
            continue;
        }
        for(int i = 1; i <= n; ++i) {
            ans[cnt++] = num[i];
            ans[cnt++] = num[1];
        }
        printf("%d\n", cnt);
        for(int i = 0; i < cnt; ++i) {
            if(i != 0) {
                printf(" ");
            }
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}