CF1071

Codeforces Round 517 (Div. 1, based on Technocup 2019 Elimination Round 2)

CF1071A

link

CF1071A题意

现在你有两天的时间备考NOI，两天各有 \(a\) 小时，\(b\) 小时（~~时空扭曲~~）。

每天可以看若干份笔记。编号为 \(k\) 的笔记需要看 \(k\) 小时(请不要忽略，最后输出有用)。为了考得更好，你需要最大化看的笔记份数。请你求出最多能看多少份笔记。

注意，看过的笔记需要都不相同。即使是不在同一天看的。

\((1 \leq a, b \leq 10^9)\)。

CF1071A题解

这个显然从小到大的贪心选择 \(1\sim k\) 之间的笔记，然后对于第一天尽可能分配给 \(1\sim x\)，如果有一个笔记看了超时，不看时间还不够，那么就把之前时间为 \((\sum_{i=1}^xi)-a\) 的那篇笔记分给第二天即可满足条件。

CF1071A代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e6 + 10;
bool book[maxn];
int a, b;
vector<int> v1, v2;
signed main(){
    a = read(); b = read();
    int sum = a + b, tmp = 0,point = 1;
    while(tmp + point <= sum){tmp += point;point++;}
    tmp = 0;point--;
    for(int i = 1;i <= point;i++){
        if(tmp + i > a){book[i] = 1;book[tmp + i - a] = 0;break;}
        if(tmp + i == a){book[i] = 1;break;}
        book[i] = 1;tmp += i;
    }
    for(int i = 1;i <= point;i++){
        if(book[i])v1.push_back(i);
        else v2.push_back(i);
    }
    printf("%d\n",v1.size());for(int i : v1)printf("%d ",i);puts("");
    printf("%d\n",v2.size());for(int i : v2)printf("%d ",i);puts("");
    return 0;
}

CF1071B

link

CF1071B题意

给你一个 \(n\times n\) 的全是小写字母的矩阵，你能改变 \(k\) 个字母

你要从左上角走到右下角，且每步只能移动到右边或下边的字母上。

对于每一条路径都会得到一个由你经过的所有字母组成的字符串。当然，它的长度是 \(2\times n-1\)。

在你最多改动 \(k\) 个字母的情况下，找到一个得到字符串字典序最小的路径。

CF1071B题解

设 \(f_{i,j}\) 表示从 \((1,1)\) 出发经过不是a字符的最少情况。
那么从 \(f_{i,j}=k\)（如果任意一个都少于 \(k\)，那就从 \(f\) 最大的位置出发）出发，每次bfs搜索最优的路径即可。

CF1071B代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
char ch[maxn][maxn];
int f[maxn][maxn];
int n, k;
char ans[maxn * 2];
bool book[maxn][maxn];
queue<pair<int,int> > que;
signed main(){
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;i++){scanf("%s",ch[i] + 1);}
    for(int i = 0;i <= n + 1;i++)f[i][0] = f[0][i] = 0x3f3f3f3f;
    f[1][0] = 0;int st = 0, tmp = 0;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++){
            f[i][j] = min(f[i - 1][j],f[i][j - 1]) + (ch[i][j] != 'a');
            if(f[i][j] <= k)st = max(st,i + j - 1),tmp = max(tmp,f[i][j]);
        }
    for(int i = 1;i <= n * 2;i++)ans[i] = 'z' + 1;
    if(k == 0){
        que.push(make_pair(1,1));st = 0;ans[1] = ch[1][1];
        while(!que.empty()){
            int u = que.front().first, v = que.front().second;que.pop();
            if(ch[u][v] > ans[u + v - 1])continue;
            if(v + 1 <= n){
                ans[u + v] = min(ans[u + v],ch[u][v + 1]);
                if(!book[u][v + 1] && ch[u][v + 1] == ans[u + v]){book[u][v + 1] = 1;que.push(make_pair(u,v + 1));}
            }
            if(u + 1 <= n){
                ans[u + v] = min(ans[u + v],ch[u + 1][v]);
                if(!book[u + 1][v] && ch[u + 1][v] == ans[u + v]){book[u + 1][v] = 1;que.push(make_pair(u + 1,v));}
            }
        }
    }
    else{
        for(int i = 1;i <= st && i <= n;i++)
            if(f[i][st - i + 1] == tmp){que.push(make_pair(i,st - i + 1));book[i][st - i + 1] = 1;}
        
        while(!que.empty()){
            int u = que.front().first, v = que.front().second;que.pop();
            if(ch[u][v] > ans[u + v - 1])continue;
            if(v + 1 <= n){
                ans[u + v] = min(ans[u + v],ch[u][v + 1]);
                if(!book[u][v + 1] && ch[u][v + 1] == ans[u + v]){book[u][v + 1] = 1;que.push(make_pair(u,v + 1));}
            }
            if(u + 1 <= n){
                ans[u + v] = min(ans[u + v],ch[u + 1][v]);
                if(!book[u + 1][v] && ch[u + 1][v] == ans[u + v]){book[u + 1][v] = 1;que.push(make_pair(u + 1,v));}
            }
        }
    }
    for(int i = 1;i <= st;i++){putchar('a');}
    for(int i = st + 1;i <= n * 2 - 1;i++)putchar(ans[i]);
    puts("");
    return 0;
}

