Codeforces Round #839 (Div. 3) A~G all answer

2024-03-26 22:20
文章标签 codeforces round div answer 839

本文主要是介绍Codeforces Round #839 (Div. 3) A~G all answer,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Dashboard - Codeforces Round #839 (Div. 3) - Codeforces

        最近状态奇差无比,还有点生病,低烧反复横跳,应该没阳?(虽然家人都阳了,就剩我一个了wuwuwu~(A B C就不作解释了,看下题面和代码应该就能懂~)

———————————————————————————————————————————

目录

A. A+B?

B. Matrix Rotation

C. Different Differences

 D. Absolute Sorting

E. Permutation Game

F. Copy of a Copy of a Copy

G. Gaining Rating


A. A+B?

/*Looking! The blitz loop this planet to search wayOnly my RAILGUN can shoot it 今すぐ身体中を  光の速さで駆け巡った確かな予感掴め! 望むものなら残さず輝ける自分らしさで信じてるよ  あの日の誓いをこの瞳に光る涙それさえも  強さになるから*/
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
int n,t;
inline __int128 read(){__int128 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 * 10 + ch - '0';ch = getchar();}return x * f;
}
inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print(x / 10);putchar(x % 10 + '0');
}void wanyurukong(){string s;cin>>s;printf("%d\n",s[0]+s[2]-2*'0');
}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {wanyurukong();}//wanyurukongreturn 0;
}

B. Matrix Rotation

/*Looking! The blitz loop this planet to search wayOnly my RAILGUN can shoot it 今すぐ身体中を  光の速さで駆け巡った確かな予感掴め! 望むものなら残さず輝ける自分らしさで信じてるよ  あの日の誓いをこの瞳に光る涙それさえも  強さになるから*/
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
int n,t;
inline __int128 read(){__int128 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 * 10 + ch - '0';ch = getchar();}return x * f;
}
inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print(x / 10);putchar(x % 10 + '0');
}int a1,a2,a3,a4;
void wanyurukong(){cin>>a1>>a2>>a3>>a4;for (int i =0; i<4; i++) {if (a1<a2&&a3<a4&&a1<a3&&a2<a4) {printf("YES\n");return;}swap(a1, a2);swap(a1, a3);swap(a3, a4);}printf("NO\n");
}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {wanyurukong();}//wanyurukongreturn 0;
}

C. Different Differences

/*Looking! The blitz loop this planet to search wayOnly my RAILGUN can shoot it 今すぐ身体中を  光の速さで駆け巡った確かな予感掴め! 望むものなら残さず輝ける自分らしさで信じてるよ  あの日の誓いをこの瞳に光る涙それさえも  強さになるから*/
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
int n,t;
inline __int128 read(){__int128 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 * 10 + ch - '0';ch = getchar();}return x * f;
}
inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print(x / 10);putchar(x % 10 + '0');
}
int k;
int ssr[1005];
void wanyurukong(){cin>>n>>k;int kl=1;int ff=0;int jk=1;ssr[1]=1;for (int i =2; i<=n; i++) {ssr[i] = ssr[i - 1] + jk;jk++;if (ssr[i]  > k+i-n) {ssr[i] = ssr[i - 1] + 1;jk--;}}for (int i =1; i<=n; i++) {printf("%d ",ssr[i]);}printf("\n");
}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {wanyurukong();}//wanyurukongreturn 0;
}

 D. Absolute Sorting

题目:

您将得到一个由𝑛个整数组成的数组𝑎。

你想让数组𝑎通过应用下面的操作进行排序:

选择一个整数𝑥,然后为每个𝑖∈(1,𝑛),取代𝑎𝑖由|𝑎𝑖−𝑥|。
找到任何将使数组排序的𝑥值,或者报告没有这样的值。

排序成𝑎1≤𝑎2≤⋯≤𝑎𝑛。

思路:如果a[i]>=a[i-1],那么当他们减去 (a[i]+a[i-1])/2 ,仍然会保持这种状态,这是可以减去的最大值,如果比这个值大,就会打破原有状态,所以我们需要取可以维护这种状态的最小值,如果a[i-1]>a[i],最小减去(a[i]+a[i-1]+1)/2,则会将其反转过来,变成a[i]>a[i-1],所以我们要全部将其反转,不断取其最大值,所以我们需要所以我们需要保证数组中a[i]>=a[i-1]的状态,反转a[i-1]>a[i]的状态即可,所以我们只需要遍历一遍,在反转所有的同时,还维护原有的情况时否存在即可。

