Codeforces Round #648(Div.2) 1365 ABCDEF 문제 해결
파티원 링크 Cue 하기:
핵심 선수:https://me.csdn.net/qq_43559193
핵심 선수:https://me.csdn.net/weixin_43916298
경기 링크:https://codeforces.ml/contest/1362
카탈로그
A. Matrix Game
제목 대의:
제목:
Code:
B. Trouble Sort
제목 대의:
제목:
Code:
C. Rotation Matching
제목 대의:
제목:
D. Solve The Maze
제목 대의:
제목:
Code:
E. Maximum Subsequence Value
제목 대의:
제목:
Code:
F. Swaps Again
제목 대의:
제목:
Code:
A. Matrix Game
제목 대의:
두 사람이 게임을 하면 각자 돌을 놓을 수 있다. 돌을 놓을 수 있는 요구는 해당 줄이나 이 열에 돌이 없으면 돌을 놓을 수 없는 사람이 실패하는 것이다.
초기 바둑판 레이아웃을 제시하다
쌍방이 모두 최우선의 전략을 채택하여 누가 이길 수 있느냐고 묻다.
제목:
바둑 이론이잖아.
이 문제를 다시 결합하면 A문제이니 그리 어려운 바둑은 아닐 것이다.
필수태는 매우 쉬운데, 행과 열이 없기 때문에, 행과 열의 최소치를 보아라
짝짓기를 판단하시면 됩니다.
Code:
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include
#include
#include
#include
#include
#include
#define debug(x) cout<'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll mp[105][105];
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);read(m);
for(int i=1;i<=n;i++){
for(int k=1;k<=m;k++)
read(mp[i][k]);
}
ll ans = 0,ans1 = 0;
for(int i=1;i<=n;i++){
ll p = 0;
for(int k=1;k<=m;k++){
if(mp[i][k]) break;
if(k == m) ans++;
}
}
for(int k=1;k<=m;k++){
for(int i=1;i<=n;i++){
if(mp[i][k]) break;
if(i == n) ans1++;
}
}
ll temp = min(ans,ans1);
if(temp&1) printf("Ashish
");
else printf("Vivek
");
}
return 0;
}
/**
1[2[a]3[b]4[1[b]2[c]]]
aabbb[bccb
**/
B. Trouble Sort
제목 대의:
a수조와 b수조를 제시하면ai와aj는 교환할 수 있고 b만 교환할 수 있습니다!=bj
b 배열은 0, 1만 포함
몇 번의 교환을 통해 a수 그룹이 단조롭고 떨어지지 않도록 할 수 있느냐고 물었다
제목:
먼저 하나의 결론을 알 수 있다. 01은 반드시 존재할 수 있다. (옛 결론, 믿지 않으면 증명할 수 있다. 모든 교환된 원소는 하나의 원소를 통해 교환할 수 있고 양자의 교환을 실현할 수 있다)
01이 동시에 존재하지 않으면 원수조의 질서를 볼 수 밖에 없다
Code:
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include
#include
#include
#include
#include
#include
#define debug(x) cout<'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll a[maxn],b[maxn];
struct node{
ll w;
int id;
}save[maxn];
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);
int f = 0;
a[0] = -1;
for(int i=1;i<=n;i++){
read(a[i]);
if(a[i] C. Rotation Matching
제목 대의:
a, b 두 개의 그룹을 보여 줍니다. 매번 a가 왼쪽으로 이동하거나 오른쪽으로 k자리를 이동할 수 있도록 (k는 임의의 값을 얻는다) 최대 몇 개의ai=bi가 있는지 물어보세요.
제목:
우선, 이동 위치의 제한이 없기 때문에 오른쪽으로 이동하면 왼쪽으로 이동하는 것을 대체할 수 있다
그래서 b가 변하지 않도록 제어하여 a를 오른쪽으로 이동시킨다. 이때 최대 n-1위가 이동하고 n-1위가 넘으면 하나의 순환절이 된다.
그래서 숫자마다 몇 자리를 이동해야 b의 숫자와 대응할 수 있는지 한번 볼게요.
마지막으로 이동 비트 공헌의 최대치를 구하면 숫자 개수입니다.
하나의 경험: 전체 배열의 문제를 많이 풀었는데, 기본적으로 위치와 관계가 있다. 왜냐하면 전체 배열의 위치->값은 일일이 비치기 때문이다.
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include
#include
#include
#include
#include
#include
#define debug(x) cout<'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll a[maxn],b[maxn];
int pos[maxn];
int val[maxn];
int main(){
read(n);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++){
read(b[i]);
pos[b[i]] = i;
}
for(int i=1;i<=n;i++){
int temp = pos[a[i]];
if(temp>=i) val[temp-i]++;
else val[n-i+temp]++;
}
int maxl = 0;
for(int i=0;i<=n-1;i++){
maxl = max(maxl,val[i]);
}
printf("%d
",maxl);
return 0;
}
/**
1[2[a]3[b]4[1[b]2[c]]]
aabbb[bccb
**/ D. Solve The Maze
제목 대의:
지도 한 장 주세요. G는 좋은 사람이고, B는 나쁜 사람이고,공터다 #벽이다 끝은 n,m
몇몇 점을 벽으로 만들어 모든 좋은 사람들이 결승점에 도달할 수 있고 모든 나쁜 사람들이 결승점에 도달할 수 없느냐고 물었다.
제목:
나쁜 놈들을 봉쇄해서 모든 좋은 사람들이 결승점에 도달할 수 있는지 없는지를 생각하면 된다
어떻게 봉쇄하느냐가 문제고, 여기도 무모하다. 우선 욕심을 내어 좋은 사람에게 미치는 영향을 최소화하려면 봉쇄의 범위가 가장 작아야 한다고 생각한다.
그래서 우선 B가 종점에 도달할 수 있는지를 고려해야 한다. 만약에 종점에 도착하지 않으면 봉쇄할 필요가 없다.
종점에 도착하면 무모하게 이웃의 네 점을 봉쇄한다.
그러나 지나간 후에 어떤 남자가 이것이 정확하다는 것을 증명할 수 있는지 평론 구역에서 토론할 수 있다. (나는 출구를 봉쇄하고 출구를 봉쇄하지 않는다고 느낀다. 출구를 봉쇄하지 않으면 도착할 수 없기 때문이다. 그러나 이때 출구를 봉쇄하면 좋은 사람이 생길 수 있다. 그러나 이런 상황에 대해 나는 복잡하게 생각하는지 어떻게 생각하는지 모르겠다)
봉쇄한 후에 모든 좋은 사람들이 도착할 수 있는지 다시 한 번 보면 된다
Code:
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include
#include
#include
#include
#include
#include
#define debug(x) cout<'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
char mp[105][105];
int visp[55][55];
int vis[55][55];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
int judge(int x,int y){
if(x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]!='#') return 1;
return 0;
}
int bfs(int sx,int sy){
queue>q;
for(int i=1;i<=n;i++){
for(int k=1;k<=m;k++){
vis[i][k] = 0;
}
}
if(mp[sx][sy] == '#') return 0;
q.push({sx,sy});
vis[sx][sy] = 1;
while(!q.empty()){
auto u = q.front();q.pop();
int x = u.first,y = u.second;
for(int i=0;i<4;i++){
int mx = x+dx[i],my = y+dy[i];
if(judge(mx,my)&&!vis[mx][my]){
q.push({mx,my});
vis[mx][my] = 1;
}
}
}
return vis[n][m];
}
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);read(m);
memset(visp,0,sizeof(visp));
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
bfs(n,m);
for(int i=1;i<=n;i++){
for(int k=1;k<=m;k++){
if(mp[i][k] == 'B'&&vis[i][k]) visp[i][k] = 1;
}
}
int f = 0;
for(int i=1;i<=n;i++){
for(int k=1;k<=m;k++){
if(visp[i][k]){
for(int j=0;j<4;j++){
int mx = i +dx[j],my = k+dy[j];
if(judge(mx,my)){
if(mp[mx][my] == 'G') f = 1;
mp[mx][my] = '#';
}
}
}
}
}
bfs(n,m);
for(int i=1;i<=n;i++){
for(int k=1;k<=m;k++){
if(mp[i][k]=='G'&&!vis[i][k]) f = 1;
}
}
if(f) printf("No
");
else printf("Yes
");
}
return 0;
}
/**
3
011
100
111
**/
E. Maximum Subsequence Value
제목 대의:
길이가 k라고 가정한 하위 서열의 원소를 2진법으로 나누는 하위 서열을 선택하십시오.
만약 i위의 1의 개수>=max(k-2,1)가 있다면 이 자리는 2^i를 공헌할 것입니다
-- 서열의 최대 공헌은 얼마인가.
제목:
k는 1, 2, 3만 받을 수 있습니다.
여기서 증명해 봅시다.
사실 123은 분명히 성립되므로 3보다 큰 사람은 123보다 큰 공헌을 하지 않는다는 것을 증명하기만 하면 된다
만약 서열이 i위에서 만족하지 않는다면, 원소의 개수를 늘리면, 새로 추가된 원소는 이 위치에서 0 또는 1일 수밖에 없다
0이면 서열 길이 1 증가, 제한 조건 max(k-2,1)도 1 증가, 그러나 이 위치는 증가하지 않아 공헌하지 않습니다
1이면 서열 길이 1 증가, 제한조건 max(k-2,1)도 1 증가, 이 비트 증가 +1, 이전에 만족하지 않았기 때문에 지금도 만족하지 않습니다
따라서 길이가 3인 서열에 있어 그 위에 원소를 확충하려면 만족하는 것은 만족하고 만족하지 않는 것은 만족하지 않기 때문에 확충은 소용없다.
그래서 1, 2, 3의 상황만 생각하면 돼요.
Code:
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include
#include
#include
#include
#include
#include
#define debug(x) cout<'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll num[maxn];
ll c[65];
vectorv;
int main(){
read(n);
ll maxl = 0;
for(int i=1;i<=n;i++){
read(num[i]);
maxl = max(maxl,num[i]);
for(int k=0;k<=62;k++) c[k] += ((num[i]>>k&1)?1:0);
}
for(int i=1;i<=n;i++){
for(int k=i+1;k<=n;k++){
maxl = max(maxl,num[i]|num[k]);
}
}
for(int i=1;i<=n;i++){
for(int k=i+1;k<=n;k++){
for(int j=k+1;j<=n;j++){
maxl =max(maxl,((num[i]|num[k])|num[j]));
}
}
}
printf("%lld
",maxl);
return 0;
}
/**
3
011
100
111
**/ F. Swaps Again
제목 대의:
a수조와 b수조를 제시하고 매번 a수조를 조작하여 전 k개와 후 k개를 교환할 수 있다(k
몇 번 교환한 후에 수조b를 얻을 수 있는지 물어보세요.
제목:
이게 규칙이나 결론 문제일 것 같은데?
먼저 x와 y가 대칭적이라면 아무리 교환해도 여전히 대칭적인 성질을 발견해야 한다.
1 2 5 6: 1 대응 6, 2 대응 5
교환 후:
5, 6, 1, 2, 1 여전히 대응 6, 2 여전히 대응 5
그래서 우리는 b수조의 대응 관계만 볼 수 있다. 만약에 a수조가 이 모든 대응 관계를 만족시킬 수 있다면 각 조의 대응 관계는 어떻게 교환해도 얻을 수 있다.
그래서 대칭적 판단만 생각해보면 돼요. 어떻게 대칭적 판단을 해요?
a_i는 너무 크지만 n은 확실히 작아서 a 를i 이산화, 2차원 그룹으로 표시
a[x][y] x가 y에 대응하는 관계가 몇 개인지 표시해 주세요.
a의 관계가 모두 만족할 수 있는지 보면 된다. 이때 관계는 양방향이므로 양방향 판단이 필요하다.
Code:
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include
#include
#include
#include
#include
#include
#define debug(x) cout<'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll num[maxn];
ll judge[505][505];
vectorv;
int getid(ll x){
return lower_bound(v.begin(),v.end(),x)-v.begin() +1;
}
ll a[maxn],b[maxn],c[maxn],d[maxn];
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);
for(int i=0;i<=n;i++){
for(int k=0;k<=n;k++){
judge[i][k] = 0;
}
}
v.clear();
for(int i=1;i<=n;i++){
read(a[i]);
c[i] = a[i];
v.push_back(a[i]);
}
for(int i=1;i<=n;i++){
read(b[i]);
d[i] = b[i];
}
sort(a+1,a+1+n);
sort(b+1,b+1+n);
int f = 0;
for(int i=1;i<=n;i++){
if(a[i] != b[i]) f = 1;
}
if(f){
printf("No
");
continue;
}
sort(v.begin(),v.end());//
v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=n;i++){
int id1 = getid(c[i]);
int id2 = getid(c[n-i+1]);
judge[id1][id2]++;
judge[id2][id1]++;
}
for(int i=1;i<=n;i++){
int id1 = getid(d[i]);
int id2 = getid(d[n-i+1]);
if(judge[id1][id2]>0&&judge[id2][id1]>0){
judge[id1][id2] --;
judge[id2][id1] --;
}
else{
f = 1;
break;
}
}
if(f) printf("No
");
else printf("Yes
");
}
return 0;
}
/**
3
011
100
111
**/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
