T1 词典

贪心 + 字符串

solution

没什么好讲的。。。

code

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

const int N = 3e3 + 5;

int n , to[100] , m;
string s[N];
char mx[N][N] , mi[N][N];

bool cmp(char a[] , char b[]){
	for(int i = 1 ; i <= m ; i ++){
		if(a[i] > b[i]) return true;
		if(a[i] < b[i]) return false;
	}
	return false;
}

bool check(int x){
	for(int i = 1 ; i <= n ; i ++){
		if(i == x) continue;
		
		if(cmp(mi[x] , mx[i])) return false;
	}
	return true;
}

int main(){            qwq
	cin >> n >> m;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> s[i];
		
		memset(to , 0 , sizeof to);
		for(int j = 0 ; j < m ; j ++){
			to[s[i][j] - 'a'] ++;
		}
		int idx = 0;
		for(int j = 25 ; j >= 0 ; j --){
			for(int k = 1 ; k <= to[j] ; k ++){
				mx[i][++ idx] = j + 'a';
			}
		}
		idx = 0;
		for(int j = 0 ; j <= 25 ; j ++){
			for(int k = 1 ; k <= to[j] ; k ++){
				mi[i][++ idx] = j + 'a';
			}
		}
	}
	
	for(int i = 1 ; i <= n ; i ++){
		if(check(i)) cout << '1';
		else cout << '0';
	}
	return 0;
}

T2 三值逻辑

并查集 + 基环树

solution

鸽。。。

code

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

const int N = 3e5 + 5;
const int T = 1e5 + 1;
const int F = -1e5 - 1;
const int U = 0;

int c , t , n , m , ans;
int fa[N] , vis[N];

int find(int x){
	int tmp = 0;
	
	if(x == T || x == F) tmp = x;
	else if(x == U || vis[n - x]) tmp = U;
	else if(vis[n + x]) tmp = T;
	else if(x > 0){
		if(x == fa[x]) tmp = x;
		else{
			vis[n + x] = 1;
			tmp = fa[x] = find(fa[x]);
			vis[n + x] = 0;
		}
	}
	else{
		if(x == -fa[-x]) tmp = x;
		else{
			vis[n + x] = 1;
			tmp = fa[x] = find(-fa[-x]);
			vis[n + x] = 0;
		}
	}
	return tmp;
}