代码:

/*Looking! The blitz loop this planet to search wayOnly my RAILGUN can shoot it 今すぐ身体中を  光の速さで駆け巡った確かな予感掴め! 望むものなら残さず輝ける自分らしさで信じてるよ  あの日の誓いをこの瞳に光る涙それさえも  強さになるから*/
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
int n,t;
inline __int128 read(){__int128 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 * 10 + ch - '0';ch = getchar();}return x * f;
}
inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print(x / 10);putchar(x % 10 + '0');
}ll a[200005];
void wanyurukong(){cin>>n;for (int i =1; i<=n; i++) {cin>>a[i];}ll ff=1e8+5,fl=0;for (int i =2; i<=n; i++) {if (a[i]>a[i-1]) {ff=min(ff, (a[i]+a[i-1])/2);}else if(a[i-1]>a[i]){fl=max(fl, (a[i]+a[i-1]+1)/2);}}if (ff>=fl) {printf("%lld\n",ff);}else{printf("-1\n");}
}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {wanyurukong();}//wanyurukongreturn 0;
}

E. Permutation Game

题意:

两个玩家在玩游戏。它们有一个整数的排列1 2…,𝑛(排列是一个数组,其中从1到𝑛的每个元素恰好出现一次)。排列不是按升序或降序(即。排列没有形式[1,2,…,𝑛]或[𝑛,𝑛−1,…,1])。

最初,排列的所有元素都是红色的。选手们轮流上场。在他们的回合中,玩家可以做以下三种行动之一:

重新排列排列的元素,使所有红色元素保持它们的位置(注意,蓝色元素可以相互交换,但这不是强制性的);
将一个红色元素的颜色改为蓝色;
跳过。
如果排列是按升序排列的(即第一个玩家赢。它变成[1,2,…,𝑛])。如果排列是按降序排列的,那么第二个玩家获胜。变成[𝑛,𝑛−1,…,1])。如果游戏持续100500回合,没有人赢,则以平局结束。

你的任务是确定游戏的结果,如果两个玩家都玩得很好。

思路:

每次改颜色,或者重新排列,或者跳过。想赢的话,就需要把每个不符合自己位置的染色排列。

这就出现了两种情况,一种是一个人需要染色这个,另一种是两个人都需要染色这个,最优的情况肯定是先染自己需要染的,因为共同染的,对方也想赢,如果对方自己染的已经染完了,为了胜利就会去染共同的对吧。

这时候我们模拟一下,就会发现,如果都将自己的染完,最后一起染共同的,那么当剩最后一块的时候,谁染谁输,因为染色过后就可以排列了,所以在这种情况下就是平局对吧?

那么怎么样才能赢了,如果第一个人独自需要染的+共同染的<=第二个人要染的,这种情况下第一个人就能赢,因为是第一个人先手,同时染完,那么第一个人就直接排列 胜利。

第二个人同理,第二个人独自需要染的+共同染的<第一个人要染的。

代码:

/*Looking! The blitz loop this planet to search wayOnly my RAILGUN can shoot it 今すぐ身体中を  光の速さで駆け巡った確かな予感掴め! 望むものなら残さず輝ける自分らしさで信じてるよ  あの日の誓いをこの瞳に光る涙それさえも  強さになるから*/
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
int n,t;
inline __int128 read(){__int128 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 * 10 + ch - '0';ch = getchar();}return x * f;
}
inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print(x / 10);putchar(x % 10 + '0');
}int a[500005];
int b[500005];
int c[500005];
bool cmp(int a,int b){return a>b;
}
void wanyurukong(){cin>>n;for (int i =1; i<=n; i++) {cin>>a[i];b[i]=a[i];c[i]=a[i];}sort(b+1, b+1+n,cmp);sort(c+1, c+1+n);int a1=0,b1=0;map<int,int>q;for (int i=1  ; i<=n; i++) {if (a[i]!=b[i]) {a1++;q[i]++;}}for (int i =1; i<=n; i++) {if (a[i]!=c[i]) {b1++;q[i]++;}}int xu=0;int ff=0;for(auto [x,y]:q){if (y==0) {xu++;}if (y==2) {ff++;}}a1-=ff;b1-=ff;
//    printf("%d %d %d\n",a1,b1,ff);
//    if ((a1==n&&b1>=n-1)&&(a1+xu==b1||b1+xu==a1)) {
//        printf("Tie\n");return;
//    }
//
////    if (xu>=ff) {
//        printf("Tie\n");return;
//    }if (b1+ff<=a1) {printf("First\n");}else if(a1+ff<b1){printf("Second\n");}else{printf("Tie\n");}}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {wanyurukong();}//wanyurukongreturn 0;
}

