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\) 中偶数串出现的次数，状态转移方程为：
\[ f[i]=f[p[i]]+(i\&1\oplus1) \]其中 \(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函数……
这是我能做的？再见！
贴一个老师给的题解
标签：石子,le,20230712,NOIP,int,ll,位置,SG,模拟 From： https://www.cnblogs.com/WANG-YIN/p/17737137.html显然这是公平博恋，我们要用到 \(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)\)。