CF1071C

link

CF1071C题意

给你一个长度为 \(n\) 的数组，包含\(0,1\)，

你可以执行若干次操作，每次操作包含两个步骤：

选择三个位置\(x,y,z\)，满足\(1\le x<y<z\le n,y-x=z-y\)，
将这三个位置上的数取反（\(0\)变成\(1\)，\(1\)变成\(0\)）。

若存在方案使每一位都为\(0\)且操作次数不超过 \((\lfloor \frac{n}{3} \rfloor + 12)\)，第一行输出\(YES\)，输出方案。

若无解，输出\(NO\)。

\(3\le n\le 10^5\)。

CF1071C题解

暴力+打表=正解。
*2600的黑题恐怖如斯。

尝试跑暴力，有以下两个发现：

所有长度大于 \(8\) 的数组一定有解。
在一个长度为 \(11\) 的数组中，不超过两次就能够把 \([1,6]\) 之间的任意数字变成 \(0\)。

于是先打表打出长度为 \(11\) 时将 \([1,6]\) 区间变成 \(0\) 的方法，然后剩下的直接暴力搜索即可。
需要注意的是，这道题的限制次数比较紧，尽可能的多节约次数。

CF1071C代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f=  1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e5 + 10;
const int opt[1 << 6][7] = {
{-1,-1,-1,-1,-1,-1},
{6,8,10,-1,-1,-1},
{5,8,11,-1,-1,-1},
{5,6,7,-1,-1,-1},
{4,7,10,-1,-1,-1},
{4,6,8,-1,-1,-1},
{3,4,5,3,7,11},
{4,5,6,-1,-1,-1},
{3,7,11,-1,-1,-1},
{3,6,9,-1,-1,-1},
{3,5,7,-1,-1,-1},
{1,3,5,1,6,11},
{3,4,5,5,7,9},
{2,3,4,2,6,10},
{3,4,5,-1,-1,-1},
{3,4,5,6,7,8},
{2,4,6,4,6,8},
{2,6,10,-1,-1,-1},
{2,5,8,-1,-1,-1},
{2,5,8,6,7,8},
{2,3,4,3,7,11},
{2,4,6,-1,-1,-1},
{2,3,4,3,5,7},
{2,4,6,5,7,9},
{2,3,4,4,7,10},
{1,2,3,1,6,11},
{1,2,3,1,5,9},
{2,3,4,4,5,6},
{2,3,4,-1,-1,-1},
{2,3,4,6,7,8},
{2,3,4,5,7,9},
{2,3,4,5,6,7},
{1,3,5,3,5,7},
{1,6,11,-1,-1,-1},
{1,5,9,-1,-1,-1},
{1,3,5,3,6,9},
{1,4,7,-1,-1,-1},
{1,4,7,6,7,8},
{1,4,7,5,7,9},
{1,4,7,5,6,7},
{1,3,5,5,7,9},
{1,2,3,2,6,10},
{1,3,5,-1,-1,-1},
{1,3,5,6,7,8},
{3,4,5,1,5,9},
{1,2,3,2,4,6},
{1,3,5,4,7,10},
{1,3,5,4,6,8},
{1,2,3,3,7,11},
{1,2,3,3,6,9},
{1,2,3,3,5,7},
{2,5,8,1,6,11},
{2,4,6,1,6,11},
{1,4,7,2,6,10},
{1,2,3,3,4,5},
{2,4,6,1,5,9},
{1,2,3,-1,-1,-1},
{1,2,3,6,7,8},
{1,2,3,5,7,9},
{1,2,3,5,6,7},
{1,2,3,4,7,10},
{1,2,3,4,6,8},
{2,3,4,1,5,9},
{1,2,3,4,5,6}
};
int n;
int a[maxn];
vector<pair<int,pair<int,int> > > res;

