Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics)

Dashboard - Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics) - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1649先放个连接，之前都是打虚拟赛，第一次打实时赛只做出来两题，好菜啊自己

A. Game

因为只能跳一次，双指针找左边最右的1和右边最左的1就好

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 1e2+10;int num[maxn];int main() {ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int t,n;cin>>t;while(t--){cin>>n;for(int i = 1;i<=n;i++)cin>>num[i];int tar = 1,ptr = n;while(tar<n){if(num[tar])tar++;elsebreak;}while(ptr>1){if(num[ptr])ptr--;elsebreak;}if(tar==n)cout<<0<<endl;elsecout<<ptr-tar+2<<endl;}
}//只能走陆地，可以花x跳跃x，只能花一次，问花费最少是几次

B. Game of Ball Passing

有点博弈论贪心的感觉？拿 1 1 举例，传一个球就结束了，如果变成2 1，就需要两个球，要想仍然只需要一个球，那么要么 2 2，要么 1 2 1，从第二种情况不难推出，优先策略就是每个人轮流削减当前最大人的能传球的数目，如果能把当前最大的人变成当前非最大传球数的人（1 2 1变成 1 1），那么一个球就行，如果不能，最后就剩下一个人还有传球次数，一个球传一次。最后一种情况，大家都是0

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 1e5+10;int num[maxn];int main() {ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int t,n;cin>>t;while(t--){cin>>n;int maxx = 0;int tar = 0;for(int i = 1;i<=n;i++) {cin >> num[i];}for(int i = 1;i<=n;i++)if(maxx<num[i]){maxx = num[i];tar = i;}if(maxx==0){cout<<0<<endl;continue;}int j = 1;for(int i = 1;i<=n;i++){if(i==tar)continue;maxx-=num[i];if(maxx<=0) {j = 0;break;}}if(j)cout<<maxx<<endl;elsecout<<1<<endl;}
}//传球，第一个球能消耗大量的次数，贪心一下一共就两种情况，一种是一个球能解决，一种是所有数之和小于最大的那个数，差多少就要多少个球

C. Weird Sum

（c题，1个半小时没a，痛死我了）

思路是这样的，首先对manhattan distance这个特殊的计算要有理解，因为横纵坐标之差是用加和的形式，所以我们完全可以分开去处理，分开处理的话就可以用一阶差分然后去优化做，这样就可以加速了，模拟一下四个横坐标的情况（x1，x2,x3,x4）距离差和就是（x2-x1）+（2x3-x2-x1）+（3x4-x3-x2-x1）

同时，我们需要sort一下，然后去计算（因为我们的距离是加和，距离算出来有正有负，又不能直接abs）

唯一要注意的是，计算的过程中可能会出现int*int超int范围导致溢出的情况，想避免的话要么*1ll，要么开其中一个int开longlong

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 1e5+10;int num[maxn];
vector<int>px[maxn],py[maxn];
vector<int>chu;
int vis[maxn];int main() {ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int r,c,x;cin>>r;cin>>c;for(int i = 1;i<=r;i++)for(int j = 1;j<=c;j++){cin>>x;px[x].push_back(i);py[x].push_back(j);if(!vis[x]){chu.push_back(x);vis[x] = 1;}}long long ans = 0;for(auto k = chu.begin();k!=chu.end();k++){int now = *k;sort(px[now].begin(), px[now].end());sort(py[now].begin(), py[now].end());long long xsum = 0;long long ysum = 0;for(int i = 0;i<px[now].size();i++){ans+=(px[now][i]*i-xsum);xsum += px[now][i];}for(int i = 0;i<py[now].size();i++){ans+=(1ll*py[now][i]*i+-ysum);ysum += py[now][i];}}cout<<ans;
}

D. Integral Array

D题tle了一次就没往下做了，后面看题解感觉还是偏数学思路，不过可以学一手前缀和记录状态进行区间状态比较，这个做法还是挺有意思的（1899ms，差点没过）

我们转化一下思路，x/y的floor等于t。y，x,t都在这个数组中，先假设t是存在的，就可以把x的存在转换成y*t<=x<=min(c,y*(t+1)-1)，在这个区间里面一定存在着一个数。
前缀和记录数组中出现的数字，换而言之，只要y*t-1和min(c,y*(t+1)-1)下标的内容不同，说明存在这样的x。

此时再去判断t是否存在即可，注意，判断条件是x和y都存在的情况下，t不存在才说明false，其他情况是不可以的（t的存在依赖于x和y的同时存在）

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 1e6+10;int sum[2*maxn],vis[maxn];  //前缀和记录状态，vis记录是否有这个数int main(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int t;cin>>t;while(t--){int n,c,x;cin>>n>>c;memset(vis,0,sizeof vis);for(int i = 1;i<=n;i++){cin>>x;vis[x]++;}for(int i = 1;i<=c;i++)sum[i] = sum[i-1]+vis[i];int jj = 1;for(int i = 1;i<=c;i++){if(vis[i])  //数组中有这个数，把它当成y{for(int j = 1;i*j<=c;j++) //遍历每个可能的t{if(sum[i*j-1]<sum[min(c,i*(j+1)-1)]&&!vis[j]) {  //x存在（前缀和体现的）同时这样的t也存在jj = 0;break;}}}if(!jj)break;}if(jj)cout<<"Yes"<<endl;elsecout<<"No"<<endl;}}
//我们转化一下思路，x/y的floor等于t,y，x,t都在这个数组中，我们处理一下，再遍历一遍数组,找到存在的y和t，如果成立y*t<=x<=min(c,y*(t+1)-1)
//前缀和记录数组中出现的数字，换而言之，只要y*t-1和min(c,y*(t+1)-1)下标的内容不同，说明存在这样的x,遍历一边，都成立的话这个式子转化就成立
//这个思路的问题是，只有当x和y存在，t才会存在，我们假设出的内容，不能这样逆推，让y和t存在，去看有没有这样的x（可能这样的x和t都没有）