Codeforces Round 914 (Div. 2)（A~D）

2023-12-12 16:04
文章标签 codeforces round div 914

本文主要是介绍Codeforces Round 914 (Div. 2)（A~D），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A - Forked! 

        

思路：定1求1，将所有能打到国王的棋子位置求出，看是否能打到王后。

 

// Problem: A. Forked!
// Contest: Codeforces - Codeforces Round 914 (Div. 2)
// URL: https://codeforces.com/contest/1904/problem/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
int tx[4] = {-1 , -1 , 1 , 1};
int ty[4] = {1 , -1 , 1 , -1};
void solve() 
{int a , b;cin >> a >> b;map<pair<int,int> , int>pl;int x1 , y1 , x2 , y2;cin >> x1 >> y1 >> x2 >> y2;int cnt = 0;for(int i = 0 ; i < 4 ; i ++){int nx = x1 + tx[i] * a;int ny = y1 + ty[i] * b;if((abs(x2 - nx) == a && abs(y2 - ny) == b) ||( abs(x2 - nx) == b && abs(y2 - ny) == a)){if(!pl.count({nx,ny})){cnt++;pl[{nx,ny}] = 1;}}}for(int i = 0 ; i < 4 ; i ++){int nx = x1 + tx[i] * b;int ny = y1 + ty[i] * a;if((abs(x2 - nx) == a && abs(y2 - ny) == b) ||( abs(x2 - nx) == b && abs(y2 - ny) == a)){if(!pl.count({nx,ny})){cnt++;pl[{nx,ny}] = 1;}}}cout << cnt << endl;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

B - Collecting Game  

        题意：

        思路： 假如只考虑对一个a_{i}操作，那么可以想到对a数组先进行一个排序，然后从小到大逐个删除元素，直到没法删除为止，这样是最优情况。接下来考虑如何对所有a_{i}操作：可以发现元素越大，最后所能移除的元素数量也是越大的，而且属于包含关系，因此可以从小到大的处理a中元素，并且由于是包含关系，所有元素公用一个分数即可。

        

// Problem: B. Collecting Game
// Contest: Codeforces - Codeforces Round 914 (Div. 2)
// URL: https://codeforces.com/contest/1904/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{cin >> n;vector<LL>ans(n , 0);vector<LL>pos(n , 0);for(int i = 0 ; i < n ; i ++){pos[i] = i;}	for(int i = 0 ; i < n ; i ++)cin >> a[i];auto cmp = [&](LL x , LL y){return a[x] < a[y];};sort(pos.begin() , pos.end() , cmp);LL sum = 0;int l = 0;for(int i = 0 ; i < n ; i ++){if(l == i){sum += a[pos[l]];l ++;}while(l < n && sum >= a[pos[l]]){sum += a[pos[l]];l++;}ans[pos[i]] = l - 1;}for(int i = 0 ; i < n ; i ++){cout << ans[i] << " ";}cout << endl;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

 

C - Array Game 

        题意：

        思路：可以发现，当操作数大于等于3时，一定能构造出0。第一步 c = a - b  ， 第二步 d = a - c ， 第三步 e = d - b = a - c - b= a - a - b - b  = 0。 当操作数为1时，最小值必定存在于原数组以及所有能构造出的数当中。当操作数为2时，观察数据发现可以暴力枚举，直接暴力枚举出所有可能构造出的数，然后模拟构造出的数在第二轮的情况。在第二轮的情况中，当前所构造出的数不需要与其他所有的数都操作，只需要与最接近它的两个数相操作即可。

// Problem: C. Array Game
// Contest: Codeforces - Codeforces Round 914 (Div. 2)
// URL: https://codeforces.com/contest/1904/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
#define int long long
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{cin >> n >> m;	for(int i = 0 ; i < n ; i ++)cin >> a[i];if(m >= 3){cout << 0 << endl;}else{sort(a.begin() , a.begin() + n);int maxx = 1e18 + 10;for(int i = 0 ; i < n ; i ++){maxx = min(maxx , a[i]);}if(m == 1){for(int i = 0 ; i < n - 1; i ++){maxx = min(maxx , a[i + 1] - a[i]);}cout << maxx << endl;}else{for(int i = 0 ; i < n ; i ++){for(int j = i + 1; j < n ; j ++){int res = a[j] - a[i];maxx = min(maxx , res);auto it = upper_bound(a.begin() , a.begin() + n , res);maxx = min(maxx , *it - res);if(it != a.begin()){it--;maxx = min(maxx , res - *it);}}}cout << maxx << endl;}}
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

D1 - Set To Max (Easy Version)  

        题意：

        思路:考虑不能的情况：

1、首先如果a_{i} > b_{i} , 那么将无法修改为b_{i}

2、其次若要将a_{i}修改为b_{i},需要找到数组a中等于b_{i}的数a_{j}。由于一次操作是取max[l , r],所以如果从 i - >j当中存在比b_{i}还要大的数，那么这个操作也是无法成立的。因此若想要操作成立，则需要j尽可能的靠近i，因此一次操作找出的j为最接近i的左右两个j。

        找出两个j以后，还需要考虑能否满足 i - >j当中的所有数，若 i - >j当中的某个下标b_{x} < b_{i},那么在该次操作中会使得a_{x} = b_{i} > b_{x},那么将变为情况1。同样，若i - >j当中的某个下标a_{x} > b_{i} , 那么会使得a_{i} = a_{x} > b_{i},同样变为情况1。

        接下来考虑怎么样的顺序去修改a最好：可以发现若按照数组b从小到大排序以后，先修改小的数，是不会影响后面的数的。若先修改大的数，可能会使得前面小的数变为情况1。

        整个题目变成了求数组中等于某个数的位置和若干区间内最大的数和最小的数。前者用set二分查找很方便，后者用ST表解决比较方便。

// Problem: D1. Set To Max (Easy Version)
// Contest: Codeforces - Codeforces Round 914 (Div. 2)
// URL: https://codeforces.com/contest/1904/problem/D1
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
int a[N];
int b[N];
int Max[N][21];
int Min[N][21];
struct ST{//RMQ问题void init(){for(int i = 1 ; i <= n ; i ++){Max[i][0] = a[i];Min[i][0] = b[i];}}void work(){for(int j = 1;j <= 21;j++)for(int i = 1;i + (1 << j) - 1 <= n ; i++){	            Max[i][j] = max(Max[i][j - 1] , Max[i + (1 << (j - 1))][j - 1]);Min[i][j] = min(Min[i][j - 1] , Min[i + (1 << (j - 1))][j - 1]);	}}int QueryMax(int l,int r){int k = log2(r-l+1); return max(Max[l][k],Max[r-(1<<k)+1][k]);//把拆出来的区间分别取最值 }	int QueryMin(int l , int r){int k = log2(r-l+1); return min(Min[l][k],Min[r-(1<<k)+1][k]);//把拆出来的区间分别取最值 		}
};
void solve() 
{cin >> n;set<int>pos[n + 5];vector<array<int,3>>v(n + 5);ST st;for(int i = 1 ; i <= n ; i ++)cin >> a[i] , pos[a[i]].insert(i);for(int i = 1 ; i <= n ; i ++)cin >> b[i] ,v[i][0] = b[i] ,  v[i][1] = a[i] , v[i][2] = i;sort(v.begin() + 1 , v.begin() + n + 1);st.init();st.work();for(int i = 1 ;i <= n ; i++){if(v[i][0] < v[i][1]){cout <<"NO\n";return;}else if(v[i][0] > v[i][1]){int flag = 0;int p = v[i][2];auto pr = pos[v[i][0]].upper_bound(p);if(pr != pos[v[i][0]].end()){int r = *pr;if(st.QueryMax(p ,r) == v[i][0] && st.QueryMin(p , r) == v[i][0]){flag = 1;}}if(flag == 0){if(pr != pos[v[i][0]].begin()){pr--;int l = *pr;if(st.QueryMax(l , p) == v[i][0] && st.QueryMin(l , p) == v[i][0]){flag = 1;}}}if(!flag){cout <<"NO\n";return;}}}cout <<"YES\n";
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

这篇关于Codeforces Round 914 (Div. 2)（A~D）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/485165。

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
Codeforces Round #261 (Div. 2)小记

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件，我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m
阅读更多...
Codeforces Beta Round #47 C凸包 （最终写法）

Codeforces Beta Round #47 C凸包 （最终写法）

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op
阅读更多...
Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A， 多边形B， 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包，如果凸包上的点是B的某个点，则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法，只需在求凸包的时候， <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int
阅读更多...
Codeforces 482B 线段树

Codeforces 482B 线段树

求是否存在这样的n个数； m次操作，每次操作就是三个数 l ，r，val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja
阅读更多...
CSS实现DIV三角形

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor
阅读更多...
创建一个大的DIV，里面的包含两个DIV是可以自由移动

创建一个大的DIV，里面的包含两个DIV是可以自由移动

创建一个大的DIV，里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;
阅读更多...
Codeforces Round 971 (Div. 4) (A~G1)

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单，不做解释 C 对于 x y 两个方向，每一个方向至少需要 x / k 向上取整的步数，取最大值。 由于 x 方向先移动，假如 x 方向需要的步数多于 y 方向的步数，那么最后 y 方向的那一步就不需要了，答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>
阅读更多...
CF#271 (Div. 2) D.（dp）

CF#271 (Div. 2) D.（dp）

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/474/problem/D We s
阅读更多...
CF #278 (Div. 2) B.（暴力枚举+推导公式+数学构造）

CF #278 (Div. 2) B.（暴力枚举+推导公式+数学构造）

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/488/problem/B There
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2