void solve(){
	cin >> n >> m;
	
	for(int i = 1 ; i <= n ; i ++){
		fa[i] = i;
	}
	for(int i = 1 ; i <= m ; i ++){
		char op;
		int x , y;
		
		cin >> op;
		
		if(op == 'T'){
			cin >> x;
			fa[x] = T;
		}
		else if(op == 'F'){
			cin >> x;
			fa[x] = F;
		}
		else if(op == 'U'){
			cin >> x;
			fa[x] = U;
		}
		else if(op == '+'){
			cin >> x >> y;
			fa[x] = fa[y];
		}
		else{
			cin >> x >> y;
			fa[x] = -fa[y];
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		if(find(i) == U) ans ++;
	}
	cout << ans << '\n';
}

int main(){             qwq
	cin >> c >> t;
	
	while(t --){
		ans = 0;
		solve();
	}
	return 0;
}

T3 双序列拓展

dp + 贪心 + Ad-hoc

solution

鸽。。。

code

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

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

struct node{
	int id , w;
}tmpa[N] , tmpb[N];

int c , q , n , m , idx , id_pa , id_qa , id_pb , id_qb , w_pa , w_qa , w_pb , w_qb;   // p : max , q : min
int a[N] , b[N] , mxa[N] , mia[N] , rmxa[N] , rmia[N] , mxb[N] , mib[N] , rmxb[N] , rmib[N];
char ans[N];

void solve(){
	w_pa = 0 , w_qa = inf , w_pb = 0 , w_qb = inf;
	
	for(int i = 1 ; i <= n ; i ++){
		mxa[i] = max(mxa[i - 1] , a[i]);
		mia[i] = min(mia[i - 1] , a[i]);
		if(w_pa < a[i]) w_pa = a[i] , id_pa = i;
		if(w_qa > a[i]) w_qa = a[i] , id_qa = i;
	}
	for(int i = 1 ; i <= m ; i ++){
		mxb[i] = max(mxb[i - 1] , b[i]);
		mib[i] = min(mib[i - 1] , b[i]);
		if(w_pb < b[i]) w_pb = b[i] , id_pb = i;
		if(w_qb > b[i]) w_qb = b[i] , id_qb = i;
	}
	for(int i = n ; i >= 1 ; i --){
		rmxa[i] = max(rmxa[i + 1] , a[i]);
		rmia[i] = min(rmia[i + 1] , a[i]);
	}
	for(int i = m ; i >= 1 ; i --){
		rmxb[i] = max(rmxb[i + 1] , b[i]);
		rmib[i] = min(rmib[i + 1] , b[i]);
	}
	
	if(a[1] < b[1]){
		// (1 , 1) -> (id_qa , id_pb)   can arrive?
		
		if(w_qa > w_qb || w_pa > w_pb){
			ans[++ idx] = '0'; return;
		}
		int lt = 2 , flag = 1;
		for(int i = 2 ; i < id_qa ; i ++){
			for(int j = lt ; j < id_pb ; j ++){
				if(a[i] < mxb[j]){
					lt = max(j - 1 , lt); break;
				}
				if(b[j] <= mia[i - 1]){
					flag = 0; break;
				}
				else if(b[j + 1] <= mia[i]){
					flag = 0; break;
				}
			}
		}
		// (id_qa , id_pb) -> (n , m) can arrive?
		lt = m;
		for(int i = n ; i >= id_qa ; i --){
			for(int j = lt ; j >= id_pb ; j --){
				if(a[i] < rmxb[j]){
					lt = min(j + 1 , lt); break;
				}
				if(b[j] <= rmia[i + 1]){
					flag = 0; break;
				}
				else if(b[j - 1] <= rmia[i]){
					flag = 0; break;
				}
			}
		}
		if(!flag){
			ans[++ idx] = '0'; return;
		}
		ans[++ idx] = '1';
	}
	// ----- ------------- - - - -----------
	if(a[1] > b[1]){
		// (1 , 1) -> (id_pa , id_qb)   can arrive?
		
		if(w_pa < w_pb || w_qa < w_qb){
			ans[++ idx] = '0'; return;
		}
		int lt = 2 , flag = 1;
		for(int i = 2 ; i < id_pa ; i ++){
			for(int j = lt ; j < id_qb ; j ++){
				if(a[i] > mib[j]){
					lt = max(j - 1 , lt); break;
				}
				if(b[j] >= mxa[i - 1]){
					flag = 0; break;
				}
				else if(b[j + 1] >= mxa[i]){
					flag = 0; break;
				}
			}
		}
		// (id_pa , id_qb) -> (n , m) can arrive?
		lt = m;
		for(int i = n ; i >= id_pa ; i --){
			for(int j = lt ; j >= id_qb ; j --){
				if(a[i] > rmib[j]){
					lt = min(j + 1 , lt); break;
				}
				if(b[j] >= rmxa[i + 1]){
					flag = 0; break;
				}
				else if(b[j - 1] >= rmxa[i]){
					flag = 0; break;
				}
			}
		}
		if(!flag){
			ans[++ idx] = '0'; return;
		}
		ans[++ idx] = '1';
	}
	if(a[1] == b[1]) ans[++ idx] = '0';
}

int main(){                qwq
	cin >> c >> n >> m >> q;
	
	mia[0] = inf , rmia[n + 1] = inf , mib[0] = inf , rmib[m + 1] = inf;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	for(int i = 1 ; i <= m ; i ++){
		cin >> b[i];
	}
	solve();
	
	while(q --){
		int kx , ky , x;
		cin >> kx >> ky;
		
		for(int i = 1 ; i <= kx ; i ++){
			cin >> tmpa[i].id >> x;
			tmpa[i].w = a[tmpa[i].id];
			a[tmpa[i].id] = x;
		}
		for(int i = 1 ; i <= ky ; i ++){
			cin >> tmpb[i].id >> x;
			tmpb[i].w = b[tmpb[i].id];
			b[tmpb[i].id] = x;
		}
		solve();
		for(int i = 1 ; i <= kx ; i ++) a[tmpa[i].id] = tmpa[i].w;
		for(int i = 1 ; i <= ky ; i ++) b[tmpb[i].id] = tmpb[i].w;
	}
	for(int i = 1 ; i <= idx ; i ++) cout << ans[i];
	return 0;
}

T4 天天爱打卡

dp + 线段树 + 离散化

solution

code

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

inline int read(){
	int s = 0 , w = 1;
	char c = getchar();
	
	if(c == '-') w = -1 , c = getchar();
	while(c >= 48 && c <= 57){
		s = (s << 1) + (s << 3) + c - '0';
		c = getchar();
	}
	return s * w;
}

const int N = 2e5 + 20;

struct node{
	int l , r , v;
}q[N];

struct val{
	int l , w;
};

struct segmentTree{
	ll s , t , w , b;
}tr[N << 2];

int c , t , n , m , k , d , idx;
ll dp[N] , X[N];
vector<val> v[N];

inline void pushup(int p){
	tr[p].w = max(tr[p << 1].w , tr[p << 1 | 1].w);
}

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

inline void build(int l , int r , int p){
	tr[p] = {l , r , 0 , 0};
	if(l == r) return;
	
	int mid = (l + r) >> 1;
	build(l , mid , p << 1);
	build(mid + 1 , r , p << 1 | 1);
}

inline void modify(int l , int r , ll k , int p){
	int s = tr[p].s , t = tr[p].t , mid = (s + t) >> 1;
	if(l <= s && t <= r){
		tr[p].w += k , tr[p].b += k;
		return;
	}
	pushdown(p);
	if(l <= mid) modify(l , r , k , p << 1);
	if(r > mid) modify(l , r , k , p << 1 | 1);
	pushup(p);
}

inline ll query(int l , int r , int p){
	int s = tr[p].s , t = tr[p].t , mid = (s + t) >> 1;
	if(l <= s && t <= r){
		return tr[p].w;
	}
	ll res = 0;
	pushdown(p);
	if(l <= mid) res = query(l , r , p << 1);
	if(r > mid) res = max(res , query(l , r , p << 1 | 1));
	return res;
}

inline void solve(){
	n = read() , m = read() , k = read() , d = read();
	
	for(int i = 1 ; i <= m ; ++ i){
		int x = read() , y = read() , v = read();
		
		q[i] = {x - y , x , v};
		X[++ idx] = x - y , X[++ idx] = x;
	}
	sort(X + 1 , X + idx + 1);
	idx = unique(X + 1 , X + idx + 1) - (X + 1);
	
	for(int i = 1 ; i <= m ; ++ i){
		int l = lower_bound(X + 1 , X + idx + 1 , q[i].l) - X;
		int r = lower_bound(X + 1 , X + idx + 1 , q[i].r) - X;
		
		v[r].push_back({l , q[i].v});
	}
	build(0 , idx , 1);
	
	for(int i = 1 ; i <= idx ; ++ i){
		modify(0 , i - 1 , -(X[i] - X[i - 1]) * d , 1);
		for(auto u : v[i]){
			modify(0 , u.l , u.w , 1);
		}
		int pl = lower_bound(X + 1 , X + idx + 1 , X[i] - k) - X;
		dp[i] = max(dp[i - 1] , query(pl , i - 1 , 1));
		if(i < idx) modify(i + 1 , i + 1 , dp[i] , 1);
		
		v[i].clear();
	}
	cout << dp[idx] << '\n';
}

int main(){
	c = read() , t = read();
	
	while(t --){
		idx = 0;
		solve();
	}
	return 0;
}