永远不要相信他的数据强度
考试经过
开题，T1感觉很sb半小时切了，拍上不管了，T2题目感觉很毒瘤，于是先打了T3和T4的暴力，然后推波柿子搞上T3的15部分分，剩不到一个小时回头看T2，看着样例解释脑补了一个贪心策略，然后一个\(n\log n\)的模拟，怕挂掉就写了\(20pts\)的测试点分治
实测100+100+35+0=235，由于后面新造了好多数据所以排名一直在变，前两个切了，然而T4暴力挂了，rank就炸了
T1.异或
据说可以直接算，不过我还是写了数位dp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int bit[62],g[62];
inline int get(int l)
{
int ans=0;
for(int i=0;i<l;i++)ans+=(i+1)*bit[l-1-i];
ans+=l+1;
return ans;
}
int dfs(int lim,int x,int s)
{
if(!x)return s+1;
int ans=0;
if((lim>>(x-1))&1)
{
ans+=g[x-1];
ans+=dfs(lim,x-1,s+1);
}
else ans+=dfs(lim,x-1,0);
return ans;
}
signed main()
{
bit[0]=1;for(int i=1;i<=60;i++)bit[i]=bit[i-1]*2;
g[0]=1;for(int i=1;i<=60;i++)g[i]=get(i);
int n;cin>>n;
cout<<dfs(n-1,60,0)<<endl;
return 0;
}
T2.赌神
正确策略是：你每次按照剩的球等比例下注，把钱全下完，对手一定选当前数量最多的球落下，也就是让球数尽量平均，模拟即可
似乎不太好理性证明，但是可以感性理解
如果你的最优策略一旦确定，那么对面的操作对你的收益是没有影响的，这个策略会让你的收益更大
题解先用了dp，然后验证之后发现就是一个从 \(n\)维平面某个点走到原点的方案，显然可重集排列，所以直接一个柿子推出来
我用堆实现带一个\(log\)，用桶模拟是\(O(n)\)
#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=1000050;
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
int a[N],inv[N],n;
priority_queue <pair<int,int> > q;
signed main()
{
n=read();int sum=0;
for(int i=1;i<=n;i++)
{
a[i]=read();sum+=a[i];
q.push(make_pair(a[i],i));
}
inv[1]=1;for(int i=2;i<=sum;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
int ww=1;
while(sum)
{
int x=q.top().second,w=q.top().first;q.pop();
ww=1ll*ww*inv[sum]%mod*w%mod*n%mod;
q.push(make_pair(w-1,x));sum--;
}
cout<<ww<<endl;
return 0;
}
有时候问题不一定非要往复杂想，简单化可能就是正解
T3.路径
被告知是知识点的原题，涉及到斯特林数
这个套路是对这个\(k\)次方展开，把它改成斯特林的形式
假设\(ans_x\)代表每个x到所有点的答案，最后求和再除以二，直接贴柿子
所以求出对应的\(\sum C\)就行了
设\(f_{i,j}\)表示在\(i\)的子树内对应\(j\)的\(\sum\)的答案，利用组合数的性质可以递推
然后做一个换根dp就行，注意取模
#include <bits/stdc++.h>
using namespace std;
const int N=1000050;
const int mod=998244353;
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
inline int A(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int P(int x,int y){return x-y>0?x-y:x-y+mod;}
struct node{
int from,to,next;
}a[2*N];
int head[N],mm=1;
inline void add(int x,int y)
{
a[mm].from=x;a[mm].to=y;
a[mm].next=head[x];head[x]=mm++;
}
int f[N][105],g[N][105],n,k;bool v[N];
void dfs1(int x)
{
v[x]=1;f[x][0]=1;
for(int i=head[x];i;i=a[i].next)
{
int y=a[i].to;
if(v[y])continue;
dfs1(y);
for(int j=1;j<=k;j++)
f[x][j]=A(A(f[x][j],f[y][j]),f[y][j-1]);
f[x][0]=A(f[x][0],f[y][0]);
}
}
void dfs2(int x)
{
v[x]=1;
for(int i=head[x];i;i=a[i].next)
{
int y=a[i].to;
if(v[y])continue;
for(int j=0;j<=k;j++)
{
int f1=0,f2=0;
f1=P(P(g[x][j],f[y][j]),((j-1>=0)?f[y][j-1]:0));
f2=P(((j-1>=0)?P(g[x][j-1],f[y][j-1]):0),((j-2>=0)?f[y][j-2]:0));
g[y][j]=A(A(f[y][j],f1),f2);
}
dfs2(y);
}
}
int sit[105][105],jc[105];
signed main()
{
n=read(),k=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
add(x,y);add(y,x);
}
dfs1(1);memset(v,0,sizeof(v));
for(int i=0;i<=k;i++)g[1][i]=f[1][i];
dfs2(1);
sit[0][0]=jc[0]=1;
for(int i=1;i<=k;i++)
{
sit[i][0]=0;
for(int j=1;j<=i;j++)
sit[i][j]=A(1ll*j*sit[i-1][j]%mod,sit[i-1][j-1]);
jc[i]=1ll*jc[i-1]*i%mod;
}
int ans=0;
for(int i=1;i<=n;i++)for(int j=0;j<=k;j++)
ans=A(ans,1ll*sit[k][j]*jc[j]%mod*g[i][j]%mod);
cout<<1ll*ans*499122177%mod;
return 0;
}
有关斯特林的先咕了，等学到了详细写
T4.树
分块好题，dfs序分块+根号分治
暂时没做，学了之后一定要做
吐槽下这数据弱的真实，最大树高25也是醉了
考试总结
乱搞能力太差，这是一个比较尴尬的缺点，别人会骗到很多分，自己只有暴力
写的时候一定要专注，不要轻敌，细节把握好，记得检查