比赛链接：https://codeforces.com/contest/1430
A：https://codeforces.com/contest/1430/problem/A
题意：给你一个n，让你输出三个数a，b，c使得3 * a+5 * b+7 * c=n。如果不存在的话，输出-1就好。
思路：看一下数据范围，大暴力就好。（我写的时候根本不敢暴力，最后抱着必WA的心态交的）
//team yglance+xhwl+TTD
//author： CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int main()
{
ios::sync_with_stdio(false);
//freopen("in.in","r",stdin);
//freopen("mine.out","w",stdout);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a=0,b=0,c=0;
if(n%3==0)
{
a=n/3;
cout<<a<<" "<<b<<" "<<c<<endl;
continue;
}
if(n%5==0)
{
b=n/5;
cout<<a<<" "<<b<<" "<<c<<endl;
continue;
}
if(n%7==0)
{
c=n/7;
cout<<a<<" "<<b<<" "<<c<<endl;
continue;
}
int f=0;
for(a=n/3+1;a>=0;a--)
{
for(b=0;b<=201;b++)
{
for(c=0;c<=143;c++)
{
if(a*3+b*5+c*7==n)
{
cout<<a<<" "<<b<<" "<<c<<endl;
a=-5;
b=2000;
c=3000;
f=1;
break;
}
}
}
}
if(f==0)
{
cout<<"-1"<<endl;
}
}
return 0;
}
B：https://codeforces.com/contest/1430/problem/B
题意：给你n个装了水的水桶（容量无限），有k次机会可以相互倒而且数量任意，叫你最大化含水量最多和最少的水桶的差值。
思路：求和就好，把最大的k桶水都放进这k个桶中一个里，它和其他为零的桶的差值必然最大
//team yglance+xhwl+TTD
//author：CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=2e5+7;
const double pi=acos(-1);
using namespace std;
ll a[maxn];
int main()
{
ios::sync_with_stdio(false);
//freopen("in.in","r",stdin);
//freopen("mine.out","w",stdout);
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
for(int i=n-2;i>=0&&k;i--)
{
a[n-1]+=a[i];
a[i]=0;
k--;
}
cout<<a[n-1]<<endl;
}
return 0;
}
C：https://codeforces.com/contest/1430/problem/C
题意：给你1-n的序列，你可以任意选择两个进行求和，然后删除它们，然后又把它们的平均值加回来。要最后回剩下一个数，要你最小化这个数，并展示过程。
思路：不难发现答案必然为2。你把n-2和n删除后，可以得到n-1，然后两个n-1变成1个。这个时候比最大值恰好小1的数是不存在。你的用n-1与n-3来获取n-2，不断地把X（当前最大值）与X-2相消以获得X-1，最后恰好可以变成1与3，得到答案2。我这个办法除了第一步和第二步特殊外，其他都很常规。所以需特判掉2。
例子：
//team yglance+xhwl+TTD
//author： CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=2e5+7;
const double pi=acos(-1);
using namespace std;
int main()
{
ios::sync_with_stdio(false);
//freopen("in.in","r",stdin);
//freopen("mine.out","w",stdout);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
if(n==2)
{
cout<<2<<endl;
cout<<1<<" "<<2<<endl;
continue;
}
cout<<2<<endl;
cout<<n<<" "<<n-2<<endl;
cout<<n-1<<" "<<n-1<<endl;
for(int i=n-1;i>=3;i--)
{
cout<<i<<" "<<i-2<<endl;
}
}
return 0;
}
D：https://codeforces.com/contest/1430/problem/D
题意：给你一个长度为n的01串，每次操作你可以任意删除一个元素，然后把当前串的最大相同前缀（这里指的就是所有连续的0和1）删除，问你这个串最多需要多少次操作才能删除到成为一个空串。
思路：不难发现这道题中连续的串意义很大，如果形如111的串在最前面（在最前面2个就好），那么这次删除就可以只损失这些1，而不损失任何0。如果形如111的串不在最前面（不在最前面3个才有统计的意义，具体原因请继续看），那么当最前面是形如010的情况时，可以在111里面删除一个1，使损失更小，不会使得前面损失两种不同的数。这么一来就很清楚了，首先我们要欲处理字符串中的连续部分的长度，哪怕长度为1也是需要的。然后就是计算答案的过程。如果最前面的是一个比1大的数，说明形如11……的串在前面，这次删除我们可以使另一种数不被删除。但是如果是形如010……这样的最前面两个不相同且为1。这时我们说到的形如111的串不在最前面就派上用场了，我们可以在111……里面删除一个，然后前面就只会损失一种数，但是如果被删除后恰好为2了，就不能再用它，否则它为最前面的时候就要给后面添麻烦了。
至此代码也就写出来了。对于寻找长度大于3等于的连续串，我们可以用队列来帮助我们。
//team yglance+xhwl+TTD
//author： CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=2e5+7;
const double pi=acos(-1);
using namespace std;
string s ;
ll a[maxn];//记录s中的连续串长度
ll ans=0;
queue<ll > que;//记录长度大于等于3 的连续串在a中的位置
int main()
{
ios::sync_with_stdio(false);
//freopen("in.in","r",stdin);
//freopen("mine.out","w",stdout);
int t ;
cin>>t;
while(t--)
{
while(!que.empty())//队列清空
{
que.pop();
}
int n;
cin>>n;
cin>>s;
int cnt=0;//记录连续串的数量
int p=0;//记录连续串的头部
ans=0;
for(int i=0;i<n;i++)
{
if(s[i]==s[p])
{
continue;
}
else
{
if(i-p<=2)//长度为 1或2 、 3+的连续串处理方法不同
{
a[cnt++]=i-p;
p=i;
}
else//大于等于3，它们需要入队
{
a[cnt++]=i-p;
que.push(cnt-1);
p=i;
}
}
}
a[cnt++]=n-p;//最后一组别忘记
if(n-p>=3)
{
que.push(cnt-1);
}
// for(int i=0;i<cnt;i++)
// {
// cout<<a[i]<<" ";
// }
// cout<<endl;
for(int i=0;i<cnt;)
{
if(a[i]==1)//如果最前面是个单独串（单独字符）
{
if(i==cnt-1)//额外判断一下是不是最后一个
{
ans++;
i++;
}
else
{
if(que.empty() !=1)//队列不为空，去后面找长度大于等于3的串来帮忙
{
a[que.front()]--;
if(a[que.front()]==2)//长度变成2了，失去作用！
{
que.pop();
}
i++;
ans++;
}
else//队列空了
{
if(a[i+1]==1)// 最前面两个不相同且为1
{
ans++;
i+=2;//这次要位移两个单位
}
else//第二位开始有一个不为长度 1 的连续串
{
ans++;
a[i+1]--;//记得把长度减去
i+=1;
}
}
}
}
else//最前方长度不为1。
{
ans++;
i++;
}
while(que.empty() !=1 && que.front()<=i)//这里要注意，很可能我们删除的最前面的串就是队列里的串。
{
que.pop();
}
}
cout<<ans<<endl;
}
return 0;
}
写在最后：
人和人之间学习能力的差距怎么这么大？
京公网安备 11010502036488号