2021 CCPC 网络赛题解

Problem A. Cut The Wire

签到题 略

Problem B. Time-Division Multiplexing

考虑到单个串$n<=12$所有字符串的lcm为$2?3?2?5?7?2?3?11=27720$,所以一个循环节最长为$27720?n$，不同的字符最多散落在两个循环节内，故总长度应该是$27720?n?2$。然后用一个双指针算法求解即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;int n;
char s[110][14];
int p[110];
int cnt[256];int main() {
    int T;scanf("%d", &T);while (T--) {
    scanf("%d", &n);memset(cnt, 0, sizeof cnt);int c = 1;for (int i = 0; i < n; i++) {
    scanf("%s", s[i]);p[i] = strlen(s[i]);for (int j = 0; j < p[i]; j++) cnt[s[i][j]]++;}int diff = 0;for (int i = 0; i < 256; i++) if (cnt[i]) diff++;string tdm;for (int i = 0; i < 27720 * 2; i++) {
    for (int j = 0; j < n; j++) {
    tdm.push_back(s[j][i % p[j]]);}}//第二个指针, 不同的个数int j = 0, tot = 0, res = 1e9;memset(cnt, 0, sizeof cnt);for (int i = 0; i < tdm.size(); i++) {
    char c = tdm[i];if (!cnt[c]) tot++;cnt[c]++;while (cnt[tdm[j]] > 1) {
    cnt[tdm[j]]--;j++;}if (tot == diff) {
    res = min(res, i - j + 1);}}printf("%d\n", res);}return 0;
}

Problem F. Power Sum

对于相邻的四个数字，有$(x+1{)}^2?(x+2{)}^2?(x+3{)}^2+(x+4{)}^2=4$
故有$F(5)=F(1)+"1001"$，$F(9)=F(5)+"1001"$。构造出四个边界$F(1),F(2),F(3),F(4)$，递推即可得到答案

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;int main() {
    int T;scanf("%d", &T);string s[5] = {
     "","1", "0001", "01001", "001" };while (T --) {
    string t;int n;scanf("%d", &n);t = s[n % 4 == 0 ? 4 : n % 4];int k = (n - 1) / 4;string b = "1001";while (k) {
    if (k & 1) t = t + b;b = b + b;k >>= 1;}printf("%d\n%s\n", strlen(t.c_str()), t.c_str());}return 0;
}

Problem G. Function

注意到g(x)最大值为$g(99999)=54$,因此可以枚举$[1，54]$,固定住g(x)，然后$f(x)$就是一个二次函数了，这样的话就可以利用抛物线开口的情况进行分类讨论求解。在这里先预处理出满足$g(x)=t$的所有x，然后用二分就可以快速实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int  M = 2e5;ll A, B, C, D, N;
int n;
vector<int> gx[55];inline int g(int x) {
    int res = 0;while (x) {
    res += x % 10;x /= 10;}return res;
}ll calc(ll a, ll b, ll x) {
    return a * x * x + b * x;
}
void init() {
    for (int i = 1; i <= 1000000; i++) {
    gx[g(i)].push_back(i);}
}int main() {
    int T;scanf("%d", &T);init();while (T--){
    scanf("%lld%lld%lld%lld%lld", &A, &B, &C, &D, &N);ll res = 9e18;for (int i = 1; i <= 54; i++) {
    if (gx[i].size() == 0 || gx[i][0]> N) continue;//找到第一个大于N的下标, 则gx[i][r - 1]是满足 <= N的最大数字int r = upper_bound(gx[i].begin(), gx[i].end(), N) - gx[i].begin();ll a = A * i + B, b = C * i * i + D * i;if (a <= 0) res = min(res, min(calc(a, b, gx[i][0]), calc(a, b, gx[i][r - 1])));else{
    //对称轴int mid = -b / (2 * a);if (mid <= gx[i][0]) res = min(res, calc(a, b, gx[i][0]));else if (mid >= gx[i][r - 1]) res = min(res, calc(a, b, gx[i][r - 1]));else {
    int pos = lower_bound(gx[i].begin(), gx[i].begin() + r, mid) - gx[i].begin();for (int j = -1; j <= 1; j++) {
    int t = pos + j;if (t >= 0 && t < r) res = min(res, calc(a, b, gx[i][t]));}}}}printf("%lld\n", res);}return 0;
}

Problem I. Command Sequence

