网站建设与管理做什么,二手站网站怎做,关卡页面设计,丹阳房价Codeforces Round 592 (Div. 2)#xff08;A - G#xff09;
Dashboard - Codeforces Round 592 (Div. 2) - Codeforces
A. Pens and Pencils(思维)
思路#xff1a;比较完成 绘画课 和 讲座 所需的 最小笔数 和 k 的关系即可。 时间复杂度 O ( 1 ) 时间复杂度O(1) 时间复…Codeforces Round 592 (Div. 2)A - G
Dashboard - Codeforces Round 592 (Div. 2) - Codeforces
A. Pens and Pencils(思维)
思路比较完成 绘画课 和 讲座 所需的 最小笔数 和 k 的关系即可。 时间复杂度 O ( 1 ) 时间复杂度O(1) 时间复杂度O(1)
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N 2e6 10;
const int mod 1e9 7;
typedef pairint,intPII;int a , b , c , d , k , t;signed main(){cin t;while(t --){cin a b c d k;int cnt1 (a - 1) / c 1;int cnt2 (b - 1) / d 1;if(cnt1 cnt2 k){cout cnt1 k - cnt1 \n;} else {cout -1\n;}}return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);B. Rooms and Staircases(思维)
思路对于每一个纵向的梯子 如果走过梯子后不改变方向 那么是否经过梯子不影响结果 所以经过梯子后一定要改变方向 贡献就是梯子位置离出发点的二倍 枚举梯子位置计算最大贡献即可。 时间复杂度 O ( n ) 时间复杂度O(n) 时间复杂度O(n)
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N 2e6 10;
const int mod 1e9 7;
typedef pairint,intPII;int t , n;
string s;signed main(){IOScin t ;while(t --){cin n s;int maxx n;for(int i 0 ; i n ; i ){if(s[i] 1) maxx max(maxx , (i 1) * 2);}for(int i n - 1 ; i 0 ; i --){if(s[i] 1) maxx max(maxx , (n - i) * 2);}cout maxx \n;}return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);C. The Football Season扩展欧几里得算法)
大意给出两个式子 x ∗ w y ∗ d p ( 1 ) x*wy*dp~~(1) x∗wy∗dp (1) x y z n ( 2 ) xyzn~~(2) xyzn (2)
现给出 n , p , w , d , 求是否存在一组 (x , y , z) 满足上式且都为非负数。
思路看到 (1) 式 不难想到扩欧去解 x , y 的通解 观察 (2) 式 可以发现我们要在满足条件的情况下使 (x y) 尽可能小 这样 z 才能最大可能的有解 。
已知了 x y 的通解 如何在满足条件(即 x , y 非负)的情况下使得 (x y) 最小呢
观察我们求出的通解 x x 0 ∗ p g c d ( w , d ) k ∗ d g c d ( w , d ) xx_0*{p\over gcd(w,d)}{k*d\over gcd(w,d)} xx0∗gcd(w,d)pgcd(w,d)k∗d y y 0 ∗ p g c d ( w , d ) − k ∗ w g c d ( w , d ) yy_0*{p\over gcd(w,d)}-{k*w\over gcd(w,d)} yy0∗gcd(w,d)p−gcd(w,d)k∗w
题目中有一个极其重要的条件 即d w , 即在 k 不断增大的时候 (x y) 的和是不断在变小的 我们可以根据 (y ≥ 0) 的条件算出满足条件的最大的 k 即算出了 (x y) 的最小值 判断是否有满足条件的 z 即可。 时间复杂度 O ( l o g n ) 时间复杂度O(logn) 时间复杂度O(logn)
易错点
1. 会爆 long long 用 __int128
2. 算出 k 带入通解求出 x 之后需要判断 x 是否合法。
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int __int128
const int N 2e6 10;
const int mod 1e9 7;
typedef pairint,intPII;inline void read(int n){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); chgetchar();}n x * f;
}
inline void write(int n){if(n 0){ putchar(-); n * -1; }if(n 9) write(n / 10);putchar(n % 10 0);
}int exgcd(int a , int b , int x , int y){if(b 0){ x 1; y 0; return a;}int g exgcd(b , a % b , y , x);y - a / b * x;return g;
}int n , p , w , d , g , x , y;signed main(){read(n);read(p);read(w);read(d);g exgcd(w , d , x , y);if(p % g){write(-1);}else{w / g;d / g;p / g;int k floor(1.0L * (y * p) / (1.0L * w));int xx x * p k * d;int yy y * p - k * w;if(xx yy n || xx 0){write(-1);}else{write(xx);putchar( );write(yy);putchar( );write(n - (xx yy));}}return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);D. Paint the Tree(树链 构造)
思路不难发现 要染色树必须是一条链 。 且确定一条链一侧的两个节点颜色后整条链的颜色就确定了 总共 6 种染色方案 依次遍历求最小值即可。 时间复杂度 O ( n l o g n ) 时间复杂度O(nlogn) 时间复杂度O(nlogn)
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N 2e6 10;
const int mod 1e9 7;
typedef pairint,intPII;
int val[N][4] , n , cnt , in[N] , lis[4];
vectorintve[N];
bool vis[N];
struct node{int x , ans;
}a[N];bool bfs(){queueintq;for(int i 1 ; i n ; i ){if(in[i] 1) {q.push(i);a[cnt].x i;vis[i] 1;break;}}while(q.size()){int now q.front();q.pop();for(auto k : ve[now]){if(vis[k]) continue;vis[k] 1;q.push(k);a[cnt].x k;}if(q.size() 1) return 0;}return 1;
}signed main(){cin n;for(int i 1 ; i 3 ; i ){for(int j 1 ; j n ; j ){cin val[j][i];}}for(int i 1 ; i n - 1 ; i ){int u , v;cin u v;in[u] 1;in[v] 1;ve[u].push_back(v);ve[v].push_back(u);}if(bfs()){int all 6;for(int i 0 ; i 3 ; i ) lis[i] i 1;int minn 9e18;while(all --) {int now 0;for(int i 1 ; i n ; i ){now val[a[i].x][lis[i % 3]];}if(now minn) {minn now;for(int i 1 ; i n ; i ){a[i].ans lis[i % 3];}}next_permutation(lis , lis 3);}sort(a 1 , a 1 n , [](node x , node y){return x.x y.x;});cout minn \n;for(int i 1 ; i n ; i ){cout a[i].ans ;}cout \n;}else{cout -1\n;}return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);E. Minimizing Difference(双指针 贪心)
思路不难发现 想要让 (max(a) - min(a)) 减小 1 , 每次操作就要让所有的最小值增加 1 或者 让所有的最大值 减小 1. 所以考虑每次贪心的操作最大值和最小值中少的那个 那么变化多少呢 以最小值为例 由于我们是以个数少为贪心的策略 当最小值变化到次小值的时候显然个数会发生变化 此时就要重新调整策略 故每次调整的上界就是和相邻值的差值 双指针维护即可。 时间复杂度 O ( n ) 时间复杂度O(n) 时间复杂度O(n)
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N 2e6 10;
const int mod 1e9 7;
typedef pairint,intPII;int n , k;
int a[N];signed main(){cin n k;for(int i 1 ; i n ; i ) cin a[i];sort(a 1 , a 1 n);int l 1 , r n;int cntl 1 , cntr 1;int now a[r] - a[l] , res 0;while(l r) {while(a[l] a[l 1]) l 1 , cntl 1;while(a[r] a[r - 1]) r - 1 , cntr 1;if(cntl cntr) {res (a[l 1] - a[l]) * cntl;if(k res) {k - res;now - (a[l 1] - a[l]);l 1;cntl 1;} else {int cntk k / cntl;now - cntk;break;}} else {res (a[r] - a[r - 1]) * cntr;if(k res) {k - res;now - (a[r] - a[r - 1]);r - 1;cntr 1;} else {int cntk k / cntr;now - cntk;break;}}} cout max(0ll , now) \n;return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);F. Chips(分类讨论 模拟)
思路 手模一下发现可以分类讨论 我们把环拆成两种序列。
第一种序列是 相邻元素相同的序列 例如 WWW , BBBBB
第二种序列是 两种元素交错出现的序列 例如 WBWBWBW
每次操作 第一种序列是不会改变的 而第二种序列会被两侧的第一种序列不断同化 每次操作第二种序列的长度减少 2
举例假如环是 WWBWBWBWW 我们可以把环拆成 WWWW 和 BWBWB
第一次操作序列会变成 WWWBWBWWW
第二次操作序列会变成 WWWWBWWWW
第三次操作序列会变成 WWWWWWWWW
举例假如环是 WWBWBWBB 我们可以把环拆成 WW BB 和 BWBW
第一次操作序列会变成 WWWBWBBB
第二次操作序列会变成 WWWWBBBB
如果 k 足够大 第二种序列会被前后的第一种序列同化 否则剩余的部分会根据 k 的奇偶性决定是否变化。
分三种情况讨论
1. 环上全是第一种序列 如何操作都不发生变化
2. 环上全是第二种序列 根据 k 的奇偶性发生变化。
3. 环中既有第一种序列也有第二种序列 考虑断环为链 取出环中所有的第二种序列 根据 序列的长度 与 操作次数的关系 分类讨论即可。 时间复杂度 O ( n l o g n ) 时间复杂度O(nlogn) 时间复杂度O(nlogn)
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N 2e6 10;
const int mod 1e9 7;
typedef pairint,intPII;int n , m ;
string s;
int vis[N] , now[N];int nex(int x) {return (x 1) % n;
}
int pre(int x){return (x - 1 n) % n;
}signed main(){cin n m s;for(int i 0 ; i n ; i ) {if(s[i] s[nex(i)]) {if(s[i] B) vis[i] vis[nex(i)] 1;else vis[i] vis[nex(i)] -1;}}int cnt 0;for(int i 0 ; i n ; i ) {if(vis[i]) cnt 1;}if(cnt n) {cout s \n;} else if (cnt 0) {if(m 1) {for(int i 0 ; i n ; i ) if(s[i] B) s[i] W; else s[i] B;}cout s \n;} else {settupleint , int , intinfo;for(int i 0 ; i 2 * n ; i ) {if(i n) now[i] vis[i];else now[i] vis[i - n];
// cout now[i] ;}
// cout \n;int l 0 , r 2 * n - 1;while(!now[l]) l 1;while(!now[r]) r - 1;
// cout l r \n;bool tag 0;int ans_l 0 , ans_r 0 , len 0;for(int i l ; i r ; i ) {if(now[i]) {if(!tag) continue;ans_r (i - 1) % n;info.insert({ans_l , ans_r , len});len 0;tag 0;continue;}if(!tag) {ans_l i % n;tag 1;len 1;} else {len 1;}}// for(int i 0 ; i n ; i ) cout vis[i] ; cout \n;for(auto [l , r , len] : info) {
// cout l r len \n;int typel vis[pre(l)];int typer vis[nex(r)];if(m (len 1) / 2) {for(int i 1 , j l , k r; i (len 1) / 2 ; i , j nex(j) , k pre(k)) {vis[j] typel;vis[k] typer;}} else {int j l , k r;for(int i 1 ; i m ; i , j nex(j) , k pre(k)) {vis[j] typel;vis[k] typer;}if(m 1) for(int i j ; i ! nex(k) ; i nex(i)) if(s[i] W) vis[i] 1 ; else vis[i] -1;else for(int i j ; i ! nex(k) ; i nex(i)) if(s[i] W) vis[i] -1 ; else vis[i] 1;}}for(int i 0 ; i n ; i ){if(vis[i] 1) cout B;else if(vis[i] -1) cout W;}}return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);/*
5 1
WBBWB
*/G. Running in Pairs (贪心 构造)
思路对于一个 n 我们不难发现其下界的 max 数组是 [ n , n − 1 , . . . , 2 , 1 ] [n ~,~ n-1~,~... ~~,~2~,~1] [n , n−1 , ... , 2 , 1]
即 ( n 1 ) ∗ n 2 \frac{(n1)*n}{2} 2(n1)∗n
其上界的 max 数组是 [ n , n , n − 1 , n − 1 , . . . , ( n 1 ) / 2 ] [n ~,~ n~, n-1~,n-1,~... ~~,~(n1)/2~] [n , n ,n−1 ,n−1, ... , (n1)/2 ]
即 ( n / 2 ) ∗ ( n 1 ( n 1 ) / 2 ) ( n 1 ) / 2 ∗ ( n 1 ) (n / 2) * (n 1 (n 1) / 2) (n 1) / 2 * (n~\~1) (n/2)∗(n1(n1)/2)(n1)/2∗(n 1)
而且显然上下界之间的数字都是能构造出来的
以 n 5 举例
上界[5 , 5 , 4 , 4 , 3] 21
下界[5 , 4 , 3 , 2 , 1] 15
15[5 , 4 , 3 , 2 , 1]16[5 , 5 , 3 , 2 , 1]17[5 , 5 , 4 , 2 , 1]18[5 , 5 , 4 , 3 , 1]19[5 , 5 , 4 , 4 , 1]20[5 , 5 , 4 , 4 , 2]21[5 , 5 , 4 , 4 , 3]
这样给出一个 k 值 我们对上下界区间 和 k 值进行分类讨论
1 : k 小于 下界 无解
2 : k 大于上界 取上界
3 : k 在上下界之间 我们可以根据其与上下界之间的差值构造出 max 数组 接下来的任务就是把 max 数组分成两个排列 。
如何把max数组分成两个排列呢 这里我们要用到贪心的思想。
首先把 max 数组中重复出现的元素放到第二个数组中 然后对于剩下的元素 我们用排列中未出现的元素进行填充 如何填充呢 考虑贪心的从大往小填充 因为 max 数组中大的也在前面 填充完第一个数组填充第二个数组即可。
例n 5 k 20
max 数组 [5 , 5 , 4 , 4 , 2]
分离
数组 1 [5 , 0 , 4 , 0 , 2]
数组 2 [0 , 5 , 0 , 4 , 0]
填充
数组 1 [5 , 3 , 4 , 1 , 2]
数组 2 [3 , 5 , 2 , 4 , 1]
这样贪心的填充是一定不会影响原来的 max 数组的值的。 时间复杂度 O ( n ) 时间复杂度O(n) 时间复杂度O(n)
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N 2e6 10;
const int mod 1e9 7;
typedef pairint,intPII;int n , k;int pre[N] , nex[N] , cnt[N] , ans[N];
bool vis[N];signed main(){cin n k;int l (n 1) * n / 2;int r (n / 2) * (n 1 (n 1) / 2) (n 1) / 2 * (n 1);// cout l r \n;if(k l) {cout -1\n;} else if(k r) {cout r \n;for(int i 1 ; i n ; i ) cout i ;cout \n;for(int i n ; i 1 ; i --) cout i ;cout \n;} else {cout k \n;for(int i 1 ; i n ; i ) pre[i] (n - i 1);for(int i 1 , j n ; i n ; i ) {nex[i] j;if(!(i 1)) j - 1;}int res k - l;for(int i 1 ; i n ; i ) {int now nex[i] - pre[i];if(now res) {res - now;pre[i] now;} else {pre[i] res;break;}}for(int i 1 ; i n ; i ) {if(vis[pre[i]]) {ans[i] pre[i];pre[i] 0;} else {vis[pre[i]] 1;}}for(int i 1 , j n ; i n ; i ) {while(vis[j]) j - 1;if(pre[i]) continue;vis[j] 1;pre[i] j;}for(int i 1 ; i n ; i ) vis[i] 0;for(int i 1 ; i n ; i ) vis[ans[i]] 1;for(int i 1 , j n ; i n ; i ) {while(vis[j]) j - 1;if(ans[i]) continue;vis[j] 1;ans[i] j;}for(int i 1 ; i n ; i ) cout ans[i] ;cout \n;for(int i 1 ; i n ; i ) cout pre[i] ;cout \n;}return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);/*
5 5 4 4 3
5 4 3 2 1
加不会溢出 减会溢出
*/
