https://codeforces.com/contest/1612
VP 过了 A~E，感觉海星。
F,G 这几天补。
主要是 luogu 有翻译拯救了英语不好的我。
A
一眼 \(x+y\equiv 0\pmod{2}\)，否则无解。那么显然距离应该是 \((x+y)/2\)，考虑别超过 \(\min(x,y)\)，不然答案就改了，然后就想到钦定最小的直接放满了。
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
void solve() {
int x,y;
cin>>x>>y;
if((x+y)&1) {
cout<<"-1 -1\n"; return ;
}
if(x<y) {
int qwq=(x+y)/2;
cout<<x<<" "<<qwq-x<<'\n';
} else {
int qwq=(x+y)/2;
cout<<qwq-y<<" "<<y<<'\n';
}
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int T; cin>>T; while(T--) solve();
return 0;
}
B
憨憨题，比 A 更一眼。luogu 翻译错了。。。
考虑钦定完最大值最小值后，最大值择从小到大，最小值择从大到小，这样对双方都是更优的。
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
using namespace std;
const int N=105;
bool vis[N];
int n,a,b,ans[N];
void solve() {
memset(vis,0,sizeof(vis));
cin>>n>>a>>b;
ans[1]=a; ans[n/2+1]=b;
vis[a]=vis[b]=1;
int t1=1;
for(int i=n;i>=1;i--) {
if(vis[i]) continue ;
if(i<a) {
cout<<"-1\n"; return ;
}
vis[i]=1; ans[++t1]=i;
if(t1>=n/2) break ;
}
t1=n/2+1;
for(int i=1;i<=n;i++) {
if(vis[i]) continue ;
if(i>b) {
cout<<"-1\n"; return ;
}
vis[i]=1; ans[++t1]=i;
if(t1>=n) break ;
}
for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
cout<<'\n';
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int T; cin>>T; while(T--) solve();
return 0;
}
C
也是憨憨题，没啥思维可言。
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
int get(int fir,int x) {
int las=fir-x+1;
return (fir+las)*x/2;
}
void solve() {
int n,k;
cin>>n>>k;
if(k<=n*(n+1)/2) {
int l=1,r=n,res=0;
while(l<=r) {
int mid=(l+r)>>1;
if(mid*(mid+1)/2>=k) res=mid,r=mid-1;
else l=mid+1;
}
cout<<res<<'\n'; return ;
}
k-=n*(n+1)/2;
int l=1,r=n-1,res=n-1;
while(l<=r) {
int mid=(l+r)>>1;
if(get(n-1,mid)>=k) res=mid,r=mid-1;
else l=mid+1;
}
cout<<res+n<<'\n';
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int T; cin>>T; while(T--) solve();
return 0;
}
D
第一眼，感觉是不是只要满足不定方程 \(k_1a+k_2b=x\) 就好了啊。。。
写了个暴力，显然不是。
但是暴力中好像一直执行某个策略直到没有。
然后手玩了下，考虑一直执行某个策略。
若 \(x<y\)，要么变成 \((x,y-x)\)，要么 \((y-x,y)\)，然后考虑后面的，\((y-x,y)\)，可变成 \((y-x,x)\)，或者 \((x,y)\)，然后发现没啥用。。。因为它能表示的之前那个一定可以。
所以我们只考虑 \(x<y\) 的情况写暴力，且只使用 \((x,y-x)\) 这种变形。
然后考虑改变 \(x,y\) 相对大小的时刻，注意中间可能达到目标了。
然后就过了。
考虑先猜想后证明，我们猜这样是 \(\mathcal{O}(\log_2 n)\) 的，只要证明我们的操作每次强于 \(y/2\)，即可，若 \(y=kx\)，显然操作后 \(y<x\)，于是每次操作都强于。
这道题俺能想出来也是很不可思议（（，其实在 AC 这道题后我才发现自己在一个暴力的情况下就确认了一定只有操作 1，然后后面才去证明。暴力后的发现再到手玩，再到大胆猜想，以及后面的证明，每一步都是具有启发性意义的！总之，对于这类题目需要大力手玩和暴力，以及猜想后的大胆提交！
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
int gcd(int x,int y) {
return !y?x:gcd(y,x%y);
}
map<pair<int,int>,bool>mp;
int a,b,X;
bool fl;
void solve(int x,int y) {
// cout<<x<<" "<<y<<'\n';
if(fl) return ;
if(mp.count(make_pair(x,y))) return ;
if(x==X||y==X) {
fl=1; return ;
}
if(!x||!y) return ;
mp[make_pair(x,y)]=1;
if(x<y) {
int qwq=y/x;
// y-qwq*x=X
if((y-X)>=0&&(y-X)%x==0&&(y-X)/x<=qwq) {
fl=1; return ;
}
solve(x,y-qwq*x);
} else solve(y,x);
}
void solve() {
mp.clear();
cin>>a>>b>>X; fl=0;
solve(a,b);
if(fl) cout<<"YES\n";
else cout<<"NO\n";
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int T; cin>>T; while(T--) solve();
return 0;
}
E
溜达了几十分钟回来结果赛时被卡常，赛后 2min 过。。。
问题不大。
一眼枚举 \(t\)，但我们不知道上界，那就先不管，看看能不能通过计算答案方式来确定上界。
考虑对于每种都计算出选取它能带来的期望人数，之后我们从大到小排序选取前 \(t\) 个即可。
考虑期望有独立性，因此我们可以考虑每个人然后再合起来，作为选取这条消息带来的期望贡献。
考虑对于每个人，选取它的消息，这个人能带来的期望贡献。
倘若 \(t<=k_i\)，显然贡献一定是 \(1\)。
否则，根据俺目前的定义，当前选取的 \(t\) 条消息一定有它需要的。
那么只要考虑它随机 \(k_i\) 个然后抽到对应的概率即可，显然钦定然后其他乱选为 \(\binom{t-1}{k_i-1}\)，总方案为 \(\binom{t}{k_i}\)，然后贡献人数为 \(1\)，期望就出来了。
不难发现上界只跟 \(k\) 有关，赛时猜了个 \(20\)，然后卡卡常就过了。
仅仅求数组前 \(k\) 大可以用 nth_element
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=(int)(2e5+5);
struct node {
int x,y;
}a[N];
int n,tot;
ll gcd(ll x,ll y) {
return !y?x:gcd(y,x%y);
}
struct Frac {
ll x,y;
Frac() {
x=0; y=1;
}
Frac(const ll &xx) {
x=xx; y=1;
}
Frac(const ll &xx,const ll &yy) {
ll d=gcd(xx,yy);
x=xx/d; y=yy/d;
}
}ans[N];
inline Frac operator + (const Frac &x,const Frac &y) {
int qwq=x.x*y.y+y.x*x.y,d=gcd(qwq,x.y*y.y);
return Frac(qwq/d,x.y*y.y/d);
}
inline bool operator < (const Frac &x,const Frac &y) {
return x.x*y.y<y.x*x.y;
}
inline ll C(int n,int m) {
if(m<0||m>n||n<0) return 0;
ll res=1;
for(int i=m+1;i<=n;i++) res=1ll*res*i;
for(int i=1;i<=n-m;i++) res/=i;
return res;
}
ll CC[22][22];
inline Frac cal(int x,int y) {
// cout<<x<<" "<<y<<" "<<C(tot-1,x-1)<<" "<<C(tot,x)<<" "<<C(x,y)<<" "<<C(x-1,y-1)<<'\n';
return Frac(CC[x-1][y-1],CC[x][y]);
}
bool vis[N];
int lsh[N];
bool cmp(const int &x,const int &y) {
return ans[y]<ans[x];
}
int vec[22],vectot;
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
for(int i=0;i<=20;i++)
for(int j=0;j<=20;j++)
CC[i][j]=C(i,j);
// int mx=0;
// for(int i=1;i<=n;i++) mx=max(mx,a[i].y);
Frac answ;
for(int i=1;i<=20;i++) {
for(int j=1;j<=n;j++) vis[a[j].x]=0,ans[a[j].x]=Frac(0);
for(int j=1;j<=n;j++) {
if(a[j].y>=i) {
ans[a[j].x]=ans[a[j].x]+Frac(1);
} else {
// cout<<cal(i)<<'\n';
ans[a[j].x]=ans[a[j].x]+cal(i,a[j].y);
}
}
tot=0;
for(int j=1;j<=n;j++) if(!vis[a[j].x]) lsh[++tot]=a[j].x,vis[a[j].x]=1;
stable_sort(lsh+1,lsh+1+tot,cmp);
Frac res;
for(int j=1;j<=min(i,tot);j++) res=res+ans[lsh[j]];
// cout<<answ.x<<" "<<answ.y<<'\n';
// cout<<res.x<<" "<<res.y<<'\n';
if(answ<res) {
answ=res;
vectot=0;
for(int j=1;j<=min(i,tot);j++) vec[++vectot]=lsh[j];
}
}
cout<<vectot<<'\n';
for(int i=1;i<=vectot;i++) cout<<vec[i]<<' ';
return 0;
}