HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）（A,B,C,D,E,F,G）

看不懂的英文，题意很难理解，这场还是有点难度的。

C需要处理，D是不太明显的dijikstra，E是线段树优化dp，F是个不好想的线段树，主席树应该也能做。

我觉得讲的很好的宝藏up主->B站视频讲解。之后会比较忙，一篇上万字的题解太费时间了，之后的题解可能就没办法大段大段的来讲了，只说重点。

---

A Yay!

题意：

长度大于等于3的字符串里只有两种字符，其中一种字符只出现了一次，找到它的位置。

思路：

我的思路：
如果我们事先知道只出现一次的那个字符是什么，就可以直接用string里内置的 find_first_of() 函数来找位置，或者知道另一种字符，就可以用string里内置的 find_first_not_of() 函数来找位置。

字符串第一个字符一定属于两种字符之一，假设出现了一次的字符为a，出现多次的字符为b。分类讨论：

1. 如果第一个字符是a，find_first_of(str[0],1) 会返回 string::npos ，这时第一个字符就是a
2. 如果第一个字符是b，find_first_of(str[0],1) 会返回一个合法位置，这时直接 find_first_not_of(str[0],1) 就能找到a了

jiangly大佬的思路：
使用string内置的 count(str[0]) 函数，如果个数大于1就是b字符，如果个数为1就是a字符

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;string str;int main(){cin>>str;if(str.find_first_of(str[0],1)==string::npos)cout<<1;else cout<<str.find_first_not_of(str[0])+1;return 0;
}

---

B - Which is ahead?

题意：

$N$ 个人排成一队，每个人有个编号 $P_i$。有 $Q$ 次询问，每次询问给出两个编号 $A_i$ 和 $B_i$，输出靠前的那个人的编号。

思路：

对每个编号记录它在队列中的位置，之后拿到编号直接查询位置。

code：

#include <iostream>
#include <cstdio>
using namespace std; 
const int maxn=105;int n,idx[maxn],q;int main(){cin>>n;for(int i=1,t;i<=n;i++){cin>>t;idx[t]=i;}cin>>q;for(int i=1,a,b;i<=q;i++){cin>>a>>b;printf("%d\n",(idx[a]>idx[b])?b:a);}return 0;
}

---

C - Many Replacement

题意：

给你一个长为 $N$ 的小写字母组成的字符串 $S$。有 $Q$ 次询问，每次询问给出两个小写字母 $c_i,d_i$ ，表示将字符串中所有 $c_i$ 字符换成 $d_i$。问最后得到的字符串是什么。

思路1：

但是发现对每种字符，我们只关心它最后变成了哪种字符，因此用map记录一下这个字符最后变成了什么就行了，也就是这个字符最后映射为什么字符。

更详细的说，一开始每个字符都映射为自己，每次修改把所有映射值为 $c_i$ 的键值对改成映射为 $d_i$，最后把原字符串映射一下就行了。时间复杂度 $O(26\ast q\ast log(26)+n\ast log(26))$

code1：

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
using namespace std;int n,q;
string str;
map<char,char> mp;
vector<int> a[30];
int c;int main(){cin>>n>>str;for(char ch='a';ch<='z';ch++)mp[ch]=ch;cin>>q;for(int i=1;i<=q;i++){char c1,c2;cin>>c1>>c2;for(char ch='a';ch<='z';ch++)if(mp[ch]==c1)mp[ch]=c2;}for(auto x:str)printf("%c",mp[x]);return 0;
}

思路2：

赛时丑陋的想法。

把每个字符看成一个人，它一开始有把仓库钥匙，仓库里的货物就是原字符串填有这个字符的所有位置。每次进行字符修改的时候，就像把钥匙给了别人，不用动货物。

听着挺直观的，但是不好写。

code2：

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
using namespace std;int n,q;
string str;
map<char,int> mp;
vector<int> a[30];
int c;int main(){cin>>n>>str;for(int i=0;i<n;i++){if(mp.find(str[i])==mp.end())mp[str[i]]=++c;a[mp[str[i]]].push_back(i);}cin>>q;for(int i=1;i<=q;i++){char t1,t2;int n1,n2;cin>>t1>>t2;if(mp.find(t1)==mp.end() || t1==t2)continue;if(mp.find(t2)==mp.end())mp[t2]=mp[t1];else {n1=mp[t1];n2=mp[t2];a[n2].insert(a[n2].end(),a[n1].begin(),a[n1].end());a[n1].clear();}mp.erase(t1);}for(auto x:mp){for(auto idx:a[x.second]){str[idx]=x.first;}}cout<<str;return 0;
}

---

D - Square Pair

题意：

给你有 $N$ 个非负数的数组 $A$，找到有多少对 $(i,j)$ 满足 $1\le i<j\le N$ 且 $A_i\ast B_j是平方数$。

