The first character of $$$t_1$$$ isn't equal to the last character of $$$t_k$$$.

#include <cstdio>

const int maxn = 110;

int n;
char s[maxn];

void solve() {
	scanf("%d%s", &n, s + 1);
	puts(s[1] != s[n] ? "Yes" : "No");
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Try to rephrase the operations of both players.

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

const int maxn = 100100;

int n, a[maxn];

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	sort(a + 1, a + n + 1, greater<int>());
	printf("%d\n", a[(n + 1) / 2]);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

You should understand what is a good pair.

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 1000100;

int n;
pii a[99];
char s[maxn];

void solve() {
	scanf("%d%s", &n, s + 1);
	for (int i = 0; i < 26; ++i) {
		a[i] = mkp(0, i);
	}
	for (int i = 1; i <= n; ++i) {
		++a[s[i] - 'a'].fst;
	}
	sort(a, a + 26, greater<pii>());
	queue<pii> q;
	while (a[0].fst > a[1].fst) {
		putchar('a' + a[0].scd);
		--a[0].fst;
	}
	for (int i = 0; i < 26; ++i) {
		q.push(a[i]);
	}
	while (q.size()) {
		pii p = q.front();
		q.pop();
		if (!p.fst) {
			continue;
		}
		putchar('a' + p.scd);
		--p.fst;
		q.push(p);
	}
	putchar('\n');
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Choose the same integer twice.

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

ll n, m, a[maxn];
bool vis[maxn];

void solve() {
	scanf("%lld%lld", &n, &m);
	ll k = 0;
	while (n--) {
		int t;
		scanf("%d", &t);
		for (int i = 0; i <= t + 5; ++i) {
			vis[i] = 0;
		}
		for (int i = 1; i <= t; ++i) {
			scanf("%lld", &a[i]);
			if (a[i] <= t + 4) {
				vis[a[i]] = 1;
			}
		}
		ll mex = 0;
		while (vis[mex]) {
			++mex;
		}
		vis[mex] = 1;
		while (vis[mex]) {
			++mex;
		}
		k = max(k, mex);
	}
	printf("%lld\n", k >= m ? (m + 1) * k : k * k + (m + k) * (m - k + 1) / 2);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Construct a directed graph and rephrase the operation.

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

ll n, m, a[maxn], f[maxn];
pii b[maxn];
bool vis[maxn];
vector<int> G[maxn];

inline ll calc(ll l, ll r) {
	return (l + r) * (r - l + 1) / 2;
}

void solve() {
	scanf("%lld%lld", &n, &m);
	ll t = -1, ans = 0, k = 0;
	for (int i = 1, l; i <= n; ++i) {
		scanf("%d", &l);
		for (int j = 1; j <= l; ++j) {
			scanf("%lld", &a[j]);
			if (a[j] < maxn) {
				vis[a[j]] = 1;
			}
		}
		ll u = 0;
		while (vis[u]) {
			++u;
		}
		t = max(t, u);
		ll v = u;
		vis[u] = 1;
		while (vis[v]) {
			++v;
		}
		b[i] = mkp(u, v);
		k = max(k, v);
		vis[u] = 0;
		for (int j = 1; j <= l; ++j) {
			if (a[j] < maxn) {
				vis[a[j]] = 0;
			}
		}
	}
	for (int i = 0; i <= k; ++i) {
		vector<int>().swap(G[i]);
	}
	for (int i = 1; i <= n; ++i) {
		G[b[i].fst].pb(b[i].scd);
	}
	for (int u = k; ~u; --u) {
		f[u] = u;
		for (int v : G[u]) {
			f[u] = max(f[u], f[v]);
		}
		if ((int)G[u].size() >= 2) {
			t = max(t, f[u]);
		}
	}
	for (int i = 0; i <= min(k, m); ++i) {
		ans += max(t, f[i]);
	}
	if (k < m) {
		ans += calc(k + 1, m);
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Divide all numbers into small numbers and large numbers.

Use DP.

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 5050;

int n, m, f[maxn][maxn], a[maxn], b[maxn];

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n + 1; ++i) {
		for (int j = 0; j <= n + 1; ++j) {
			f[i][j] = -1e9;
		}
		a[i] = 0;
	}
	for (int i = 1, l, r; i <= m; ++i) {
		scanf("%d%d", &l, &r);
		a[l] = r;
	}
	f[0][0] = 0;
	for (int i = 1; i <= n; ++i) {
		if (a[i]) {
			int p = a[i];
			for (int j = 0; j < i; ++j) {
				for (int k = 1; k <= p - i; ++k) {
					f[p][j + k] = max(f[p][j + k], f[i - 1][j] + (p - i + 1 - k) * j);
				}
			}
			i = p;
		} else {
			for (int j = 0; j <= i; ++j) {
				f[i][j] = f[i - 1][j] + j;
				if (j) {
					f[i][j] = max(f[i][j], f[i - 1][j - 1]);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; ++i) {
		ans = max(ans, f[n][i] + i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
	}
	printf("%d\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Try to handle overlapping intervals.

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 5050;
const int inf = 0x3f3f3f3f;

int n, m, b[maxn], c[maxn], f[maxn][maxn];
struct node {
	int l, r;
} a[maxn];

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		c[i] = -1;
		b[i] = 0;
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &a[i].l, &a[i].r);
	}
	if (!m) {
		printf("%d\n", n * (n - 1) / 2);
		return;
	}
	sort(a + 1, a + m + 1, [&](const node &a, const node &b) {
		return a.l < b.l;
	});
	int mnl = a[1].l, mxl = a[1].l, mnr = a[1].r, mxr = a[1].r;
	for (int i = 2; i <= m + 1; ++i) {
		if (i == m + 1 || a[i].l > mxr) {
			if (mxl >= mnr) {
				puts("-1");
				return;
			}
			for (int j = mnl; j < mxl; ++j) {
				c[j] = 0;
			}
			for (int j = mnr + 1; j <= mxr; ++j) {
				c[j] = 1;
			}
			b[mxl] = mnr;
			mnl = mxl = a[i].l;
			mnr = mxr = a[i].r;
		} else {
			mnl = min(mnl, a[i].l);
			mxl = max(mxl, a[i].l);
			mnr = min(mnr, a[i].r);
			mxr = max(mxr, a[i].r);
		}
	}
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) {
			f[i][j] = -inf;
		}
	}
	f[0][0] = 0;
	for (int i = 1; i <= n; ++i) {
		if (b[i]) {
			int p = b[i];
			for (int j = 0; j < i; ++j) {
				for (int k = 1; k <= p - i; ++k) {
					f[p][j + k] = max(f[p][j + k], f[i - 1][j] + (p - i + 1 - k) * j);
				}
			}
			i = p;
		} else if (c[i] == 1) {
			for (int j = 1; j <= i; ++j) {
				f[i][j] = f[i - 1][j - 1];
			}
		} else if (c[i] == 0) {
			for (int j = 0; j < i; ++j) {
				f[i][j] = f[i - 1][j] + j;
			}
		} else {
			for (int j = 0; j <= i; ++j) {
				f[i][j] = max(f[i - 1][j] + j, j ? f[i - 1][j - 1] : -inf);
			}
		}
	}
	int ans = -1;
	for (int i = 0; i <= n; ++i) {
		ans = max(ans, f[n][i] + i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
	}
	printf("%d\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

There exists a $$$O(n + m)$$$ solution to this problem.

What will you do if the number of possible values for $$$b_i$$$ is small?

Try some randomized algorithms, like color-coding.

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 3030;

int n, m, a[maxn], b[maxn], c[maxn], d[maxn], e[maxn];

struct BIT {
	int c[maxn];
	
	inline void init() {
		mems(c, -0x3f);
	}
	
	inline void update(int x, int d) {
		for (int i = x; i <= n; i += (i & (-i))) {
			c[i] = max(c[i], d);
		}
	}
	
	inline int query(int x) {
		int res = -1e9;
		for (int i = x; i; i -= (i & (-i))) {
			res = max(res, c[i]);
		}
		return res;
	}
} T[32];

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &b[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &c[i]);
	}
	mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
	int ans = 0;
	for (int _ = 0; _ < 300; ++_) {
		for (int i = 1; i <= n; ++i) {
			d[i] = rnd() % m;
		}
		for (int i = 1; i <= n; ++i) {
			e[i] = d[b[i]];
		}
		for (int i = 0; i < (1 << m); ++i) {
			T[i].init();
		}
		T[0].update(1, 0);
		for (int i = 1; i <= n; ++i) {
			for (int S = 0; S < (1 << m); ++S) {
				if (S & (1 << e[i])) {
					continue;
				}
				T[S | (1 << e[i])].update(a[i], T[S].query(a[i]) + c[i]);
			}
		}
		ans = max(ans, T[(1 << m) - 1].query(n));
	}
	printf("%d\n", ans > 0 ? ans : -1);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}