当前位置: 首页 > news >正文

NOIP 2024

时隔一年重新做。

T1 因为之前做过的缘故 大概 15min 贪心秒了。都不能换就跳过,相同也跳过。否则诶个检查 \(s_1,s_2\) 可不可以换成功,成功了就跳过不要再多换一次了。

换的过程考虑从 \(i\) 后面开始一直走,直到遇见不能换的字符终止。期间如果有与原位置字符不一样的我们就可以交换它和原字符。因为可以互相交换所以内部顺序必定可以调整到和原来一样。所以直接换没问题。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define For(i,l,r) for(int i=l;i<=r;i++)
int n,ans,j,j2,f;
string s1,s2,t1,t2;
void work(string &t,string &s,int i,int &j){for(j=max(j,i+1);t[j]=='1';j++){if(s[i]==s[j])continue;f=1;swap(s[i],s[j]);ans++;break;}
} 
void solve(){cin>>n>>s1>>s2>>t1>>t2;ans=j=j2=0;For(i,0,n-1){if(s1[i]==s2[i]){ans++;continue;}if(t1[i]==t2[i]=='0')continue;f=0;if(t1[i]=='1')work(t1,s1,i,j);if(f)continue;if(t2[i]=='1')work(t2,s2,i,j2);}cout<<ans<<"\n";
} 
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int T;cin>>T;while(T--)solve();return 0;
}

T2 一眼数学题,用时 30min 左右。正难则反考虑总方案数减去特意构造的不合法方案。由题意知每个位置的限制只和它前面的数字有关,而前面的数字一直往前继续相关,最终得到这个数字只和其前面第一个指定的 \(x_c=d\) 这里有关系,再往前的并没有影响。对于第一个 \(x_c=d\) 的前缀无限制,\(a_i,b_i\) 两变元随便选所以有 \(v^2\) 种选法,对于每个 \(1\rightarrow c_1-1\) 的位置都乘上这个贡献即可。

其它中间段的总方案数同样这么算,\(total={v^2}^{r-l}=v^{2(r-l)}\)。现在考虑如何构造不合法情况。

不合法,即前面指定的 \(x\) 推出与后面指定 \(x\) 的值不同的一个情况。怎么推呢,很明显只有 \(x_i=a_i \rightarrow x_{i+1}=b_i\) 且有 \(a_{i+1}=x_{i+1} \rightarrow x_{i+2}=b_{i+1}\),然后继续,\(a_{i+2}=x_{i+2} \rightarrow x_{i+3}=b_{i+2}\)……最后一环套一环唯一确定了下一个指定位置的值,此时如果这个值和预期不同就不合法了。

不合法方案数如何计算?中间这些位置的 \(a_i\) 都是被上一个限制了的,所以它们已经确定只能 \(\times 1\)。但是 \(b\) 可以自己指定,所以有 \(v\) 的贡献,不过最后一个 \(b\) 的指定要避开当前值,所以是乘的 \(v-1\)

点击查看代码
#include<bits/stdc++.h> 
using namespace std; 
#define ll long long 
#define For(i,l,r) for(int i=l;i<=r;i++) 
ll n,v;
int m;
const int N=1e5+10;
const ll p=1e9+7;
struct node{ll c,d;
}a[N];
bool cmp(node x,node y){return x.c<y.c;
}
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;
}
void solve(){ bool f=0;cin>>n>>m>>v;For(i,1,m)cin>>a[i].c>>a[i].d;sort(a+1,a+m+1,cmp);ll ans=qpow(v,2*(a[1].c-1))%p;For(i,1,m-1){ll l=a[i].c,r=a[i+1].c;if(l==r&&a[i].d!=a[i+1].d){f=1;break;}if(l==r)continue;ans=(ans*(qpow(v,2*(r-l))-(v-1)*qpow(v,r-l-1)%p+p)%p)%p;}ans=(ans*qpow(v,2*(n-a[m].c)))%p;if(f)cout<<"0\n";else cout<<ans<<"\n";
} 
int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T; cin>>T; while(T--)solve(); return 0; 
} 

