本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!