对于每一个点位，看看之前遍历过的序列之中有多少个点和其相同，这样就找到了一个序列，这一点可以用一个hash表来实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5, M = 2e5;map<ll, int> S;
char s[N];
int n;ll get(int x, int y) {
    x += N, y += N;return (ll)x * M + y;
}int main() {
    int T;scanf("%d", &T);while (T--){
    scanf("%d", &n);scanf("%s", s);int x = 0, y = 0;S.clear();S[get(x,y)]++;ll res = 0;for (int i = 0; i < n; i++) {
    if (s[i] == 'U') x--;else if (s[i] == 'D') x++;else if (s[i] == 'L') y--;else y++;res += S[get(x, y)];S[get(x, y)]++;}printf("%lld\n", res);}return 0;
}

Problem K. Shooting Bricks

贴一个原题链接。。
P1174 打砖块

#include <iostream>
#include <cstring>
using namespace std;
const int N = 210;int f[N][N][2];
int g[N][N], v[N][N][2];
bool st[N][N];
int n, m, k;int main()
{
    
#ifdef ONLINE_JUDGE
#else freopen("in.txt", "r", stdin);
#endifcin >> n >> m >> k;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){
    char c;cin >> g[i][j] >> c;if(c == 'Y') st[i][j] = true;}for(int i = 1; i <= m; i++) {
    for(int j = n, cnt = 0; j ; j--) {
    if(st[j][i]) v[i][cnt][1] += g[j][i];else {
    cnt++;v[i][cnt][1] = v[i][cnt][0] = v[i][cnt - 1][1] + g[j][i];} }}for(int i = 1; i <= m; i++)for(int j = 0; j <= k; j++)for(int l = 0; l <= min(n, j); l++){
    f[i][j][1] = max(f[i][j][1], f[i - 1][j - l][1] + v[i][l][1]);//从前面借if(l) f[i][j][0] = max(f[i][j][0], f[i - 1][j - l][1] + v[i][l][0]);if(j > l) f[i][j][0] = max(f[i][j][0], f[i - 1][j - l][0] + v[i][l][1]);}cout << f[m][k][0];return 0;
}

Problem L. remove

一道贪心题，首先可以先构造一个序列$a_n$，然后再套公式，用快速幂来求解答案，题目要求mod$2^{64}$，那么用unsigned long long 即可

首先，可以知道当$i>=lcm(p_i)$的时候，$a[i]=0$, 所以，只需要处理[1, min((lcm{ $p_i$}, n)]这个区间的所有数字即可。

然后，在有解的情况下，a[i]是单调不减的，可以自行证明

如果我们想要求一个x，如果它有一个质因子p在给定的质数集合之中，那么，x可以转移的范围是[x+1,x+p-1]（逆着考虑）。所以可以先类似于素数筛，把[1, min((lcm{ $p_i$}, n)]这个区间中p的倍数都标记上。对于每个位置i，$f[i]（p_k|i）$ 为位置i可以转移到最远位置所用的质数，最后枚举每个i，那么$i+f[i]?1$就是i能转移到的最大右边界，如果$i+f[i]?1>=r$，则让r一直往后走就行，$g[r]=g[i]+1$ (r > i)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e6 + 10, M = 1e5 + 10;
typedef unsigned long long ULL;
typedef long long LL;
int n, m;
int a[N], p[N], f[N], g[N];ULL qmi(ULL a, ULL b) {
    ULL res = 1;while(b) {
    if(b & 1) res = res * a;a *= a;b >>= 1;}return res;
}
int main()
{
    int T;scanf("%d", &T);while(T--) {
    scanf("%d%d", &n, &m);fill(f, f + n + 1, 0);for(int i =  1; i <= m; i++) scanf("%d", p + i);LL mul = 1;for(int i = 1; i <= m; i++) {
    mul *= p[i];if(mul > n) {
    mul = n + 1;break;}}for(int i = 1; i <= m; i++) {
    for(int j = 0; j < mul; j += p[i]) {
    f[j] = max(f[j], p[i]);}}g[0] = 0;for(int i = 0, r = 1; i < mul; i++) {
    while(r <= i + f[i] - 1 && r <  mul) g[r++] = g[i] + 1;        }ULL res = 0;for(int i = 1; i < mul; i++) res += (ULL)g[i] * qmi(23333, n - i);cout << res << endl;}return 0;
}