T3 突然困难,主播一直在想……首先是可以拿到 \(k=1\) 那档最简单的,不到 5min 就可以拿下高贵的 28 分。这告诉我们 NOIP 部分分一定要全部去想一遍。用时 10min。

点击查看代码
#include<bits/stdc++.h> 
using namespace std; 
#define ll long long 
#define For(i,l,r) for(int i=l;i<=r;i++) 
int n,k;
const int N=1e5+10;
const ll p=1e9+7;
ll fac[N],inv[N];
vector<int>G[N];
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;
}
void init(){fac[0]=inv[0]=1;For(i,1,n)fac[i]=fac[i-1]*i%p;inv[n]=qpow(fac[n],p-2)%p;for(int i=n-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%p;
}
#define pb push_back
int d[N];
int e[N];
void solve(){cin>>n>>k;For(i,1,n){G[i].clear(),d[i]=0;}init();For(i,1,n-1){int u,v;cin>>u>>v;G[u].pb(v);G[v].pb(u);d[u]++;d[v]++;}For(i,1,k)cin>>e[i];ll ans=1;For(i,1,n){//k=1ans=(ans*fac[d[i]-1])%p;}cout<<ans<<"\n";
}
int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int c,T; cin>>c>>T; while(T--)solve(); return 0; 
} 

此时正在模拟赛的我暂时跳过了这题去看了 T4,下面是补题:

T4

太典了,这场 NOIP 结束后我听这个结论听了 800 回了,不可避免的被透露解法了/kel。

区间 \(LCA\) 可以变成两两相邻点 \(LCA\) 的最小高度。剩下部分我就引用下别人打好的东西,实在太经典了,调了大概 2h 多过了。

区间 \(\text{LCA}\) 的深度为:

\[\min_{l\le i<r}{\text{dep}_{\text{LCA}(i,i+1)}} \]

找出以 \(\text{LCA}(i,i+1)\) 为最近公共祖先的最大区间 \([x_i,y_i,v_i]\)\(v_i\)\(\text{dep}_{\text{LCA}(i,i+1)}\)

查询是求与 \([l,r]\) 交集至少为 \(k\),且最大的 \(v_i\)。可列出可行条件的不等式组。

1.满足:

\[y_i\ge r \]

\[x_i\le r-k+1 \]

2.或者满足:

\[l+k-1\le y_i\le r \]

\[y_i-x_i+1\ge k \]

第一个对 \(r\) 扫描线,第二个对 \(k\) 扫描线,时间复杂度 \(O(n\log n)\)

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;i++)
const int N=5e5+10;
int n,m;
vector<int>G[N];
int fa[N],sz[N];
int dep[N];
int wc[N],tp[N];
void dfs(int u,int f){fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;for(int v:G[u]){if(v==f)continue;dfs(v,u);sz[u]+=sz[v];if(sz[v]>sz[wc[u]])wc[u]=v;}
}
void dfs2(int u,int t){tp[u]=t;if(wc[u])dfs2(wc[u],t);for(int v:G[u]){if(v==fa[u]||v==wc[u])continue;dfs2(v,v);}
}
int lca(int a,int q){while(tp[a]!=tp[q]){if(dep[tp[a]]>=dep[tp[q]])a=fa[tp[a]];else q=fa[tp[q]];}if(dep[a]<dep[q])return a;else return q;
}
struct node{int l,r,v,id;}a[N];
struct Node{int l,r,k,id;}q[N];
int ans[N];
#define lc u<<1
#define rc u<<1|1
struct Seg{int mx[N<<2];void upd(int u,int L,int R,int p,int v){mx[u]=max(mx[u],v);if(L==R)return;int mid=(L+R)>>1;if(mid>=p)upd(lc,L,mid,p,v);else upd(rc,mid+1,R,p,v);}int qry(int u,int L,int R,int l,int r){if(l<=L&&R<=r)return mx[u];int mid=(L+R)>>1;if(mid>=r)return qry(lc,L,mid,l,r);//都在左边if(mid<l)return qry(rc,mid+1,R,l,r);//都在右边return max(qry(lc,L,mid,l,r),qry(rc,mid+1,R,l,r));}
}t[2];
#define pb push_back
bool cmp(node x,node y){return x.r-x.l>y.r-y.l;}
bool cmp2(Node x,Node y){return x.k>y.k;}
bool cmp3(node x,node y){return x.r>y.r;}
bool cmp4(Node x,Node y){return x.r>y.r;}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;For(i,1,n-1){int u,v;cin>>u>>v;G[u].pb(v);G[v].pb(u);}dfs(1,0);dfs2(1,1);For(i,1,n-1){a[i].id=i;a[i].v=dep[lca(i,i+1)];}For(i,1,n)t[0].upd(1,1,n,i,dep[i]);//单调栈求控制区间设置边界a[0].v=a[n].v=-1;stack<int>s;s.push(0);For(i,1,n-1){while(a[s.top()].v>=a[i].v)s.pop();a[i].l=s.top()+1;//左边第一个val<vs.push(i);}while(!s.empty())s.pop();s.push(n);for(int i=n-1;i>=1;i--){while(a[s.top()].v>=a[i].v)s.pop();a[i].r=s.top()-1;//右边第一个val<vs.push(i);}cin>>m;For(i,1,m){cin>>q[i].l>>q[i].r>>q[i].k;q[i].id=i;q[i].r--;//边的编号q[i].k--;//转换为边数差}//1.对k扫描线sort(a+1,a+n,cmp);//区间长度降序排序,保证处理查询时所有满足长度>=k的边已加入线段树sort(q+1,q+m+1,cmp2);//k降序排序int u=1;//边的遍历指针For(i,1,m){if(q[i].k==0){//所有区间ans[q[i].id]=t[0].qry(1,1,n,q[i].l,q[i].r+1);//边r对应节点r+1continue;}//将所有长度>=当前查询k的边加入t[1]while(u<n&&a[u].r-a[u].l+1>=q[i].k){//边的val存入t[1],位置为边的控制区间右端点rt[1].upd(1,1,n,a[u].r,a[u].v);u++;}//查询边区间[q[i].l+k-1,q[i].r]的max valans[q[i].id]=t[1].qry(1,1,n,q[i].l+q[i].k-1,q[i].r);}//2.对r扫描线sort(a+1,a+n,cmp3);//r降序排序sort(q+1,q+m+1,cmp4);//r降序排序memset(t[1].mx,0,sizeof(t[1].mx));u=1;For(i,1,m){//所有r>当前查询r的边加入t[1]while(u<n&&a[u].r>q[i].r){t[1].upd(1,1,n,a[u].l,a[u].v);u++;}//查询边区间[1,q[i].r-q[i].k+1]的max val,与原答案取maxans[q[i].id]=max(ans[q[i].id],t[1].qry(1,1,n,1,q[i].r-q[i].k+1));}For(i,1,m)cout<<ans[i]<<'\n';return 0;
}
http://www.hskmm.com/?act=detail&tid=29013

