本次战绩：五题
但其实还是有水分的hhh，主要是今天打CCF-CSP认证太累了，本人大一第一次打，虽然只得了200分。。。
让我们看题吧：
目录
A题：小红买橘子
签到
B题：小红的传送带
循环比较
C题：小红的好三角形
map
D题：小红的子序列计数
数论
E题：小红的博弈
博弈论
核心结论
为什么会这样？（关键证明）
A题：小红买橘子
签到
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x,y,z;
cin>>x>>y>>z;
int res=z/y;
if(z%y)res++;
cout<<res*x<<endl;
return 0;
}
B题：小红的传送带
循环比较
就是，直接走到的时间，和用每一个传送带的时间比较，就行啦
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
LL n,k;
cin>>n>>k;
LL res=abs(k);
for(int i=1;i<=n;i++)
{
LL x,y;
cin>>x>>y;
res=min(res,abs(x)+abs(k-y));
}
cout<<res<<endl;
return 0;
}
前两个题真的超级水
C题：小红的好三角形
map
就是记录一下可以当顶点的点，坐标范围比较大，要用map，还有要注意，不能三点共线，这个细节要扣一下
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
vector<PLL>dot;
unordered_map<LL, int> cnth, cntz;
unordered_map<LL, unordered_map<LL, int>> same_h, same_z;
int main()
{
int n;
cin>>n;
LL res=0;
for(int i=1;i<=n;i++)
{
LL x,y;
cin>>x>>y;
if(dot.empty())dot.push_back({x,y});
else
{
for(auto t:dot)
{
LL x1=t.first;
LL y1=t.second;
if(x1==x&&(y1+y)%2==0)
{
LL mid = (y1+y)/2;
cntz[mid]++;
same_z[mid][x]++;
}
else if(y1==y&&(x1+x)%2==0)
{
LL mid = (x1+x)/2;
cnth[mid]++;
same_h[mid][y]++;
}
}
dot.push_back({x,y});
}
}
for(auto q:dot)
{
LL x=q.first;
LL y=q.second;
LL add = cnth[x] – same_h[x][y] + cntz[y] – same_z[y][x];
res += add;
}
cout<<res<<endl;
return 0;
}
D题：小红的子序列计数
数论
6 的倍数必须同时满足两个条件：
关键观察：前导零不影响这两个条件（加 0 不改变数字和，也不改变最后一位）。因此问题简化为：统计所有非空子序列中，最后一位是偶数且数字和模 3 等于 0的数量。
我们用动态规划维护前 i 个字符中，子序列和模 3 等于 0、1、2 的数量，遍历每个字符时：
- 如果当前字符是偶数，累加满足条件的子序列数到答案
- 更新 dp 数组，将当前字符加入所有可能的子序列
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD=998244353;
int main()
{
int n;
string s;
cin>>n>>s;
LL cnt[3]={1,0,0};
LL ans=0;
for(char c:s)
{
int d=c-'0';
if(d%2==0)
{
int need=(3-d%3)%3;
ans=(ans+cnt[need])%MOD;
}
LL old[3];
for(int i=0;i<3;i++) old[i]=cnt[i];
int r=d%3;
for(int i=0;i<3;i++)
{
cnt[i]=(old[i]+old[(i-r+3)%3])%MOD;
}
}
cout<<ans<<endl;
return 0;
}
E题：小红的博弈
这个题我其实也不会，没怎么做过博弈论的题，最后靠可以明白了
博弈论
看看AI写的解析吧，我觉得挺清楚的，也很巧妙：
核心结论
这个游戏的胜负条件异常简单：
统计每个石子数出现的次数，如果存在至少一个数出现奇数次，小红（先手）赢；否则小芳（后手）赢。
为什么会这样？（关键证明）
这个结论看似反直觉，但完全符合博弈论的最优策略：
必败态（后手赢）：所有石子数都出现偶数次
- 无论先手从哪一堆取多少个石子，后手总能从另一堆相同数量的石子中取走相同个数，保持所有数出现偶数次
- 最终先手会先无法操作，后手获胜
必胜态（先手赢）：存在至少一个数出现奇数次
- 先手只需取走任意一个出现奇数次的堆的全部石子，就能让所有数都变成偶数次，将必败态抛给后手
- 如果最大的数出现奇数次，先手直接取走最大的堆，剩下的所有石子都小于这次取的 x，后手直接无法操作，先手秒杀获胜
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int T;
cin>>T;
while(T–)
{
int n;
cin>>n;
vector<LL> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
sort(a.begin(),a.end());
bool red_win=false;
int cnt=1;
for(int i=1;i<n;i++)
{
if(a[i]==a[i-1]) cnt++;
else
{
if(cnt&1) red_win=true;
cnt=1;
}
}
if(cnt&1) red_win=true;
cout<<(red_win?"red":"fang")<<endl;
}
return 0;
}
