由于作者太菜了，就只总结 T1 和 T4 吧 qwq

T1 机器人

分层图 + 最短路

solution

可以将点拆为 did_{i} 种状态，设 disu,pdis_{u , p} 表示通过第 pp 条道路到达 uu 节点时所需要的最小代价

注意这里 disdis 不能开静态数组，因为每个点最多有 kk 个状态，若开静态数组空间复杂度为 Θ(nk)\Theta(nk) 会爆。但是因为只有 mm 条边，所以状态数量之和为 2m2m，因此我们可以开 nn 个 map 表示 disdis 数组

初始化为 dis1,1=0dis_{1,1} = 0

转移容易推导，为：

$$dis_{u' , p'} = \min(dis_{u , p} + W(u , u') + f(p , p'))$$

其中 f(p,p′)f(p , p') 为机器人从参数 pp 调为参数 p′p' 所需要的代价，用前缀和即可 O(1)O(1) 处理

最后统计一下最小值即为节点答案

时间复杂度：O(nlog⁡n)O(n\log n)

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 3e5 + 5;
const ll inf = 1e18;

struct node{
	ll x , d , p;
	
	bool operator <(const node &lhs)const &{
		return d > lhs.d;
	}
};

struct edge{
	ll to , w;
};

int c , n , m , k;
ll v[N] , w[N] , sv[N] , sw[N];
unordered_map<int , ll> vis[N] , dis[N];
vector<edge> g[N];

ll solve(int l , int r){
	if(l <= r) return sv[r - 1] - sv[l - 1];
	else return sw[l] - sw[r];
}

void dijkstra(){
	priority_queue<node> q;
	q.push({1 , 0 , 1});
	dis[1][1] = 0;
	
	while(!q.empty()){
		node u = q.top(); q.pop();
		if(vis[u.x].count(u.p)) continue;
		vis[u.x][u.p] = 1;
		
		for(int i = 0 ; i < g[u.x].size() ; i ++){
			edge v = g[u.x][i];
			if(vis[v.to].count(i + 1)) continue;
			
			if(!dis[v.to].count(i + 1) || dis[v.to][i + 1] > u.d + v.w + solve(u.p , i + 1)){
				dis[v.to][i + 1] = u.d + v.w + solve(u.p , i + 1);
				q.push({v.to , dis[v.to][i + 1] , i + 1});
			}
		}
	}
}

int main(){
	cin >> c >> n >> m >> k;
	
	for(int i = 1 ; i < k ; i ++){
		cin >> v[i];
		sv[i] = sv[i - 1] + v[i];
	}
	for(int i = 2 ; i <= k ; i ++){
		cin >> w[i];
		sw[i] = sw[i - 1] + w[i];
	}
	
	for(int i = 1 ; i <= n ; i ++){
		int d;
		cin >> d;
		
		for(int j = 1 ; j <= d ; j ++){
			int y , z;
			cin >> y >> z;
			g[i].push_back({y , z});
		}
	}
	dijkstra();
	
	for(int i = 1 ; i <= n ; i ++){
		ll res = inf;
		for(auto v : dis[i]) res = min(res , v.second);
		
		cout << (res == inf ? -1 : res) << " ";
	}
	return 0;
}

T4 三目运算符

数学 + 线段树

solution

首先通过观察（玩样例）可知：

  • 如果 SS 中所有的 1 间隔的 0 的数量大于 11，则 SS 为 ff 的不动点，即 k=0k = 0
  • 如果存在 pp 使得 Sp...SnS_p ... S_n 全为 1，S1...SpS_1...S_p 满足上述条件，则 SS 为 ff 的不动点
  • 如果 SS 中所有的 1 间隔的 0 的数量大于 00。即没有连续的 1，则经过一次变换后 SS 为 ff 的不动点，即 k=1k = 1

我们还可以发现：若存在 110110 这样的子串，则它会在变换中一直向后面覆盖 1，即如下情况

$$\begin{split} &1100... \text{ ->} 1110... \\ &11010... \text{ ->} 11101... \end{split}$$

此时设 pp 为第 11 次 110110 出现的 00 的下标：S1...Sp−2S_1...S_{p-2} 根据性质一次就可以便为不动点，Sp...SnS_p ... S_n 中 00 要向后移动 n−p+1n - p + 1 次，即变换 n−p+1n-p+1 次后为不动点

所以可以得出 SS

  1. 存在 110110，则 k=n−p+1k = n - p + 1
  2. 不存在 110110，此时如果存在 101101 则 k=1k = 1 否则 k=0k = 0

因为这道题还需要修改，考虑用线段树解决，可以用线段树维护最早 110110 中 00 所在下标 pos，显然

posp=min⁡(poslp,posrp,pos′)pos_p = \min(pos_{lp} , pos_{rp} , pos')

其中 pos′pos' 为考虑 lplp 和 rprp 区间是否能拼出 110110，求 pos′pos' 可以用线段树维护区间前两个数和后面两个数，大力分讨即可。线段树还需维护 101101 存在性，方法和 110110 相同

对于修改，用懒标记处理，注意我们修改时不仅要将区间前两个数和后面两个数取反，还要处理 pospos。所以需要再维护 001001 的下标，修改时交换一下即可，处理 101101 同理

code

#include<bits/stdc++.h>
#define qwq ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int N = 4e5 + 5;
const int inf = 0x3f3f3f3f;

struct segmentTree{
	int s , t , ls0 , ls1 , rs0 , rs1 , b , p110 , p101 , p001 , p010;
}tr[N * 4];

long long c , t , n , q , ans;
string a;

void pushup(int p){
	int s = tr[p].s , t = tr[p].t , lp = p << 1 , rp = p << 1 | 1;
	tr[p].ls0 = tr[lp].ls0 , tr[p].rs0 = tr[rp].rs0;
	tr[p].p110 = min(tr[lp].p110 , tr[rp].p110) , tr[p].p101 = tr[lp].p101 | tr[rp].p101;
	tr[p].p001 = min(tr[lp].p001 , tr[rp].p001) , tr[p].p010 = tr[lp].p010 | tr[rp].p010;
	
	if(t - s + 1 == 2) tr[p].ls1 = tr[rp].rs0 , tr[p].rs1 = tr[lp].ls0;
	else if(t - s + 1 == 3){
		if(tr[lp].ls1 != -1) tr[p].ls1 = tr[lp].ls1 , tr[p].rs1 = tr[lp].ls1;
		else if(tr[rp].rs1 != -1) tr[p].ls1 = tr[rp].rs1 , tr[p].rs1 = tr[rp].rs1;
	}
	else tr[p].ls1 = tr[lp].ls1 , tr[p].rs1 = tr[rp].rs1;
	
	if(tr[lp].rs0 == 1 && tr[rp].ls0 == 1 && tr[rp].ls1 == 0) tr[p].p110 = min(tr[p].p110 , tr[rp].s + 1);
	else if(tr[lp].rs1 == 1 && tr[lp].rs0 == 1 && tr[rp].ls0 == 0) tr[p].p110 = min(tr[p].p110 , tr[rp].s);
	
	if(tr[lp].rs0 == 0 && tr[rp].ls0 == 0 && tr[rp].ls1 == 1) tr[p].p001 = min(tr[p].p001 , tr[rp].s + 1);
	else if(tr[lp].rs1 == 0 && tr[lp].rs0 == 0 && tr[rp].ls0 == 1) tr[p].p001 = min(tr[p].p001 , tr[rp].s);
	
	if(tr[lp].rs0 == 0 && tr[rp].ls0 == 1 && tr[rp].ls1 == 0) tr[p].p010 = 1;
	else if(tr[lp].rs1 == 0 && tr[lp].rs0 == 1 && tr[rp].ls0 == 0) tr[p].p010 = 1;
	
	if(tr[lp].rs0 == 1 && tr[rp].ls0 == 0 && tr[rp].ls1 == 1) tr[p].p101 = 1;
	else if(tr[lp].rs1 == 1 && tr[lp].rs0 == 0 && tr[rp].ls0 == 1) tr[p].p101 = 1;
}

void change(int p){
	tr[p].ls0 ^= 1 , tr[p].ls1 ^= 1 , tr[p].rs0 ^= 1 , tr[p].rs1 ^= 1 , tr[p].b ^= 1;
	swap(tr[p].p001 , tr[p].p110); swap(tr[p].p101 , tr[p].p010);
}

void pushdown(int p){
	if(tr[p].b){
		change(p << 1); change(p << 1 | 1);
		tr[p].b = 0;
	}
}

void build(int s , int t , int p){
	tr[p] = {s , t , -1 , -1 , -1 , -1 , 0 , inf , 0 , inf , 0};
	
	if(s == t){
		if(a[s] == '1') tr[p] = {s , t , 1 , -1 , 1 , -1 , 0 , inf , 0 , inf , 0};
		else tr[p] = {s , t , 0 , -1 , 0 , -1 , 0 , inf , 0 , inf , 0};
		return;
	}
	int m = (s + t) >> 1;
	build(s , m , p << 1);
	build(m + 1 , t , p << 1 | 1);
	pushup(p);
}

void modify(int l , int r , int p){
	int s = tr[p].s , t = tr[p].t , m = (s + t) >> 1;
	if(l <= s && t <= r){
		change(p);
		return;
	}
	pushdown(p);
	if(l <= m) modify(l , r , p << 1);
	if(r > m) modify(l , r , p << 1 | 1);
	pushup(p);
}

void solve(){
	cin >> n >> q >> a;
	
	a = " " + a;
	build(1 , n , 1);
	if(tr[1].p110 != inf) ans ^= ((n - tr[1].p110 + 1) * 1ll);
	else ans ^= (tr[1].p101);
	
	for(int i = 1 ; i <= q ; i ++){
		int l , r;
		
		cin >> l >> r;
		modify(l , r , 1);
		
		if(tr[1].p110 != inf) ans ^= ((n - tr[1].p110 + 1) * 1ll * (i + 1));
		else ans ^= (tr[1].p101 * 1ll * (i + 1));
	}
	cout << ans << '\n';
}

int main(){         qwq
	cin >> c >> t;
	
	while(t --){
		ans = 0;
		solve();
	}
	return 0;
}
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 38ms
  4. Powered by Hydro v5.0.0-beta.13 Community