相关文章:

  • 2025/10/11
  • 好玩热门的switch游戏推荐【PC+安卓】塞尔达传说:王国之泪|v1.4.2整合版|官方中文| 附switch模拟器
  • 十年运维工程师总结
  • 运动控制教学——5分钟学会Dijkstra与A*搜索算法!(附仿真视频及代码) - 教程
  • ffplay数据结构解析
  • CNN 发展历程
  • FileX和ThreadX精简版
  • ue4素材场景 - MKT
  • 阅读《构建之法》的思考与问题
  • 实验报告5(链栈基本操作,数制转换,匹配算法,伴舞问题)
  • 阅读和提问作业1:《构建之法》提问
  • 企业推行OKR中层领导关注的10个关键问题及解决方案
  • 初四夜间/休息日安排
  • AWS自然语言处理技术实战指南
  • 多线程
  • 三级模式
  • abc427
  • 20232320 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • [HarekazeCTF2019]baby_rop2
  • 开个视频网站很烧钱吧
  • 13. Canvas画布
  • 预训练相关的一些概念
  • 2025/10/11 模拟赛总结 - sb
  • 分布式训练的一些知识
  • Visual Studio 2013 Update 4 中文版安装步骤(带TFS拥护)附安装包​
  • 排列
  • 白纷纷副
  • 低秩适配器(LoRA)
  • ROC曲线
  • 10.12~10.18随笔