VP时间
A.贪心
A大B就小,B小A就大
排序
wa4发
5.ac
B.
计算贡献
中间贡献1
左右两边贡献
如果相等贡献2
如果不相等贡献1
1.ac
C.贪心
Alice放入小的,才能得到大的
Bob拿走的肯定是小的,Alice得放回来
Bob拿0,Alice放回去
无限循环
我们只要考虑第一次操作即可
第一次放mex即可
cout<<endl 自动刷新缓冲区
1.Idleness limit exceeded on test?1
2.ac
题解
A.
这个很贪得想会
// Problem: A. green_gold_dog, array and permutation
// Contest: Codeforces - Codeforces Round 897 (Div. 2)
// URL: https://codeforces.com/contest/1867/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//へ /|
// /\7 ∠_/
// / │ / /
// │ Z _,< / /`ヽ
// │ ヽ / 〉
// Y ` / /
// イ● 、 ● ??〈 /
// () へ | \〈
// >ー 、_ ィ │ //
// / へ / ノ<| \\
// ヽ_ノ (_/ │//
// 7 |/
// >―r ̄ ̄`ー―_
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N =4e4+ 9;
int ans[N];
struct node{
int num,index;
}a[N];
bool cmp(node a,node b){
return a.num<b.num;
}
void solve() {
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].num;
a[i].index=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
ans[a[i].index]=n-i+1;
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<'\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int q;
cin >> q;
while (q--) {
solve();
}
return 0;
}
B.
求回文串
从中间入手往两边延伸
如果两边一样记录一下goodbi++(好的一对)
如果两边不一样记录一下badbi++(坏的一对)
如果要构造成回文串
至少要变badbi次,至多就是badbi+goodbi*2(闲的没事干把好的一起变)
奇数还要考虑中间那个数字,至多badbi+goodbi*2+1(中间那个数字也可以变)
让这些位置都被赋值1,其他是0
// Problem: B. XOR Palindromes
// Contest: Codeforces - Codeforces Round 897 (Div. 2)
// URL: https://codeforces.com/contest/1867/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
using namespace std;
const int N=1e5+9;
int ans[N];
struct {
void start(){
int n;
cin>>n;
string s;
cin>>s;
int badbi=0,goodbi=0;
for(int i=0;i<=n;i++){
ans[i]=0;
}
s=" "+s;
for(int i=1;i*2<=n;i++){
if(s[i]==s[n-i+1]){
goodbi++;
}else{
badbi++;
}
}
for(int i=0;i<=goodbi;i++){
ans[badbi+i*2]=1;
if(n&1){
ans[badbi+i*2+1]=1;
}
}
for(int i=0;i<=n;i++){
cout<<ans[i];
}
cout<<'\n';
}
}Genshin;
int main(){
int q;
cin>>q;
while(q--){
Genshin.start();
}
return 0;
}
C.
互动题
Idleness limit exceeded on test?1 这种错误要<<endl刷新缓冲区
// Problem: C. Salyg1n and the MEX Game
// Contest: Codeforces - Codeforces Round 897 (Div. 2)
// URL: https://codeforces.com/contest/1867/problem/C
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//へ /|
// /\7 ∠_/
// / │ / /
// │ Z _,< / /`ヽ
// │ ヽ / 〉
// Y ` / /
// イ● 、 ● ??〈 /
// () へ | \〈
// >ー 、_ ィ │ //
// / へ / ノ<| \\
// ヽ_ノ (_/ │//
// 7 |/
// >―r ̄ ̄`ー―_
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N];
void solve() {
int n;
int y;
cin>>n;
set<int>st;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
st.insert(a[i]);
}
int mex=0;
for(int i=0;i<=n;i++){
if(!st.count(i)){
mex=i;
break;
}
}
cout<<mex<<endl;
cout.flush();
while(1){
int y;
cin>>y;
if(y==-1){
return;
}
cout<<y<<endl;
}
cout.flush();
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int q;
cin >> q;
while (q--) {
solve();
}
cout.flush();
return 0;
}