Codeforces Round 918 (Div. 4)（AK）

2023-12-29 08:36
文章标签 codeforces round div ak 918

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

A、模拟

B、模拟

C、模拟

D、模拟

E、思维，前缀和

F、思维、逆序对

G、最短路

A - Odd One Out 

    题意：给定三个数字，有两个相同，输出那个不同的数字。

    直接傻瓜写法

void solve() 
{int a , b , c;cin >> a >> b >> c;if(a == b){cout << c << endl;}	else if(a == c){cout << b << endl;}elsecout << a << endl;
}

 B - Not Quite Latin Square

        题意：给定一个3*3的矩阵，每一行每一列都有且仅有A、B、C三个字母组成。现在给出矩阵中有一个? , 求这个？代表哪个字母。

        可以用二进制表示三个字母是否存在

void solve() 
{string s[3];for(int i = 0 ; i < 3; i ++)cin >> s[i];for(int i = 0 ; i < 3 ;i ++){int mask = 0;for(int j = 0 ; j < 3 ; j ++){mask += (1 << (s[i][j] - 'A')) * (s[i][j] != '?');}if(mask != 7){for(int j = 0 ; j < 3 ; j ++){if((mask >> j) & 1){continue; }else{char c = j + 'A';cout << c <<endl;}}}}
}

C - Can I Square? 

        题意：给定一个数组，求数组之和能否形成完全平方数。

        注意：直接用sqrt会因为精度问题而出错，所以在[sqrt - 2 , sqrt + 2]之间都试一遍即可。

        

void solve() 
{LL sum = 0;cin >> n;for(int i = 0 ; i < n ; i ++){int x;cin >> x;sum += x;}	LL t = sqrt(sum);for(LL i = t - 1 ; i <= t + 1 ; i ++){if(i < 0)continue;if(i * i == sum){cout <<"YES\n";return;}}cout <<"NO\n";
}

 D - Unnatural Language Processing 

        题意：

        思路：将a、e看成0，b、c、d看成1。整个单词变成了一个01串，然后发现：当连续的两个1出现时，前一个1需要放到前面的音节结尾。当只有一个连续的1，那么这个1就是音节的开头。然后模拟整个过程就行。

        

