2022.11.28 - 12.4 训练小记

UVA12620 Fibonacci Sum

斐波那契数列在取模意义下是有循环节的（具体计算以后补），一个结论是在模 \(p\) 的意义下，循环节的大小不会大于 \(6p\)。因此直接 \(\mathcal{O}(n^2)\) 判断或打表即可。对于该题结论为每 \(300\) 项为一循环节。

\(\texttt{Main Code}\)

inline void query(i64 l, i64 r){
	i64 n = r / 300 - (l + 299) / 300;
	i64 ans = n * s[300];
	ans += s[300] - s[(l - 1) % 300];
	ans += s[((r - 1) % 300 + 1) % 300];
	cout << ans << '\n';
}

CF1099 C. Postcard

分字符串中有无 * 贪心就可以了。略考验码力。

\(\texttt{Main Code}\)

void solve(){
	string s; int k; cin >> s >> k;
	int cnt = 0, cnt2 = 0, cnt3 = 0;
	for(int i = 0; i < s.length(); ++i){
		if(s[i] == '*') ++cnt3;
		else if(s[i] == '?') ++cnt2;
		else ++cnt;
	}
	if(!cnt3 && cnt < k){
		cout << "Impossible\n";
		return;
	}
	if(cnt - cnt2 - cnt3 > k){
		cout << "Impossible\n";
		return;
	}
	string ans;
	if(cnt3){
		bool ok = 1;
		int add = k - (cnt - cnt2 - cnt3);
		for(int i = 0; i < s.length(); ++i){
			if(i == s.length() - 1){
				ans += s[i];
				break;
			}
			if(s[i + 1] == '?') {++i; continue;}
			if(s[i + 1] == '*'){
				if(ok) ans.append(add, s[i]), ok = 0;
				++i; continue;
			}
			ans += s[i];
		}
	}else{
		int cur = cnt - cnt2;
		for(int i = 0; i < s.length(); ++i){
			if(i == s.length() - 1){
				ans += s[i];
				break;
			}
			if(s[i + 1] == '?'){
				if(cur < k) ans += s[i], ++cur;
				++i; continue;
			}
			ans += s[i];
		}
	}
	cout << ans << '\n';
}

P4366 [Code+#4]最短路

有一定思维的图论题。

直接加边作完全图一定会炸，考虑怎么将路径转化为等价的路径。注意到题目中从点 \(i\) 到点 \(j\) 的路径权值为 \((i~\mathrm{xor}~j) \times C\)，可以证明若不考虑题目中新增的边，则从点 \(i\) 到点 \(j\) 的最短路径长即为 \((i~\mathrm{xor}~j) \times C\)，因为所有 \(i~\mathrm{xor}~j\) 上为 \(1\) 的位都必定对答案有贡献。

由此，我们可以拆位考虑，对所有 \(i~\mathrm{xor}~j\) 上为 \(1\) 的位分别处理。记 \(cur\) 为目前到达的位置（初始 \(cur \gets i\)），欲使 \(cur\) 跳到点 \(j\)，若 \((i~\mathrm{xor}~j)\) 的第 \(k\) 位 (0-indexed) 为 \(1\)，则令 \(cur \gets cur~\mathrm{xor}~2^k\)。这个过程显然可以实现 \(i \to j\)，且其耗费和同样为 \((i~\mathrm{xor}~j) \times C\)。

这启示我们对于每一个点 \(i\)，只需连 \(i \to (i~\mathrm{xor}~2^k)\) 的有向边即可覆盖所有情况。此时路径的权值显然是 \(2^k \times C\)。

这样的边数是 \(\mathcal{O}(m + n \log n)\) 的，需要使用线段树优化 \(dijkstra\) 或者直接开 O2。

\(\texttt{Main Code}\)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 3e6 + 10;
struct edge{
	int v, nxt, w;
}e[M];
int head[N], tot;
inline void add(int u, int v, int w){
	e[++tot].nxt = head[u];
	head[u] = tot;
	e[tot].v = v;
	e[tot].w = w;
}
struct node{
	int val, u;
	bool operator < (const node &x) const {return val > x.val;}
};
priority_queue<node> pq;
bool vis[N];
int dis[N];
void dijkstra(int s){
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	pq.push((node){0, s});
	while(!pq.empty()){
		int u = pq.top().u; pq.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = head[u]; i; i = e[i].nxt){
			if(dis[e[i].v] > dis[u] + e[i].w){
				dis[e[i].v] = dis[u] + e[i].w;
				pq.push((node){dis[e[i].v], e[i].v});
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int n, m, C; cin >> n >> m >> C;
	int u, v, w;
	for(int i = 1; i <= m; ++i){
		cin >> u >> v >> w;
		add(u, v, w);
	}
	int to;
	for(int i = 0; i <= n; ++i){
		for(int j = 0; j <= 20; ++j){
			to = i ^ (1 << j);
			if(to <= n) add(i, i ^ (1 << j), (1 << j) * C);
		}
	}
	cin >> u >> v;
	dijkstra(u);
	cout << dis[v];
}