A
直接按照1，2，3这样下去一直构造即可。
需要考虑可能重叠的情况，所以需要特判修改一下\(x_k,y_k\)。
（这个地方一开是写错了，被罚惨了）。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int xc,yc,k; cin>>xc>>yc>>k;
int sx=xc*k,sy=yc*k;
std::vector<int> vx(k+1,0);
std::vector<int> vy(k+1,0);
int sumx=0,sumy=0;
if(k==1)
{
cout<<xc<<" "<<yc<<"\n";
return;
}
for(int i=1;i<=k;i++)
{
if(i==k) vx[i]=sx-sumx,vy[i]=sy-sumy;
else vx[i]=i,sumx+=i,vy[i]=i,sumy+=i;
}
if(vx[k]==vy[k] && vx[k]<k && vx[k]>=1)
{
vx[1]-=vx[k],vx[k]*=2;
vy[1]-=vy[k],vy[k]*=2;
}
for(int i=1;i<=k;i++)
{
cout<<vx[i]<<" "<<vy[i]<<"\n";
}
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
B
不难想到：对每一个数加1，然后最大的减去\(n-1\)即可。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
std::vector<int> v(n,0);
int maxn=0;
for(auto &t: v) cin>>t,maxn=max(maxn,t);
for(auto &t: v)
{
if(t==maxn) cout<<1<<" ";
else cout<<t+1<<" ";
}
cout<<"\n";
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
C
可以发现，如果对中位数\(midian(c_i)\)进行修改，那么效果肯定是不如对\(a_i\)进行修改的。（因为修改\(median(c_i)\)的效率是小于等于1）。所以我们可以分类讨论一下：
- 如果\(a_i\)可以修改，那么我们直接把全部的修改次数用到\(a_i\)上
- 否则，对\(median(c_i)\)进行修改，尽可能使得其更大。
第一种情况：枚举每一个可以修改的\(a_i\)，并且进行计算，选取最大值。
第二种情况：要找一个中位数（或者百分位数），常用的一个技巧是用二分，
我们二分要找的中位数数的值，那么在整个数列中，肯定有一半及以上的数字是超过中位数，我们可以计算满足的个数，然后来判断我们目前二分的这个值是否合法。
\(check\)函数：可以先记录大于等于\(x\)的个数（记作\(cnt\)），然后再寻找那些可以修改的，并且小于\(x\)的数，计算需要的贡献\(need\)，如果中间\(need>k\)，那么\(x\)不合法，直接退出。否则最后判断\(cnt\)是否大于数组的一半大小。
还需要考虑的一点就是：\(a_i\)的位置，会对\(median(c_i)\)的位置产生影响。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
ll k; cin>>k;
std::vector<pair<ll,bool>> a(n,{0,0});
for(auto &t: a) cin>>t.first;
for(auto &t: a) cin>>t.second;
sort(a.begin(),a.end(),[&](pair<ll,bool> a, pair<ll,bool> b){ return a.first<b.first; });
ll ans=0;
for(int i=0;i<n;i++)
{
if(a[i].second)
{
if(i<n/2) ans=max(ans,k+a[i].first+a[n/2].first);
else ans=max(ans,k+a[i].first+a[n/2-1].first);
}
}
auto check=[&](ll x,int p)->bool
{
int cnt=0;
for(int i=n-1;i>=0;i--)
{
if(a[i].first>=x) cnt++;
}
ll need=0;
for(int i=n-1;i>=0 && cnt<n-p;i--)
{
if(a[i].second && a[i].first<x)
{
need+=x-a[i].first;
if(need>k) return false;
cnt++;
}
}
return cnt>=n-p;
};
auto findMid=[=](int pos)->ll
{
ll l=0,r=1e9;
while(l<r)
{
ll mid=(l+r+1)>>1;
if(check(mid,pos)) l=mid;
else r=mid-1;
}
return l;
};
ll maxMid_1=findMid(n/2);
ll maxMid_2=findMid(n/2-1);
for(int i=0;i<n;i++)
{
if(a[i].second==0)
{
if(a[i].first<maxMid_1) ans=max(ans,a[i].first+maxMid_1);
if(a[i].first>=maxMid_2) ans=max(ans,a[i].first+maxMid_2);
}
}
cout<<ans<<"\n";
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
D
可以从考虑Elsie什么时候能赢入手。
可以发现：如果Elise能赢，那么他一定是在某一次跳跃（也就是alternative
bridges）后，跳到了Bessie的前面。这样他才有可能赢。
考虑详细一点：如果Elise能走到这一步，前提是什么？
- Elise前面走过的岛屿，Bessie都没走过（每一轮Bessie先走），不然岛屿就会坍塌，Elise直接失败。所以Bessie肯定只能在Elise的jump起点之后的岛屿出发。
- 在Elise到达jump的终点后，从起点出发的这段时间\(t\)，Bessie肯定是不能到达jump的终点（记作\(y\)）的，所以可以确定Bessie只能在\(y-t\)之前的岛屿开始出发。
- 由上面，我们可以确定Bessie可以出发的一个区间。我们可以利用差分来标记这个区间，最后再统计答案。
- 求\(t\)可以用\(dp\)，我们只需要\(dp\)到达最后jump的起点的最短时间即可，这个很简单，新手都会的。
比较麻烦的一点是：因为数据是多组，所以如果开全局变量，每次clear会超时。所以只能开局部变量。
并且需要特判\(m=0\)的情况，不然会卡死。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
void solve()
{
int n,m; cin>>n>>m;
std::vector<pair<int,int>> vec(m,{0,0});
std::vector<int> dp(n+1,0);
if(m)
{
std::vector<std::vector<int>> edge(n+1);
for(int i=0;i<m;i++)
{
int u,v; cin>>u>>v;
vec[i].first=u,vec[i].second=v;
edge[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
dp[i]=dp[i-1]+1;
for(auto t: edge[i])
{
dp[i]=min(dp[i],dp[t]+1);
}
}
}
else
{
for(int i=1;i<=n;i++)
{
dp[i]=i;
}
}
std::vector<ll> d(n+1,0);
for(auto &t: vec)
{
int x=t.first;
int y=t.second;
int need=dp[x]+1;
int end=y-need;
int begin=x+1;
if(begin<=end)
{
d[begin]+=1;
d[end+1]-=1;
}
}
int cnt=0;
for(int i=1;i<n;i++)
{
cnt+=d[i];
if(cnt>0) cout<<0;
else cout<<1;
}
cout<<"\n";
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
|
