20230712 NOIP模拟(1)
[TOC]
总结
暑期第一次模拟赛
预估得分：40 分
实际得分：40 分
（有大佬AK力 Orz）
T1 前缀和 (pre)
题意
给定一个字符串，求所有长度为偶数的前缀在整个字符串中出现的次数和。
\(|S|\le200000\)。
分析
由于 KMP 的 \(p[i]\) 表示子串 \(\left[1\cdots p[i]\right]\) 和子串 \(\left[i-p[i]+1\cdots i\right]\) 相同，所以长度为 \(i\) 的前缀出现的次数就可以计入长度为 \(p[i]\) 的前缀出现次数中。
考虑 DP。
定义 \(f[i]\) 表示前缀 \(1\cdots i\) 中偶数串出现的次数，状态转移方程为：
其中 \(p[i]\) 为 KMP 中的 \(next[i]\) 数组。
代码
#include<bits/stdc++.h>
using namespace std;
#define N 200200
char c[N];
int l,ans;
int nxt[N],f[N];
int main(){
freopen("pre.in","r",stdin);
freopen("pre.out","w",stdout);
cin.sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>c+1;
l=strlen(c+1);
int j=0;
for(int i=2;i<=l;i++){
while(j&&c[i]!=c[j+1]){
j=nxt[j];
}
if(c[i]==c[j+1]) j++;
nxt[i]=j;
}
for(int i=2;i<=l;i++){
f[i]=f[nxt[i]]+(i&1^1);
ans+=f[i];
}
cout<<ans<<"\n";
return 0;
}
T2 构造完全图 (gouzao)
题意
对于完全图 \(G\)，若有且仅有一棵最小生成树 \(T\)，则称完全图 \(G\) 是由 \(T\) 拓展出的。给你一颗树 \(T\) ，找出 \(T\) 能拓展出的边权和最小的完全图 \(G\)，求出 \(G\) 的边权和。
分析
考虑两个完全图 \(G_1\) 和 \(G_2\)，已知 \(G_1\) 和 \(G_2\) 唯一的最小生成树 \(T_1\) 和 \(T_2\)。现在存在 \(u\in G_1\) 且 \(v\in G_2\)，连边 \((u,v)\)，长度为 \(w\)。现在要连 \(|G_1|\times |G_2|-1\) 条边，把这两个图合并成一个完全图，使得这个完全图唯一的最小生成树由 \(T_1\) 与 \(T_2\) 中的边与 \((u,v)\) 构成，易得这些边的边权都要大于 \(w\)。 整个过程从小到大加入边，合并并查集即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define N 100100
#define ll long long
inline void read(ll &a){
a=0;
ll f=1;
char c=getchar();
while((c<'0'||c>'9')&&c!='-'){
c=getchar();
}
if(c=='-'){
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
a=(a<<1)+(a<<3)+(c^48);
c=getchar();
}
a*=f;
}
ll n,ans;
ll fa[N],a[N];
struct edge{
ll u,v,w;
bool operator <(const edge &t)const{
return w<t.w;
}
}e[N<<1];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y,ll w){
int fx=find(x),fy=find(y);
if(fx==fy) return ;
ans+=(a[fx]*a[fy]-1)*(w+1);
fa[fx]=fy;
a[fy]+=a[fx];
}
int main(){
freopen("gouzao.in","r",stdin);
freopen("gouzao.out","w",stdout);
read(n);
for(int i=1;i<=n;i++){
fa[i]=i;
a[i]=1;
}
for(int i=1;i<n;i++){
read(e[i].u);read(e[i].v);read(e[i].w);
ans+=e[i].w;
}
sort(e+1,e+n);
for(int i=1;i<n;i++){
merge(e[i].u,e[i].v,e[i].w);
}
printf("%lld\n",ans);
return 0;
}
T3 独木桥 (bridge)
题意
在一个长度无限长的实数轴，有若干实数点。数轴从左到右坐标不断 增大。
每个点的位置用相对于数轴原点的点的坐标来表示。初始时 \(n\) 个点在 \(n\) 个互不相同的整点上。
每个点有一个初始朝向 \(d_i\)（\(d_i=0\) 则初始向左，\(d_i=1\) 则初始向右）。任何时刻所有的点都会以每秒 \(1\) 单位长度的速度匀速向所朝的方向移动。当某一时刻两个点同时移动到了同一个位置上，它们会立即改变自己的朝向（从左向 右变成从右向左，反之亦然），然后继续移动。
有 \(q\) 次询问，每次询问给定 \(k_i\) 与 \(t_i\)，询问在 \(t_i\) 秒后，孩子 \(k_i\) 目前的位置。
\(1 \le n,q \le 2\times10^5,0 \le k_i<n,0\le p_i,t_i\le10^9,d_i\in\{0,1\}\)。
分析
我们可以发现两点性质：
点在不断移动的过程中，他们的相对位置顺序永远不变。
假设相遇的点不会掉转方向（即擦肩而过），位置集合与相遇时调转方向的情况相同 然后对于每个 \(i\)，求出第 \(i\) 个孩子的位置排名（从小到大）\(rank_i\)，一组询问转化成求 \(S\)（\(t_i\) 秒后位置集合）中第 \(rank_i\) 小的数 把向左和向右的点分开处理，二分答案即可。
复杂度为 \(O\left(nlog^2n\right)\)。
代码
#include<bits/stdc++.h>
using namespace std;
#define N 200200
#define ll long long
int n,q;
int rk[N];
struct node{
ll p;
int d,id;
bool operator <(const node &t)const{
return p<t.p;
}
}x[N];
ll a[N],b[N];
int cnt1,cnt2;
inline int check(ll x,int t){
int ret1,ret2;
ret1=upper_bound(a+1,a+cnt1+1,x-t)-a-1;
ret2=upper_bound(b+1,b+cnt2+1,x+t)-b-1;
return ret1+ret2;
}
int main(){
freopen("bridge.in","r",stdin);
freopen("bridge.out","w",stdout);
cin.sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>x[i].p;
x[i].id=i;
}
for(int i=1;i<=n;++i){
cin>>x[i].d;
}
sort(x+1,x+n+1);
for(int i=1;i<=n;++i){
rk[x[i].id]=i;
if(x[i].d) a[++cnt1]=x[i].p;
else b[++cnt2]=x[i].p;
}
cin>>q;
for(int i=1;i<=q;++i){
int k,t;
cin>>k>>t;
k=rk[k+1];
ll l=x[1].p-t,r=x[n].p+t,ans;
while(l<=r){
ll mid=l+r>>1;
if(check(mid,t)>=k){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
cout<<ans<<"\n";
}
return 0;
}
另
这题数据比较友好，打部分分也能打到不少。
对于20%的数据，\(n,p_i,t_i\le 10\)。
另有10%的数据，\(d_i\) 均相等。
另有20%的数据，\(q\le 10\)。
另有15%的数据，\(t_i\le100\)。
另有20%的数据，\(n\le 1000\)。
算法一
对于 \(d_i\) 相等的情况。
根据上述第一条性质，易知对于每一个点 \(i\)，其在 \(t_i\) 秒后的位置为 \(p_i\pm t_i\)（$d_i$为 \(1\) 时取 \(+\)，\(d_i\) 为 \(0\) 时取 \(-\)）。
复杂度为 \(O(1)\)。
期望得分 10 分。
算法二
考虑上述两条性质。
不考虑相遇后方向，计算每个点 \(i\) 在 \(t_i\) 秒的位置。
根据性质一，因为每个点的相对位置不变，所以点 \(i\) 的位置即为此时排名为 \(rk_i\) 的点所在的位置。
可将问题离线，按照 \(t_i\) 排序，对于每个询问，对遍历所有点，计算在不考虑反向的情况下的位置，排序，此时第 \(rk[k_i]\) 个点的位置即为答案。
复杂度为 \(O(q(n+nlogn))\)。
实测可另得 60 分
算法三
对于 \(t_i\le 100\) 的情况
由于$t$较小，可以考虑预先求出每个时刻时各个点的位置，对于每个询问直接 \(O(1)\) 查询即可
复杂度为 \(O(q)\)
应该可另得 15 分
T4 放石子 (stone)
题意
Alice 与 Bob 在玩游戏 定义游戏规则如下：给一张 \(n\) 个点，\(m\) 条边的有向无环图，每条边有颜色 \(c\)，在图上放了 \(q\) 颗石子，每颗石子在一个点上。每次操作时选择一个有出边且点上有石子的点 \(x\)，从点上取走一颗石子，然后选 择一个颜色集合 \(S\)，对于每条满足颜色 \(e\in S\) 的出边 \(i\)，在边 \(i\) 的终点上放上一颗石子。双方轮流操作， 不能操作者负。问 Alice 是先手获胜还是后手获胜。
分析
公平博恋问题，我们要用到SG函数……
这是我能做的？再见！
贴一个老师给的题解
显然这是公平博恋，我们要用到 \(SG\) 函数。
我们将每个节点看成一个状态，将出度为 \(0\) 的点看成必败态。
首先我们知道每个石子是独立的，我们只需要考虑求一个节点 \(u\) 上有一个石子时的 \(SG(u)\) 然后将所有石子的对应的 \(SG\) 函数求异或和即可得到答案。
我们先拓扑排序，然后倒拓扑序递推。 我们把结点 \(u\) 的所有出边按颜色分类，如果 \(c\in S\)，那么每种颜色为 \(c\) 的边我们必须同时选择,所以我们可以将这一类的权值记为：
\[ \begin{align} &\oplus(u,v)\in E\\ &(u,v)\text{的颜色}=cSG(v) \end{align} \]我们将这个权值构成的集合称作 \(A\)。
那么我们所有决策对应的 \(SG\) 函数构成的集合就是 \(\{\oplus_{x\in B}|B\subset A\}\)。我们要求的就是从这个集合中任意选取一个子集，然后异或起来最小的得不到的数，\(mex\{\oplus_{x\in B}x\subset A\}\)。只有将 \(A\) 内的元素插入线性基，然后找不在线性基中的最低位，即最小的线性相关的位，设为第 \(i\) 位，就有 \(SG(u)=mex\{\oplus_{x\in B}x|B\subset A\}=2^i\) 并且求 \(SG\) 函数值的位数最坏情况下是 \(O(n)\) 的，我们需要用
bitset来储存答案。总时间复杂度为 \(O\left(\frac{|A|\times n^2}{64}\right)\)。