F. Copy of a Copy of a Copy

题意:

这一切都始于一张黑白图片,可以表示为𝑛×𝑚矩阵,其所有元素都是0或1。行编号为1 ~𝑛,列编号为1 ~𝑚。

对图片执行了几种操作(可能是0),每种操作都是以下两种:

1 选择一个不在边框上的单元格(既不是第1行或𝑛,也不是第1列或𝑚),它被四个相反颜色的单元格包围(如果是1,则是4个0,反之亦然),并将其本身涂成相反的颜色;
2 复制当前图片。
注意,操作的顺序可以是任意的,它们不一定是交替的。

您将看到结果:已生成的所有𝑘副本。此外,你会得到最初的图片。但是,所有𝑘+1的图片都被打乱了。

恢复操作顺序。如果有多个答案,打印其中任何一个。这些测试是根据实际的操作序列构造的,即。至少有一个答案总是存在的。


思路:实际操作序列,我们找到初始的第一个,然后拿第一个与之后的比较,然后排序,模拟即可。

那么第一个要怎么找呢,对矩阵有影响的只有操作一,那么对于操作一,我们发现它不具有可逆性,那么肯定是可操作是逐渐变少,所以我们拿可改变性最多的当初始即可,这个仔细想一下的就能懂什么的了。

之后我们再与其一一比较,排序,按顺序模拟即可。(结构体排序,vector或者queue套结构体也可以,此代码用的重载优先队列+vector元组,看起来比较奇怪可能~?

代码:

/*Looking! The blitz loop this planet to search wayOnly my RAILGUN can shoot it 今すぐ身体中を  光の速さで駆け巡った確かな予感掴め! 望むものなら残さず輝ける自分らしさで信じてるよ  あの日の誓いをこの瞳に光る涙それさえも  強さになるから*/
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
int n,t;
inline __int128 read(){__int128 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 * 10 + ch - '0';ch = getchar();}return x * f;
}
inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print(x / 10);putchar(x % 10 + '0');
}char as[105][35][35];
ll ff[105];
int m,k;
struct cc{bool operator()(pair<int, int>a,pair<int, int>b){return a.first>b.first;}
};
void wanyurukong(){cin>>n>>m>>k;for (int i =0; i<=k; i++) {ff[i]=0;}
//    cin>>as[0][0];
//    printf("%d %d %d",n,m,k);for (int i =0; i<=k; i++) {for (int j =0; j<n; j++) {cin>>as[i][j];
//            printf("i:%d %d %s\n",i,j,as[i][j]);}}if (k==0) {printf("1\n0\n");return;}
//    for (int i =0; i<=k; i++) {
//        for (int j =0; j<n; j++) {
//            printf("%s\n",as[i][j]);
//        }
//    }
//for (int i =0; i<=k; i++) {for (int j =1; j<n-1; j++) {for (int d=1; d<m-1; d++) {if (as[i][j][d]==as[i][j+1][d]) {continue;}if (as[i][j][d]==as[i][j-1][d]) {continue;}if (as[i][j][d]==as[i][j][d+1]) {continue;}if (as[i][j][d]==as[i][j][d-1]) {continue;}ff[i]++;}}}int ssr=0;for (int i =1; i<=k; i++) {if (ff[i]>ff[ssr]) {ssr=i;}}
//    for (int i =0; i<=k; i++) {
//        printf("%lld\n",ff[i]);
//    }priority_queue<pair<int,int>,vector<pair<int,int>>,cc>q;for (int i =0; i<=k; i++) {int kkl=0;for (int j=0; j<n; j++) {for (int d=0; d<m; d++) {if (as[i][j][d]!=as[ssr][j][d]) {kkl++;}}}q.push({kkl,i});}vector<tuple<int,int,int>>ans;printf("%d\n",ssr+1);pair<int, int>ff,now;
//    while (!q.empty()) {
//        printf("%d %d\n",q.top().first,q.top().second);q.pop();
//    }while (q.size()!=1) {ff=q.top();q.pop();now=q.top();for (int j=0; j<n; j++) {for (int d=0; d<m; d++) {if (as[ff.second][j][d]!=as[now.second][j][d]) {ans.push_back({1,j+1,d+1});}}}ans.push_back({2,now.second+1,-9});}printf("%lu\n",ans.size());for (int i =0; i<ans.size(); i++) {printf("%d %d ",get<0>(ans[i]),get<1>(ans[i]));if (get<2>(ans[i])!=-9) {printf("%d",get<2>(ans[i]));}printf("\n");}}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();t=1;while (t--) {wanyurukong();}//wanyurukongreturn 0;
}

