Codeforces Round #748
A. Elections
题意
有三个数 问每个数分别最少加多少才能使这个数成为三个数成为最大
思路
先寻找最大数的数量 最大数的数量不唯一 那么最大数需要加1 否则不用加
其他数字比最大数大1就行
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 300005
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n,t,q,l,r,k;
int a[10];
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
cin>>a[0]>>a[1]>>a[2];
int mmax=max(a[0],max(a[1],a[2]))+1;
int flag=0;
for(int i=0;i<3;i++)
{
if(a[i]==mmax-1)
flag++;
a[i]=mmax-a[i];
}
if(flag==1)
{
for(int i=0;i<3;i++)
{
if(a[i]==1)
a[i]=0;
}
}
for(int i=0;i<3;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}
B - Make it Divisible by 25
题意
给一个数 使任意删掉一些位数 使得剩下的数能被25整除 问最少需要删掉多少位 前导0自动被删除
思路
能被25删除的数末尾只能是00 25 50 75
所以从后面找到第一个0或5 在根据0或5向前找到最近的0，5或者5，7
0和5两种情况分别计算 得到最小值
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 400005
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n,t,q,l,r,k;
string s;
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
cin>>s;
int mmin=200,nn=s.size();
//int f0=0,f5=0,f2=0,f7=0;
int cnt2=0,cnt0=0,cnt5=0;
int flag0=1,flag5=1;
for(int i=s.size()-1;i>=0;i--)
{
if(flag0&&s[i]=='0')
{
cnt0=i;
flag0=0;
}
else if(flag5&&s[i]=='5')
{
cnt5=i;
flag5=0;
}
if(flag0==0&&flag5==0)
break;
}
if(!flag0)
{
for(int i=cnt0-1;i>=0;i--)
{
if(s[i]=='0'||s[i]=='5')
{
cnt2=i+1;
break;
}
}
mmin=min(mmin,nn-cnt2-1);
}
if(!flag5)
{
for(int i=cnt5-1;i>=0;i--)
{
if(s[i]=='2'||s[i]=='7')
{
cnt2=i+1;
break;
}
}
mmin=min(mmin,nn-cnt2-1);
}
cout<<mmin<<endl;
}
return 0;
}
C - Save More Mice
题意
猫在0处 洞在N>0处 中间有k只老鼠 每个时间单位 有一只老鼠向右走一步 然后猫再向右走一步 猫会抓到当前位置上所有老鼠 老鼠到达洞就是安全的 问最多有多少只老鼠进洞
思路
贪心 距离洞最近的先走
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 400005
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n,t,q,l,r,k;
ll a[N];
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=0; i<k; i++)
{
cin>>a[i];
a[i]=abs(a[i]-n);
}
sort(a,a+k);
int i=0;
ll sum=0;
for(; sum+a[i]<n; i++)
{
sum+=a[i];
if(i>=k)//注意边界判断
break;
}
cout<<i<<endl;
}
return 0;
}
D1 - All are Same
题意
给一些数 每个数减去任意次的k 使得这些数相等 问k最大是多少 如果k为任意值 输出-1
思路
所有数-最小值的差值 取所有差值的gcd
代码
#include<cstdio>
#include<cstring>//memset
#include<iostream>//c++
#include<algorithm>//stl
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<map>
#include <sstream>
#define N 400005
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n,t,q,l,r,k;
int a[N];
set<int> se;
set<int>::iterator it;
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
se.clear();
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
if(a[0]==a[n-1])
cout<<-1<<endl;
else
{
for(int i=n-1;i>=0;i--)
{
if(a[i]==a[0])
break;
se.insert(a[i]-a[0]);
}
int ans=a[n-1]-a[0];
for(it=se.begin();it!=se.end();it++)
{
ans=__gcd(ans,*it);
if(ans==1)
break;
}
cout<<ans<<endl;
}
}
return 0;
}
E. Gardener and Tree
题意
现在给你一个图 每次操作删掉所有叶结点 问k次操作后 还剩下多少结点
思路
将每个结点的度和前期结点保存起来 用bfs执行删结点操作(一层一层的删)
代码