2026夏组队训练赛第六场
A. Live Love
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
cout << m << ' ';
if (m == 0) cout << "0\n";
else {
for (int i = 1; i <= m; ++i) {
if (m % i == 0) {
if (m / i * (i + 1) - 1 <= n) {
cout << i << '\n';
break;
}
}
else {
if (m / i * (i + 1) + m % i <= n) {
cout << i << '\n';
break;
}
}
}
}
}
return 0;
}B. Red Black Tree II
cpp
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define vvpi vector<vector<pair<int, int>>>
using namespace std;
const int N = 100010;
struct VirtualTree {
using pii = pair<int, int>;
int n, lg = 1, tim = 0;
const vvpi &g;
vector<int> up;
vector<int> dep, tin, tout;
vector<int> dis;
vector<vector<pii>> vt;
vector<int> nodes;
vector<int> stk;
vector<int> buf;
VirtualTree(const vvpi &g, int root = 1)
: n((int)g.size() - 1),
g(g),
dep(n + 1),
tin(n + 1),
tout(n + 1),
dis(n + 1),
vt(n + 1) {
while ((1LL << lg) <= n)
++lg;
up.resize((int)(n + 1) * lg);
nodes.reserve(64);
stk.reserve(64);
buf.reserve(64);
init(root);
}
inline int &U(int u, int j) {
return up[(int)u * lg + j];
}
inline int U(int u, int j) const {
return up[(int)u * lg + j];
}
void init(int root) {
vector<int> par(n + 1);
vector<int> st;
st.reserve(n * 2);
par[root] = root;
st.push_back(root);
while (!st.empty()) {
int x = st.back();
st.pop_back();
if (x < 0) {
int u = -x;
tout[u] = tim;
continue;
}
int u = x;
tin[u] = ++tim;
U(u, 0) = par[u];
for (int j = 1; j < lg; ++j)
U(u, j) = U(U(u, j - 1), j - 1);
st.push_back(-u);
for (auto it = g[u].rbegin(); it != g[u].rend(); ++it) {
int w = (int)it->first;
int v = (int)it->second;
if (v == par[u])
continue;
par[v] = u;
dep[v] = dep[u] + 1;
dis[v] = dis[u] + w;
st.push_back(v);
}
}
}
inline bool ancestor(int u, int v) const {
return tin[u] <= tin[v] && tin[v] <= tout[u];
}
inline int lca(int u, int v) const {
if (ancestor(u, v))
return u;
if (ancestor(v, u))
return v;
for (int j = lg - 1; j >= 0; --j) {
int p = U(u, j);
if (!ancestor(p, v))
u = p;
}
return U(u, 0);
}
inline int dist(int u, int v) const {
int p = lca(u, v);
return dis[u] + dis[v] - 2 * dis[p];
}
inline void link(int u, int v) {
vt[u].emplace_back(dis[v] - dis[u], v);
}
template <class Vec>
int build(const Vec &key) {
for (int u : nodes)
vt[u].clear();
nodes.clear();
stk.clear();
buf.clear();
if (key.empty())
return 0;
int k = key.size();
if (buf.capacity() < k)
buf.reserve(k);
if (nodes.capacity() < k * 2)
nodes.reserve(k * 2);
if (stk.capacity() < k * 2)
stk.reserve(k * 2);
for (auto u : key)
buf.push_back((int)u);
sort(buf.begin(), buf.end(), [&](int u, int v) {
return tin[u] < tin[v];
});
buf.erase(unique(buf.begin(), buf.end()), buf.end());
stk.push_back(buf[0]);
nodes.push_back(buf[0]);
for (int i = 1; i < buf.size(); ++i) {
int u = buf[i];
int p = lca(u, stk.back());
while (stk.size() >= 2 &&
dep[stk[stk.size() - 2]] >= dep[p]) {
link(stk[stk.size() - 2], stk.back());
stk.pop_back();
}
if (stk.back() != p) {
link(p, stk.back());
stk.pop_back();
stk.push_back(p);
nodes.push_back(p);
}
stk.push_back(u);
nodes.push_back(u);
}
while (stk.size() > 1) {
link(stk[stk.size() - 2], stk.back());
stk.pop_back();
}
return stk[0];
}
};
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, m, q;
cin >> n >> m >> q;
vi r(n + 1), fir(n + 1), flg(n + 1);
vvi f(n + 1, vi(4, 0));
vvpi adj(n + 1);
for (int i = 1; i <= m; ++i) {
int t;
cin >> t;
r[t] = true;
}
for (int i = 1; i < n; ++i) {
int x, y, z;
cin >> x >> y >> z;
adj[x].emplace_back(z, y);
adj[y].emplace_back(z, x);
}
VirtualTree vt(adj);
auto dfs = [&](auto &&self, int x, int fa, int tp) -> void {
if (r[x])
tp = x;
fir[x] = tp;
for (auto &[_, y] : adj[x]) {
if (y == fa)
continue;
self(self, y, x, tp);
}
};
dfs(dfs, 1, 0, 1);
auto dp = [&](auto &&self, int x) -> void {
int cst = vt.dis[x] - vt.dis[fir[x]];
int ow = flg[x] ? cst : 0;
int mx1 = 0, mx2 = 0, id = -1;
f[x][2] = ow;
f[x][3] = 0;
for (auto &[w, y] : vt.vt[x]) {
self(self, y);
if (f[y][0] > mx1) {
mx2 = mx1;
mx1 = f[y][0];
id = y;
} else if (f[y][0] > mx2) {
mx2 = f[y][0];
}
if (fir[y] == fir[x]) {
f[x][2] = max(f[x][2], f[y][2]);
f[x][3] = max(f[x][3], f[y][3]);
} else {
f[x][3] = max(f[x][3], f[y][0]);
}
}
f[x][0] = max(f[x][2], f[x][3]);
if (r[x]) {
f[x][1] = f[x][0];
} else {
f[x][1] = max(f[x][3], max(0LL, f[x][2] - cst));
}
for (auto &[w, y] : vt.vt[x]) {
int other = (y == id ? mx2 : mx1);
f[x][1] = min(f[x][1], max({ow, other, f[y][1]}));
}
};
while (q--) {
int k;
cin >> k;
vi key(k);
for (auto &x : key)
cin >> x;
for (int i = 0; i < k; ++i) {
flg[key[i]] = 1;
if (!r[key[i]])
key.emplace_back(fir[key[i]]);
}
int rt = vt.build(key);
for (auto &x : vt.nodes)
fill(f[x].begin(), f[x].end(), 0);
dp(dp, rt);
cout << f[rt][1] << '\n';
for (int i = 0; i < k; ++i)
flg[key[i]] = 0;
}
}
return 0;
}C. Halting Problem
cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
string op[N];
unsigned char a[N];
int b[N];
bool vis[N][256];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> op[i];
int t;
cin >> t;
a[i] = t;
if (op[i] != "add") cin >> b[i];
}
fill(vis[0], vis[0] + 256 * (n + 2), 0);
bool f = false;
vis[1][0] = true;
int x = 1;
unsigned char r = 0;
while (true) {
if (x == n + 1) {
f = true;
break;
}
if (op[x] == "add") {
r += a[x];
x++;
} else if (op[x] == "beq") {
if (r == a[x]) x = b[x];
else x++;
} else if (op[x] == "bne") {
if (r != a[x]) x = b[x];
else x++;
} else if (op[x] == "blt") {
if (r < a[x]) x = b[x];
else x++;
} else if (op[x] == "bgt") {
if (r > a[x]) x = b[x];
else x++;
} else exit(123);
if (vis[x][r]) break;
vis[x][r] = true;
}
if (f) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}D. Pixel Art
cpp
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';
struct Segment {
struct Node {
int ls, rs, h, d;
bool tag;
};
vector<Node> tr;
Segment(int _n) {
tr.reserve(3000000);
tr.push_back({});
tr.push_back({0, 0, 0, 0, 1});
}
int newnode(int h = 0, int d = 0) {
tr.push_back({0, 0, h, d, 1});
return tr.size() - 1;
}
void apply(int p, int H, int D) {
tr[p].h = H;
tr[p].d = D;
tr[p].tag = 1;
}
void push(int p) {
if (!tr[p].tag) return;
if (!tr[p].ls) tr[p].ls = newnode(tr[p].h, tr[p].d);
else apply(tr[p].ls, tr[p].h, tr[p].d);
if (!tr[p].rs) tr[p].rs = newnode(tr[p].h, tr[p].d);
else apply(tr[p].rs, tr[p].h, tr[p].d);
tr[p].tag = 0;
}
void update(int p, int l, int r, int ql, int qr, int H, int D) {
if (ql <= l && r <= qr) {
apply(p, H, D);
return;
}
push(p);
int mid = (l + r) >> 1;
if (ql <= mid) {
if (!tr[p].ls) tr[p].ls = newnode();
update(tr[p].ls, l, mid, ql, qr, H, D);
}
if (qr > mid) {
if (!tr[p].rs) tr[p].rs = newnode();
update(tr[p].rs, mid + 1, r, ql, qr, H, D);
}
}
pair<int, int> query(int p, int l, int r, int x) {
if (tr[p].tag || l == r) return {tr[p].h, tr[p].d};
int mid = (l + r) >> 1;
if (x <= mid) {
if (!tr[p].ls) return {0, 0};
return query(tr[p].ls, l, mid, x);
} else {
if (!tr[p].rs) return {0, 0};
return query(tr[p].rs, mid + 1, r, x);
}
}
};
struct DSU {
int n, kind;
vector<int> fa, sz;
DSU(int _n) : n(_n), kind(_n) {
fa.assign(n + 1, 0);
sz.assign(n + 1, 1);
iota(fa.begin(), fa.end(), 0);
}
int find(int x) {
return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
if (x == 0 || y == 0) return 0;
x = find(x), y = find(y);
if (x == y) return 0;
if (sz[x] > sz[y]) swap(x, y);
fa[x] = y;
sz[y] += sz[x];
kind --;
return 1;
}
};
void solve() {
int n, m, k;
cin >> n >> m >> k;
DSU dsu(k);
Segment seg(m);
vector<ll> cnt(n + 2);
vector<int> ans(n + 1);
vector<vector<tuple<int, int, int>>> row(n + 1);
vector<vector<tuple<int, int, int>>> b(n + 1);
vector<vector<pair<int, int>>> down(n + 1);
for (int i = 1; i <= k; i ++) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
if (r1 == r2) {
row[r1].push_back({i, c1, c2});
} else {
b[r1].push_back({i, c1, r2});
down[r2].push_back({i, c1});
}
}
ll tmp = 0;
auto add_col = [&](int id, int col, int l, int r) -> void {
cnt[l] ++;
cnt[r + 1] --;
tmp ++;
auto [H, pid] = seg.query(1, 1, m, col);
if (H == l - 1) {
if (dsu.merge(id, pid)) tmp --;
}
if (col > 1) {
auto [H, pid] = seg.query(1, 1, m, col - 1);
if (H >= l) {
if (dsu.merge(id, pid)) tmp --;
}
}
if (col < m) {
auto [H, pid] = seg.query(1, 1, m, col + 1);
if (H >= l) {
if (dsu.merge(id, pid)) tmp --;
}
}
seg.update(1, 1, m, col, col, r, id);
};
auto add_row = [&](int Row) -> void {
for (auto [id, l, r] : row[Row]) {
auto [hl, dl] = seg.query(1, 1, m, l);
if (hl == Row - 1) {
if (dsu.merge(id, dl)) tmp --;
}
auto [hr, dr] = seg.query(1, 1, m, r);
if (hr == Row - 1) {
if (dsu.merge(id, dr)) tmp --;
}
if (l > 1) {
auto [H, pid] = seg.query(1, 1, m, l - 1);
if (H >= Row) {
if (dsu.merge(id, pid)) tmp --;
}
}
if (r < m) {
auto [H, pid] = seg.query(1, 1, m, r + 1);
if (H >= Row) {
if (dsu.merge(id, pid)) tmp --;
}
}
cnt[Row] += r - l + 1;
cnt[Row + 1] -= r - l + 1;
tmp ++;
seg.update(1, 1, m, l, r, Row, id);
}
if (Row == 1) return;
for (auto [id, col] : down[Row - 1]) {
auto [H, pid] = seg.query(1, 1, m, col);
if (H >= Row) {
if (dsu.merge(id, pid)) tmp --;
}
}
for (auto [id, l, r] : row[Row - 1]) {
auto [hl, dl] = seg.query(1, 1, m, l);
if (hl >= Row) {
if (dsu.merge(id, dl)) tmp --;
}
auto [hr, dr] = seg.query(1, 1, m, r);
if (hr >= Row) {
if (dsu.merge(id, dr)) tmp --;
}
}
};
for (int i = 1; i <= n; i ++) {
for (auto [id, col, r] : b[i]) {
add_col(id, col, i, r);
}
add_row(i);
ans[i] = tmp;
}
ll now = 0, sum = 0;
for (int i = 1; i <= n; i ++) {
now += cnt[i];
sum += now;
cout << sum << ' ' << ans[i] << '\n';
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t --) solve();
}F. Chaleur
cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <complex>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
void pr(vector<int> a) {
for (auto i : a)
cout << i << ' ';
cout << '\n';
}
const int mod = 998244353;
const int INF = 1e18;
const int N = 5e5 + 5;
void init() {
}
void solve() {
int n,m;
cin>>n>>m;
vvi g(n+1);
vi deg(n+1);
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
deg[u]++;
deg[v]++;
g[u].pb(v);
g[v].pb(u);
}
vi b(n);
iota(all(b),1ll);
sort(all(b),[&](int a,int b){
return deg[a]>deg[b];
});
int cur=-1,sum=0;
for(int i=0;i<n;i++){
sum+=deg[b[i]];
// cout<<sum<<endl;
if(sum==(i+1)*(i)/2+m){
cur=i;
}
}
if(cur==-1){
cout<<0<<" "<<0<<endl;
return;
}
int ans1=1;
for(int i=cur+1;i<n;i++){
if(deg[b[i]]==cur)ans1++;
}
int tmp=cur;
cur=-1,sum=0;
for(int i=0;i<n;i++){
sum+=deg[b[i]];
if(sum==(i+1)*(i)/2+m){
cur=i;
break;
}
}
if(cur==-1){
cout<<0<<" "<<0<<endl;
return;
}
int ans2=1;
for(int i=0;i<=cur;i++){
if(deg[b[i]]<=cur+1)ans2++;
}
if(tmp == 0)ans2=1;
cout<<ans1<<" "<<ans2<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}G. Couleur
cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
const int N = 100010;
struct Node {
int val, ls, rs;
} tr[N * 20];
int a[N], rt[N], tot;
LL b[N];
void modify(int &u, int v, int l, int r, int p, int t) {
u = ++tot;
tr[u] = tr[v];
if (l == r) tr[u].val += t;
else {
int mid = l + r >> 1;
if (p <= mid) modify(tr[u].ls, tr[v].ls, l, mid, p, t);
else modify(tr[u].rs, tr[v].rs, mid + 1, r, p, t);
tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
}
}
int query(int u, int v, int l, int r, int ql, int qr) {
if (!u && !v) return 0;
else if (ql <= l && r <= qr) return tr[u].val - tr[v].val;
else {
int mid = l + r >> 1, res = 0;
if (ql <= mid) res = query(tr[u].ls, tr[v].ls, l, mid, ql, qr);
if (qr > mid) res += query(tr[u].rs, tr[v].rs, mid + 1, r, ql, qr);
return res;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
tot = 0;
fill(rt, rt + n + 1, 0);
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i];
for (int i = 1; i <= n; ++i) {
modify(rt[i], rt[i - 1], 1, n, a[i], 1);
}
auto qcnt = [&](int l, int r, int ql, int qr) -> int {
if (l > r || ql > qr) return 0;
return query(rt[r], rt[l - 1], 1, n, ql, qr);
};
LL res = 0;
for (int i = 2; i <= n; ++i) {
res += qcnt(1, i - 1, a[i] + 1, n);
}
cout << res;
map<pair<int, int>, LL> sep = {{{1, n}, res}};
multiset<LL> s = {res};
for (int i = 1; i < n; ++i) {
b[i] ^= res;
auto it = sep.upper_bound({b[i], n + 1});
if (it == sep.begin()) {
cout << ' ' << res;
continue;
}
it--;
auto [p, v] = *it;
auto [l, r] = p;
// cout << l << ' ' << r << ' ' << v << '\n';
if (b[i] < l || b[i] > r) {
// for (int x : s) cout << x << ' ';
// cout << '\n';
cout << ' ' << res;
continue;
}
s.erase(s.find(v));
sep.erase(it);
if (b[i] - l < r - b[i]) {
LL rv = v;
v = 0;
rv -= qcnt(b[i] + 1, r, 1, a[b[i]] - 1);
for (int j = l; j <= b[i] - 1; ++j) {
rv -= qcnt(j + 1, r, 1, a[j] - 1);
v += qcnt(j + 1, b[i] - 1, 1, a[j] - 1);
}
if (l <= b[i] - 1) sep[{l, b[i] - 1}] = v, s.insert(v);
if (b[i] + 1 <= r) sep[{b[i] + 1, r}] = rv, s.insert(rv);
}
else {
LL lv = v;
v = 0;
lv -= qcnt(l, b[i] - 1, a[b[i]] + 1, n);
for (int j = b[i] + 1; j <= r; ++j) {
lv -= qcnt(l, j - 1, a[j] + 1, n);
v += qcnt(b[i] + 1, j - 1, a[j] + 1, n);
}
if (l <= b[i] - 1) sep[{l, b[i] - 1}] = lv, s.insert(lv);
if (b[i] + 1 <= r) sep[{b[i] + 1, r}] = v, s.insert(v);
}
// for (int x : s) cout << x << ' ';
// cout << '\n';
cout << ' ' << (res = *s.rbegin());
}
cout << '\n';
fill(tr, tr + tot + 2, Node{0, 0, 0});
}
return 0;
}H. Traveling on the Axis
cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <complex>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
void pr(vector<int> a) {
for (auto i : a)
cout << i << ' ';
cout << '\n';
}
const int mod = 998244353;
const int INF = 1e18;
const int N = 5e5 + 5;
void init() {
}
void solve() {
string s;
cin>>s;
int n=sz(s);
int ans=0;
for(int i=0;i<n;i++){
if(s[i]=='0')ans+=n-i;
ans+=(n-i+1)*(n-i)/2;
}
for(int i=1;i<n;i++){
if(s[i]==s[i-1])ans+=(i)*(n-i);
}
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}J. Press the Button
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';
void solve() {
ll a, b, c, d, v, t;
cin >> a >> b >> c >> d >> v >> t;
ll T = a * c / std::gcd(a, c);
ll ans = b + d - 1;
auto calc = [&](ll x) -> ll{
//debug(x)
ll res = 0, pre = v;
ll pos_a = a, pos_b = c;
while (pos_a <= x || pos_b <= x) {
//debug(pos_a) debug(pos_b) debug(res) debug(pre) DL
if (pos_a <= pos_b) {
if (pos_a <= pre) res += b;
else res += b - 1;
pre = pos_a + v;
pos_a += a;
} else {
if (pos_b <= pre) res += d;
else res += d - 1;
pre = pos_b + v;
pos_b += c;
}
}
return res;
};
ll k = t / T;
if (k) ans += k * calc(T);
ans += calc(t % T);
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t --) solve();
}K. XOR Clique
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t --) {
vector<int> cnt(32);
int n;
cin >> n;
for (int i = 1; i <= n; i ++) {
int x;
cin >> x;
for (int j = 30; j >= 0; j --) {
if ((1 << j) & x) {
cnt[j] ++;
break;
}
}
}
cout << *max_element(cnt.begin(), cnt.end()) << '\n';
}
}其他没做的题
- Infinite Parenthesis Sequence
- Kuririn MIRACLE