前言:本人大一萌新,第一次打ccpc线下赛,和队友A3题,收获铜牌一枚,感受到了老师所说的氛围感。因为F题滑动窗口优化不会写(坤础忘了),痛失银牌,来年再战。
题目:Problem A. 小水獭游河南(签到)
小水獭来到河南旅游,它认为一个字符串 s 是 HENAN 的当且仅当存在两个非空字符串 a 和 b 满
足如下三个条件:
• a 由小写字母组成,且 a 中每种字母只出现了一次。
• b 由小写字母组成,且 b 是回文串,也就是说将 b 翻转后得到的字符串和 b 相同。
• 将 a 和 b 顺序拼接得到的字符串和 s 相同,也就是说 s = a + b。
例如 henan 是 HENAN 的,因为 henan=he+nan,此外也可分解为 hena+n。但 hhnan 和 ysmihoyocom
不是 HENAN 的。
现在给定一个字符串,请你帮助小水獭判断它是不是 HENAN 的。
这题只需要我们暴力枚举即可,最多只用枚举到下标为25的地方(下标从0开始),因为往后必定会出现a中有重复字符的情况(英文字母就26个啊),不满足题目条件。所以只需要枚举前min(len,26)位,用substr函数截取子串,reverse翻转子串判断是否为回文串即可。
注意:这题有个坑点是len的长度为1,这样就不满足题目要求a,b都为非空的情况,直接输出NaN即可。
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include <set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int cnt[26];
void solve(){
memset(cnt,0,sizeof cnt);
string s;cin>>s;
int len=s.size();
if(len==1){
cout<<"NaN\n";
return;
}
for(int i=0;i<min(len,26);i++){
if(cnt[s[i]-'a']){
cout<<"NaN\n";
return;
}
cnt[s[i]-'a']++;
string s1,s2=s.substr(i+1);
s1=s2;
reverse(s2.begin(),s2.end());
if(s1==s2){
cout<<"HE\n";
return ;
}
}
cout<<"NaN\n";
return;
}
int main() {
int T=1;cin>>T;
while(T--)solve();
return 0;
}
题目:Problem H. Travel Begins(贪心)
这题应该是个贪心,让我们将n分成至多份,然后求每份和的最大值和最小值。
根据题上的要求,求最小时,我们把n每次分出来0.4999999...求最大时,把n每次分出来0.5。
求最小时分两种情况:1.n能分出来k个0.49999.... 2.n分不出来k个0.49999...
同理,求最大也是这个思路,观察能不能k个分出来0.5
注意:我这个方法计算时会出现浮点数,所以前面强制转了int类型。
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include <set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
void solve(){
int n,k;cin>>n>>k;
//算最小值部分
if(n-(k-1)*0.5<=0){
cout<<0;
}
else {
if((k-1)&1){
cout<<(int)(n-(k-1)*0.5+1);
}
else cout<<(int)(n-(k-1)*0.5);
}
cout<<" ";
//算最大值部分
if(n-k*0.5>0){
if((k-1)&1){
cout<<(int)(k-1+n-(k-1)*0.5)+1;
}
else cout<<(int)(k-1+n-(k-1)*0.5);
}
else {
cout<<n*2;
}
cout<<"\n";
}
int main() {
int T=1;cin>>T;
while(T--)solve();
return 0;
}
题目:Problem F. Art for Last(滑动窗口)
这题的思路是,从头开始枚举每一个长度为k的区间。在这个区间内找到一个最小的差值,然后计算(最小的差值*区间两端点的差值),最后取个min即可。证明就不写了,因为是随便选k个数,排序后直接取就行。
这题用的是滑动窗口优化写的,不然的话时间每次查找最小值时会有很多重复操作,时间复杂度是O() ,1e6的范围直接爆掉。
赛后补题用优先队列实现滑动窗口,再算上排序。时间复杂度是O(),过掉。
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include <set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=5e5+10;
int a[N],q[N],b[N],c[N];
int n,k;
int main() {
cin>>n>>k;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);//输入原数组
sort(a+1,a+1+n);//排序
for(int i=1;i<n;i++){
b[i]=a[i+1]-a[i];//计算两数差值
}
/* for(int i=1;i<n;i++)cout<<b[i]<<" ";
cout<<endl; */
priority_queue<pii,vector<pii>,greater<pii> > q;
//优先队列实现滑动窗口
for(int i=1;i<k;i++)q.push({b[i],i});
//存储差值和下标,以插值排序。我这里先存储了k个。
for(int i=1;i+k-1<=n;i++){
//枚举区间算最大
c[i]=q.top().first;
while(q.top().second<=i&&q.size())q.pop();
//下标不满足时直接删除。等同于滑动窗口的去除队头操作
q.push({b[i+k-1],i+k-1});
//直接将差值和下标加入即可,优先队列会自动排序。
}
/* for(int i=1;i<n;i++)cout<<c[i]<<" ";
cout<<endl; */
ll res= 1e18;//小心不开long long
for(int i=1;i+k-1<=n;i++){
res=min(1LL*(a[i+k-1]-a[i])*c[i],res);//计算最小值
}
cout<<res;
return 0;
}
题目:Problem C. Toxel 与随机数生成器(确实挺随机的)
题解里说解法很多,确实!
我们截取前1000个字符,然后从1001开始找,如果有相同那就是NO;否则就YES
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include <set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int main() {
string s,s1;cin>>s;
s1=s.substr(0,1000);
s.erase(0,1000);
if(s.find(s1)!=-1)cout<<"NO\n";
else
cout<<"YES\n";
return 0;
}
结尾:
大一萌新第一次参加线下比赛,能拿奖牌十分甚至九分激动。
F题的滑动窗口优化卡了很久也没能调出来,痛失银牌,很可惜(基础差了)。卡太久就应该换题了,第一次参加没有经验。团队合作是很重要的一点,找队友思维的漏洞,三个人如果自己写自己的,那只能打铁。
前几题都是思维题,并没有涉及太多算法,所以要注重对思维的训练。