Codeforces Round #463 (Div. 1 + Div. 2)

Codeforces

Contests 链接：Codeforces Round #463 (Div. 1 + Div. 2)
过题数：2
排名：2093/8251

A. Palindromic Supersequence

题意

给定一个字符串 $A$，构造一个字符串 $B$，使得字符串 $B$ 是回文串，且 $A$ 是 $B$ 的子序列。

输入

输入只包含一个字符串 $A~(1\leq|A|\leq10^3)$。

输出

输出字符串 $B$，字符串 $B$ 的长度不必是最短的，只需要在 $10^4$ 以内即可。

样例

题解

正着输出一遍 $A$ 再倒着输出一遍 $A$，就是答案，因为 $|A|\leq10^3$，所以答案最多只有 $2000\leq10^4$ 个字符。

过题代码

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

B. Recursive Queries

题意

定义函数 $f(x)$，表示数字 $x$ 的所有数位上非零数值的乘积，定义函数 $g(x)$ 如下：

$$g(x)=\begin{cases} n&n<10\\ g(f(n))&n\geq10 \end{cases}$$
有 $Q$ 次询问，每次询问区间 $x\in[l,r]$ 内，$g(x)=k$ 的 $x$ 的个数。

输入

第一行为一个整数 $Q~(1\leq Q\leq2\times10^5)$，表示询问的次数，接下去 $Q$ 行，每行三个整数 $l,r,k~(1\leq l\leq r\leq 10^6,1\leq k\leq9)$。

输出

对于每次询问输出所求答案。

样例

题解

预处理出 $[1,10^6]$ 内所有的 $g(x)$，对 $k\in[1,9]$ 的个数分别做前缀和，就可以 $O(1)$ 地查询。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 1000000 + 100;
int T, l, r, k;
int g[maxn];
int sum[maxn][10];
int f(int x) {
    int ret = 1;
    while(x != 0) {
        if(x % 10 != 0) {
            ret *= x % 10;
        }
        x /= 10;
    }
    return ret;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    for(int i = 1; i < maxn; ++i) {
        if(i < 10) {
            g[i] = i;
        } else {
            g[i] = g[f(i)];
        }
        for(int j = 1; j <= 9; ++j) {
            sum[i][j] = sum[i - 1][j];
        }
        ++sum[i][g[i]];
    }
    while(scanf("%d", &T) != EOF) {
        while(T--) {
            scanf("%d%d%d", &l, &r, &k);
            printf("%d\n", sum[r][k] - sum[l - 1][k]);
        }
    }
    return 0;
}

C. Permutation Cycle

题意

对于一个排列 $P[1...N]$，定义函数 $f(i,j)$ 为：

$$f(i,j)=\begin{cases} P[i]&j=1\\ f(P[i],j-1)&j>1 \end{cases}$$
定义函数 $g(i)$ 为使 $f(i,j)=i$ 的最小的 $j$ 的值，对于给定的整数 $N,A,B$，构造一种排列，使得 $g(i)\in\{A,B\}$。

输入

输入只包含三个整数 $N,A,B~(1\leq N\leq10^6,1\leq A,B\leq N)$。

输出

输出 $N$ 的一种满足题意的排列。

样例

题解

将每一个数字 $i$ 与其对应的下标连一条边，在全排列中就是一个个环，每一个 $i$ 都属于其中一个环，可以发现 $g(i)$ 就是第 $i$ 个数字所在环的节点数量，因此就是要构造一个序列，使这个序列中环的数量要么是 $A$ 要么是 $B$，所以相当于是要解一个方程，使得 $ax+by=n$，且 $x,y\geq0$，其中 $x$ 表示环上节点个数等于 $a$ 的环的数量，$y$ 表示环上节点个数等于 $b$ 的环的数量，由于数据范围比较小，可以暴力跑出 $x,y$ 的值，最后构造出这些环即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 1000000 + 100;
int n, a, b, cnta, cntb;
int num[maxn], ans[maxn];
void Move(int Index, int cnt, int x) {
    for(int i = 0; i < cnt; ++i) {
        ans[Index] = num[Index + x - 1];
        for(int j = 1; j < x; ++j) {
            ans[Index + j] = num[Index + j - 1];
        }
        Index += x;
    }
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    while(scanf("%d%d%d", &n, &a, &b) != EOF) {
        cnta = cntb = -1;
        for(int i = 0; i <= n; i += a) {
            if((n - i) % b == 0) {
                cnta = i / a;
                cntb = (n - i) / b;
            }
        }
        if(cnta == -1) {
            printf("-1\n");
            continue;
        }
        for(int i = 1; i <= n; ++i) {
            num[i] = i;
        }
        Move(1, cnta, a);
        Move(1 + cnta * a, cntb, b);
        for(int i = 1; i <= n; ++i) {
            if(i != 1) {
                printf(" ");
            }
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}