学长让我们刷USACO的水题果然是有道理的,做了四道挂了两道。。。细节处理一定要小心!大概都是NOIP Day1 T1的难度,但是一定要考虑全面否则还是凉凉啊。
一、USACO1.1贪婪的送礼者
题目链接:https://www.luogu.org/problemnew/show/P1201
一个人有一些钱分给一些伙伴,比如我有10块钱分给5个人每人2块(小学数学),当然如果数据都是这样当然很弱智,但是还需要考虑分不完的情况,比如10块钱分给3个人,每人三块,自己剩一块,多好多和谐。所以就是要在每次分时判断人数是否被钱数整除,如果整除直接分,否则每个人分int(money/num),自己剩money%num。
代码相信读者都会而且还会暴露笔者恶心的码风所以被和谐了。。。
二、USACO1.1坏掉的项链
题目地址:https://www.luogu.org/problemnew/show/P1203
由于是字符串环所以可以先将这个字符串复制一份接在后面每次取其中长度为n的一段,相当于在开头位置的断开,然后从两头往后判断是否为同一个字符。
需要考虑的细节:
1.得到的珠子个数大于n,比如r r r r的情况,从左可以取4个,从右可以取4个,一共8个,然而显然最多取4个。有两种处理方式:(1)直接在输出答案时判断,答案大于n就输出n,这时说明其中有重复取得珠子,只需将它给其中任意一边即可。(2)记录从左端取了mx1个,那么右端最多取n-mx1个。
2.w在一串珠子中只能代表一种颜色,比如rrwb的情况,从左取3个的话从右最多取1个,从右取2个的话从左最多取2个,然而这种情况都是与第一种情况重合的所以不用另做考虑。
3.在比较时不能单纯的将从左右开始的每一个元素只与左右端点的颜色比较,因为可能存在左右端点为w的情况,所以需要从左开始找到第一个不为w的颜色来作为参考,右边同理。
代码:
#include<bits/stdc++.h>
using namespace std;
int n;
char ch[];
int main()
{
cin>>n;
cin>>ch+;
for(int i=;i<=n;i++)
ch[i+n]=ch[i];
int ans=;
for(int i=;i<=n;i++)
{
char k1,k2;
int p1=i,p2=i+n-,mx1=,mx2=;
while(ch[p1]=='w'&&p1<=i+n-){
p1++;mx1++;
}
k1=ch[p1];
while(p1<=i+n-){
if(ch[p1]==k1||ch[p1]=='w')
mx1++,p1++;
else break;
}
while(ch[p2]=='w'&&p2>=i&&mx2<n-mx1){
p2--;mx2++;
}
k2=ch[p2];
while(p2>=i&&mx2<n-mx1){
if(ch[p2]==k2||ch[p2]=='w')
mx2++,p2--;
else break;
}
ans=max(ans,mx1+mx2);
}
printf("%d\n",ans);
return ;
}