本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-15 17:50:41

题目

考察：爆搜状压 dp。
题目简述： 给你一个 $n$，有一个 $1$ 到 $n$ 的排列 $a$，给你 $m$ 个关系，表示 $a_x$ 比 $a_y$ 大 $z$，问每一个数是否确定，若确定，输出是多少，若不是，输出 $-1$。
数据保证有解。
数据范围：
$2\le n\le 16$
$0\le m\le \frac{n(n-1)}{2}$

首先我们像图一样建边，每条边 $u,v,w$ 表示 $a_u$ 比 $a_v$ 大 $w$（$w$ 可以是负数），然后我们再来几遍 dfs，得出每个部分中的每个元素比部分中的代表元素多了多少。设 $siz_i$ 表示第 $i$ 个部分的大小，$pos_i$ 表示第 $i$ 个元素比代表元素大多少。

然后我们很容易想到状压，一个 $n$ 位的二进制数码，第 $i$ 位表示一个部分是否拥有一个比代表元素大 $i-1$ 的数。
我们设第 $i$ 个部分的二进制数码是 $res_i$，这样，问题就变成了能否取合适的 $x$，使 $res_{i}\times 2^x$ 两两不相交（交集为空）。

我们很容易发现一个部分内的元素，要么都不确定，要么都确定。那么只要把除一个之外的部分放上去，若剩余部分是固定的，则该部分都是固定的。那么我们先把除一个部分以外的部分都塞进去，然后再塞那个部分，统计一下 $x$ 有几个即可。

总体复杂度为 $O(2^nn^3)$。
代码：

#include<bits\/stdc++.h>
#define inl inline
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF LLONG_MAX
using namespace std;
const int N=25,M=(1ll<<16)+5;
int n,m,a,b,c,num,pos[N],res[N],siz[N],ans[N],vis[N];
vector<pair<int,int> >g[N],d;
bool f[N][M];
set<int>st;
inl bool cmp(pair<int,int>x,pair<int,int>y){
	return x.second<y.second;
}
inl void dfs(int x,int sum){
	vis[x]=num;
	d.push_back({x,sum});
	for(auto pr:g[x])
		if(!vis[pr.first]) dfs(pr.first,sum+pr.second);
}
signed main(){
	fst;
	cin>>n>>m;
	rep(i,1,m){
		cin>>a>>b>>c;
		g[a].push_back({b,-c});
		g[b].push_back({a,c});
	}
	rep(i,1,n)
		if(!vis[i]){
			d.clear();
			++num;
			dfs(i,0);
			sort(d.begin(),d.end(),cmp);
			for(auto pr:d){
				pos[pr.first]=pr.second-d[0].second;
				res[num]|=1ll<<pos[pr.first];
			}
			siz[num]=d[d.size()-1].second-d[0].second+1;
		}
	memset(ans,-1,sizeof(ans));
	rep(i,1,num){
		memset(f,0,sizeof(f));
		f[0][0]=1;
		rep(j,1,num)
			if(j==i) memcpy(f[j],f[j-1],sizeof(f[j-1]));
			else rep(k,0,(1ll<<n))
				if(f[j-1][k])
					rep(l,0,n-siz[j])
						if((k&(res[j]<<l))==0) f[j][k|(res[j]<<l)]=1;
		st.clear();
		rep(j,0,(1ll<<n)-1)
			if(f[num][j])
				rep(k,0,n-siz[i])
					if((j&(res[i]<<k))==0) st.insert(k);
		if(st.size()==1)
			rep(j,1,n)
				if(vis[j]==i) ans[j]=(*st.begin())+pos[j]+1;
	}
	rep(i,1,n) cout<<ans[i]<<' ';
	return 0;
} 

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-16 21:09:19

题目

考察：树状数组，线段树，动态规划。
题意简述：
有 $n+1$ 个城市，编号为 $[0,n]$，你接到了 $m$ 个关于一个活动的消息：$t_i,p_i$。
$t_i$ 表示该活动在第 $t_i$ 个城市举办，$p_i$ 表示参加活动可以获得的钱数，但是每经过一个城市，你要花费 $c$ 元的路费。
你一开始在 $0$ 号城市，每个活动你可以参加，也可以不参加，但必须按顺序参加，求获得的钱数的最大值。
数据范围：

• $1\le n,m\le 2\times 10^5$
• $1\le c\le 10^9$
• $1\le t_i\le n$
• $1\le p_i\le 10^{13}$

我们可以看出明显是一道 dp 题，然后 $f_i$ 肯定跟 $f_j\ \ (0\le j<i)$ 有关，很容易推出状态转移方程：
$$f_i=\max_{j=0}^{i-1}(f_j-c\times|x_i-x_j|+p_i)$$ 但是这样转移是 $O(m^2)$ 的，无法通过 $m\le 2\times 10^5$ 的数据，考虑优化。

每个点造成的贡献是 $f_j-c\times|x_i-x_j|+p_i$，其中 $p_i$ 是固定的，那么在 $f_j-c\times|x_i-x_j|$ 中，我们考虑如何拆掉绝对值符号，我们分类讨论 $|x_i-x_j|$：

