noip模拟测试52
这套题总体来说比较简单，但是有一些分数我没有拿到，先说T1，我10分钟左右打完了60分的暴力，然后就开始打表找规律，好像只有我去找了循环节，找规律找了一个多小时，到八点四十的时候我还没有正解做法，就直接弃掉了，浪费了好多时间…..然后是T2，看到n==1的点果断输出1，拿了20分走人，然后是T3，我觉得跟之前考过的一道题比较像，但是那道题我没有改过，不过应该是可以用类似的思想，点分治，但是我觉得复杂度有问题，于是看到了\(k==1\)的特殊性质，就去想了一个\(o(n)\)的树上dp,然后打暴力验证，最后竟然把点分治给忘了！！！！，然后是T4，我研究了一下式子，发现满足条件的点可以写成\(deep_v-deep_u=kx+y\)的形式，但是我觉得复杂度应该没什么变化，还是个暴力，就直接打了个最省事的暴力走人了，考完发现数据太水了，第三，四题我的思路完全可以过，A掉的人还是不少的。
总结一下：1.有一些思路先写下来，避免一会忘了。2.考试代码能优化一点是一点，别偷懒。3.合理安排时间，如果一个多小时还没正解思路就赶紧换题
T1 异或
思路：这题真是。。基本上人手一个AC，但是只有我去找循环节把自己搞傻了，没发现二进制下数字的表示规律。正解：考虑每一位的贡献,从低到高的第\(i\)位会每隔\(2^i\)个数变化一次,于是第\(i\)位对答案的贡献就是\(\lfloor\frac{n}{2^i}\rfloor\),把每一位的贡献加起来即可.
代码如下：
#include<bits/stdc++.h>
signed main(){long long n,ans=0;scanf("%lld",&n);for(long long i=0;(1ll<<i)<=n;i++) ans+=(n/(1ll<<i));printf("%lld\n",ans);return 0; }
T2 赌神
思路：先说一下什么叫最优策略，就是保证在任何时候都没有更劣的策略，对于这道题而言，在最优策略下,不同的掉球情况下你最终所能获得的筹码数应该相同。
代码如下：
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
const int N=1e6+10;
const int mo=998244353;
int n,inv,ans=1,up,down=1;
int a[N],jc[N];
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
ii ksm(int d,int z)
{
int out=1;
while(z){ if(z&1) out=out*d%mo;z>>=1;d=d*d%mo;}
return out%mo;
}
signed main()
{
n=read();
for(re i=1;i<=n;i++) a[i]=read(),up=up+a[i];
jc[0]=1;
for(re i=1;i<N;i++) jc[i]=jc[i-1]*i%mo;
for(re i=1;i<=n;i++) down=down*jc[a[i]]%mo;
for(re i=1;i<=up;i++) ans=ans*i%mo;
ans=ans%mo*ksm(down,mo-2)%mo;
up=ksm(n,up)%mo;
ans=up*ksm(ans,mo-2)%mo;
printf("%lld\n",ans);
return 0;
}
T3 路径
思路：我现在只会复杂度在\(o(n^2\times log(n))\)左右的做法，因为数据较水的原因，这题可以过，思路是点分治，显然是运用点分治思想的裸题，但是要存储每个点到分治中心的距离，以及这个距离的个数，不能一个一个存，会超时，虽然这样优化以后复杂度也是假的。。。
其实正解就是在此基础上用了一个fft优化，但是我不会，可以看这里
代码如下：
#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
#define head heeadd
#define next net
#define ms md
#define f() cout<<"YES"<<endl
using namespace std;
const int N=1e6+10;
const int mo=998244353;
int n,k,root,jd,tot;
int to[N<<1],head[N],next[N<<1];
int fa[N],deep[N],size[N],md[N];
int cun[N],col[N],cun_col[N];
int c2[N],cun_c2[N];
bool vis[N],hav[N],h2[N];
long long ans;
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
iv add(int x,int y)
{
to[++tot]=y;
next[tot]=head[x];
head[x]=tot;
}
long long ksm(long long d,long long z)
{
long long out=1;
while(z)
{
if(z&1) out=out*d%mo;
z>>=1;
d=d*d%mo;
}
return out;
}
iv get_root(int st,int f)
{
size[st]=1,md[st]=0;
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(p==f or vis[p]) continue;
get_root(p,st);
size[st]+=size[p];
md[st]=max(md[st],size[p]);
}
md[st]=max(md[st],jd-size[st]);
if(md[st]<md[root]) root=st;
}
iv get_dis(int st,int f)
{
deep[st]=deep[f]+1;
if(!h2[deep[st]]) h2[deep[st]]=1,cun_c2[++cun_c2[0]]=deep[st],c2[deep[st]]++;
else c2[deep[st]]++;
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(p==f or vis[p]) continue;
get_dis(p,st);
}
}
iv calc(int st)
{
for(re i=1;i<=cun_col[0];i++) hav[cun_col[i]]=0,col[cun_col[i]]=0;
cun_col[0]=0;
cun_col[++cun_col[0]]=0,hav[0]=1,col[0]=1;
deep[st]=0;
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(vis[p]) continue;
cun_c2[0]=0;
get_dis(p,st);
for(re j=1;j<=cun_col[0];j++)
{
for(re b=1;b<=cun_c2[0];b++)
ans=(ans+1ll*ksm(cun_col[j]+cun_c2[b],k)%mo*1ll*col[cun_col[j]]%mo*1ll*c2[cun_c2[b]]%mo)%mo;
}
for(re b=1;b<=cun_c2[0];b++)
{
if(!hav[cun_c2[b]]) hav[cun_c2[b]]=1,cun_col[++cun_col[0]]=cun_c2[b],col[cun_c2[b]]+=c2[cun_c2[b]];
else col[cun_c2[b]]+=c2[cun_c2[b]];
h2[cun_c2[b]]=0,c2[cun_c2[b]]=0;
}
}
}
iv solve(int st)
{
vis[st]=1;
calc(st);
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(vis[p]) continue;
root=0,ms[0]=jd=size[p]+1;
get_root(p,st);
solve(p);
}
}
signed main()
{
n=read(),k=read();
int u,v;
for(re i=1;i<n;i++)
{
u=read(),v=read();
add(u,v),add(v,u);
}
ms[0]=jd=n+1;
get_root(1,0);
solve(root);
printf("%lld\n",ans);
return 0;
}
T4 树
思路：这道题真的很暴力呀，数据真的是太水了。首先我们把满足条件的点化成\(deep_v-deep_u=k\times x+y\)的形式，然后我们用一个vector存储每一层（到达跟节点距离为x）的点，最后直接暴力枚举下跳即可。
代码如下:
#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
#define head heeadd
#define next net
using namespace std;
const int N=3e5+10;
int n,q,tot,timi;
int to[N<<1],head[N<<1],next[N<<1],val[N];
int fa[N],deep[N],dfn[N],size[N],md[N];
vector<int> v[N];
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
iv add(int x,int y)
{
to[++tot]=y;
next[tot]=head[x];
head[x]=tot;
}
iv dfs(int st,int f)
{
deep[st]=deep[f]+1,fa[st]=f,dfn[st]=++timi,size[st]=1,md[st]=deep[st];
v[deep[st]].push_back(st);
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(p==f) continue;
dfs(p,st);
size[st]+=size[p];
md[st]=max(md[st],md[p]);
}
}
iv change(int p,int x,int y,int z)
{
for(re i=deep[p]+y;i<=md[p];i+=x)
for(re j=0;j<v[i].size();j++)
if(dfn[v[i][j]]>=dfn[p] and dfn[v[i][j]]< dfn[p]+size[p]) val[v[i][j]]+=z;
}
signed main()
{
n=read(),q=read();
int u,v,opt,x,y,z;
for(re i=1;i<n;i++)
{
u=read(),v=read();
add(u,v),add(v,u);
}
dfs(1,0);
while(q--)
{
opt=read();
if(opt==1) u=read(),x=read(),y=read(),z=read(),change(u,x,y,z);
else u=read(),printf("%d\n",val[u]);
}
return 0;
}
