NOIP2024加赛2
题目来源: 2023NOIP A层联测18
\(T1\) HZTG5733. 新的阶乘 \(100pts\)
-
预处理素数后直接对 \(1 \sim n\) 进行质因数分解因为有太多冗余枚举导致无法通过。
-
考虑枚举最终形式。具体地,从质因数的角度入手,设当前枚举的质数为 \(p\) ,暴力求出 \(ip\) 中 \(p\) 的指数即可。
-
时间复杂度为 \(1 \sim n\) 中每个数质因数分解后的各指数之和 \(=O(n \log n)\) ,在 \(1s\) 内仅能处理 \(3 \times 10^{7}\) 以内的数据。
- 时间复杂度在于暴力求 \(ip\) 中 \(p\) 的指数。
点击查看代码
ll prime[700010],c[700010],len=0; bool vis[10000010]; void isprime(ll n) { memset(vis,0,sizeof(vis)); for(ll i=2;i<=n;i++) { if(vis[i]==0) { len++; prime[len]=i; } for(ll j=1;j<=len&&i*prime[j]<=n;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) { break; } } } } ll ask(ll n,ll p) { ll ans=0; while(n%p==0) { ans++; n/=p; } return ans; } int main() { freopen("factorial.in","r",stdin); freopen("factorial.out","w",stdout); ll n,cnt,mul,i,j; scanf("%lld",&n); isprime(n); for(i=1;i<=len;i++) { for(j=1;prime[i]*j<=n;j++) { c[i]+=(ask(j,prime[i])+1)*(n-prime[i]*j+1); } } printf("f(%lld)=",n); for(i=1;i<=len;i++) { printf("%lld",prime[i]); if(c[i]!=1) { printf("^%lld",c[i]); } if(i!=len) { printf("*"); } } fclose(stdin); fclose(stdout); return 0; }
-
官方题解中省去了暴力求指数的一步。
\(T2\) HZTG5734. 博弈树 \(80pts\)
-
部分分
- \(80pts\) :暴力建出博弈的搜索树,因为状态数规模为 \(O(n^{2})\) ,加个记忆化即可,可能需要 \(O(1)\) 的求 \(\operatorname{LCA}\) (?)。
点击查看代码
struct node { int nxt,to; }e[200010]; int head[100010],dfn[100010],dep[100010],cnt=0,tot=0; unordered_map<int,bool>f[100010]; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } int sx_min(int x,int y) { return dfn[x]<dfn[y]?x:y; } struct ST { int fminn[100010][20]; void init(int n) { for(int j=1;j<=log2(n);j++) { for(int i=1;i+(1<<j)-1<=n;i++) { fminn[i][j]=sx_min(fminn[i][j-1],fminn[i+(1<<(j-1))][j-1]); } } } int query(int l,int r) { int t=log2(r-l+1); return sx_min(fminn[l][t],fminn[r-(1<<t)+1][t]); } }T; void get_dep(int x,int fa) { tot++; dfn[x]=tot; dep[x]=dep[fa]+1; T.fminn[tot][0]=fa; for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa) { get_dep(e[i].to,x); } } } int lca(int u,int v) { if(dfn[u]>dfn[v]) { swap(u,v); } return (dfn[u]==dfn[v])?u:T.query(dfn[u]+1,dfn[v]); } int get_dis(int u,int v) { return dep[u]+dep[v]-2*dep[lca(u,v)]; } bool dfs(int x,int last,int n) { if(f[x].find(last)!=f[x].end()) { return f[x][last]; } for(int i=1;i<=n;i++) { int d=get_dis(x,i); if(d>last&&dfs(i,d,n)==false) { return f[x][last]=true; } } return f[x][last]=false; } int main() { freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); int n,m,u,v,i; cin>>n>>m; for(i=1;i<=n-1;i++) { cin>>u>>v; add(u,v); add(v,u); } get_dep(1,0); T.init(n); for(i=1;i<=m;i++) { cin>>u; if(dfs(u,0,n)==true) { cout<<"Alice"<<endl; } else { cout<<"Bob"<<endl; } } fclose(stdin); fclose(stdout); return 0; }
-
正解
- 若节点 \(x\) 是直径的端点,那么直接判定
Alice
必胜。否则谁先移动到直径的端点谁就输。 - 考虑删去所有直径的端点(一定是叶子节点),若节点 \(x\) 是删完后的树的直径端点,那么
Alice
也是必胜的。因为Alice
可以将点移动到删完后的树的另一个直径端点,而Bob
就只能移到原树的直径端点上,从而得到Alice
必胜。 - 考虑模拟删叶子的过程,若删到最后只剩一个点说明在这个点时
Bob
是必胜的,否则Alice
一定可以通过不断将点移动到下一层的直径端点取得胜利(对于Bob
的干扰,Alice
可以通过利用直径的最长性进行反制)。 - 而最后剩下的这个点一定是直径的中点(直径长度为奇数时),预处理即可。
点击查看代码
struct node { int nxt,to; }e[200010]; int head[200010],dep[200010],fa[200010],cnt=0; vector<int>d; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(int x,int father) { fa[x]=father; dep[x]=dep[father]+1; for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=father) { dfs(e[i].to,x); } } } int main() { freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); int n,m,u,v,rt1=0,rt2=0,i; cin>>n>>m; for(i=1;i<=n-1;i++) { cin>>u>>v; add(u,v); add(v,u); } dfs(1,0); for(i=1;i<=n;i++) { rt1=(dep[i]>dep[rt1])?i:rt1; } dfs(rt1,0); for(i=1;i<=n;i++) { rt2=(dep[i]>dep[rt2])?i:rt2; } while(rt2!=0) { d.push_back(rt2); rt2=fa[rt2]; } for(i=1;i<=m;i++) { cin>>u; if(d.size()%2==0||d[d.size()/2]!=u) { cout<<"Alice"<<endl; } else { cout<<"Bob"<<endl; } } fclose(stdin); fclose(stdout); return 0; }
- 若节点 \(x\) 是直径的端点,那么直接判定
\(T3\) HZTG5735. 划分 \(9pts\)
-
部分分
- 测试点 \(1 \sim 2\) :爆搜。
- 测试点 \(9 \sim 12\)
- 设第一个 \(1\) 出现的位置为 \(pos\) 。那么最大值一定为 \(s_{pos \sim n}\) ,因为 \([pos,n]\) 中任意断开就会导致最大值变小。方案数仅会由前面的 \(0\) 决定,即 \(\sum\limits_{i=k}^{pos}\dbinom{pos-1}{i-1}\) 。
- 若不存在 \(1\) ,则最大值为 \(0\) ,方案数为 \(\sum\limits_{i=k}^{n}\dbinom{n-1}{i-1}\) 。
点击查看代码
const ll p=998244353; ll inv[2000010],jc[2000010],jc_inv[2000010],ans=0,cnt=0; char s[2000010]; ll ask(ll l,ll r) { ll ans=0; for(ll i=l;i<=r;i++) { ans=(ans*2+s[i]-'0'); } return ans; } ll work(ll l,ll r) { ll ans=0; for(ll i=l;i<=r;i++) { ans=(ans*2%p+s[i]-'0')%p; } return ans; } void dfs(ll pos,ll n,ll k,ll sum,ll num,ll last) { if(pos==n) { num++; sum+=ask(last+1,n); if(num>=k) { if(sum>ans) { ans=sum; cnt=1; } else { if(sum==ans) { cnt++; } } } } else { dfs(pos+1,n,k,sum,num,last); dfs(pos+1,n,k,sum+ask(last+1,pos),num+1,pos); } } ll C(ll n,ll m,ll p) { return (n>=m&&n>=0&&m>=0)?(jc[n]*jc_inv[n-m]%p)*jc_inv[m]%p:0; } int main() { freopen("divide.in","r",stdin); freopen("divide.out","w",stdout); ll n,k,pos=0,sum=0,i; cin>>n>>k; for(i=1;i<=n;i++) { cin>>s[i]; pos=(pos==0&&s[i]=='1')?i:pos; } if(pos>k||pos==0) { inv[1]=1; jc[0]=jc_inv[0]=jc[1]=jc_inv[1]=1; for(i=2;i<=n;i++) { inv[i]=(p-p/i)*inv[p%i]%p; jc[i]=jc[i-1]*i%p; jc_inv[i]=jc_inv[i-1]*inv[i]%p; } if(pos==0) { for(i=k;i<=n;i++) { sum=(sum+C(n-1,i-1,p))%p; } cout<<0<<" "<<sum<<endl; } else { for(i=k;i<=pos;i++) { sum=(sum+C(pos-1,i-1,p))%p; } cout<<work(pos,n)<<" "<<sum<<endl; } } else { dfs(1,n,k,0,0,0); cout<<ans%p<<" "<<cnt%p<<endl; } fclose(stdin); fclose(stdout); return 0; }
-
正解
- 考虑不保证 \(\forall i \in [1,k],s_{i}=0\) 时怎么做。
- 最优解的划分方案一定形如选出一段 \(n-k'+1(k' \ge k-1)\) 单独作为一段,剩下的每个数单独作为一段。
- 因为 \(1\) 的数量是一定的,所以所有的构造方案对应的 \(n-k'+1(k' \ge k-1)\) 这段数的前 \(n-k\) 位一定相同(若长度不够 \(n-k+1\) 则先在前面补 \(0\) 补成长度为 \(n-k+1\) 的段,可以证明这并不影响结果)。
- 考虑二分哈希找到最大的划分点,然后哈希判断有多少个其他划分点的前 \(n-k\) 位与其相等。
- 二分哈希的写法类似 暑假集训CSP提高模拟24 D P240.最短路 。
- 需要特判 \(n=k\) 时方案数为 \(1\) 。
点击查看代码
\(T4\) HZTG5736. 灯笼 \(0pts\)
总结
- \(T3\) 没有想 \(\forall i \in [1,k],s_{i}=0\) 的 \(15pts\) 部分分。