G. Gaining Rating

题意:

Monocarp在一个流行网站上下棋。他有𝑛个可以一起玩的对手。𝑖-th对手的等级等于𝑎𝑖。Monocarp的初始评级是𝑥。Monocarp想要提高他的评级值𝑦(𝑦>𝑥)。

当Monocarp与对手对抗时,如果他当前的评级大于或等于对手的评级,他将获胜。如果Monocarp赢了,他的评分增加1,否则减少1。对手的评分不会改变。

Monocarp想要获得评级𝑦玩尽可能少的游戏。但他不能只是磨磨蹭蹭,和弱小的对手比赛。这个网站有一个规则,你应该尽可能平等地与所有对手比赛。正式地说,如果Monocarp想要对阵对手𝑖,就不应该有其他对手𝑗,这样Monocarp对阵𝑖的比赛次数就会比对阵𝑗的比赛次数多。

计算Monocarp获得评级𝑦所需的最小游戏数量,否则就说这是不可能的。注意,Monocarp对手的评级没有变化,而Monocarp的评级却发生了变化。

思路:我们看一下题目+样例,就可以判断出不可能的情况,我们可以首先将其剔除。当可以加的平分小于等于减去的评分,那么就将无法到达期望的评级。但是要判断一个在还未减的过程中,直接到达y。

之后,每轮我们都可以加到分,我们如果获胜赢下一个,那便可以一直加,如果下一个评级比我们加的+x大的话,那么之后都是输的。不过我们每轮可以加上赢得和输掉的差值,知道可与获胜,根据这个直接模拟即可。(但是需要多注意些细节!

代码:

/*Looking! The blitz loop this planet to search wayOnly my RAILGUN can shoot it 今すぐ身体中を  光の速さで駆け巡った確かな予感掴め! 望むものなら残さず輝ける自分らしさで信じてるよ  あの日の誓いをこの瞳に光る涙それさえも  強さになるから*/
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
int n,t;
inline __int128 read(){__int128 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 * 10 + ch - '0';ch = getchar();}return x * f;
}
inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print(x / 10);putchar(x % 10 + '0');
}ll x,y;
ll a[200005];
void wanyurukong(){cin>>n>>x>>y;for (int i =1; i<=n; i++) {cin>>a[i];}sort(a+1, a+1+n);int j=-1;ll an=0;ll ff=x;ll k=0;for (int i =1; i<=n; i++) {if (a[i]<=ff) {ff++;j=i;}}
//    printf("%d\n",j);if (j<=n-j&&ff<y) {printf("-1\n");return;}j=1;ff=0;ll df;while (1) {while (j<=n&&a[j]<=x+k) {j++;k++;}if (x+k>=y||j==n+1) {an+=y-x;printf("%lld\n",an);return;}ff=k-(n-k);
//        printf("%d\n",j);df=(min(y,a[j])-x-k+ff-1)/ff;an+=n*df;
//        printf("%lld %lld %lld\n",an,df,ff);x+=df*ff;}}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {wanyurukong();}//wanyurukongreturn 0;
}

感觉最近菜的不行,,,,,不对一直都菜的不行

这篇关于Codeforces Round #839 (Div. 3) A~G all answer的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/850036

相关文章

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)小记

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凸包 (最终写法)

题意慢慢看。 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 判断多边形是否在凸包内

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

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三角形

本文内容收集来自网络 #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是可以自由移动 <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)

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)

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.(暴力枚举+推导公式+数学构造)

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