A. Game

题意：由一个0和1组成的一维数组，起点1和终点n是1，1表示陆地，0表示海洋，可以花费x从$i$到达$i+x$(至多一次）,即终点是一定可达的，求最少花费。
思路：讲开头和结尾的连续的1去掉，减一下就是答案。

// Problem: A. Game
// Contest: Codeforces - Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics)
// URL: https://codeforces.com/contest/1649/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int mod=1000000007 , N = 1e2 + 10;
const double eps=1e-8;
int t;
int a[N];
int n;
int main(){cin>>t;while(t--){cin>>n;memset(a,0,sizeof a);for(int i = 0 ; i < n ; i ++ )	cin>>a[i];int ans = 0;int j = n-1 , i = 0;while(a[i] && i < n-1) i++;while(a[j] && j > 0)	j--;if(j == 0)	cout<<"0\n";else{ans = j - i + 2;cout<<ans<<"\n";}}return 0;
}

B. Game of Ball Passing

题意：n个同学在玩传球游戏，给出每个同学的传球次数，问需要最少多少个球来使所有同学的传球结束。
样例1：四个同学分别是：2 3 3 2
可以通过一个球解决：$2\to 1\to 3\to 4\to 1\to 2\to 3\to 4\to 2\to 3\to 2.$
样例2：三个同学分别是：1 5 2
需要两个球解决：$2\to 1\to 2\to 3\to 2\to 1.$
$2\to 3\to 2\to 1$
思路：问题在于解决传球次数最多的同学，经分析后发现只有两种情况

• 最大值大于其余人的和，那么结果就是max-sum
• 否则显然一个球就足够

// Problem: B. Game of Ball Passing
// Contest: Codeforces - Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics)
// URL: https://codeforces.com/contest/1649/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int mod=1000000007 , N = 1e5 + 10;
const double eps=1e-8;
int t,n;
int a[N];
int main(){scanf("%d",&t);while(t--){scanf("%d",&n);bool flag = false;ll sum = 0;for(int i = 0 ; i < n ; i ++ ){scanf("%d",&a[i]);sum += a[i];if(a[i])	flag = true;}	if(!flag){printf("0\n");continue;}sort(a,a+n);sum -= a[n-1];printf("%lld\n",max((ll)1,a[n-1] - sum));}return 0;}

C. Weird Sum

题意 ：给出一个n*m的矩阵，计算值相同的两个点之间的曼哈顿距离（不了解的可以搜一下），对于一对点只计算一次。
思路 ：两个点的曼哈顿距离由x，y的差值组成，那么显然可以将x和y两个方向的分开计算，每次将权值相同的点的x和y分别存放排序，然后只每个点和前面的点计算差值，避免重复。

// Problem: A. Weird Sum
// Contest: Codeforces - Codeforces Round #775 (Div. 1, based on Moscow Open Olympiad in Informatics)
// URL: https://codeforces.com/problemset/problem/1648/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> PII;
const int mod=1000000007 , N = 1e5 + 10;
const double eps=1e-8;
vector<PII> ve[N]; 
ll dis(vector<PII> a,int n)
{vector<ll> l,r;for(int i = 0 ; i < n ; i ++ ){l.push_back(a[i].first);r.push_back(a[i].second);}sort(l.begin(),l.end());sort(r.begin(),r.end());ll sum = 0 , ans1 = 0 , ans2 = 0;for(int i = 0 ; i < n ; i ++ ){ans1 += ((ll)l[i]*i - sum);//每个点避免重复计算，只计算每个点之后的//所以等同计算该点与前面的点的差值，i就是前面有多少点sum += l[i];}sum = 0;for(int i = 0 ; i < n ; i ++ ){ans2 += ((ll)r[i]*i - sum);sum += r[i];}return ans1 + ans2;
}
int main(){int n,m;cin>>n>>m;for(int i = 0 ; i < n ; i ++ ){for(int j = 0 ; j < m ; j ++ ){int x;cin>>x;ve[x].push_back({i,j});}}ll ans = 0;for(int i = 0 ; i <= N - 10 ; i ++ ){vector<PII> a = ve[i];int len = a.size();ans += dis(a,len);}cout<<ans<<"\n";return 0;
}

D. Integral Array

题意：各一个长度为n的数组，数组里面的所有数的值不会大于c， 问是否可以找到两个数x，y(x>=y)都在数组中存在，但是$[x/y]$ (x除以y向下取整) 在数组中找不到，可以输出No，否则输出Yes。$（1<=n<=1e6,1<=c<=1e6）$.
思路：显然暴力的做法不可取，那么可以换个思路，不直接去找x和y，假定x除以y向下取整的数为t，那么可以针对数组中不存在的t，找一个数组中存在的分母y，那么区间$[y\ast t,y(t+1)-1]$就是x的取值范围，假定数组中存在区间内的数，那么就找到了我们想要的结果。
这里使用一个前缀和数组来直接判断区间内是否有数组中的数存在。

// Problem: B. Integral Array
// Contest: Codeforces - Codeforces Round #775 (Div. 1, based on Moscow Open Olympiad in Informatics)
// URL: https://codeforces.com/contest/1648/problem/B
// Memory Limit: 512 MB
// Time Limit: 2000 ms#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int mod=1000000007 , N = 1e6 + 10;
const double eps=1e-8;
int a[N],st[N*2];
ll s[N*2];
int main(){int t;scanf("%d",&t);while(t--){int n,c;scanf("%d%d",&n,&c);for(int i = 1 ; i <= 2*c ; i ++ )	st[i] = 0;for(int i = 1 ; i <= n ; i ++ ){scanf("%d",&a[i]);st[a[i]] ++;}for(int i = 1 ; i <= 2*c ; i ++ )	s[i] = s[i-1] + st[i];bool flag = true;for(int i = 1 ; i <= c ; i ++ ){	if(!st[i])	continue;for(int j = 1 ; j * i <= c ; j ++ ){if(st[j])	continue;if(s[i*j-1] != s[i*(j+1)-1])	flag = false;//这里区间的右端点最坏取到2*c，所以数组大小开二倍}}if(flag) printf("Yes\n");else printf("No\n");}return 0;
}