Codeforces Round #682 (构造场)
Codeforces Round #682 (构造场)
题目列表
A
题意描述
思路
输出全 1 1 1或全 2 2 2即可
AC代码
#include <iostream>
#include <map>
#include <cmath>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e5+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
void solve(){
int n;
cin>>n;
rep(i,0,n) cout<<2<<' ';
cout<<endl;
}
int main(){
//IOS;
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
int t;cin>>t;
while(t--)
solve();
return 0;
}B
题意描述
思路
发现，只有数组中存在两个相同的指数时，才有可能出现 s u m sum sum相同的情况。
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e5+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
int a[N];
void solve(){
int n;
cin>>n;
set<int> s;
rep(i,0,n) cin>>a[i];
rep(i,0,n) s.insert(a[i]);
cout<<(sz(s)==n ? "No" : "Yes")<<endl;
}
signed main(){
IOS;
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
int t;cin>>t;
while(t--)
solve();
return 0;
}C
题意描述
思路
操作只会导致两种结果： 1. 1. 1. v a l u e value value奇偶值不变 2. 2. 2. v a l u e value value奇偶值改变 可以让下标和为奇数的格子放奇数，下标和为偶数的格子放偶数。如果下标和的奇偶性和格子的值不同，则让该格子的 v a l u e + 1 value+1 value+1即可。
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=105;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
int a[N][N];
void solve(){
int n,m;
cin>>n>>m;
rep(i,0,n){
rep(j,0,m){
cin>>a[i][j];
}
}
rep(i,0,n){
rep(j,0,m){
if((i+j)%2!=a[i][j]%2) a[i][j]++;
}
}
rep(i,0,n){
rep(j,0,m){
cout<<a[i][j]<<' ';
}
cout<<endl;
}
}
int main(){
IOS;
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
int t;cin>>t;
while(t--)
solve();
return 0;
}D
题意描述
思路
1. 1. 1.先考虑 n n n是奇数，是奇数时一定可以实现，因为可以先将数组变成形为 x , x , y , y , y x,x,y,y,y x,x,y,y,y式的数组，即相邻元素两两相同。 由于两个相同的元素异或起来一定为 0 0 0，所以可以将所有元素都变成数组的最后一个值。按照 ( i , i + 1 , i + 2 ) (i,i+1,i+2) (i,i+1,i+2)， ( i + 2 , i + 3 , i + 4 ) (i+2,i+3,i+4) (i+2,i+3,i+4)这样的操作顺序即可将数组变成形为 x , x , y , y , y x,x,y,y,y x,x,y,y,y式的。
2. 2. 2.再考虑 n n n是偶数。先给出结论，当整个数组异或起来为 0 0 0时，才有可能实现。首先，对 a i , a i + 1 , a i + 2 a_{i},a_{i+1},a_{i+2} ai,ai+1,ai+2进行操作并不会影响整个数组的异或值，而偶数个相同的值异或起来一定为 0 0 0，所以只有为 0 0 0的时候才能完成操作。将前 n − 1 n-1 n−1个数字进行第一种情况的操作后，整个数组的值会变成第 n n n个数字，所以按照第一种情况进行操作即可。
AC代码
#include <iostream>
#include <map>
#include <cmath>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e5+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
int a[N];
struct Range{
int a,b,c;
}range[N];
void solve(){
int n;
cin>>n;
int x=0;
rep(i,0,n) cin>>a[i],x^=a[i];
if(n&1){
int cnt=0;
cout<<"YES"<<endl;
rep(i,0,n-1){
cnt++;
range[cnt].a=i+1;
range[cnt].b=i+2;
range[cnt].c=i+3;
i++;
}
rep(i,0,n){
cnt++;
range[cnt].a=i+1;
range[cnt].b=i+2;
range[cnt].c=n;
i++;
}
cout<<cnt-1<<endl;
rep(i,1,cnt) cout<<range[i].a<<' '<<range[i].b<<' '<<range[i].c<<endl;
}else{
if(x){
cout<<"NO"<<endl;
return;
}
n--;
cout<<"YES"<<endl;
int cnt=0;
rep(i,0,n-1){
cnt++;
range[cnt].a=i+1;
range[cnt].b=i+2;
range[cnt].c=i+3;
i++;
}
rep(i,0,n){
cnt++;
range[cnt].a=i+1;
range[cnt].b=i+2;
range[cnt].c=n;
i++;
}
cout<<cnt-1<<endl;
rep(i,1,cnt) cout<<range[i].a<<' '<<range[i].b<<' '<<range[i].c<<endl;
}
}
int main(){
//IOS;
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}