言いたいことも言えなくなっていく
想说的话 也只能藏在心底
Codeforces Round 1087 (Div. 2)
A. Flip Flops 548
显然是升序排序之后尽力给怪升级到和自己现在攻击力相同然后再击败
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,c,k;
const int N=105;
int a[N];
inline void solve(){cin>>n>>c>>k;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);for(int i=1;i<=n;i++){if(c>=a[i]){if(c-a[i]<=k){k-=(c-a[i]);a[i]=c;c+=c;}else{a[i]+=k;k=0;c+=a[i];}}else{break;}}cout<<c<<'\n';return;
}
signed main(void){cin.tie(NULL)->sync_with_stdio(false);int T;cin>>T;while(T--){solve();}return 0;
}
B. Array
- 假设k趋向正无穷大，那么 \(a_i\) 和 \(a_j\) 都会变成正数，本来 \(a_j>a_i\) 的话绝对值就会大
- 假设k趋向负无穷大，那么 \(a_i\) 和 \(a_j\) 都会变成负数，本来 \(a_j<a_i\) 的话绝对值就会大
\(n^2\) 的复杂度是可以接受的
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
const int N=5005;
int a[N];
inline void solve(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){int da=0,xiao=0;for(int j=i+1;j<=n;j++){if(a[j]>a[i]){da++;}else if(a[j]<a[i]){xiao++;}}cout<<max(da,xiao)<<" ";}cout<<'\n';return;
}
signed main(void){cin.tie(NULL)->sync_with_stdio(false);int T;cin>>T;while(T--){solve();}return 0;
}
C. Find the Zero 1339
考虑把 \((1,2),(3,4),(5,6),...,(2n-1,2n)\) 配对
查询每对，若返回 \(1\) ，说明是两个零，直接输出任一值
若返回 \(0\) ，说明这一对中肯定不是两个零
**查询完 \(n\) 对如果都是 \(0\)，说明每对中至少有一个 \(0\) **
这时候就随便找两对，比如 \((1,2),(2n-1,2n)\)
先查询 \((2n-1,1)\) ，如果返回 \(1\) 则找到 \(0\)
再查询 \((2n-1,2)\) ，如果返回 \(1\) 则找到 \(0\)
如果都是 \(0\)，说明 \(2n-1\) 这个位置的数不是零，所以 \(2n\) 这个位置的数就是 \(0\)
然而我们发现这总共需要 \(n+2\) 次查询，所以我们可以省略 \((2n-1,2n)\) 这一对查询，如果都是 \(0\) 的话，那么 \((2n-1,2n)\) 这一对要么是 \((0,x)\)，要么是 \((0,0)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
inline int query(int i,int j){cout<<"? "<<i<<" "<<j<<endl;int x;cin>>x;if(x==-1) exit(0);return x;
}inline void solve(){cin>>n;for(int i=1;i<=2*n-3;i+=2){if(query(i,i+1)==1){cout<<"! "<<i<<endl;return;}}int X=2*n-1;int Y=2*n;int A=1;int B=2;if(query(X,A)==1){cout<< "! "<<X<<endl;return;}if(query(X,B)==1) {cout<<"! "<<X<<endl;return;}cout<<"! "<<Y<<endl;return;
}
signed main(void){cin.tie(NULL)->sync_with_stdio(false);int T;cin>>T;while(T--){solve();}return 0;
}
D. Ghostfires 1696
题意：任意一个鬼火 \(i\)，不能和位置 \(i+1\) 和 \(i+3\) 的鬼火型号相同，要求构造一个 \(r,g,b\) 三种型号的鬼火序列
观察发现：
- 如果位置 \(i\) 是奇数，那么位置 \(i+1\) 和 \(i+3\) 就是偶数
- 如果位置 \(i\) 是偶数，那么位置 \(i+1\) 和 \(i+3\) 就是奇数
所以先从大到小排列三种颜色，然后奇数位放剩余数最大的颜色，偶数位放剩余数次大的颜色，再留一个备用位置。
排列的时候，如果备用数量大于现在的奇数位或者偶数位，就交换两者的位置
这样排列可以避免奇数位和偶数位的颜色相同，还能最大程度的利用颜色
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,r,g,b;
int cnt[3];
char ch[3];
inline void solve(){cin>>r>>g>>b;vector<pair<int,char>> v={{r,'R'},{g,'G'},{b,'B'}};sort(v.begin(),v.end(),[&](pair<int,int> A,pair<int,int> B)->bool{return A.first>B.first;});int tm=0;for(auto [cnT,CH]:v){cnt[tm]=cnT;ch[tm]=CH;tm++;}int ji=0,ou=1,other=2;int tot=r+g+b;for(int i=1;i<=tot;i++){if(i&1){if(cnt[other]>cnt[ji]){swap(other,ji);}if(cnt[ji]==0) break;cout<<ch[ji];cnt[ji]--;}else{if(cnt[other]>cnt[ou]){swap(other,ou);}if(!cnt[ou]) break;cout<<ch[ou];cnt[ou]--;}}cout<<'\n';return;
}
signed main(void){cin.tie(NULL)->sync_with_stdio(false);int T;cin>>T;while(T--){solve();}return 0;
}
但是题解好像不是这么写的