难得在比赛中摸了五题,非常开心qwq。
第一次写小白月赛的题解,如果有误,请见谅。
A 子序列的权值最小值
这里运用到 与运算 的性质 x&y ≤ min(x,y) ,所以把数组里面的元素通通 & 一遍,就能得到答案了。
悲催的是,我在比赛时忘记了这个性质,结果脑子一热写了dfs,还好数据量够小。
#include <iostream>
using namespace std;
int main(void)
{
int n,i,t;
cin>>n;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
t=a[0];
for(i=1;i<n;i++)
t&=a[i];
cout<<t;
return 0;
}
B 魔法师晨拥
如果不考虑游戏血量下限 0 ,其实可以无限制的扣血,只用判断血量中途是否为 0 即可。
我喜欢严谨一点,把血量不为正数的随从给删掉了。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void)
{
vector<int> a; // 存储 随从 的容器
int n,m,k=2,t,i,ans=0; // k 是伤害值
cin>>n>>m; // ans 是对敌方英雄造成的伤害
for(i=0;i<n;i++)
{ // 容器的数据插入
cin>>t;
a.push_back(t);
}
for(i=0;i<m;i++)
{ // 游戏过程模拟
if(a.size()==0)
{ // 如果没有随从了,直接怼英雄
ans+=k*(m-i);
break;
}
for(int &x:a)
{ // 对随从进行攻击
x-=k;
if(x==0) // 符合题意
++k; // 增加攻击力
}
while(a.size()!=0)
{ // 删除已经死去的敌方随从
if(*a.begin()<=0)
a.erase(a.begin());
else
break;
}
ans+=k; // 对敌方英雄进行攻击
}
cout<<ans;
return 0;
}
C GCPC总决赛
有一种田忌赛马的味道,不过这里是统计所有可能出现的情况。
对其中一个数组进行全排列即可,但是又有新的问题,0 0 0 只能排 1 种,而我们期望是 6 种。
所以我把第二个数组改成 pair<int,int> 。
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
int n,i;
int t1,t2,ans1=0,ans2=0,ans3=0; // 获胜,失败,平局
cin>>n;
int a[n];
pair<int,int> b[n];
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
{
cin>>b[i].first;
b[i].second=i;
}
sort(a,a+n); // a 好像没有排序的必要
sort(b,b+n); // b 为了全排列而排序
do{
t1=0;
t2=0;
for(i=0;i<n;i++)
{ // 对局模拟
if(a[i]>b[i].first)
++t1;
else if(a[i]<b[i].first)
++t2;
}
if(t1==t2) // 平局
++ans3;
else if(t1>t2) // 获胜
++ans1;
else // 失败
++ans2;
}while(next_permutation(b,b+n)); // 全排列
cout<<ans1<<" "<<ans2<<" "<<ans3;
return 0;
}
D Ginger的大花环
最省钱的方案,就是尽量多拿花费最少的颜色,间隔处补次少的颜色。
只有一种颜色,那就没办法间隔了,需要特判。
两种及以上,先根据花费从小到大对颜色进行排序。
a[0] 是花费最少的,a[1] 是花费次少的。
然后对花的数量分类讨论,分为 0,1,2 。
n%3==0:112112...112 (n/3 个 112)
n%3==1:112112...1122 (n/3 个 112,再加一个 2)
n%3==2:112112...11212 (n/3 个 112,再加一个 12)
注意到一次染色的花费可以达到 1e9,需要使用 long long 避免溢出。
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
int main(void)
{
long long n,m,ans=0;
int k,i;
cin>>n>>k;
long long a[k];
for(i=0;i<k;i++)
cin>>a[i];
sort(a,a+k); // 对颜色进行排序
if(k==1) // 只有 1 种颜色,无法完成任务
cout<<"Ginger666";
else
{
m=n/3; // 有 m 组 112
ans=m*2*a[0]+m*a[1]; // 基础的花费
if(n%3==0)
cout<<ans;
else if(n%3==1)
cout<<ans+a[1]; // 额外的 2
else
cout<<ans+a[0]+a[1]; // 额外的 12
}
return 0;
}
E 最值区间计数
我承认我是蒙的,但是蒙对了。
题目给的样例是 2 和 4,我自己算了 1 和 3,如下所示:
n | 答案 |
---|---|
1 | 1 |
2 | 2 |
3 | 10 |
4 | 60 |
在一番思想斗争后(划掉),我决定舍弃 1 作为规律数据。
得到了递推式 a[i] = a[i-1] * (i+2) ,i>2 。
提交,AC 。
真正符合题意的思考过程,请参考炸鸡块君的视频讲解
#include <iostream>
using namespace std;
int main(void)
{
int n,i;
long long ans=2;
cin>>n;
if(n==1) // 特判 1 的情况
cout<<1;
else
{
for(i=3;i<=n;++i)
ans=ans*(i+2)%998244353;
cout<<ans;
}
return 0;
}
F Ginger的数
hhh这道题我不会做,请参考炸鸡块君的视频讲解