能用非负数的平方表示的非负数就是平方数。

思路：

对平方数进行质因数分解，它的所有质因子的次数都是偶数（这样正好可以对半分），如果两个数乘起来是平方数，那么它们含有的一种质因子的次数的奇偶性一定相同的。我们的任务就是 $logn$ 次内对一个 $i$，统计前面 $i-1$ 个数中满足和这个数每个质因子的次数的奇偶性相同的数的个数。

因为我们只关心奇偶性，所以可以把多余次数的质因数全部去掉，每个奇数次数的质因数只留下一个就行了，比如 $108=2\ast 2\ast 3\ast 3\ast 3$，去重后得到 $3$。对处理后的数存入map中就可以 logn 次查询了。

不过要特判 $0$ 的情况，因为 $0$ 可以和其他任何数产生有效的一对。如果 $0$ 的个数有 $num$ 个，那么答案会多出 $num\ast (n-1)$，不过 0 和其他 0 会重复算，再减去 $num\ast (num-1)/2$。边读数边算边特判也可以。

code：

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
const int maxn=2e5+5;int n;int g(int x){int ans=1;for(int i=2;i*i<=x;i++){if(x%i==0){int cnt=0;while(x%i==0)x/=i,cnt++;if(cnt&1)ans*=i;}}if(x>1)ans*=x;return ans;
}int main(){cin>>n;long long num=0,ans=0;map<int,long long> mp;for(int i=1,t,x;i<=n;i++){cin>>t;if(t==0){num++;continue;}x=g(t);ans+=mp[x];mp[x]++;}cout<<ans+num*(n-1)-num*(num-1)/2<<endl;return 0;
} 

---

E - Last Train

题意：

有 $N$ 个火车站，$M$ 个火车信息。第 $i$ 个火车信息有六个正整数 $l_i,d_i,k_i,c_i,A_i,B_i$，表示：

• 在每个时刻 $t=l_i,l_i+d_i,l_i+2\ast d_i,\dots ,l_i+(k_i-1)\ast d_i$，都有一列火车从车站 $A_i$ 出发，并在时刻 $t+c_i$ 到达车站 $B_i$

问你从车站 $i(1\le i\le N-1)$ 出发，到达车站 $N$ 的最晚的出发时间是多少。

思路：

乍一看不好下手，不妨从终点站来看。

要出发时间最晚，那么我们到达终点站也会很晚。为了在路上留出足够充裕的时间，我们可以假定到达终点站坐的是最后一班车。

这样来考虑的话，我们逆推得到的这些车站也可以通过尽可能晚的车次来从其他车站到达。这样逆推到我们所在的车站，就得到了我们现在要出发的车站最晚可以什么时候走。而且我们一定不会回到已经经过的车站，否则我们再从这个车站出发的话，最晚时间就会变早。

我们每次挑出最晚时间出发的车站进行逆推，把更新的车站再依次进行逆推，其实就相当于在用dijkstra算法跑最短路。

详细的来说。我们一开始读入火车信息的时候反向建边，然后后终点 $N$ 开始跑最短路。每次取出出发时刻最晚的车站，如果通过一条边（也就是一班车）可以到达一个点的时间变晚，就加入堆。

如何算出最晚车次是哪一次：假设现在所在的点的最晚时刻是 $tm$，那么有 $$l+(x-1)\ast d+c\le tm$$$$x\le \frac{tm-l-c}{d}+1$$$$x=\lfloor \frac{tm-l-c}{d}\rfloor +1(1\le x\le k)$$最后只要保证 $x\ge 1$，然后 $x$ 取 $x$ 与 $k$ 的较小值即可。发车时刻 $l+(x-1)\ast d+c$ 就是我们从目标车站的最晚出发时刻。