// Problem: D. Unnatural Language Processing
// Contest: Codeforces - Codeforces Round 918 (Div. 4)
// URL: https://codeforces.com/contest/1915/problem/D
// 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;}
}
//10 101
void solve() 
{cin >> n;string s;cin >> s;for(int i = 0 ; i < n ; i ++){if(s[i] == 'a' || s[i] == 'e'){a[i] = 0;}else{a[i] = 1;}}for(int i = 0 ; i < n ; i ++){if(a[i] == 1){cout << s[i];}else if(a[i] == 0){if(i < n - 3){if(a[i + 1] == 1 && a[i + 2] == 1){cout << s[i] << s[i + 1] <<"."; i++;}else{cout << s[i] <<".";}}else if(i == n - 3){cout << s[i] <<".";}else if(i == n - 2){cout << s[i] << s[i + 1];i++;}else{cout << s[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;
}

E - Romantic Glasses 

        题意：给定一数组，求其中是否存在某个连续子序列是否满足\sum _{i = l}^{r}a[i](i\ mod\ 2==0) = \sum _{i = l}^{r}a[i](i\ mod\ 2 == 1)

        思路：转移之后有公式\sum _{i = l}^{r}a[i](i\ mod\ 2==0) + \sum _{i = l}^{r}-a[i](i\ mod\ 2 == 1) = 0，也就是对于原数组的奇数项都乘 -1 之后，求是否存在某个区间之和为0。

        用前缀和sum数组来表示区间，也就是存在sum(r) - sum(l) = 0 , 也就是sum(r) = sum(l)。因此我们可以逐步递增 r，然后看之前是否出现过sum(l) 与 sum(r)相等。可用map或者set来存之前出现过的前缀和情况。这样整个复杂度为O(NlogN)

        

// Problem: E. Romantic Glasses
// Contest: Codeforces - Codeforces Round 918 (Div. 4)
// URL: https://codeforces.com/contest/1915/problem/E
// 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'
#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;for(int i = 0 ; i < n ; i ++){cin >> a[i];if(i % 2 == 1){a[i] *= -1;}}	set<int>pre;pre.insert(0);int sum = 0;for(int i = 0 ; i < n ; i ++){sum += a[i];//cout << sum << endl;if(pre.count(sum)){cout <<"YES\n";return;}pre.insert(sum);}cout <<"NO\n";return;
}            
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;
}

 F - Greetings 

        题意：

        思路：将所有人的起点按照从小到大进行排序，这样就满足了后面的人不会撞到前面的人（只存在后面的人已经到达终点了，然后被前面的人撞）。然后再考虑能够撞多少个人：对于排完序以后的第i个人而言，他能撞到的人是i以后的，终点小于等于b_{i}的人。因此也就是(b_{i} \geq b_{j})(i < j)的个数，也就是按照起点排完序之后的b数组的逆序对数量，然后套一遍逆序对的板子即可。

// Problem: F. Greetings
// Contest: Codeforces - Codeforces Round 918 (Div. 4)
// URL: https://codeforces.com/contest/1915/problem/F
// Memory Limit: 256 MB
// Time Limit: 5000 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;}
}
int tmp[N];
LL merge_sort(int q[], int l, int r)
{if (l >= r) return 0;int mid = (l + r) >> 1; // 二分区间LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);//归并int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r){if (q[i] <= q[j]) tmp[k ++] = q[i ++]; // 前面的排序正常，注意`=` 说明不是逆序对else{res += mid - i + 1;tmp[k ++] = q[j ++];}}// 扫尾工作while (i <= mid) tmp[k ++] = q[i ++];while (j <= r) tmp[k ++] = q[j ++];for (int i = l, j = 0; i <= r; i ++ , j ++) q[i] = tmp[j];return res;
}
void solve() 
{cin >> n;pair<int,int>po[n];for(int i = 0 ; i < n ; i++){cin >> po[i].x >> po[i].y;}	sort(po , po + n);int a[n];for(int i = 0 ; i < n ; i ++){a[i] = po[i].y;}LL ans = merge_sort(a , 0 , n  - 1);cout << ans <<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;
}

 G - Bicycles 

        题意：

       

        思路：观察到数据不大。因此直接考虑最短路算法。需要注意的是，整个过程不仅仅有点这一个条件，还有自行车速度系数这个限制。因此需要将这两个限制都表示出来，具体看代码注释

// Problem: G. Bicycles
// Contest: Codeforces - Codeforces Round 918 (Div. 4)
// URL: https://codeforces.com/contest/1915/problem/G
// Memory Limit: 256 MB
// Time Limit: 4000 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 = 1010;
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;}
}
struct node{int num;int dis;bool operator > (const node &t) const{return dis > t.dis;}int own;
}tmp;
int dis[N][N];//到达i点，且拥有自行车系数j的最短距离
int vis[N][N];//到达i点，且拥有自行车系数j的可能性
vector<node>tr[N];
int cost[N];
void dij(int s)
{for(int i = 1 ; i <= n ; i ++){for(int j = 0 ; j <= 1000 ; j ++){dis[i][j] = llinf;}}priority_queue<node,vector<node> , greater<node> > q;q.push({s , 0 , cost[1]});dis[s][cost[1]] = 0;while(!q.empty()){tmp = q.top();int x = tmp.num;//所在地int y = tmp.own;//拥有的自行车系数q.pop();if(vis[x][y] == 1)continue;vis[x][y] = 1;for(int i = 0 ; i < (int)tr[x].size() ; i ++ ){node now = tr[x][i];int len = tr[x][i].dis;//距离int e = tr[x][i].num;//目标地int pp = min(y , cost[e]);//到达目的地之后所拥有的自行车系数if(dis[e][pp] > dis[x][y] + len * y){dis[e][pp] = dis[x][y] + len * y;q.push({e , dis[e][pp] , pp});}}}
}
void solve() 
{cin >> n >> m;for(int i = 1 ; i <= n ; i ++){tr[i].clear();for(int j = 0 ; j <= 1000 ; j ++){vis[i][j] = 0;}}for(int i = 0 ; i < m ; i ++){int u , v , dis;cin >> u >> v >> dis;tr[u].pb({v , dis , 0});tr[v].pb({u , dis , 0});}for(int i = 1 ; i <= n ; i ++){cin >> cost[i];}dij(1);int ans = llinf;for(int i = 0 ;i <= 1000 ;  i++){ans = min(ans , dis[n][i]);}cout << ans << 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;
}

        

        

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


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

相关文章

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