小小模拟赛
忘记把原题的pdf留下来了，差不多随便写写。
第一道
一个数 $ n $ ，找到一个最小的$k$，使得$k^2$ 是$n$ 的倍数而$k$不是，否则则输出$-1$。
看到这种题先打暴力打个表再想（毕竟要对拍）。
想到质因数分解，那么就显然了，一个数的倍数的质因子一定完全包含这个数的质因子，所以类似于把$n$开个根号，就是质因子次数除以$2$上取整。较简单，不过多描述。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,b;
int res=1;
int qmi(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a;
a=a*a;
b>>=1;
}
return res;
}
signed main(){
//freopen("biao.out","w",stdout);
cin>>n;
res=1;
b=n;
for(int i=2;i<=n/i;i++){
int cnt=0;
while(!(b%i)){
b/=i;
cnt++;
}
if(cnt) res=res*qmi(i,(cnt+1)/2);
}
if(b!=1&&b!=n) res*=b;
if(res==1||res==n) cout<<-1<<'\n';
else cout<<res<<'\n';
}华二
题目描述
Ayano 喜欢 GCD。
现在她有一个长度为 $n$ 的数列 $A=(a_1,⋯,a_n)$，其中 $1 \leq a_i \leq 9$。对于其中相邻的两项的 ai 和 ai+1 ，满足 $ /gcd(a_i,a_{i+1})=1$ 时，Ayano 可以通过一次操作交换 $a_i$ 和 $a_{i+1}$ $(1 \leq i \leq n−1)$。
请你计算 Ayano 可以通过这个操作得到多少种数列（包含原数列） ($mod \ 998244353$) 。
解题思路
考场上看了一眼这题没怎么仔细想，先去打第三四题去了。
显然对于数字$1,5,7$ 可以随意放在任何位置（和任何数都可以交换）。所以可以考虑先放这几个数，简单的组合数学。
接下来把剩下的数分为$3$类，分别为${2,4,8},{3,9},{6}$，这里$6$单独分出显然是因为它与一二类都不互质，所以在$6$左侧的一二类数不可能交换到右侧，右侧同理。
于是我们把$6$当作一个分界线，在他一侧有$x$个一类和$y$个二类时，相当于有$C_{x+y}^y$种。最后把答案都算出来即可。
由于是除法取模需要取逆元，可以线性求逆元。（但我数论只会gcd和快速幂。）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
const int mod=998244353;
int n,x,y,a[N],fac[N],inv[N],c[N],ans=1;
int C(int n,int m){
return n<m?0:1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
long long qmi(long long a,long long b){
long long res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
signed main(){
cin>>n;
fac[0]=inv[0]=inv[1]=1;
for(int i=1;i<=n;i++){
fac[i]=1ll*fac[i-1]*i%mod;
inv[i]=qmi(fac[i],mod-2);
}
for(int i=1;i<=n;i++){
cin>>a[i];
}
a[n+1]=6;
for(int i=1;i<=n+1;i++){
if(a[i]==6) ans=ans*C(x+y,x)%mod,x=y=0;
else x+=!(a[i]%2),y+=!(a[i]%3),c[a[i]]++;
}
ans=ans*C(n,c[1])%mod*C(n-c[1],c[5])%mod*C(n-c[1]-c[5],c[7])%mod;
cout<<ans<<'\n';
}高爸
题目描述
Shintaro 有 $n$ 条龙。 第 $i$ 条龙的力量值是 $x_i$。现在 Shintaro 想与这些龙交朋友。
Shintaro 会使用以下两种魔法来平衡龙的力量值（使某些龙的力量值相等），以免与他交朋友的龙互相打架。
强化魔法：消耗 $a$ 点 mp，使某条龙的力量值增加$1$点。
弱化魔法：消耗 $b$ 点 mp，使某条龙的力量值降低$1$点。
在第 $i$ 次，Shintaro 想与前 $i$ 条龙交朋友($1 \leq i \leq n$)。我们有很多种使用魔法的方案，使前 $i$ 条龙力量值相等。请你找到消耗 mp 点数最小的方案，并输出 mp 点数。
数据范围
$50%:n≤1000$
另$20%:1≤xi≤100$
$100%:1≤n≤100000,1≤a,b≤10^4,1≤xi≤10^9$
解题思路
看到这题的第一眼是差分，后来打算用dp拿个部分分。
设$dp_{i,j}$ 表示前$i$个数全都变为第$j$条龙的代价。
先写一个$O(n^3)$的dp，显然第一层枚举$i$,第二层枚举$j$，第三层枚举第$1$到第$i$条龙全部变为第$j$条龙的代价。
想一想优化，显然，对于$j \le i$ 的情况下，$dp_{i,j}$可以从$dp_{i-1,j}$+cost(i to j) 转移而来，对于$dp_{i,i}$，我们在第二层循环即可处理出$dp_{i,i}$的值。所以打了一个$O(n^2)$的dp。五十分到手。
观察到还有二分$x_i \leq 100$，所以对于这部分数据只要把$j$的含义，改为将变为数值为$j$的龙即可。
正解是每插入一条新的龙，最优的解一定只换成两边其中一条龙，用对顶堆即可实现。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
priority_queue<int> down;
priority_queue<int,vector<int>,greater<int> > up;
int n,a,b,num[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>a>>b;
for(int i=1;i<=n;i++) cin>>num[i];
int mid=num[1],cnt=1;
long long ans=0;
cout<<ans<<'\n';
for(int i=2;i<=n;i++){
if(num[i]>mid){
ans+=(num[i]-mid)*b;
up.push(num[i]);
}
else if(num[i]<mid){
ans+=(mid-num[i])*a;
down.push(num[i]);
}
else cnt++;
long long res1=1e18,res2=1e18;
if(up.size()){
int tp=up.top();
int sz=up.size();
res1=ans+(tp-mid)*(i-sz)*a-(tp-mid)*sz*b;
}
if(down.size()){
int tp=down.top();
int sz=down.size();
res2=ans+(mid-tp)*(i-sz)*b-(mid-tp)*sz*a;
}
if(res1<res2&&res1<ans){
ans=res1;
for(int i=1;i<=cnt;i++){
down.push(mid);
}
cnt=0;
mid=up.top();
while(up.size()&&up.top()==mid){up.pop(),cnt++;}
}
else if(res2<=res1&&res2<ans){
ans=res2;
for(int i=1;i<=cnt;i++){
up.push(mid);
}
cnt=0;
mid=down.top();
while(down.size()&&down.top()==mid){
down.pop();
cnt++;
}
}
cout<<ans<<'\n';
}
}金牌
题目描述
Ayano 有一棵 $n$ 个顶点的树（编号从 $1$ 到 $n$ )。 这棵树有 $n−1$ 条边，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 由于Ayano 非常喜欢这棵树，树上的每条路径都被赋予了价值。具体地，这棵树上长度为 $d$ 的简单路径的价值是 $2^d$。
现在 Ayano 对你发出了 $q$ 次询问，每次给出两个正整数 $x$,$y$ ，请你回答所有通过顶点 $x$ 和 $y$ 的简单路径的价值之和 (mod $998244353$) 。
注：简单路径是指路径上的各顶点均不互相重复的路径，路径的长度是指一条路径经过的边的条数。
解题思路
简单模拟一下可以发现显然与lca有关，算出之后分类讨论一下预处理出各种情况代价即可，考场上写挂了。
一共有两种情况，我们先从简单的开始。假设查询的点为u和v。
我们随意以一个点作为根。
由于是一棵树，所以两个点的最简单的路径只有一条，就是两个点到他们的lca的路径，接下来考虑怎么快速的求出价值。
对于题目将价值定义为$2^d$，显然，我们可以通过预处理处理出这个点到它往下的任何一个点的长度之和或者说是价值之和。我们将它存在一个数组w内。
情况1
查询的两个定点的lca不是他们中的任意一个。
由于不能重复经过一个点多次，所以不可能继续路径从lca继续朝根走。只能从u或v两个点处朝下走，所以最后的答案一共只需再加上两部分。在图中即为$w_u \times w_v$，最后再乘上必经之路上的长度的价值即可。
情况2
查询的两个定点的lca是他们中的某一个，为什么说这总情况复杂呢？简单画个图。
同情况$1$，只不过价值变成了$3$部分。
第$1$部分最好计算，$w_v$即可。
第$2$部分略微不好计算，需要$w_u -w_x$，x可以在求lca处理出来。
第$3$部分是最复杂的地方可以发现，这里是从lca往根节点走，而不是朝子儿子走，所以说第一次的预处理无法处理这种情况，所以我们要在开一个数组g来存储这个点朝上的价值总和。（由于计算方便可能要再存一点东西）具体实现自己思考一下。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
const int mod=998244353;
int e[N<<1],ne[N<<1],h[N],idx;
int si[N],w[N],g[N];
int siz[N],son[N],f[N],top[N],dep[N];
int n,m,q;
void add(int x,int y){
e[++idx]=y;ne[idx]=h[x];h[x]=idx;
e[++idx]=x;ne[idx]=h[y];h[y]=idx;
}
int read(){
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
return x;
}
void dfs(int ver,int fa){
w[ver]=1;
f[ver]=fa;
dep[ver]=dep[fa]+1;
son[ver]=-1;
siz[ver]=1;
for(int i=h[ver];i;i=ne[i]){
int j=e[i];
if(j!=fa){
dfs(j,ver);
siz[ver]+=siz[j];
if(siz[j]>siz[son[ver]]) son[ver]=j;
si[ver]++;
w[ver]=(w[ver]+(w[j]<<1))%mod;
}
}
}
void dfs2(int ver,int to){
top[ver]=to;
if(son[ver]!=-1) dfs2(son[ver],to);
for(int i=h[ver];i;i=ne[i]){
int j=e[i];
if(j!=f[ver]&&j!=son[ver]){
dfs2(j,j);
}
}
}
void dfs3(int ver,int fa){
for(int i=h[ver];i;i=ne[i]){
int j=e[i];
if(j==fa) continue;
g[j]=(g[ver]-w[j]*2%mod+mod)%mod*2%mod+w[j]%mod;
dfs3(j,ver);
}
}
int lca(int x,int y,int &o){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){
o=top[y];
y=f[top[y]];
}
else o=top[x],x=f[top[x]];
}
if(x==y) return x;
return dep[x]>dep[y]?((o=son[y])+y-son[y]):((o=son[x])+x-son[x]);
}
int qmi(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
n=read();
for(int i=1;i<n;i++){
int u,v;
u=read(),v=read();
add(u,v);
}
q=read();
dep[1]=1;
f[1]=1;
dfs(1,1);
g[1]=w[1];
dfs2(1,1);
dfs3(1,1);
for(int i=1;i<=q;i++){
int u,v;
int res=0;
u=read();
v=read();
int x;
int lc=lca(u,v,x);
if(lc==u||lc==v){
if(dep[u]>dep[v]) swap(u,v);
int de=dep[v]-dep[u];
res=(g[u]-w[x]*2%mod+mod)%mod*w[v]%mod;
res=res*qmi(2,de)%mod;
cout<<res<<'\n';
}
else{
//cout<<lc<<'\n';
res=(((w[u]*w[v])%mod)*qmi(2,dep[u]-dep[lc]+dep[v]-dep[lc]))%mod;
cout<<res<<'\n';
}
}
// for(int i=1;i<=n;i++) cout<<siz[i]<<' ';
// cout<<'\n';
// for(int i=1;i<=n;i++) cout<<w[i]<<' ';
}
/*
5
1 2
2 3
2 4
4 5
3
1 3
2 3
3 4
*/