code：

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define pii pair<ll,ll>
const int maxn=2e5+5;
const ll inf=2e18;int n,m;int head[maxn],cnt;
struct edge{int v,nxt;ll l,d,k,c;
}e[maxn];
void add(int u,int v,ll l,ll d,ll k,ll c){e[++cnt].v=v;e[cnt].l=l;e[cnt].d=d;e[cnt].k=k;e[cnt].c=c;e[cnt].nxt=head[u];head[u]=cnt;
}ll dis[maxn];
bool vis[maxn];
void dijkstra(){for(ll i=1;i<=n;i++)dis[i]=-inf,vis[i]=false;priority_queue<pii> h;dis[n]=inf;h.push(pii(dis[n],n));while(!h.empty()){int dt=h.top().first,u=h.top().second;h.pop();if(vis[u])continue;else vis[u]=true;for(ll i=head[u],v,l,d,k,c,ti,tm;i;i=e[i].nxt){v=e[i].v;l=e[i].l;d=e[i].d;k=e[i].k;c=e[i].c;ti=min(k,(dis[u]-c-l)/d+1);//坐哪一趟车 if(ti<1)continue;tm=l+(ti-1)*d;//发车时间if(dis[v]<tm){dis[v]=tm;h.push(pii(dis[v],v));} }}
}int main(){cin>>n>>m;for(ll i=1,l,d,k,c,a,b;i<=m;i++){cin>>l>>d>>k>>c>>a>>b;add(b,a,l,d,k,c);}dijkstra();for(int i=1;i<n;i++)if(dis[i]!=-inf)printf("%lld\n",dis[i]);else printf("Unreachable\n");return 0;
}

---

F - Black Jack

题意：

有一个 $D$ 面骰子和两个变量 $x,y$，一开始 $x=y=0$

你可以投若干次骰子，并把骰子的值加到 $x$ 上。

然后庄家投若干次骰子，并把骰子的值加到 $y$ 上。如果某次投骰子后 $y>L$，庄家就停止投骰子。

如果 $x>N$ ，则你输。如果 $x>y$ 或 $y>N$ 则你赢。两种情况都不是算你输（也就是 $x,y>N$）

问你采取最大胜率的策略，胜率是多少。

思路：

jiangly的思路（写法不太一样）：

当我们是某个点数的时候，我们可以选择投骰子或者不投。选择哪一个取决于哪个胜率更高。而庄家的策略始终不变，因此庄家投出的每种 $y$ 的概率是固定的。

当我们选择投骰子时，那么假设 $dp[i]$ 是我们当前点数为 $i$ 时的胜率， 那么 $dp[i]={\sum }_{k=i+1}^{i+d}dp[k]\ast \frac{1}{d}$ 。如果我们选择不投骰子，假设 $f[i]$ 表示庄家投出点数为 $i$ 的概率，我们的胜率就是 ${\sum }_{y=L}^{x-1}f[i]+{\sum }_{y=n+1}^{l+d-1}f[i]$（后者表示庄家投出了比 $n$ 大的点数，显然这时只要我们的点数不超过 $n$ 就行）。两种选择取较大值就是 $dp[i]$ 了。

$f$ 数组需要预处理，当算到 $f[i]$ 时，我们只需要算出前 $d$ 个的值，这时可以边算 $f$ 数组，边处理一个前缀和数组，这样就可以每次 $O(1)$ 得到区间和，整个预处理过程是 $O(n)$ 的。不过需要注意的是，庄家投骰子的策略是投到 $y>=L$ 就立刻停止，因此前缀和只处理到前 $0\sim L-1$ ，后面不再加入新 $f[i]$ 值。${\sum }_{y=n+1}^{l+d-1}f[i]$ 这个东西也可以预先直接算出来。之后为了方便处理，我们再处理一个 $g[i]$ 数组，表示我们投出点数为 $i$ 时，庄家的败率（也就是我们选择停手的胜率）。

因为计算 $dp$ 值时，我们需要后面 $d$ 位的 $dp$ 值，所以从后向前计算。

code：

WA3个点，精度损失严重。

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn=4e5+5;int n,L,d;//上界为n下界为l，面数为d  
double f[maxn],g[maxn],s[maxn],lose;
double dp[maxn];int main(){cin>>n>>L>>d;s[0]=f[0]=1;for(int i=1,l,r;i<=n;i++){l=max(0,i-d);r=min(i-1,L-1);f[i]=(s[r]-((l>0)?s[l-1]:0))/d;//庄家投出i的概率 s[i]=s[i-1]+f[i];}for(int i=n+1,l,r;i<L+d;i++){//投出i点 l=max(0,i-d);r=L-1;lose+=(s[r]-((l>0)?s[l-1]:0))/d;}for(int i=0;i<L;i++)f[i]=0;f[0]=lose;for(int i=0;i<n;i++)g[i+1]=g[i]+f[i];//庄家败率 s[n+1]=0;for(int i=n,l,r;i>=0;i--){l=i+1;r=min(i+d,n);dp[i]=max(g[i],(s[l]-s[r+1])/d);s[i]=s[i+1]+dp[i]; }printf("%.15lf\n",dp[0]);return 0;
}

由于前缀和的精度损失比较严重，所以会WA掉三个点，因此采用线段树维护单点修改，区间和查询。

我前缀和调半天还WA三个点，改成线段树还T，而jiangly大佬直接一遍A了。。。

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn=2e5+5;int n,L,d;//上界为n下界为l，面数为d  
double f[maxn],g[maxn],lose;
double dp[maxn];struct segement_tree{#define ls p<<1#define rs p<<1|1int n;struct Node{double val;}t[maxn<<2];void push_up(int p){t[p].val=t[ls].val+t[rs].val;}void print(int p,int l,int r){printf("%2d:[%2d,%2d] %lf\n",p,l,r,t[p].val);if(l==r)return;int mid=(l+r)>>1;print(ls,l,mid);print(rs,mid+1,r);}void print(){print(1,0,n);}void build(int p,int l,int r){if(l==r){t[p].val=0;return;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);push_up(p);}void build(int _n){n=_n;build(1,0,n);}void mdy(int p,int l,int r,int x,double val){if(l==r){t[p].val=val;return;}int mid=(l+r)>>1;if(x<=mid)mdy(ls,l,mid,x,val);else mdy(rs,mid+1,r,x,val);push_up(p);}inline void mdy(int id,double val){mdy(1,0,n,id,val);}double query(int p,int l,int r,int L,int R){if(L<=l && r<=R){return t[p].val;}int mid=(l+r)>>1;double ans=0;if(L<=mid)ans+=query(ls,l,mid,L,R);if(R>mid)ans+=query(rs,mid+1,r,L,R);return ans;}inline double query(int l,int r){return query(1,0,n,l,r);}#undef ls#undef rs
}tr;int main(){cin>>n>>L>>d;tr.build(n);f[0]=1;tr.mdy(0,f[0]);for(int i=1,l,r;i<=n;i++){l=max(0,i-d);r=min(i-1,L-1);f[i]=tr.query(l,r)/d;//庄家投出i的概率 tr.mdy(i,f[i]);}for(int i=n+1,l,r;i<L+d;i++){//投出i点 l=max(0,i-d);r=L-1;lose+=tr.query(l,r)/d;}for(int i=0;i<L;i++)f[i]=0;f[0]=lose;for(int i=0;i<n;i++)g[i+1]=g[i]+f[i];//庄家败率 for(int i=n,l,r;i>=0;i--){l=i+1;r=min(i+d,n);dp[i]=max(g[i],(l<=r)?tr.query(l,r)/d:0);tr.mdy(i,dp[i]);}printf("%.15lf\n",dp[0]);return 0;
}

---

G - Retroactive Range Chmax

题意：

给你有 $N$ 个正整数的数组 $A$，有 $Q$ 次操作，操作有三种：

• 输入 1 l r x ：将 $A_l,A_{l+1},\dots ,A_r$ 的每个数 $A_i$ 变成 m a x { A i , x } max\{A_i,x\} max{Ai​,x}。
• 输入 2 i ：将第 $i$ 个操作撤销，保证第 $i$ 个操作是第一种操作，并且之前没有被撤销过
• 输入 3 i ：查询 $A_i$ 的值。

思路：

借鉴这位大佬

相当于记录每个点所有可能的值，显然在某个时刻查询的时候，我们只要给出最大的那个就行了。但是直接暴力存储每个点的可能的值既会爆空间又会爆时间。因此用线段树维护，我们这里的值不需要 push_up 和 push_down 来维护，查询时只需要返回到达 $A_i$ 时线段树路径上的最大值就行了。

code：

基本相当于照抄了（汗

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
const int maxn=2e5+5;int n,a[maxn];
int q;struct segement_tree{#define ls p<<1#define rs p<<1|1int n;struct Node{map<int,int> val;}t[maxn<<2];void build(int p,int l,int r){if(l==r){t[p].val[a[l]]++;return;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);}void build(int _n){n=_n;build(1,1,n);}void mdy(int p,int l,int r,int L,int R,int d,bool x){if(L<=l && r<=R){if(x){t[p].val[d]++;}else {if(--t[p].val[d]==0)t[p].val.erase(d);}return;}int mid=(l+r)>>1;if(L<=mid)mdy(ls,l,mid,L,R,d,x);if(R>mid)mdy(rs,mid+1,r,L,R,d,x);}int query(int p,int l,int r,int L,int R){if(L<=l && r<=R){return t[p].val.rbegin()->first;}int mid=(l+r)>>1,ans=0;if(!t[p].val.empty())ans=t[p].val.rbegin()->first;if(L<=mid)ans=max(ans,query(ls,l,mid,L,R));if(R>mid)ans=max(ans,query(rs,mid+1,r,L,R));return ans;}#undef ls#undef rs
}tr;struct opter{int l,r,d;
}opt[maxn];int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];tr.build(n);cin>>q;for(int i=1;i<=q;i++){int op;cin>>op;if(op==1){cin>>opt[i].l>>opt[i].r>>opt[i].d;tr.mdy(1,1,n,opt[i].l,opt[i].r,opt[i].d,1);}else if(op==2){cin>>opt[i].d;tr.mdy(1,1,n,opt[opt[i].d].l,opt[opt[i].d].r,opt[opt[i].d].d,0);}else {cin>>opt[i].d;cout<<tr.query(1,1,n,opt[i].d,opt[i].d)<<endl;}}return 0;
}