2024牛客暑期多校训练营8
Preface
最赤石的一集
开局磕磕绊绊一发过了 K,A,E，然后跟榜开 J 出了 114514 个假做法
中间注意到 D 是个模拟+阅读理解的赤石题，滚上去摸了半天被题意杀了一发后过了
（很幸运的是我直接用 double 反而误打误撞过了，没有被卡心态）
然后试图开 G 发现假了，没有想象中的简单，遂全队一起 Rush J
最后搞出来一个差不多对的构造思路，可惜一些边界没处理好最后赛时没改出来，被狠狠拷打了
由于晚上在忙着搞下周百度之星出行的相关事务，G 题的补题就先坑着过两天再说
Haitang and Game
手玩发现这题的博弈部分是假的，只要统计出可以被生成出的数的数量即可，不论使用什么策略最后都是一个萝卜一个坑
从大到小考虑每个数 \(x\) 能否被生成，此时所有 \(>x\) 的数的生成情况已经确定了
要判断是否存在一对数的 \(\gcd\) 等于 \(x\)，算是个经典问题了，用约数容斥一下即可解决
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N],c[N]; long long f[N];
int main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n); memset(c,0,sizeof(c)); int ret=0;
for (RI i=1;i<=n;++i) scanf("%d",&a[i]),c[a[i]]=1;
for (RI i=100000;i>=1;--i)
{
f[i]=0;
for (RI j=i;j<=100000;j+=i) f[i]+=c[j];
f[i]=f[i]*(f[i]-1)/2LL;
for (RI j=i*2;j<=100000;j+=i) f[i]-=f[j];
if (!c[i]&&f[i]>0)
{
//printf("gen = %d\n",i);
c[i]=1; ++ret; f[i]=0;
for (RI j=i;j<=100000;j+=i) f[i]+=c[j];
f[i]=f[i]*(f[i]-1)/2LL;
for (RI j=i*2;j<=100000;j+=i) f[i]-=f[j];
}
}
puts(ret%2?"dXqwq":"Haitang");
}
return 0;
}
Haitang and Uma Musume
赤石模拟题，但比起模拟感觉难点在于阅读题意，读懂了之后写起来还是很容易的
值得一提的是我赛时写的时候没管精度直接 double 乱艹搞过去了，没有加 EPS 之类的
同校很多队伍都是用 long double 反而被卡了，只能说是侥幸
#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#define RI register int
#define CI const int&
using namespace std;
vector <int> base[6][5];
inline void init_base(void)
{
base[1][0]={10,0,5,0,0,2};
base[1][1]={0,9,0,4,0,2};
base[1][2]={0,5,8,0,0,2};
base[1][3]={4,0,4,8,0,2};
base[1][4]={2,0,0,0,9,4};
base[2][0]={11,0,5,0,0,2};
base[2][1]={0,10,0,4,0,2};
base[2][2]={0,5,9,0,0,2};
base[2][3]={4,0,4,9,0,2};
base[2][4]={2,0,0,0,10,4};
base[3][0]={12,0,5,0,0,2};
base[3][1]={0,11,0,4,0,2};
base[3][2]={0,6,10,0,0,2};
base[3][3]={4,0,4,10,0,2};
base[3][4]={3,0,0,0,11,4};
base[4][0]={13,0,5,0,0,2};
base[4][1]={0,12,0,4,0,2};
base[4][2]={0,6,11,0,0,2};
base[4][3]={4,0,4,11,0,2};
base[4][4]={3,0,0,0,12,4};
base[5][0]={14,0,5,0,0,2};
base[5][1]={0,13,0,4,0,2};
base[5][2]={0,7,12,0,0,2};
base[5][3]={5,0,5,12,0,2};
base[5][4]={4,0,0,0,13,4};
}
const double coef[5]={-0.2,-0.1,0,0.1,0.2};
int n,abt[6],abt_mul[6],card[7][10];
int main()
{
init_base();
for (RI i=0;i<=4;++i) scanf("%d",&abt[i]); abt[5]=120;
for (RI i=0;i<=4;++i) scanf("%d",&abt_mul[i]);
for (RI i=1;i<=6;++i)
{
for (RI j=6;j<=8;++j) scanf("%d",&card[i][j]);
// 0~5:ability; 6:friend; 7:drive_pls; 8:train;
int dlt; for (RI j=0;j<=4;++j)
scanf("%d",&dlt),abt[j]=min(1200,abt[j]+dlt);
for (RI j=0;j<=4;++j) scanf("%d",&card[i][j]);
}
scanf("%d",&n); int lv_sp[5]={1,1,1,1,1},cnt_sp[5]={0,0,0,0,0};
for (RI i=1;i<=n;++i)
{
int summer,wgt,drv,tp,m;
scanf("%d%d%d%d%d",&summer,&wgt,&drv,&tp,&m);
vector <pair <int,int>> S;
for (RI j=1;j<=m;++j)
{
int x,y; scanf("%d%d",&x,&y);
S.push_back({x,y});
}
for (RI j=0;j<=5;++j)
{
int lv=summer?5:lv_sp[tp];
double dlt=base[lv][tp][j];
for (auto [x,y]:S) dlt+=card[x][j];
for (auto [x,y]:S)
if (y) dlt*=(1.0+0.01*card[x][6]);
int sum_train=0;
for (auto [x,y]:S) sum_train+=card[x][8];
dlt*=(1.0+0.01*sum_train);
int sum_drv_pls=0;
for (auto [x,y]:S) sum_drv_pls+=card[x][7];
dlt*=(1.0+coef[drv]*(1.0+0.01*sum_drv_pls));
dlt*=(1.0+0.01*abt_mul[j]);
dlt*=(1.0+0.05*m);
int Dlt=(int)floor(dlt);
if (wgt==1&&j==0) Dlt=0;
if (j<=4) abt[j]=min(1200,abt[j]+Dlt);
else abt[j]+=Dlt;
}
if (!summer)
{
++cnt_sp[tp];
if (cnt_sp[tp]==4) lv_sp[tp]=min(5,lv_sp[tp]+1),cnt_sp[tp]=0;
}
for (RI j=0;j<=5;++j) printf("%d%c",abt[j]," \n"[j==5]);
}
return 0;
}
Haitang and Math
不会区间筛，但我们有速率优秀的 Pollard_Rho 爆艹
首先不难想到暴力枚举 \(S(m)=r\)，由于取值只有 \([1,108]\) 因此复杂度可以接受
现在式子转为 \((n-r)\bmod m=0\)，一个必要条件：\(m\) 是 \(n-r\) 的约数
由于一个数的约数个数大约是 \(O(n^\frac{1}{3})\) 级别的，但我们不能直接 \(O(\sqrt n)\) 地枚举约数，而是得先分解质因数后再组合起来
使用 Pollard_Rho，可以勉强卡着时限通过
#include<cstdio>
#include<iostream>
#include<vector>
#include<random>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
namespace Pollard_Rho
{
mt19937_64 rnd(20030909);
inline int quick_mul(CI x,CI y,CI mod)
{
return (__int128)(x)*y%mod;
}
inline int sum(CI x,CI y,CI mod)
{
return x+y>=mod?x+y-mod:x+y;
}
inline int sub(CI x,CI y,CI mod)
{
return x-y<0?x-y+mod:x-y;
}
inline int quick_pow(int x,int p,int mod,int mul=1)
{
for (;p;p>>=1,x=quick_mul(x,x,mod)) if (p&1) mul=quick_mul(mul,x,mod); return mul;
}
inline bool Miller_Rabin(CI n)
{
if (n<=1) return 0;
vector <int> base={2,3,5,7,11,13,17,19,23};
for (int x:base)
{
if (n==x) return 1;
if (n%x==0) return 0;
}
int m=(n-1)>>__builtin_ctzll(n-1);
for (int x:base)
{
int t=m,a=quick_pow(x,m,n);
while (t!=n-1&&a!=1&&a!=n-1) a=quick_mul(a,a,n),t*=2;
if (a!=n-1&&t%2==0) return 0;
}
return 1;
}
inline int get_fact(CI n)
{
if (n%2==0) return 2;
auto f=[&](CI x)
{
return sum(quick_mul(x,x,n),1,n);
};
int x=0,y=0,tot=0,p=1,q,g;
for (int i=0;(i&0xff)||(g=__gcd(p,n))==1;++i,x=f(x),y=f(f(y)))
{
if (x==y) x=tot++,y=f(x);
q=quick_mul(p,sub(x,y,n),n); if (q) p=q;
}
return g;
}
inline vector <int> solve(CI n)
{
if (n==1) return {};
if (Miller_Rabin(n)) return {n};
int d=get_fact(n); auto v1=solve(d),v2=solve(n/d);
auto i1=v1.begin(),i2=v2.begin(); vector <int> ans;
while (i1!=v1.end()||i2!=v2.end())
{
if (i1==v1.end()) ans.push_back(*i2++);
else if (i2==v2.end()) ans.push_back(*i1++);
else ans.push_back(*i1<*i2?*i1++:*i2++);
}
return ans;
}
};
using namespace Pollard_Rho;
int t,n,r,ans; vector <int> p,c;
inline int S(int x)
{
int ret=0; while (x) ret+=x%10,x/=10; return ret;
}
inline void DFS(CI now=0,CI m=1)
{
if (now>=(int)p.size())
{
int tmp=S(m);
if (tmp==r&&n%m==tmp) ++ans;
return;
}
int cur=1; for (RI i=0;i<=c[now];++i) DFS(now+1,m*cur),cur*=p[now];
}
signed main()
{
for (scanf("%lld",&t);t;--t)
{
scanf("%lld",&n); ans=0;
for (r=1;r<=min(108LL,n-1);++r)
{
auto fact=solve(n-r);
p.clear(); c.clear();
for (auto x:fact)
if (p.empty()||x!=p.back()) p.push_back(x),c.push_back(1); else ++c.back();
DFS();
}
printf("%lld\n",ans);
}
return 0;
}
Haitang and Rock Paper Scissors
比赛时候上去冲了一发 DP 发现没法区分最优策略和中间转移的策略，因此感觉是个 DP 套 DP
赛后看题解也没咋看懂，等过段时间看下视频讲解再琢磨下
Haitang and Triangle
最唐氏的一集，全队被这个过穿了的题腐乳，直到最后徐神发现了三个数一组的构造方式，但我上去 Rush 的时候边界写唐了就寄了
大致思路和题解中讲的大差不差，主要要想到构造一种 \(m=0\) 的方案，其它的情况都在上面扩展
以下以 \(n=9,10,11\) 三种情况展示构造思路：
n = 9: 3 6 9 2 5 8 1 4 7
n = 10: 10 3 6 9 2 5 8 1 4 7
n = 11: 10 3 6 9 2 5 8 1 4 7 11
#include<bits/stdc++.h>
using namespace std;
vector<int> pushNone(int x){
vector<int> res;
if (x%3>0) res.push_back(x/3*3 + 1);
int len=x/3;
for (int i=len; i>0; --i){
res.push_back(i);
res.push_back(i+len);
res.push_back(i+2*len);
}
if (x%3==2) res.push_back(x);
return res;
}
void solve(){
int n, m; cin >> n >> m;
if (m>=n-2){
cout << "-1\n";
return;
}
vector<int> ans = pushNone(n-m);
for (int i=n-m+1; i<=n; ++i) ans.push_back(i);
if ((n-m)%3==1 && m>0) swap(ans[0], ans[n-m]);
for (int x : ans) cout << x << ' '; cout << '\n';
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while (t--) solve();
return 0;
}
Haitang and Ava
神秘签到题，我题意都不知道
#include <bits/stdc++.h>
void work() {
std::string s; std::cin >> s;
std::vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for(int i = 0; i < s.size(); ++i) if(dp[i]) {
if(i + 3 <= s.size() && strncmp(s.c_str() + i, "ava" , 3) == 0) dp[i + 3] = true;
if(i + 5 <= s.size() && strncmp(s.c_str() + i, "avava", 5) == 0) dp[i + 5] = true;
}
std::cout << (dp[s.size()] ? "Yes\n" : "No\n");
}
int main() {
std::ios::sync_with_stdio(false);
int T; std::cin >> T; while(T--) work();
return 0;
}
Postscript
看似好转的病情看来又加重了，明天开火车估计要被 Div.2 创飞了
辣鸡老年选手AFO在即