• 当 $x_i\ge x_j$ 时：
  $$\begin{aligned}c\times|x_i-x_j|&=c\times(x_i-x_j)\&=c\times x_i-c\times x_j\end{aligned}$$ $c\times x_i$ 是固定的，那么我们只需要找出 $-c\times x_j$ 的最大值即可。
• 当 $x_i<x_j$ 时： $$\begin{aligned}c\times|x_i-x_j|&=c\times(x_j-x_i)\&=c\times x_j-c\times x_i\end{aligned}$$ $-c\times x_i$ 是固定的，那么我们只需要找出 $c\times x_j$ 的最大值即可。

那么我们可以用树状数组或线段树维护 $f_{x_j}\ (x_j\le x_i)$ 的前缀最大值，$f_{x_j}\ (x_j>x_i)$ 的后缀最大值（由于树状数组只能维护前缀最大值，所以我们将 $f_{x_j}$ 变为 $f_{n-x_j}$）
我们定义两个树状数组，$f$ 是维护 $x_j\le x_i$ 的最大值，查询的结果是 $fmax$，$g$ 是维护 $x_j>x_i$ 的最大值，查询的结果是 $gmax$，那么 $f_i$ 就等于： $$f_i=\max(fmax+c\times x_i,gmax-c\times x_i)+p_i$$ 然后我们在修改 $f,g$ 中的值即可。

这样我们就可以在 $O(m\log_2n)$ 的复杂度内完成本题。

