实小社团练习赛11
本文总阅读量次
T1
简单排序
不做解释了……
T2
排序
1.首先要对字符串中的字母进行排序
cin>>s[i]; //字符串小白注意:这里s[i]表示字符串不是单个字符
sort(s[i].begin(),s[i].end());
2.然后对整个字符串数组排序
sort(s+1,s+1+n);
3.经过步骤2,相同字符串已经排在一起了,有两种思路可以统计出有多少对满足要求。
<1>方法1:用打擂台拓展的方式统计出每段的长度,然后用组合公式计算出有多少对符合要求,例如长度5的一段,方案数为
long long cnt = 0;
for(int i = 1; i <= n+1; i++)
if(w[i]==w[i-1]) cnt++;
else{
if(cnt>1) ans += cnt*(cnt-1)/2; //组合公式计算
cnt = 1;
}
<2>方法2:打枪法。
还是以长度5为例,第一个字符串可以跟后面4个搭配,第二个字符串可以跟后面3个搭配,以此类推。
那么,扫描的过程中,搭配个数刚好反过来(递减改递增),见下面这段代码:
for(int i=2;i<=n;i++){
if(s[i]==s[i-1]){ //跟打枪法统计的个数刚好相反,但规律一致
cnt++;
}
else cnt=0;
ans+=cnt;
}
T3
贪心
扫描5个上菜时间,寻找最优的点菜时间,会遇到两种情况:
1.上菜时间是10的倍数,则不做任何处理(马上可以接着点菜),直接累加。
2.上菜时间不是10的倍数,则计算出还差几分钟到10的倍数,算出新的点菜时间后累加(上菜时间+等待时间=下一道菜的点菜时间)。
需要注意的是,最后一个菜下单后不用再点菜了,所以5个上菜时间中,要找出不是10的倍数的上菜时间中,余数最小的那道菜,最后去掉步骤2中加上的时间。
T4
二分答案
数列分段经典题,奶牛题月度花费换内容后的题。
自己要分析出是数列分段。
答案检测
bool check(int x){
int s=0,cnt=1;
for (int i=1;i<=n;i++){
if (a[i]>x) return 0; //还不出
if (s+a[i]>x) s=0,cnt++; //分段
s+=a[i]; //计算一段的和
}
if (cnt<=m) return 1; //段数多了不符合,偏小了;反之符合
return 0;
}