Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics)A~C 题解(原来如此简单,超级详细入门必备)
A. Game
题目理解:一个人要过河,这个人不会游泳,只能走陆地,一旦碰水就死翘翘,但是现在给你一个bug,只要你给x个硬币,你就可以传送到i+x块陆地上面,比如你在第5块土地上面,给5个硬币,那么你会出现在第10块土地上面。第一块和最后一块土地必然存在,求最少花硬币的数量。
解题思路:不能碰水,第一块和最后一块总是存在,那就从头到尾和从尾到头开始分别遍历,最后处理这两个变量就好
关键代码:
l=1;r=n;
while(a[l]==1&&l<=n)l++;
while(a[r]==1&&r>=1)r--;
最后a[l]==0,a[r]==0。
源代码:
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<string.h>
#include<stdio.h>
#include<deque>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<set>
#define int long long
#define endl '\n'
#define rg register int
#define fe(i,a,b) for(i = a ; i <= b ; ++ i)
#define de(i,a,b) for(i = a ; i >= b ; -- i)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(),(x).end()
#define sz size()
#define ce cout<<endl
//#define jian1 std::ios::sync_with_stdio(false)
//#define jian2 cin.tie(0)
//#define jian3 cout.tie(0)
using namespace std;
int a[10000005];
signed main()
{
//要开全局变量记得删除变量
int i,j,t;int da1,da2,n,m,k,l,r,sum,ans;
// jian1;jian2;jian3;
cin>>t;
while(t--){
cin>>n;ans=0;
fe(i,1,n){
cin>>a[i];
}
l=1;r=n;
while(a[l]==1&&l<=n)l++;
while(a[r]==1&&r>=1)r--;
ans=r-l+2;
if(ans<0)ans=0;
cout<<ans<<endl;
}
return 0;
}
B. Game of Ball Passing
题目理解:n个人相互传球,每个人有一定的传球数,然后你去安排怎么去传球,使得这些活泼可爱的小孩子用的球最少。
解题思路:我们发现如果2个以上的人的传球数是一样的时候,那么我们只会用一颗球,比如1 2 3 4 4,我们先让4号5号相互穿一次球,然后3号,4号,5号相互传一次球....最后1号,2号,3号,4号,5号相互传球。同样的我们发现就算你不可传球了,但是你其实还可以去接球,所以某人的传球数可以直接减一;
因此我们得到题解,只要将数据排序,只要前缀和大于a[n],那么就是一个球,不然就算a[n]-sum。
源代码:
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<string.h>
#include<stdio.h>
#include<deque>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<set>
#define int long long
#define endl '\n'
#define rg register int
#define fe(i,a,b) for(i = a ; i <= b ; ++ i)
#define de(i,a,b) for(i = a ; i >= b ; -- i)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(),(x).end()
#define sz size()
#define ce cout<<endl
//#define jian1 std::ios::sync_with_stdio(false)
//#define jian2 cin.tie(0)
//#define jian3 cout.tie(0)
using namespace std;
int a[10000005];
signed main()
{
//要开全局变量记得删除变量
int i,j,t;int da1,da2,n,m,k,l,r,sum,ans;
// jian1;jian2;jian3;
cin>>t;
while(t--){
cin>>n;
fe(i,1,n)cin>>a[i];
sort(a+1,a+1+n);
if(a[n]==0){
cout<<0<<endl;
continue;
}
sum=0;m=0;
fe(i,1,n-1){
sum+=a[i];
if(sum+1>=a[n]){
m=1;
break;
}
}
if(m)cout<<1<<endl;
else{
cout<<a[n]-sum<<endl;
}
}
return 0;
}
C. Weird Sum
题目理解:给你n x m的矩阵,然后让你求各个相同数的各个曼哈顿距离和。
解题思路:因为是曼哈顿距离所以我们直接拆开x和y算就好了,并且将数组排序,然后计算,每一段相邻距离对整个队伍的贡献
关键式子:
注意这里的n是指当前数对应的n
源代码:
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<string.h>
#include<stdio.h>
#include<deque>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<set>
#define int long long
#define endl '\n'
#define rg register int
#define fe(i,a,b) for(i = a ; i <= b ; ++ i)
#define de(i,a,b) for(i = a ; i >= b ; -- i)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(),(x).end()
#define sz size()
#define ce cout<<endl
//#define jian1 std::ios::sync_with_stdio(false)
//#define jian2 cin.tie(0)
//#define jian3 cout.tie(0)
using namespace std;
int a[10000005];
int b[10000005];
const int maxn=1e5+5;
vector<int >hang[maxn];
vector<int >lie[maxn];
signed main()
{
//要开全局变量记得删除变量
int i,j,t;int da1,da2,n,m,k,l,r,sum,ans;
// jian1;jian2;jian3;
cin>>n>>m;sum=0;
fe(i,1,n){
fe(j,1,m){
cin>>k;
if(!b[k]){
a[++sum]=k;
b[k]=1;
}
hang[k].pb(i);
lie[k].pb(j);
}
}
ans=0;
// cout<<sum<<endl;
fe(i,1,sum){
sort(hang[a[i]].begin(),hang[a[i]].end());
sort(lie[a[i]].begin(),lie[a[i]].end());
// cout<<"hang"<<endl;
fe(j,1,hang[a[i]].size()-1){
ans=ans+(hang[a[i]][j]-hang[a[i]][j-1])*j*(hang[a[i]].size()-j);
}
// cout<<"lie"<<endl;
fe(j,1,lie[a[i]].size()-1){
ans=ans+(lie[a[i]][j]-lie[a[i]][j-1])*j*(lie[a[i]].size()-j);
}
}
cout<<ans<<endl;
return 0;
}
作者还在持续更新中,敬请期待0.0~~~