一些CF&AT de 好题记录【年轻人训练 # Round11 + 周末做的题】
选自 年轻人训练 # Round11 and 一点周末做的题
都是非常锻炼思维或者值得积累的题ww
前排%龙哥
A - Nastia and Nearly Good Numbers CodeForces - 1521A 【思维】
题意：构造3个不同的数x,y,z,使得x + y = z,且x, y只能被A整除，z可以被A * B整除。【给出的A,B保证不会有A是B的倍数】
思路： 思维题，可以构造x = A * (B - 1) 和y = A， 满足z = x + y = A * B,可以被A * B整除。但是要注意，如果B是1，答案是NO;如果B是2，要把B变成4【否则B - 1 == 1】
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010;
ll a,b,t;
int main(){
cin >> t;
while(t --){
cin >> a >> b;
if(b == 2) b *= 2;
if(b == 1){
puts("NO");
continue ;
}
ll t1 = b - 1;
puts("YES");
printf("%lld %lld %lld\n", a, a * b - a, a * b);
}
return 0;
} C - ARC Wrecker AtCoder - arc117_b 【思维,乘法原理】
题意： 给出N(1e5)个数，组成一个序列。可以做任意次以下操作，问可能形成的序列共有多少种。
操作： 任意选择一个数（不一定要是序列中的数），使得序列中小于该数的所有数都-1.
思路：可以发现，一样的数字只能做同样的变化（要不变都不变，要减少都减少）。例如1 1， 序列只可能有两种答案【1 1和0 0】,这样我们就可以去重了。所以可以从小到大排序（例如这个序列是【3， 5】），先考虑第一个数3，可以有3,2,1,0四种变化； 对应的考虑5这个数，如果第一个数是3，那它可以是5,4,3;如果第一个数是2,它只能是4,3,2而不可以是5了(因为3变成2，证明比3大的数都至少要-1).可以发现，对于第一个数3，有4种不同序列，每一种变化会对应下一个数的(两数差+1)种不同序列(本栗子是5 - 3 + 1 = 3种)，以此类推。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010, mod = 1e9 + 7;
int n;
int main(){
cin >> n;
vector<int> nums;
for(int i = 1; i <= n; ++ i){
int x;
cin >> x;
nums.push_back(x);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
ll ans = nums[0] + 1;
for(int i = 1; i < nums.size(); ++ i){
ll tmp = nums[i] - nums[i - 1] + 1;
ans = (ans * tmp) % mod;
}
cout << ans;
return 0;
}D - Basic Diplomacy CodeForces - 1484C 【贪心,网络流】 %%龙哥tql
题意：某人有 n 个朋友，在 m 天中，每天会有 k 个朋友有空，问是否存在一种方案使得每个朋友出现的次数不大于ceil(m/2)，存在则输出YES和每天选择的朋友编号，否则输出 NO。(n,m <=1e5)
思路：贪心。先只考虑那些1天只有1个朋友出现的情况，这些朋友必选。如果这种情况下有人出现次数大于ceil(m/2)，答案就是NO，否则就是YES。YES的情况下，每天只需要选择当前出现次数最少(那些1天只有1个朋友出现的朋友出现次数要先算在内)的人即可。【因为题目保证所有样例每一天出现的朋友数量之和<=2e5,所以可以暴力找】
简单证明为什么是对的：这个贪心应该是第一感觉Qwq,肯定先选之前选过次数最少的朋友。在YES的前提下，只剩下那些一天至少有两个朋友的情况需要考虑 ，不妨假设某一天就只有两个朋友，选择他们之中被选择次数最少的朋友一定不会使得该朋友被选择的次数 > ceil(m/2)。【反证：如果m是偶数，要是>ceil(m/2)即m/2,那两个朋友的被选次数就必须都是m/2,这时，就代表m天已经选完了，和当前这一天正在选择矛盾;如果是奇数例如7，要想选完之后>ceil(m/2)即大于4，那两个朋友的被选次数就必须都是4，这就表明已经有8天选择了这两个朋友，和当前只有7天矛盾。】
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010;
int t,n,m,k,x;
int st[N];
vector<int> v[N];
bool cmp(int x, int y){ return st[x] < st[y];}
void solve(){
bool f = 1;
for(int i = 1; i <= m; ++ i){
scanf("%d", &k);
for(int j = 1; j <= k; ++ j){
scanf("%d", &x);
v[i].push_back(x);
}
if(k == 1){
st[x] ++;
if(st[x] > (m + 1) / 2) f = 0;
}
}
if(!f) puts("NO");
else{
puts("YES");
for(int i = 1; i <= m; ++ i){
if(v[i].size() == 1) printf("%d ", v[i][0]);
else{
sort(v[i].begin(), v[i].end(), cmp);
printf("%d ", v[i][0]);
st[v[i][0]] ++;
}
}
putchar('\n');
}
}
int main(){
scanf("%d", &t);
while(t --){
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; ++ i) v[i].clear();
memset(st, 0, sizeof st);
solve();
}
return 0;
}F - Miracle Tree AtCoder - arc117_d 【树的直径，构造，树学, siwei】
一个非常好的题，值得反复看！。
题意：给树上节点赋予权值，使得每个节点权值>1;任意两个节点权值差的绝对值>这两个节点之间的距离；满足前两个要求的情况下，最小化最大权值。
思路:第二个条件要满足，则不可能有相同权值的节点。
从这里可以发现，如果存在多个子链，那么下一条子链的第一个权值=上一条子链最后一个权值+回溯链长。
为了使得回溯链长总和最小，容易想到将最长的链放到最后赋值。
具体做法是先找到树的直径，然后从直径的一端点开始赋值，先对非直径赋值，再对直径赋值，回溯的时候赋值用的tot++，因为要加上回溯链长。
tips:小技巧
1.因为要找输的直径的端点，只能使用dfs求，无法用树形dp求树的直径；
2.如何标记树的直径?在第二次dfs的时候标记一下！类似树链剖分找重儿子
注意看dfs2，因为是从树的直径的一端开始进行的，son里保存的就是当前节点连接的树的直径上的点
3.回溯的时候记录链长 可以通过在dfs返回时cnt ++实现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200010, M = 2 * N;
int idx, ne[M], e[M], h[N];
int n,m,dep[N],rt,rt2,ans[N],son[N],cnt;
bool st[N];
void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}
void dfs1(int u, int fa, int depth){
dep[u] = depth;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue ;
dfs1(j, u, depth + 1);
}
}
void dfs2(int u, int fa){
dep[u] = 0;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue ;
dfs2(j, u);
dep[u] = max(dep[u], dep[j] + 1);
if(dep[j] > dep[son[u]]) son[u] = j;
}
}
void dfs3(int u, int fa){
ans[u] = ++ cnt;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa || j == son[u]) continue ;
dfs3(j, u);
}
if(son[u]) dfs3(son[u], u);
cnt ++;
}
int main(){
scanf("%d", &n);
memset(h, -1, sizeof h);
for(int i = 1; i <= n - 1; ++ i){
int a, b;
scanf("%d%d",&a,&b);
add(a, b), add(b, a);
}
dfs1(1, 0, 1);
for(int i = 1; i <= n; ++ i) if(dep[i] > dep[rt]) rt = i;
dfs2(rt, -1);
dfs3(rt, -1);
for(int i = 1; i <= n; i ++) printf("%d ", ans[i]);
return 0;
} H - Pawn CodeForces - 41D 【dp】
题意：给一个n * m的矩阵，可以在最低一行的任意位置开始启动，只能往左上或者右上走，获得该格子里的糖豆。在满足最后获得糖豆的数目可以被(k + 1)整除的前提下，可以获得多少糖豆？并输出最开始的位置和路径方案。
思路：如果没有 %(k + 1) == 0的条件，就是数字三角形。现在多了一个条件，就增加一维，表示当前获得的糖豆总数 %(k + 1)的余数。
dp的时候记录一下路径，然后反向dfs输出即可。
P.S.这种记录mod的dp，类似这个F - Potion
tips:
1.这里的l变量表示的是加上当前格子的糖豆数之后，%(k + 1)是l，所以要反推出满足这个条件下，上一行的余数是几【这个写法很类似exgcd里求最小正整数解，%k + k % k,第一个%k必不可少】。
2.一开始dp要memset成-1，表示这个状态不存在，只有一开始的某几个状态是存在的;
3.第三个else里的int tmp1 = -1, tmp2 = -1;很重要qwq 一开始顺手写了0，结果调了一会emm 因为dp是初始化的-1，后面的if如果都不满足，会用tmp来更新dp数组，初始化成0的话当场gg
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 110;
int n,m,k,dp[N][N][15],a[N][N],ans[N][N][15],beginn;
vector<char> v;
void dfs(int r, int c, int remain){
if(r == n) return (void)(beginn = c);
v.push_back(ans[r][c][remain] == -1 ? 'R' : 'L');
dfs(r + 1, c + ans[r][c][remain], ((remain - a[r][c]) % k + k) % k);
}
int main(){
cin >> n >> m >> k; k ++;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
scanf("%1d",&a[i][j]);
memset(dp, -1, sizeof dp);
for(int i = 1; i <= m; ++ i) dp[n][i][a[n][i] % k] = a[n][i];
for(int i = n - 1; i >= 1; -- i)
for(int j = 1; j <= m; ++ j)
for(int l = 0; l < k; ++ l){ // % k的余数
int tmp = ((l - a[i][j]) % k + k) % k; //3 9 4
if(j == 1){
if(dp[i + 1][j + 1][tmp] == -1) continue ;
dp[i][j][l] = dp[i + 1][j + 1][tmp] + a[i][j];
ans[i][j][l] = 1;
}else if(j == m){
if(dp[i + 1][j - 1][tmp] == -1) continue ;
dp[i][j][l] = dp[i + 1][j - 1][tmp] + a[i][j];
ans[i][j][l] = -1;
}else{
int tmp1 = -1, tmp2 = -1;
if(dp[i + 1][j - 1][tmp] != -1) tmp1 = dp[i + 1][j - 1][tmp] + a[i][j];
if(dp[i + 1][j + 1][tmp] != -1) tmp2 = dp[i + 1][j + 1][tmp] + a[i][j];
if(tmp1 > tmp2) dp[i][j][l] = tmp1, ans[i][j][l] = -1;
else dp[i][j][l] = tmp2, ans[i][j][l] = 1;
}
}
int w = 0;
for(int i = 1; i <= m; ++ i) if(dp[1][i][0] > dp[1][w][0]) w = i;
if(!w) puts("-1");
else{
printf("%d\n", dp[1][w][0]);
dfs(1, w, 0);
printf("%d\n", beginn);
for(int i = v.size() - 1; i >= 0; -- i) printf("%c", v[i]);
}
return 0;
}I - Sequence operation HDU - 3397 【线段树区间合并】
不说了都是泪emm 见之前的博客
#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
const int N = 100010;
int n,w[N],m,t;
struct node{
int l, r, llen0, llen1, rlen0, rlen1, tlen0, tlen1, sz0, sz1, sz, reverse, lazy; //lazy = -1表示初始化
}tr[N << 2];
void pushup(node& rt, node& ls, node& rs){
rt.sz = ls.sz + rs.sz, rt.sz0 = ls.sz0 + rs.sz0, rt.sz1 = ls.sz1 + rs.sz1;
rt.llen0 = ls.llen0, rt.llen1 = ls.llen1, rt.rlen0 = rs.rlen0, rt.rlen1 = rs.rlen1;
rt.tlen0 = max(max(ls.tlen0, rs.tlen0), ls.rlen0 + rs.llen0);
rt.tlen1 = max(max(ls.tlen1, rs.tlen1), ls.rlen1 + rs.llen1);
if(ls.tlen1 == ls.sz) rt.llen1 += rs.llen1;
if(ls.tlen0 == ls.sz) rt.llen0 += rs.llen0;
if(rs.tlen1 == rs.sz) rt.rlen1 += ls.rlen1;
if(rs.tlen0 == rs.sz) rt.rlen0 += ls.rlen0;
}
void pushup(int u){ pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);}
void build(int u, int l, int r){
tr[u] = {l,r,w[l] == 0,w[l] == 1,w[l] == 0,w[l] == 1,w[l] == 0,w[l] == 1,w[l] == 0,w[l] == 1,1,0,-1};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void Swap(node&rt){swap(rt.sz0, rt.sz1),swap(rt.llen0, rt.llen1),swap(rt.rlen0, rt.rlen1),swap(rt.tlen0, rt.tlen1);}
void pushdown(int u){
node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
if(rt.l == rt.r) return ;
if(rt.reverse){
pushdown(u << 1), pushdown(u << 1 | 1);
Swap(ls); Swap(rs);
ls.reverse ^= 1, rs.reverse ^= 1;
rt.reverse = 0;
}
if(rt.lazy != -1){
rt.reverse = ls.reverse = rs.reverse = 0;
if(rt.lazy == 1){
ls.lazy = rs.lazy = 1;
ls.sz1 = ls.sz, rs.sz1 = rs.sz, ls.sz0 = rs.sz0 = 0;
ls.llen1 = ls.rlen1 = ls.tlen1 = ls.sz;
ls.llen0 = ls.rlen0 = ls.tlen0 = 0;
rs.llen1 = rs.rlen1 = rs.tlen1 = rs.sz;
rs.llen0 = rs.rlen0 = rs.tlen0 = 0;
}else{
ls.lazy = rs.lazy = 0;
ls.sz0 = ls.sz, rs.sz0 = rs.sz, ls.sz1 = rs.sz1 = 0;
ls.llen0 = ls.rlen0 = ls.tlen0 = ls.sz;
ls.llen1 = ls.rlen1 = ls.tlen1 = 0;
rs.llen0 = rs.rlen0 = rs.tlen0 = rs.sz;
rs.llen1 = rs.rlen1 = rs.tlen1 = 0;
}
rt.lazy = -1;
}
}
void modify(int u, int l, int r, int v){
node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
if(tr[u].l >= l && tr[u].r <= r){
if(v == 1){
rt.lazy = 1, rt.reverse = 0, rt.llen0 = rt.sz0 = rt.rlen0 = rt.tlen0 = 0;
rt.llen1 = rt.sz1 = rt.rlen1 = rt.tlen1 = rt.sz;
}else if(v == 0){
rt.lazy = 0, rt.reverse = 0, rt.llen0 = rt.sz0 = rt.rlen0 = rt.tlen0 = rt.sz;
rt.llen1 = rt.sz1 = rt.rlen1 = rt.tlen1 = 0;
}else{
if(rt.lazy != -1) rt.lazy ^= 1;
rt.reverse ^= 1;
Swap(rt);
}
}else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, v);
if(r > mid) modify(u << 1 | 1, l, r, v);
pushup(u);
}
}
node query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u];
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) return query(u << 1, l, r);
if(l > mid) return query(u << 1 | 1, l, r);
else{
node n1 = query(u << 1, l, r);
node n2 = query(u << 1 | 1, l, r);
node res = {l,r,0,0,0,0,0,0,0,0,0,0,-1}; pushup(res, n1, n2);
return res;
}
}
int main(){
cin >> t;
while(t --){
cin >> n >> m;
for(int i = 1; i <= n; ++ i) scanf("%d",&w[i]);
build(1, 1, n);
while(m --){
int op, x, y;
scanf("%d%d%d",&op,&x,&y); x ++, y ++;
if(op == 0) modify(1, x, y, 0);
else if(op == 1) modify(1, x, y, 1);
else if(op == 2) modify(1, x, y, 2);
else if(op == 3) printf("%d\n", query(1, x, y).sz1);
else{
node n1 = query(1, x, y);
printf("%d\n", n1.tlen1);
}
}
}
return 0;
}
F - Potion AtCoder Beginner Contest 192 【dp】
题意：有n种药物，每种有一个能量值A【i】.选择其中的k种，把他们混合(只能在一开始混合一次），得到的能量值就是他们的和。然后这些药每分钟会增加k点能量值，问恰好涨到X能量值最少需要多久。
tips:01背包，其实就是前i种药品里选择k个。但是多出来一个恰好要达到X能量值的限制，所以要增加一维表示余数。sum + ans * k == X, 等式两边同时mod k,可以得到sum % k == X % k.
注意理解！ 这题的mod是药品的总数，所以要多出一维来枚举一共要选多少种药品混合，而不能只用3重循环来算前i种药品中选k个，余数是j然后用k来当模数。【根据上面的式子，mod应该选取的是一共选择多少种药，而不是过程中的变量】
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 110;
int n;
ll X, dp[N][N][N], ans = 1e18, a[N];
int main(){
cin >> n >> X;
for(int i = 1; i <= n; ++ i) cin >> a[i];
for(int t = 1; t <= n; ++ t){ //一共选t个
memset(dp, 0xcf, sizeof dp);
dp[0][0][0] = 0;
for(int i = 1; i <= n; ++ i){ //前i个物品中选
dp[i][0][0] = 0;
for(int k = 1; k <= min(i, t); ++ k){ //选k个
for(int j = 0; j < t; ++ j)
dp[i][k][j] = max(dp[i - 1][k][j], dp[i - 1][k - 1][((j - a[i]) % t + t) % t] + a[i]);
}
}
if(dp[n][t][X % t] >= 0) ans = min(ans, (X - dp[n][t][X % t]) / t);
}
cout << ans;
return 0;
}AcWing 3549. 最长非递减子序列 【dp】
题意：给定一个只有1 2组成的序列，可以选择其中连续的一段翻转，求翻转后最长不下降子序列的长度。
思路：非常好的线性dp.首先是子序列而不是子串(可以不连续)。可以发现，只有111222211122这种才有翻转的必要。用dp考虑,设s1为11111这种形状的子序列最大长度,s2是1112222这种形状的子序列的最大长度,s3是1112222111这种形状子序列的最大长度,s4是111122221111222这种子序列的最大长度(!注意这里面每一段连续1和2长度都可以为0)
1.输入1,s1直接加1
2.输入2,s2的长度等于(s1的长度 + 连续2)的长度,最坏情况下连续2仅有一个,那输入2之后s2只能更新成s1+1的长度,如果不是最坏情况则直接s2+1,写成式子就是s2 = max(s1+1,s2+1)
3.输入1,s3的长度等于(s2的长度+连续1)的长度,最坏情况下连续1仅有一个,那输入1之后s3只能更新为s2+1的长度,如果不是最坏情况则直接s3+1,写成式子就是s3 = max(s2+1,s3+1)
4.s4…同理,最坏s3+1,正常s4+1
最后答案一定在s3,s4中。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,s1,s2,s3,s4;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++ i){
int x;
scanf("%d", &x);
if(x == 1) s1 ++, s3 = max(s3 + 1, s2 + 1);
if(x == 2) s2 = max(s2 + 1, s1 + 1), s4 = max(s4 + 1, s3 + 1);
}
printf("%d\n", max(max(s1, max(s2, s3)), s4));
return 0;
}1872. 石子游戏 VIII 力扣周赛 【博弈Dp】
思路：关键在于定义状态。我们定义dp[i]为当前玩家可以在[i,n - 1]中选取石子，所能获得的最大差。【注意两点：首先是当前玩家，即这个dp是对当前行动者来说的最优，而不是针对Alice,尽管最后需要求的是Alice最优，但是既然对手足够聪明，博弈dp的核心就是“在最坏情况下找最好”; 再者这里定义的是可以从[i, n]中选，并不表示当前玩家选从1->i这个区间！（这样定义转移方程就不一样了）】
那么对于当前玩家来说，他有两种选择：选i和不选i。如果不选择i，那dp[i] = dp[i + 1];否则，dp[i] = sum[i] - dp[i + 1].这里注意：减法的意义是轮到对手行动，对手足够聪明，他一定会选择他的最优解，即dp[i + 1]，他的最优和我们的最优是相反的,所以要减；i + 1的意思是，当前玩家选了从头到i，对手至少要选择2个石子，所以只能从i + 1开始选【这也是为什么答案是dp2而不是dp1原因，Alice只能在【2,n】中选择】。最后注意一下边界，如果全选（到n），那直接就是一个前缀和的值。
class Solution {
public:
int stoneGameVIII(vector<int>& w) {
int n = w.size();
vector<int> dp(n + 1), s(n + 1);
for(int i = 1; i <= n; ++ i) s[i] = s[i - 1] + w[i - 1];
dp[n] = s[n];
for(int i = n - 1; i >= 2; -- i){
dp[i] = max(dp[i + 1], s[i] - dp[i + 1]);
}
return dp[2];
}
};