代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define fst; ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define fi first
#define se second
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int n,c,m,t,p,num,ans; 
struct BIT{
	int a[N];
	inl BIT(){
		memset(a,-0x3f,sizeof(a));
	}
	inl int lowbit(int x){
		return x&(-x);
	}
	inl void add(int x,int k){
		while(x<=n){
			a[x]=max(a[x],k);
			x+=lowbit(x);
		}
		return;
	}
	inl int getmax(int x){
		int mx=-INF;
		while(x){
			mx=max(mx,a[x]);
			x-=lowbit(x);
		}
		return mx;
	}
}t1,t2;
signed main(){
	fst; 
	cin>>n>>c>>m;
	t1.add(1,c);
	t2.add(n,-c);
	rep(i,1,m){
		cin>>t>>p;
		num=max(t1.getmax(t)-c*t,t2.getmax(n-t)+c*t)+p;
		ans=max(ans,num);
		t1.add(t,num+c*t);
		t2.add(n-t+1,num-c*t);
	}
	cout<<ans;
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-23 21:21:19

题目

题目考察：树状数组，线段树，动态规划。
题意简述： 给你一个序列 $\{a_n\}$，求序列内有哪些数可能成为最长上升子序列的其一个元素。
注：最长上升子序列：$\forall i\in[1,n),a_i<a_{i+1}$。
数据范围：

• $1\le t,n,\sum n\le 2\times 10^5$
• $\forall i\in[1,n],1\le a_i\le 10^9$

我们都知道，最长上升子序列应该用 dp 写，设 $\forall i\in[1,n]$，$f_i$ 表示以第 $i$ 个数结尾的最长上升子序列的长度，那么： $$f_i=\max_{j=0,a_j<a_i}^{i-1}(f_i)+1$$ 这样复杂度是 $O(n^2)$ 的，考虑优化。

我们知道树状数组（设其为 $t$）可以维护前缀极值，那么我们可以每算完一个 $f_i$ 后，就把他存进对应的 $t_{a_i}$ 中，我们就可以在 $O(n\log_2n)$ 的复杂度中处理 $f_i$。
当然 $a_i$ 是很大的，那么我们将其离散化，结果不变。

那么，我们得到了 $f_i$，若它在最长上升子序列里，有以下可能：

• $f_i=\max_{j=1}^n(f_j)$。
• $\max_{j=i+1}^n([f_j=f_i+1\land a_j>a_i])=1$

按上述模拟即可。
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(int i=x;i<=y;++i) 
#define per(i,x,y) for(int i=x;i>=y;--i)
#define endl '\n'
#define fi first
#define se second
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int t,n,a[N],b[N],cnt,dp[N],mx[N],tot,ans[N],mxx;
struct BIT{
	int f[N];
	inl void init(){
		rep(i,1,cnt) f[i]=0;  
	}
	inl int lowbit(int x){
		return x&-x;
	}
	inl void add(int x,int k){
		while(x<=cnt){
			f[x]=max(f[x],k);
			x+=lowbit(x); 
		}
	}
	inl int getmax(int x){
		int mx=0;
		while(x){
			mx=max(mx,f[x]);
			x-=lowbit(x);
		}
		return mx;
	}
}bit; 
inl void solve(){
	bit.init();
	rep(i,1,mxx) mx[i]=0;
	rep(i,1,n) dp[i]=0;
	mxx=tot=0;
	cin>>n;
	rep(i,1,n) cin>>a[i];
	rep(i,1,n) b[i]=a[i];
	sort(b+1,b+n+1);
	cnt=unique(b+1,b+n+1)-b-1;
	rep(i,1,n) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
	rep(i,1,n){
		dp[i]=bit.getmax(a[i]-1)+1;
		bit.add(a[i],dp[i]);
	}
	rep(i,1,n) mxx=max(mxx,dp[i]);
	per(i,n,1)
		if(dp[i]==mxx||mx[dp[i]+1]>a[i]){
			ans[++tot]=i;
			mx[dp[i]]=max(mx[dp[i]],a[i]);
		}
	sort(ans+1,ans+tot+1);
	cout<<tot<<endl;
	rep(i,1,tot) cout<<ans[i]<<' ';
	cout<<endl;
}
signed main(){
	fst;
	cin>>t;
	while(t--) solve();
	return 0;
} 

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-30 21:12:56

注：此题为 IO 交互题。

题目考察：交互，最短路。
题目简述：
给你三个整数 $n,l,r$，指评测机随机生成了一个长度为 $2^n$ 的序列 $\{a_{2^n}\}$（题目从 $0$ 开始计数），让你求区间 $[l,r]$ 的和对 $100$ 取模的结果 $\displaystyle(\sum_{i=l}^ra_i)\bmod 100$。
你可以问评测机若干个问题，每次以 ? l r 的形式给出，意为询问区间 $[2^ij,2^i(j+1)-1]$ 的和对 $100$ 取模的结果，若得到了答案，以 ! ans 的形式给出答案，并立即终止程序。
要求在能确定答案的情况下，问题数最少，你要按照以上描述给出答案。
数据范围：

• $n\in[1,18]\cap\mathbb N$
• $l,r\in[0,2^n-1]\cap\mathbb N$
• $l\le r$

为了方便，我们将 $[l,r+1)$ 当作题目的 $[l,r]$。
我们将这道题建模为由 $r+1$ 走到 $l$ 的最短路，我们可以由 $x$ 转移到 $x-2^i$ 和 $x+2^i$（$i\in\mathbb Z,2^i|x$），由于边权都为 $1$，所以使用 BFS 即可。
记录路径时我们记录其前驱结点即可。

这样我们就得到了路径，然后我们对其进行询问，最后输出答案即可。

代码：

#include<bits\/stdc++.h>
#define int long long
#define reg register
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(reg int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(reg int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define gc getchar
#define pc putchar
#define endl '\n'
#define fi first
#define se second
using namespace std;
inl int read(){
	reg int f=1,x=0;
	reg char ch;
	while(!isdigit(ch=gc()))
		if(!(ch^'-')) f=-1;
	x=ch^48;
	while(isdigit(ch=gc())) x=(x<<1)+(x<<3)+(ch^48);
	return f*x;
}
inl void write(int x,char ch){
	if(x<0){
		pc('-');
		x=-x;
	}
	if(x>=10) write(x\/10,0);
	pc(x%10^48);
	if(ch) pc(ch);
}
inl string get(){
	char ch;
	string s="";
	while((ch=gc())=='\r'||ch=='\n'||ch==' ');
	s+=ch;
	while((ch=gc())!='\r'&&ch!='\n'&&ch!=' ') s+=ch;
	return s;
}
inl char gett(){
	char ch;
	while((ch=gc())=='\r'||ch=='\n'||ch==' ');
	return ch;
}
inl int maxx(int a,int b,int c){
	return max(a,max(b,c));
}
inl int minn(int a,int b,int c){
	return min(a,min(b,c));
}
const int N=(1<<18)+10,MOD=100;
int n,l,r,lst[N],ans,now,res;
queue<int>q;
inl void bfs(){
	q.push(l);
	while(!q.empty()){
		reg int x=q.front();
		q.pop();
		rep(i,0,__lg(n)){
			rep(j,-1,1)
				if(j){
					reg int tx=x+(1<<i)*j;
					if(tx>=0&&tx<=n&&!(~lst[tx])){
						lst[tx]=x;
						q.push(tx);
					}
				}
			if(x&(1<<i)) break;
		}
	}
}
signed main(){
	memset(lst,-1,sizeof(lst));
	n=(1<<read());
	l=read();
	r=read()+1;
	bfs();
	now=r;
	while(now!=l){
		reg int f=1,a=lst[now],b=now;
		if(a>b){
			swap(a,b);
			f=-1;
		}
		putchar('?');
		putchar(' ');
		write(__lg(b-a),' ');
		write(a\/(b-a),endl);
		fflush(stdout);
		res=read();
		(ans+=f*res+MOD)%=MOD;
		now=lst[now];
	}
	putchar('!');
	putchar(' ');
	write(ans,endl);
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-06 22:08:50

题目考察：前缀和，二分，调和级数。
题目简述：
给你 $\{a_n\}$，求：
$$\sum_{i=1}^{n-1}\sum_{j=i+1}^n\lfloor\frac{\max(a_i,a_j)}{\min(a_i,a_j)}\rfloor$$
数据范围：

• $1\le n\le 2\times 10^5$
• $\forall i\in[1,n],1\le a_i\le 10^6$

我们将式子变形得： $$\sum_{i=1}^{n-1}\sum_{j=i+1}^n\lfloor\frac{\max(a_i,a_j)}{\min(a_i,a_j)}\rfloor=\sum_{i=1}^n\sum_{j=1}^n[a_j\ge a_i\land i\ne j]\times\lfloor\frac{a_j}{a_i}\rfloor$$ 我们再将 $\{a_n\}$ 升序排序变为：
$$\sum_{i=1}^n\sum_{j=1}^n[a_j\ge a_i\land i\ne j]\times\lfloor\frac{a_j}{a_i}\rfloor=\sum_{i=1}^{n-1}\sum_{j=i+1}^n\lfloor\frac{a_j}{a_i}\rfloor$$ 那么我们考虑如何快速求 $\displaystyle \sum_{i=1}^{n-1}\sum_{j=i+1}^n\lfloor\frac{a_j}{a_i}\rfloor$，我们将 $\{a_n\}$ 分块，将 $\displaystyle\lfloor\frac{a_j}{a_i}\rfloor$ 相同的 $a_j$ 分在一组。设 $\displaystyle k=\lfloor\frac{a_j}{a_i}\rfloor$，则这些数一定是区间 $[ka_i,(k+1)a_i)$ 之间的数，那么我们可以用二分或者前缀和来维护个数，我用的是二分（设 $a_l\ge ka_i>a_{l-1}$，$a_{r+1}\ge(k+1)a_i>a_r$，$l,r$ 为满足上述条件的数），这组数的贡献就是 $k(r-l+1)$。
这样的做法显然可以被一半 $1$，一半不是 $1$，使复杂度退化为 $O(n^2)$，所以我们要特判相同数字。

证明时间复杂度合理：
这样运行次数最多为 $\displaystyle\sum_{i=1}^n\lfloor\frac{n-i}{i}\rfloor$，下面证明复杂度：
$$\begin{aligned}\sum_{i=1}^n\lfloor\frac{n-i}{i}\rfloor&\le\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\&\le\sum_{i=1}^n\lfloor\frac{n}{2^{\lfloor\log_2i\rfloor}}\rfloor\&=\sum_{i=1}^{\lfloor\log_2n\rfloor}2^i\times\lfloor\frac{n}{2^i}\rfloor\&\le\sum_{i=1}^{\lfloor\log_2n\rfloor}2^i\times\frac{n}{2^i}\&=\sum_{i=1}^{\lfloor\log_2n\rfloor}n\&\le n\log_2n\end{aligned}$$ 故复杂度小于 $n\log_2n$，实际约为 $n\ln n$。

代码：

#include<bits\/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=y;++i) 
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define endl '\n'
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int n,a[N],ans;
signed main(){
	fst;
	cin>>n;
	rep(i,1,n) cin>>a[i];
	sort(a+1,a+n+1);
	rep(i,1,n){
		reg int l=i+1,tot=a[l]\/a[i],sum=0;
		while(l<=n){
			reg int r=lower_bound(a+l,a+n+1,a[i]*(tot+1))-a-1;
			sum+=(r-l+1)*tot;
			l=r+1;
			tot=a[l]\/a[i];
		}
		ans+=sum;
		while(a[i+1]==a[i]){
			--sum;
			ans+=sum;
			++i;
		}
	}
	cout<<ans;
	return 0;
} 

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-13 21:59:32

[ABC357E] Reachability in Functional Graph

题目考察：图论，tarjan，缩点。
题目简述：
给你一个有向图，有 $n$ 条边和 $n$ 个点，其中第 $i$（$1\le i\le n$）个点有一条出边，指向 $a_i$，求图中每个点可达点的个数之和。
其中 $u$（$1\le u\le n$）点的可达点指：

• $u$ 点是他自身的可达点。
• 若 $x$ 点是 $u$ 点的可达点，且 $y=a_x$，则 $y$ 点是 $u$ 点的可达点（$1\le x\le n$）。

数据范围：

• $1\le n\le 2\times 10^5$
• $1\le a_i\le n$

我们先看一下样例 $2$：
很明显如果没有 $\{1,2,4\}$ 这个环，我们直接建反图跑 topsort 即可。可以设 $u$ 点（$1\le u\le n$）可达点数为 $num_u$，若 $u=a_v$，则：
$$num_u=num_v+1$$ 可是这只是假设，如果有环该怎么办呢？
一个合理的想法是把这个环（强连通分量）缩成一个点，以此来跑 topsort。

那么我们就需要用到 tarjan 缩点算法，通过栈来实现。

首先我们需要的是一个时间戳 $dfn_i$（$1\le i\le n$）和一个记录他自身和他的后继节点且未访问或在栈里的的时间戳的最小值 $low_i$，还有一个在栈里的标记 $vis_i$，显然 $low_i$ 等于：
$$low_i=\min(dfn_i,\min_{(i,j)\in E\land(dfn_i=0\lor vis_i=\text{true})}(dfn_j))$$ 我们先把 $i$ 存入栈中，然后我们对他的未访问的后继结点进行 dfs，dfs 完后若 $dfn_i=low_i$，则有两种情况：

• 他不在一个环里，这样其未访问的后继结点的 $dfn_j$（$(i,j)\in E$）一定大于 $dfn_i$。
• 它是一个环的起点，这样这个环里的所有点都能通过若干条有向边到达 $i$，所以这个环里的点的 $low_j$ 都等于 $dfn_i$。

综上所述，他一定是一个强连通分量的起点，那么强连通分量的所有点一定都在栈的上层，那么我们把他们弹出来，并对他们进行染色。
这样我们就知道他们之中的环在哪里了，然后我们重新建图，具体请看模板题 P3387 【模板】缩点。

代码：

模板题代码：
时间复杂度为 $\Theta(n)$。

#include<bits\/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=y;++i) 
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define endl '\n'
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int n,a[N],dfn[N],low[N],tim,sum[N],col,color[N],in[N],num[N],ans,u,v,m;
bool vis[N];
stack<int>st;
queue<int>q;
vector<int>g[N],gx[N];
inl void topsort(){
	rep(i,1,col)
		if(!in[i]){
			q.push(i);
			num[i]=sum[i];
		}
	while(!q.empty()){
		reg int u=q.front();
		q.pop();
		for(reg auto v:gx[u]){
			num[v]=max(num[v],num[u]+sum[v]);
			--in[v];
			if(!in[v]) q.push(v);
		}
	}
}
inl void tarjan(int u){
	vis[u]=1;
	st.push(u);
	dfn[u]=low[u]=++tim;
	for(reg auto v:g[u])
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]) low[u]=min(low[u],low[v]);
	if(dfn[u]==low[u]){
		reg int v;
		++col;
		while(!st.empty()){
			v=st.top();
			st.pop();
			color[v]=col;
			vis[v]=0;
			sum[col]+=a[v];
			if(u==v) break;
		}
	}
}
signed main(){
	fst;
	memset(num,-1,sizeof(num));
	cin>>n>>m;
	rep(i,1,n) cin>>a[i];
	rep(i,1,m){
		cin>>u>>v;
		g[u].push_back(v);
	}
	rep(i,1,n)
		if(!dfn[i]) tarjan(i);
	rep(i,1,n)
		for(reg auto j:g[i])
			if(color[i]!=color[j]){
				gx[color[i]].push_back(color[j]);
				++in[color[j]];
			}
	topsort();
	rep(i,1,col) ans=max(ans,num[i]);
	cout<<ans;
	return 0;
} 

本题代码：
时间复杂度为 $\Theta(n)$。

#include<bits\/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=y;++i) 
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define endl '\n'
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int n,a[N],dfn[N],low[N],tim,sum[N],col,color[N],in[N],num[N],ans;
bool vis[N];
stack<int>st;
queue<int>q;
vector<int>g[N];
inl void topsort(){
	rep(i,1,col)
		if(!in[i]){
			q.push(i);
			num[i]=sum[i];
		}
	while(!q.empty()){
		reg int u=q.front();
		q.pop();
		for(reg auto v:g[u]){
			num[v]=sum[v]+num[u];
			--in[v];
			if(!in[v]) q.push(v);
		}
	}
}
inl void tarjan(int u){
	vis[u]=1;
	st.push(u);
	dfn[u]=low[u]=++tim;
	if(!dfn[a[u]]){
		tarjan(a[u]);
		low[u]=min(low[u],low[a[u]]);
	}else if(vis[a[u]]) low[u]=min(low[u],low[a[u]]);
	if(dfn[u]==low[u]){
		reg int v;
		++col;
		while(!st.empty()){
			v=st.top();
			st.pop();
			color[v]=col;
			vis[v]=0;
			++sum[col];
			if(u==v) break;
		}
	}
}
signed main(){
	fst;
	memset(num,-1,sizeof(num));
	cin>>n;
	rep(i,1,n) cin>>a[i];
	rep(i,1,n)
		if(!dfn[i]) tarjan(i);
	rep(i,1,n)
		if(color[i]!=color[a[i]]){
			g[color[a[i]]].push_back(color[i]);
			++in[color[i]];
		}
	topsort();
	rep(i,1,col) ans+=num[i]*sum[i];
	cout<<ans;
	return 0;
} 

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-16 11:53:50

[ABC358E] Alphabet Tiles

题目考察：组合数学，动态规划。
题目简述：
给你一个数 $k$ 和一个序列 $\{c_{26}\}$，求满足以下条件的字符串的个数对 $998244353$ 取模的结果：

• $1\le |s|\le k$。
• 设一序列 $\{p_{26}\}$ 的 $p_i$ 为在大写字母中第 $i$ 组字母，如 $p_1$ 为 A，$p_5$ 为 E 等，则 $\displaystyle \forall i\in[1,26],\sum_{j=1}^{|s|}[s_j=p_i]\le c_i$。
  数据范围：
• $1\le k\le 10^3$
• $\forall i\in[1,26],0\le c_i\le 10^3$

我们设 $m=26$，则若直接暴力枚举，则复杂度为 $\Theta(m^k)$，根本无法接受。

考虑 dp。
我们设 $f_{i,j}$（$\displaystyle 1\le i\le 26,1\le j\le \min(k,\sum_{s=1}^{26}c_s)$）为在前 $i$ 组字母中选出 $j$ 个字母组成字符串的方案数对 $998244353$ 取模的结果，他可以由 $f_{i-1,l}$（$\max(0,j-c_i)\le l\le j$）转移而来，但是是如何转移的呢？
我们的这个长度为 $j$ 的字符串 $s$ 的第 $x$ 位（$1\le x\le j$）可以分配给前 $i-1$ 组字母其中的一组，也可以分配给第 $i$ 组，由于必须分配给前 $i-1$ 组字母 $l$ 位，则分配的方式有 $\displaystyle\binom{j}{l}$ 种，由于前 $i-1$ 组字母还可以有 $f_{i-1,l}$ 种排列，那么我们就得到了状态转移方程：
$$f_{i,j}=\sum_{l=j-c_i}^jf_{i-1,l}\times\binom{j}{l}$$ 我们可以先预处理 $\displaystyle\binom{i}{j}$（$0\le i\le k,0\le j\le i$）： $$\binom{i}{j}=\binom{i-1}{j}+\binom{i-1}{j-1}$$ 再进行 dp。

由于 $f_{i,j}$ 只与 $f_{i-1,l}$ 有关，所以我们可以将第一维压掉。

总体复杂度为 $\Theta(mk^2)$，$mk^2\le 2.6\times 10^7$，可以接受。

代码：

#include<bits\/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=y;++i) 
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define endl '\n'
#define INF 1e16
#define pb push_back
#define fi first
#define se second
#define lcm(x,y) x\/__gcd(x,y)*y
#define ull unsigned long long
using namespace std;
const int N=1005,M=35,MOD=998244353;
int c[M],f[N],dp[N][N];
signed main(){
	fst;
	reg int n,ans=0,ret=0;
	cin>>n;
	rep(i,1,26){
		cin>>c[i];
		ret+=c[i];
	}
	n=min(n,ret);
	f[0]=dp[1][1]=1;
	rep(i,2,n+1)
		rep(j,1,i) dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%MOD;
	rep(i,1,26)
		per(j,n,1)
			rep(k,max(0ll,j-c[i]),j-1) (f[j]+=f[k]*dp[j+1][k+1]%MOD)%=MOD;
	rep(i,1,n) (ans+=f[i])%=MOD;
	cout<<ans;
	return 0;
} 

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-01 11:32:08

[ABC360E] Random Swaps of Balls

题目考查：期望，逆元。
题目简述：
给你一个数 $n$，有 $n-1$ 个白球和 $1$ 个黑球，黑球一开始在最左侧。有 $k$ 次操作，每次操作等概率随机地从区间 $[1,n]$ 选出两个数 $a,b$，交换处于从左往右数第 $a$ 个球和第 $b$ 个球，求最后黑球所在位置的期望值对 $998244353$ 取模的结果。
数据范围：

• $1\le n<998244353$
• $1\le k\le 10^5$

很容易发现除了黑球在第一个位置外，黑球在其他位置上的概率是相同的。
那么我们设第 $i$ 次操作后黑球在第一个位置上的概率（当然要对 $998244353$ 取模，下同）为 $f_i$，在其他位置上的概率为 $g_i$。

注：
$\displaystyle(\frac{a}{b}+\frac{c}{d})\bmod p$ 和 $\displaystyle(\frac{a}{b}\bmod p+\frac{c}{d}\bmod p)\bmod p$ 是相同的，下面给出证明：
$$\begin{aligned}(\frac{a}{b}+\frac{c}{d})\bmod p&=\frac{ad+bc}{bd}\bmod p\&=(ad+bc)(bd)^{-1}\bmod p\end{aligned}$$ 根据费马小定理（$a^p\equiv a\pmod p$，$p\in \text{prime}$），得：
$$\begin{aligned}(\frac{a}{b}+\frac{c}{d})\bmod p&=(ad+bc)(bd)^{-1}\bmod p\&=(ad+bc)(bd)^{p-2}\bmod p\end{aligned}$$ 而：
$$\begin{aligned}(\frac{a}{b}\bmod p+\frac{c}{d}\bmod p)\bmod p&=(ab^{-1}+cd^{-1})\bmod p\&=(ab^{p-2}+cd^{p-2})\bmod p\end{aligned}$$ 我们将 $(ad+bc)(bd)^{p-2}$ 转化：
$$\begin{aligned}(ad+bc)(bd)^{p-2}&=ad(bd)^{p-2}+bc(bd)^{p-2}\&=ab^{p-2}d^{p-1}+cd^{p-2}b^{p-1}\&=ab^{p-2}+cd^{p-2}\end{aligned}$$ 证毕。
减法，乘法同理。

接下来对 $f_i$ 考虑转移方程，想要将黑球移到其他地方，有 $(1,2),(1,3),\dots,(1,n-1),(1,n)$ 和 $(2,1),(3,1),\dots,(n-1,1),(n,1)$ 这些 $2(n-1)$ 种方法，那么黑球留在原地就有 $n^2-2(n-1)$ 种方法，得转移方程：
$$f_i=((n^2-2(n-1))f_{i-1}+2(n-1)g_{i-1})\bmod 998244353$$ 然后对 $g_i$ 考虑转移方程，想要将黑球移到最左边，只有 $2$ 种方法。那么留在除了最左边的其他地方有 $n^2-2$ 种方法，得转移方程： $$g_i=((n^2-2)g_{i-1}+2f_{i-1})\bmod 998244353$$ 最后答案就是：
$$ans=(f_k+(n(n+1)-1)g_k)\bmod 998244353$$

总体复杂度为 $\Theta(k)$。
代码：

#include<bits\/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i) 
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
#define rpr(i,x,y,z) for(reg int i=x;i<=(y);i+=z)
#define epe(i,x,y,z) for(reg int i=x;i>=(y);i-=z)
#define endl '\n'
#define INF 1e16
#define pb push_back
#define fi first
#define se second
#define lcm(x,y) x\/__gcd(x,y)*y
#define ull unsigned long long
#define prr make_pair
#define pii pair<int,int> 
#define gt(s) getline(cin,s)
#define at(x,y) for(reg auto x:y)
#define ff fflush(stdout)
#define mt(x,y) memset(x,y,sizeof(x))
#define idg isdigit
#define fp(s) string ssss=s;freopen((ssss+".in").c_str(),"r",stdin);freopen((ssss+".out").c_str(),"w",stdout);
using namespace std;
const int N=1e5+5,MOD=998244353;
int f[N],g[N];
inl int ksm(int a,int b){
	reg int num=a%MOD,ans=1;
	while(b){
		if(b&1) (ans*=num)%=MOD;
		(num*=num)%=MOD;
		b>>=1; 
	}
	return ans;
}
inl int inv(int a,int b){
	return a*ksm(b,MOD-2)%MOD;
}
signed main(){
	fst;
	reg int n,k,p,q,r,s;
	cin>>n>>k;
	p=inv((n-1<<1)%MOD,n*n%MOD);
	q=inv(2,n*n%MOD);
	r=inv((n*n-(n-1<<1))%MOD,n*n%MOD);
	s=inv((n*n-2)%MOD,n*n%MOD);
	f[0]=1;
	g[0]=0;
	rep(i,1,k){
		f[i]=(f[i-1]*r%MOD+g[i-1]*p%MOD)%MOD;
		g[i]=(g[i-1]*s%MOD+f[i-1]*q%MOD)%MOD;
	}
	cout<<(f[k]+((n*(n+1)>>1)-1)%MOD*g[k]%MOD)%MOD;
	return 0;
} 

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-09 10:29:53

[ABC361E] Tree and Hamilton Path 2
考察：树的直径，dfs，dp。
题目简述：
给定一棵有 $n$ 个点的树，从任意一个点开始，经过所有点后所走过的最短路径。
一个点可以经过多次，最后不一定要回到原点。
数据范围：

• $n\le 2\times 10^5$

考虑下图：

其满足限制的最短路径是 $9\Rightarrow6\Rightarrow1\Rightarrow2\Rightarrow7\Rightarrow2\Rightarrow4\Rightarrow5\Rightarrow8\Rightarrow5\Rightarrow3$，长度为 $4+3+2+5+5+3+5+1+1+4=33$。
我们将其标在树上，就成了下图： 我们发现有向图比原树少了 $3$ 到 $9$ 的这一条路径，而这条路径就是树的直径。
那么我们得出答案就是（设直径为 $len$）： $$\sum_{(u_i,v_i,w_i)\in E}w_i-len$$ 直径采用 dp 就可得到。

代码：

#include<bits\/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i) 
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
#define rpr(i,x,y,z) for(reg int i=x;i<=(y);i+=z)
#define epe(i,x,y,z) for(reg int i=x;i>=(y);i-=z)
#define endl '\n'
#define INF 1e16
#define pb push_back
#define fi first
#define se second
#define lcm(x,y) x\/__gcd(x,y)*y
#define ull unsigned long long
#define prr make_pair
#define pii pair<int,int> 
#define gt(s) getline(cin,s)
#define at(x,y) for(reg auto x:y)
#define ff fflush(stdout)
#define mt(x,y) memset(x,y,sizeof(x))
#define idg isdigit
#define fp(s) string ssss=s;freopen((ssss+".in").c_str(),"r",stdin);freopen((ssss+".out").c_str(),"w",stdout);
#define sstr stringstream 
#define all(x) x.begin(),x.end()
#define mcy(a,b) memcpy(a,b,sizeof(b))
using namespace std;
const int N=2e5+5;
vector<pii >g[N];
int mx[N],mx2[N];
bool vis[N];
inl void dfs(int u,int &num){
	vis[u]=1;
	at(v,g[u])
		if(!vis[v.fi]){
			dfs(v.fi,num);
			if(mx[u]<mx[v.fi]+v.se){
				mx2[u]=mx[u];
				mx[u]=mx[v.fi]+v.se;
			}else mx2[u]=max(mx2[u],mx[v.fi]+v.se);
		}
	num=max(num,mx[u]+mx2[u]);
}
signed main(){
	fst;
	reg int n,num=0,ans=0;
	cin>>n;
	rep(i,2,n){
		reg int u,v,w;
		cin>>u>>v>>w;
		g[u].pb(prr(v,w));
		g[v].pb(prr(u,w));
		ans+=w<<1;
	}
	dfs(1,num);
	cout<<ans-num;
	return 0;
} 

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-12 11:00:08

一、单选题：

1. 常量的关键字是 const，选 B。
2. $12345670_8+07654321_8=22222211_8$，用竖式计算，选 D。
3. data 是一个变量，排除 C 和 D，调用成员时变量名在前，选 A。
4. 首先申请新空间，再赋值，然后将其下一个节点指向 head，最后将 head 指向它，选 A。
5. 首先根节点的高度为 $1$，然后求 $\displaystyle\sum_{i=0}^{m-1}3^i\le2023$，即 $\displaystyle\frac{3^m-1}{2}\le2023$，$m=8$，选 C。
6. 数学题，参加 $1$ 次就有 $7$ 种，$2$ 次有 $10$ 种，$3$ 次只有 $1$ 种，选 B。
7. 设两数的长度分别为 $n$ 和 $m$，高精度乘法复杂度为 $\Theta(nm)$，选 C。
8. 建表达式树，答案是 $((6-(2+3))\times(3+8\div2))^2+3$，选 A。
9. $101010_2=52_8$，$101010_2+166_8=52_8+166_8=240_8=A0_{16}$，选 D。
10. 给定了频率，这样就可以建 Huffman 树，选 A。
11. 已知先序中序求后序，后序遍历是 EDBGFCA，选 A。
12. 拓扑排序，$1$ 必须是第一个，$4$ 必须是最后一个，选 B。
13. bit 是存储的基本单位，选 B。
14. 分类讨论，如果有 $1$ 个女生，有 $\displaystyle\binom{10}{2}\times\binom{12}{1}=\frac{10\times9}{2}\times12=540$ 种选择；如果有 $2$ 个女生，就有 $\displaystyle\binom{10}{1}\times\binom{12}{2}=10\times\frac{12\times11}{2}=660$ 种选择，如果全选女生就有 $\displaystyle\binom{12}{3}=\frac{12\times11\times10}{6}=220$ 种选择，选 A。
15. HTML 是编程语言，选 D。

二、阅读程序：
（1）：
判断题：

1. $p=\frac{2+2+2}{2}=3$，$\sqrt{p(p-a)(p-b)(p-c)}=\sqrt3\pprox1.7321$，正确。
2. 乘法交换律，正确。
3. 第 $10\sim11$ 行将浮点数输出设为了 $4$ 位小数，正确。

选择题：

1. $p=\frac{3+4+5}{2}=6$，$\sqrt{p(p-a)(p-b)(p-c)}=\sqrt{36}=6$，选 A。
2. $p=\frac{5+12+13}{2}=15$，$\sqrt{p(p-a)(p-b)(p-c)}=\sqrt{900}=30$，选 B。

（2）：
判断题：

1. f 函数返回的是最长公共子序列，当然小于等于 $\min(n,m)$，正确。
2. 最长公共子序列非最长公共子串，错误。
3. 自己当然是自己的子序列，正确。

选择题：

1. 将 v[m][n] 换成 v[n][m]，当 $n\ne m$ 时会数组越界，选 D。
2. p-jcs 是 csp-jcsp-j 的子序列，选 B。
3. spsccp 是 csppsccsppsc 的子序列，选 D。

（3）：
判断题：

1. solve2 函数返回的就是 $n$ 的因子的平方和，正确。
2. 就是为了重复计算，正确。
3. 若 $n\in\text{prime}$，则其因子只有 $1$ 和 $n$，因子平方和为 $n^2+1$，正确。

选择题：

1. 若 $n=p^2,p\in\text{prime}$，则其因子有 $p^2$，$p$ 和 $1$，因子平方和为 $(p^2)^2+P^2+1^2=n^2+n+1$，选 B。
2. $n^2$ 的因子平方和小于等于 $n$ 的因子平方和的平方（不会证，建议举例子），选 D。
3. $5$ 是质数，$25$ 的因子平方和是 $25^2+25+1=651$，$5$ 的因子平方和的平方一定大于等于 $651$，选 C。

三、完善程序：
（1）：

1. 等差序列第 $mid$ 项是 nums[0]+mid，选 B。
2. 二分板子，left=mid+1，选 A。
3. 二分板子，right=mid，选 C。
4. 第 $left$ 项是 nums[0]+left，选 A。
5. 最后返回的是 nums[0]+n-1，应为 nums[n-1]，选 D。

（2）：

1. 当 $i=0$ 时，编辑距离是 $j$，选 A。
2. 同上，选 B。
3. 这里要判断这一位两个字符串是否相等，选 A。
4. 这里直接不用操作，dp[i-1][j-1]，选 B。
5. 这里还可以替换，dp[i-1][j-1]，选 C。