Tajan / 序列问题专项

save

原题链接
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

对于 \(50\%\) 的数据，\(n \le 100\)

对于 \(100\%\) 的数据，\(n \le 500\)

保证输出不会超过 \(10^{18}\)

100 pts 做法

考虑 Tarjan 点双缩点后的图。注意记录每个点双的割点数。

• 若无割点：随意选择两个点建立出口；

• 一个割点：在非割点的点中建立一个出口；

• 两个以上：无须建立割点。

分类及证明比较显然。

#include<bits/stdc++.h>
#define ll long long
const int N = 1005;
using namespace std;
ll T, n, m, ind;
ll dfn[N], low[N], anc;
ll cnt, num[N];
ll cut[N];
bool flag[N];
vector < ll > G[N], vDCC[N];
stack < ll > st;
void tarjan(int u){
	dfn[u] = low[u] = ++ind;
	int son = 0; st.push(u);
	for(int i = 0; i < G[u].size(); i++){
		int v = G[u][i];
		if(!dfn[v]){
			son++; tarjan(v);
			low[u] = min(low[u], low[v]);
			if((low[v] >= dfn[u] && u != anc) || (son >= 2 && u == anc))
			  flag[u] = true;
			if(low[v] >= dfn[u]){
				cnt++;
				while(st.top() != v){
					vDCC[cnt].push_back(st.top());
					st.pop();
				}
				vDCC[cnt].push_back(v); st.pop();
				vDCC[cnt].push_back(u);
			}
		} else low[u] = min(low[u], dfn[v]);
	}
	return;
}
void work(){
	memset(dfn, 0, sizeof dfn);
	memset(low, 0, sizeof low);
	memset(flag, 0, sizeof flag);
	memset(cut, 0, sizeof cut);
	ll u, v; vector < ll > tt;
	for(int i = 1; i <= n; i++) G[i] = tt, vDCC[i] = tt;
	n = 0; cnt = 0;
	for(int i = 1; i <= m; i++){
		scanf("%d %d", &u, &v);
		G[u].push_back(v); G[v].push_back(u);
		n = max(n, v); n = max(n, v);
	}
	for(int i = 1; i <= n; i++)
	  if(!dfn[i]) anc = i, tarjan(i);
	for(int i = 1; i <= cnt; i++){
		num[i] = vDCC[i].size(); 
		for(int j = 0; j < num[i]; j++)
		  cut[i] += flag[vDCC[i][j]];
	}
	ll ans1 = 0, ans2 = 1;
	for(int i = 1; i <= cnt; i++){
		if(cut[i] == 0)
		  ans1 += 2, ans2 *= num[i] * (num[i] - 1) / 2;
		else if(cut[i] == 1)
		  ans1 ++, ans2 *= num[i] - 1;
	}
	printf("Case %d: %lld %lld\n", ++T, ans1, ans2);
}
int main(){
	freopen("save.in", "r", stdin);
	freopen("save.out", "w", stdout);
	while(scanf("%d", &m) && m) work();
	return 0;
}

chocolate

你面前的巧克力礼盒中共有 \(n\) 块有序的巧克力，其中一部分是黑巧克力，一部分是白巧克力。

你希望找到一些有序三元组 \((i, j, k)\)，满足：

• \(i < j < k\)；

• 第 \(i\) 块和第 \(k\) 块巧克力是黑巧克力，第 \(j\) 块巧克力是白巧克力。

你需要求出共有多少个满足条件的有序三元组 \((i, j, k)\)，答案对 \(10^9 + 7\) 取模。

对于 \(100\%\) 的数据，\(3 \le n \le 10^6\)，保证 \(s\) 中只包含 \(\texttt{B}\) 和 \(\texttt{W}\)。

range

所有人，都有一段支离破碎的过去。

你有 \(n\) 段过去的经历，有时顺利，有时不顺，于是你用一个评价值 \(a_i\) 来描述你的第 \(i\) 段经历，它们构成了长度 \(n\) 为的序列 \(a\) 。你决定对过去进行反思总结，反思深度为 \(d\)。如果 \(d \ge 1\)，那你就要算出 \(a\) 的所有子区间的和之和；如果 \(d \ge 2\)，那你还要算出 \(a\) 的所有子区间的极差之和；如果 \(d \ge 3\)，那你也要算出 \(a\) 的所有子区间的平均值之和。

定义：子区间是指序列中连续的一段；区间和为区间所有数相加的和；区间极差为区间的最大值减去最小值；区间的平均值为区间和除以区间元素个数。

为了输出方便，输出平均值时请乘上 \(n!\)，所有输出对 \(1336363663\) 取模。

对于 \(100\%\) 的数据，\(1 \le n \le 3\times 10^6\)，\(0 \le d \le 3\)，\(1 \le a_i \le 10^9\)

graph

给定一张 \(n\) 个点 \(m\) 条边的无向图，现在想要把这张图定向。

有 \(p\) 个限制条件，每个条件形如 \((x_i, y_i)\)，表示在新的有向图当中，\(x_i\) 要能够沿着一些边走到 \(y_i\)。

现在请你求出，每条边的方向是否能够唯一确定。同时请给出这些能够唯一确定的边的方向。

对于 \(30\%\) 的数据，\(n,m \le 1000, p \le 100\)

对于 \(60\%\) 的数据，\(p \le 100\)

对于 \(100\%\) 的数据，\(n,m,p \le 100000\)