NOIP2024加赛5
题目来源： 2023NOIP A层联测31
\(T1\) HZTG5777. 暴力操作（opt） \(40pts\)
-
先将 \(\{ a \}\) 升序排序。
-
因为 \(\left\lfloor \dfrac{\left\lfloor \frac{a}{b} \right\rfloor}{c} \right\rfloor=\left\lfloor \dfrac{a}{bc} \right\rfloor\) ，先钦定 \(\forall i,j \in \mathbb{N}^{*},c_{i,j} \le c_{i}+c_{j}\) ，并让每个数仅被操作一遍。
-
考虑二分答案，并只对 \([1,\left\lceil \frac{n}{2} \right\rceil]\) 进行操作。
-
此时需要解形如 \(\left\lfloor \frac{a_{i}}{x} \right\rfloor \le mid\) 的不等式，可以使用二分求解，也可以观察到 \(\frac{a_{i}}{x} < mid+1\) 从而得到 \(x \ge \left\lfloor \frac{a_{i}}{mid+1} \right\rfloor+1\) 。然后取 \(\min\limits_{k \in [\left\lfloor \frac{a_{i}}{mid+1} \right\rfloor+ \infty)}\{ c_{x} \}\) 加入代价。
-
对于 \(\min\limits_{k \in [\left\lfloor \frac{a_{i}}{mid+1} \right\rfloor+ \infty)}\{ c_{x} \}\) 初始时仅通过调和级数处理到 \(m\) 是不够的。
-
设 \(\{ suf \}\) 表示 \(\{ c \}\) 的后缀 \(\min\) 。不妨先处理出 \([1,m]\) 的后缀 \(\min\) ，此时有 \(suf_{m+1}=\min\limits_{i=1}^{m}\{ c_{i}+suf_{\left\lceil \frac{m+1}{i} \right\rceil} \}\) ，再次倒着更新 \([1,m+1]\) 的后缀 \(\min\) 即可。
点击查看代码
ll a[500010],c[500010],suf[500010]; bool check(ll n,ll m,ll k,ll mid) { ll sum=0; for(ll i=1;i<=n/2+1;i++) { if(a[i]>mid) { sum+=suf[a[i]/(mid+1)+1]; } } return sum<=k; } int main() { #define Isaac #ifdef Isaac freopen("opt.in","r",stdin); freopen("opt.out","w",stdout); #endif ll n,m,k,l=0,r,mid,ans=-1,i,j; scanf("%lld%lld%lld",&n,&m,&k); r=m; for(i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(i=1;i<=m;i++) { scanf("%lld",&c[i]); } sort(a+1,a+1+n); c[1]=0; for(i=1;i<=m;i++) { for(j=1;i*j<=m;j++) { c[i*j]=min(c[i*j],c[i]+c[j]); } } suf[m]=c[m]; for(i=m-1;i>=1;i--) { suf[i]=min(suf[i+1],c[i]); } suf[m+1]=0x3f3f3f3f; for(i=1;i<=m;i++) { j=ceil(1.0*(m+1)/i); if(j<=m) { suf[m+1]=min(suf[m+1],c[i]+suf[j]); } } for(i=m;i>=1;i--) { suf[i]=min(suf[i+1],c[i]); } while(l<=r) { mid=(l+r)/2; if(check(n,m,k,mid)==true) { ans=mid; r=mid-1; } else { l=mid+1; } } printf("%lld\n",ans); return 0; }
\(T2\) HZTG5778. 异或连通（xor） \(50pts\)
-
部分分
- 子任务 \(1\) ：\(DFS\) 找连通块。
- 子任务 \(2\) ：加个记忆化即可。
点击查看代码
struct node { ll nxt,to,w; }e[200010]; ll head[200010],vis[200010],siz,cnt=0; unordered_map<ll,ll>f; void add(ll u,ll v,ll w) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; } void dfs(ll u,ll x,ll k) { siz++; vis[u]=1; for(int i=head[u];i!=0;i=e[i].nxt) { if(vis[e[i].to]==0&&(e[i].w^x)<k) { dfs(e[i].to,x,k); } } } int main() { #define Isaac #ifdef Isaac freopen("xor.in","r",stdin); freopen("xor.out","w",stdout); #endif ll n,m,q,k,u,v,w,x,ans=0,i,j; scanf("%lld%lld%lld%lld",&n,&m,&q,&k); for(i=1;i<=m;i++) { scanf("%lld%lld%lld",&u,&v,&w); add(u,v,w); add(v,u,w); } for(j=1;j<=q;j++) { scanf("%lld",&x); if(f.find(x)==f.end()) { ans=0; memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) { if(vis[i]==0) { siz=0; dfs(i,x,k); ans+=siz*(siz-1)/2; } } f[x]=ans; } printf("%lld\n",f[x]); } return 0; } -
正解
- 等学了线段树分治再来补。
\(T3\) HZTG5779. 诡异键盘（keyboard） \(20pts\)
-
部分分
- 子任务 \(1\) ：哈希优化字符串匹配后跑 \(O(n^{3})\) 的 \(DP\) 。
点击查看代码
const ll mod=1000003579,base=13331; ll f[5010],hshs[5010],lent[5010],jc[5010]; vector<ll>hsht[5010]; char s[1000010]; void sx_hash(char s[],ll len) { for(ll i=0;i<=len;i++) { hshs[i]=(i==0)?0:(hshs[i-1]*base%mod+s[i])%mod; } } void sx_hash_t(char s[],ll len,ll id) { for(ll i=0;i<=len;i++) { hsht[id][i]=(i==0)?0:(hsht[id][i-1]*base%mod+s[i])%mod; } } ll ask_hash(ll l,ll r) { return (hshs[r]-hshs[l-1]*jc[r-l+1]%mod+mod)%mod; } int main() { #define Isaac #ifdef Isaac freopen("keyboard.in","r",stdin); freopen("keyboard.out","w",stdout); #endif int t,n,m,len,i,j,k,h; cin>>t; for(i=0;i<=5000;i++) { jc[i]=(i==0)?1:jc[i-1]*base%mod; } for(h=1;h<=t;h++) { memset(f,0x3f,sizeof(f)); cin>>n>>m; for(i=1;i<=n;i++) { cin>>(s+1); lent[i]=strlen(s+1); hsht[i].clear(); hsht[i].resize(lent[i]+10); sx_hash_t(s,lent[i],i); } cin>>(s+1); len=strlen(s+1); sx_hash(s,len); f[0]=0; for(i=1;i<=len;i++) { for(j=0;j<=i-1;j++) { for(k=1;k<=n;k++) { if(i-j<=lent[k]&&ask_hash(j+1,i)==hsht[k][i-j]) { f[i]=min(f[i],f[j]+lent[k]-(i-j)+1); } } } } cout<<((f[len]==0x3f3f3f3f3f3f3f3f)?1:f[len])<<endl; } return 0; } -
正解
\(T4\) HZTG5780. 民主投票（election） \(5pts\)
-
部分分
- 子任务 \(1\) ：模拟。
点击查看代码
vector<int>e[1000010]; int siz[1000010],dfn[1000010],out[1000010],pos[1000010],fa[1000010],sum[1000010],tot; void add(int u,int v) { e[u].push_back(v); } void dfs(int x) { siz[x]=1; tot++; dfn[x]=tot; pos[tot]=x; for(int i=0;i<e[x].size();i++) { dfs(e[x][i]); siz[x]+=siz[e[x][i]]; } out[x]=tot; } bool work(int x,int maxx) { if(x==1) { return true; } x=fa[x]; while(x!=0) { if(sum[x]+1<maxx) { sum[x]++; return true; } x=fa[x]; } return false; } int check(int x,int n) { memset(sum,0,sizeof(sum)); int maxx=siz[x]-1; for(int i=1;i<=n;i++) { if((i<=dfn[x]||i>out[x])&&work(pos[i],maxx)==false) { return 0; } } return 1; } int main() { #define Isaac #ifdef Isaac freopen("election.in","r",stdin); freopen("election.out","w",stdout); #endif int t,n,i,j,k; scanf("%d",&t); for(k=1;k<=t;k++) { scanf("%d",&n); tot=0; for(i=1;i<=n;i++) { e[i].clear(); } for(i=2;i<=n;i++) { scanf("%d",&fa[i]); add(fa[i],i); } dfs(1); for(i=1;i<=n;i++) { printf("%d",check(i,n)); } printf("\n"); } return 0; } -
正解
- 等有时间再补。
总结
- \(T1\) 调和级数仅处理到了 \(m\) ，挂了 \(60pts\) 。
- \(T4\) 链的部分分写假了，挂了 \(20pts\) 。
后记
- \(T1\) 题面从 \(tgHZOJ\) 搬过来的时候忘把更改后的题面（将原 \(x \in [1,m]\) 改成了 \(c_{x \in [1,m]}\)）搬过来了，赛时 \(feifei\) 用画图更改了题面重新下发了。
- \(T3\) 未注明 \(\sum|S_{i}|\) 为单组数据的数据规模。