int pr[40][2], tot;
bool chose[40];
bool flag = false;
int add;
void dfs(int step,int sta,int nsta){
    if(flag)return;
    // printf("sta =  %d nsta = %d\n",sta,nsta);
    if(nsta == sta){
        int cnt = 0;
        for(int i = 0;i <= tot;i++){
            if(chose[i])res.push_back(make_pair(pr[i][0] - pr[i][1] + add,make_pair(pr[i][0] + add,pr[i][0] + pr[i][1] + add)));
        }
        flag = true;
        return;
    }
    if(step == -1){return;}
    int x1 = pr[step][0] - pr[step][1],x2 = pr[step][0],x3 = pr[step][0] + pr[step][1];
    x1 = n - x1;x2 = n - x2;x3 = n - x3;
    nsta ^= (1 << x1);nsta ^= (1 << x2);nsta ^= (1 << x3);
    chose[step] = 1; dfs(step - 1,sta,nsta);
    nsta ^= (1 << x1);nsta ^= (1 << x2);nsta ^= (1 << x3);
    chose[step] = 0;dfs(step - 1,sta,nsta);
}
signed main(){
    n = read();
    for(int i = 1;i <= n;i++)a[i] = read();
    int l = 1;
    for(int i = 1;i <= n;i += 6,l = i){
        int sta = 0;
        for(int j = 0;j < 6;j++)sta = (sta << 1) + a[i + j];
        if(opt[sta][2] + i - 1 > n || opt[sta][5] + i - 1 > n)break;
        if(opt[sta][0] != -1){
            res.push_back(make_pair(opt[sta][0] + i - 1,make_pair(opt[sta][1] + i - 1,opt[sta][2] + i - 1)));
            a[opt[sta][0] + i - 1] ^= 1;a[opt[sta][1] + i - 1] ^= 1;a[opt[sta][2] + i - 1] ^= 1;
        }
        if(opt[sta][3] != -1){
            res.push_back(make_pair(opt[sta][3] + i - 1,make_pair(opt[sta][4] + i - 1,opt[sta][5] + i - 1)));
            a[opt[sta][3] + i - 1] ^= 1;a[opt[sta][4] + i - 1] ^= 1;a[opt[sta][5] + i - 1] ^= 1;
        }
    }
    int sta = 0;
    if(n - l + 1 < 8){l = max(1,n + 1 - 8);}
    for(int j = l;j <= n;j++)sta = (sta << 1) + a[j];
    add = l - 1;
    int cnt = 0;
    for(int i = 2;i < n - l + 1;i++)
        for(int r = 1;i - r >= 1 && i + r <= n - l + 1;r++){
            pr[cnt][0] = i;pr[cnt++][1] = r;
        }
    n = n - l + 1;
    flag = 0;cnt--;tot = cnt;dfs(tot,sta,0);
    // printf("sta = %d,flag = %d\n",sta,flag);
    if(flag){
        puts("YES");
        printf("%d\n",res.size());
        for(auto i : res)printf("%d %d %d\n",i.first,i.second.first,i.second.second);
    }
    else{puts("NO");}
    return 0;
}

CF1071D

link

CF1071D题意

t组数据，每组给定两个数a,b
有两种操作:
1.把 a或b 变为它乘上任意一个质数
2.把 a或b 中的一个数变为它除以它的任意一个质因子
求最少的操作次数，使得a,b有相同的因子个数
a,b≤10^6,t≤105

CF1071D题解

不难想到，将每个数质因数分解之后，我们要的是 \(p_i^{k_i}\) 上面的 \(k_i\)，顺序和 \(p_i\) 都不关心。
将所有得出的结果记作向量 \(\vec{k_1,k_2,\dots,k_x},k_1\ge k_2\ge\dots\ge k_x\)
这样之后，我们能够得出不超过 \(289\) 个向量。
但是这样仍然不会涵盖所有情况，可能最终得到的数字会大于 \(10^6\)。
但是我们关心的是 \(\prod_{i=1}^x(k_i+1)\)，于是直接暴力维护即可。