A Live Love
水。
#include<bits/stdc++.h> using namespace std; typedef long long ll;
const double eps = 1e-;
const int INF = 0x3f3f3f3f;
const ll MOD = (int)1e9 + ;
const int maxn = (int)1e6 + ; int n, m; inline void RUN()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d %d", &n, &m);
int ans1 = m;
int ans2 = (n) / (n - m + );
printf("%d %d\n", ans1, ans2);
}
} int main()
{
#ifdef LOCAL_JUDGE
freopen("Text.txt", "r", stdin);
#endif // LOCAL_JUDGE RUN(); #ifdef LOCAL_JUDGE
fclose(stdin);
#endif // LOCAL_JUDGE
return ;
}
B Red Black Tree
题意：有一个树，上面有红点和黑点，有边权，每个点的花费定义为它到离它最近的红点的距离，每次询问给出一些点，能够将这棵树中的一个黑点变为红点，使得这些点中的最大花费最小
思路：二分答案，符合条件的点不管，将不符合条件的点LCA求出来，变红，然后算距离
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define ll long long
#define INFLL 0x3f3f3f3f3f3f3f3f struct Edge
{
int to, nx; ll w;
inline Edge() {}
inline Edge(int to, int nx, ll w) : to(to), nx(nx), w(w) {}
}edge[N << ]; int t, n, m, q, k;
int isred[N], prered[N], head[N], arr[N], pos;
int rmq[N << ], F[N << ], P[N], deep[N], cnt;
ll dist[N]; inline void Init()
{
memset(head, -, sizeof head); pos = ;
memset(isred, , sizeof isred); deep[] = ;
} inline void addedge(int u, int v, ll w)
{
edge[++pos] = Edge(v, head[u], w); head[u] = pos;
} struct ST
{
int mm[N << ];
int dp[N << ][];
inline void init(int n)
{
mm[] = -;
for (int i = ; i <= n; ++i)
{
mm[i] = ((i & (i - )) == ) ? mm[i - ] + : mm[i - ];
dp[i][] = i;
}
for (int j = ; j <= mm[n]; ++j)
{
for (int i = ; i + ( << j) - <= n; ++i)
{
dp[i][j] = rmq[dp[i][j - ]] < rmq[dp[i + ( << (j - ))][j - ]] ? dp[i][j - ] : dp[i + ( << (j - ))][j - ];
}
}
}
inline int query(int a, int b)
{
if (a > b) swap(a, b);
int k = mm[b - a + ];
return rmq[dp[a][k]] <= rmq[dp[b - ( << k) + ][k]] ? dp[a][k] : dp[b - ( << k) + ][k];
}
}st; inline void DFS(int u, int pre, int prer)
{
F[++cnt] = u;
rmq[cnt] = deep[u];
P[u] = cnt;
prered[u] = prer;
for (int it = head[u]; ~it; it = edge[it].nx)
{
int v = edge[it].to;
if (v == pre) continue;
if (isred[v]) dist[v] = ;
else dist[v] = dist[u] + edge[it].w;
deep[v] = deep[u] + ;
DFS(v, u, isred[v] ? v : prer);
F[++cnt] = u;
rmq[cnt] = deep[u];
}
} inline void Lca_Init(int root, int node_num)
{
cnt = ;
DFS(root, root, );
st.init( * node_num - );
} inline int query_lca(int u, int v)
{
return F[st.query(P[u], P[v])];
} vector <int> v;
inline bool check(ll mid)
{
v.clear();
for (int i = ; i <= k; ++i)
{
if (dist[arr[i]] > mid)
v.emplace_back(arr[i]);
}
if (v.empty()) return true;
int lca = v[];
for (int i = , len = v.size(); i < len; ++i)
lca = query_lca(lca, v[i]);
if (isred[lca]) return false;
for (auto it : v)
{
if (deep[lca] < deep[prered[it]]) return false;
else if (dist[it] - dist[lca] > mid) return false;
}
return true;
} inline void Run()
{
for (scanf("%d", &t); t--; )
{
scanf("%d%d%d", &n, &m, &q); Init();
for (int i = , u; i <= m; ++i)
{
scanf("%d", &u);
isred[u] = ;
}
ll w;
for (int i = , u, v; i < n; ++i)
{
scanf("%d%d%lld", &u, &v, &w);
addedge(u, v, w); addedge(v, u, w);
}
Lca_Init(, n);
for (int qq = ; qq <= q; ++qq)
{
scanf("%d", &k);
for (int i = ; i <= k; ++i) scanf("%d", arr + i);
if (k == )
{
puts("");
continue;
}
ll l = , r = INFLL, ans;
while (r - l >= )
{
ll mid = (l + r) >> ;
if (check(mid))
{
ans = mid;
r = mid - ;
}
else
l = mid + ;
}
printf("%lld\n", ans);
}
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
愚蠢的倍增求LCA（排序一下）
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll MOD = (int)1e9 + ;
const int maxn = (int)1e5 + ; const int DEG = ; struct Edge {
int to, nxt;
ll w;
inline Edge(){}
inline Edge(int to,int nxt,ll w):to(to),nxt(nxt),w(w){}
}edge[maxn << ]; int head[maxn], tot;
int red[maxn]; inline void addedge(int u, int v, ll w)
{
edge[tot] = Edge(v, head[u], w); head[u] = tot++;
} inline void Init(int n)
{
for (int i = ; i <= n; ++i)
{
red[i] = ;
head[i] = -;
}
tot = ;
} ll dis[maxn];
int fa[maxn][DEG];
int deg[maxn];
int pre[maxn]; inline void BFS(int root)
{
queue<int>q;
dis[root] = ;
deg[root] = ;
fa[root][] = root;
pre[root] = root;
q.push(root);
while (!q.empty())
{
int tmp = q.front();
q.pop();
for (int i = ; i < DEG; ++i)
{
fa[tmp][i] = fa[fa[tmp][i - ]][i - ];
}
for (int i = head[tmp]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
ll w = edge[i].w;
if (v == fa[tmp][]) continue;
deg[v] = deg[tmp] + ;
fa[v][] = tmp;
if (red[v])
{
pre[v] = v;
}
else
{
pre[v] = pre[tmp];
}
if (red[v])
{
dis[v] = ;
}
else
{
dis[v] = dis[tmp] + w;
}
q.push(v);
}
}
} inline int LCA(int u, int v)
{
if (deg[u] > deg[v]) swap(u, v);
int hu = deg[u], hv = deg[v];
int tu = u, tv = v;
for (int det = hv - hu, i = ; det; det >>= , ++i)
{
if (det & )
{
tv = fa[tv][i];
}
}
if (tu == tv) return tu;
for (int i = DEG - ; i >= ; --i)
{
if (fa[tu][i] == fa[tv][i]) continue;
tu = fa[tu][i], tv = fa[tv][i];
}
return fa[tu][];
} int n, m, q, k;
int arr[maxn]; inline bool cmp(int a, int b)
{
return dis[a] > dis[b];
} inline bool check(ll mid)
{
int root = arr[];
int cnt = ;
for (int i = ; i <= k; ++i)
{
if (dis[arr[i]] > mid)
{
if (pre[root] != pre[arr[i]]) return false;
root = LCA(root, arr[i]);
cnt++;
}
}
if (cnt == || cnt == ) return true;
for (int i = ; i <= k; ++i)
{
if (dis[arr[i]] > mid)
{
if (dis[arr[i]] - dis[root] > mid) return false;
}
}
return true;
} inline void RUN()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d %d %d", &n, &m, &q);
Init(n);
for (int i = ; i <= m; ++i)
{
int u;
scanf("%d", &u);
red[u] = ;
}
for (int i = ; i < n; ++i)
{
int u, v;
ll w;
scanf("%d %d %lld", &u, &v, &w);
addedge(u, v, w);
addedge(v, u, w);
}
BFS();
while (q--)
{
scanf("%d", &k);
for (int i = ; i <= k; ++i)
{
scanf("%d", arr + i);
}
if (k == )
{
puts("");
continue;
}
sort(arr + , arr + + k, cmp);
ll l = ;
ll r = INFLL;
ll ans = ;
while (r - l >= )
{
ll mid = (r + l) >> ;
if (check(mid))
{
r = mid - ;
ans = mid;
}
else
{
l = mid + ;
}
}
printf("%lld\n", ans);
}
}
} int main()
{
#ifdef LOCAL_JUDGE
freopen("Text.txt", "r", stdin);
#endif // LOCAL_JUDGE RUN(); #ifdef LOCAL_JUDGE
fclose(stdin);
#endif // LOCAL_JUDGE
return ;
}
C Halting Problem
题意：给出五种操作，机器从第一条命令开始，问是否能到n+1条命令。
思路：暴力，记录状态，若来到重复状态则输出No
#include<bits/stdc++.h> using namespace std; typedef long long ll;
const double eps = 1e-;
const int INF = 0x3f3f3f3f;
const ll MOD = (int)1e9 + ;
const int maxn = (int)1e4 + ; int n, num;
int vis[maxn][];
struct node {
char op[];
int v, k;
}arr[maxn]; inline void RUN()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = ; i <= n; ++i)
{
for (int j = ; j < ; ++j)
{
vis[i][j] = ;
}
}
int flag = true;
int s = ;
int now = ;
for (int i = ; i <= n; ++i)
{
scanf("%s", arr[i].op);
if (strcmp(arr[i].op,"add") == )
{
scanf("%d", &arr[i].v);
arr[i].k = ;
}
else
{
scanf("%d %d", &arr[i].v, &arr[i].k);
}
}
while ()
{
if (now == n + )
{
flag = true;
break;
}
if (vis[now][s])
{
flag = false;
break;
}
vis[now][s]++;
if (strcmp(arr[now].op, "add") == )
{
s = (s + arr[now].v);
if (s >= )s -= ;
now++;
}
else if (strcmp(arr[now].op, "beq") == )
{
if (s == arr[now].v)
{
now = arr[now].k;
}
else
{
now++;
}
}
else if (strcmp(arr[now].op, "bne") == )
{
if (s != arr[now].v)
{
now = arr[now].k;
}
else
{
now++;
}
}
else if (strcmp(arr[now].op, "blt") == )
{
if (s < arr[now].v)
{
now = arr[now].k;
}
else
{
now++;
}
}
else if (strcmp(arr[now].op, "bgt") == )
{
if (s > arr[now].v)
{
now = arr[now].k;
}
else
{
now++;
}
}
}
puts(flag ? "Yes" : "No");
}
} int main()
{
#ifdef LOCAL_JUDGE
freopen("Text.txt", "r", stdin);
#endif // LOCAL_JUDGE RUN(); #ifdef LOCAL_JUDGE
fclose(stdin);
#endif // LOCAL_JUDGE
return ;
}
D Pixel Art
留坑。
E Infinite Parenthesis Sequence
留坑。
F Chaleur
留坑。
G Couleur
题意：每次标记一个数不可用，那么就将原数组分成多一段，然后找出子数组中异或最大。
思路：每次划分成两边，对小的那边暴力，可以用set 来找左界右界，map 来找出当前界中的值 multiset 找最大值
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define M N * 30
using ll = long long;
using pii = pair <int, int>; int t, n;
set <int> s;
multiset <ll> mst;
map <pii, ll> mp;
int arr[N], p[N];
ll ans; struct BIT
{
int a[N];
inline void update(int x)
{
for (int i = x; i <= n; i += i & -i)
++a[i];
}
inline int query(int x)
{
int res = ;
for (int i = x; i > ; i -= i & -i)
res += a[i];
return res;
}
}bit; struct chairman_tree
{
int T[N], L[M], R[M], C[M], tot;
inline int build(int l, int r)
{
int root = tot++;
C[root] = ;
if (l < r)
{
int mid = (l + r) >> ;
L[root] = build(l, mid);
R[root] = build(mid + , r);
}
return root;
}
inline int update(int root, int pos)
{
int newroot = tot++, tmp = newroot;
C[newroot] = C[root] + ;
int l = , r = n;
while (l < r)
{
int mid = (l + r) >> ;
if (pos <= mid)
{
L[newroot] = tot++; R[newroot] = R[root];
newroot = L[newroot], root = L[root];
r = mid;
}
else
{
L[newroot] = L[root], R[newroot] = tot++;
newroot = R[newroot], root = R[root];
l = mid + ;
}
C[newroot] = C[root] + ;
}
return tmp;
}
inline int query(int left_root, int right_root, int pos, int vis)
{
int l = , r = n, res = ;
while (l < r)
{
int mid = (l + r) >> ;
if (pos <= mid)
{
left_root = L[left_root];
right_root = L[right_root];
r = mid;
}
else
{
res += C[L[left_root]] - C[L[right_root]];
left_root = R[left_root];
right_root = R[right_root];
l = mid + ;
}
}
if (vis) res += C[left_root] - C[right_root];
return res;
}
}ct; inline void Init()
{
memset(bit.a, , sizeof bit.a); ct.tot = ;
s.clear(), mst.clear(), mp.clear(); ans = ;
s.emplace(), s.emplace(n + );
ct.T[n + ] = ct.build(, n);
} inline void Run()
{
for (scanf("%d", &t); t--; )
{
scanf("%d", &n); Init();
for (int i = ; i <= n; ++i)
{
scanf("%d", arr + i);
bit.update(arr[i]);
ans += i - bit.query(arr[i]);
}
for (int i = ; i <= n; ++i) scanf("%d", p + i);
for (int i = n; i >= ; --i) ct.T[i] = ct.update(ct.T[i + ], arr[i]);
mp[pii(, n)] = ans; mst.insert(ans);
for (int i = ; i <= n; ++i)
{
printf("%lld%c", ans, " \n"[i == n]);
if (ans)
{
int id = int(ans ^ p[i]), l, r;
l = *(--s.upper_bound(id)) + ;
r = *(s.upper_bound(id)) - ; s.insert(id);
ll val = mp[pii(l, r)];
mst.erase(mst.lower_bound(val));
mp.erase(pii(l, r));
val -= id - l - ct.query(ct.T[l], ct.T[id], arr[id], );
if (id - l < r - id) // goto left
{
for (int j = l; j <= id; ++j)
val -= ct.query(ct.T[id + ], ct.T[r + ], arr[j], );
ll vall = , valr = ;
for (int j = l + ; j < id; ++j)
vall += j - l - ct.query(ct.T[l], ct.T[j], arr[j], );
valr = val - vall;
mst.insert(vall), mst.insert(valr);
mp[pii(l, id - )] = vall; mp[pii(id + , r)] = valr;
}
else // goto right
{
for (int j = id + ; j <= r; ++j)
val -= id - l + - ct.query(ct.T[l], ct.T[id + ], arr[j], );
ll vall = , valr = ;
for (int j = id + ; j <= r; ++j)
valr += j - id - - ct.query(ct.T[id + ], ct.T[j], arr[j], );
vall = val - valr;
mst.insert(vall), mst.insert(valr);
mp[pii(l, id - )] = vall; mp[pii(id + , r)] = valr;
}
ans = *(mst.rbegin());
}
}
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
H Traveling on the Axis
题意：一个字符串表示当前点是红灯还是绿灯，灯一秒变一次，求$\sum_{p = 0}^{n - 1}\sum_{q = p +1}^{n} t(p, q)$
思路：前缀搞一搞
#include<bits/stdc++.h> using namespace std; char st[+];
long long f[+];
int main() {
long long t,n,i,j,k;
long long ans;
scanf("%lld",&t);
while (t--) {
scanf("%s",st);
n=strlen(st);
f[]=; ans=;
for (i=;i<n;++i)
if (st[i]==st[i-]) f[i+]=;
else f[i+]=;
for (i=;i<=n;++i) {
ans+=(f[i])*i*(n-i+);
if (st[i-]=='') ans+=n-i+;
if (f[i]==) ans-=n-i+;
}
printf("%lld\n",ans);
}
return ;
}
J Press the Button
题意：周期性按灯，每按一次，如果灯本来是亮着就++， 求最后+了多少次
思路：记录lcm时间内的增加次数以及t%lcm时间内的增加次数。用两个时间节点记录两人下次按的时间，然后暴力跑出lcm以及t%lcm时间内的增加次数即可
#include<bits/stdc++.h> using namespace std; typedef long long ll;
const double eps = 1e-;
const int INF = 0x3f3f3f3f;
const ll MOD = (int)1e9 + ;
const int maxn = (int)1e4 + ; inline ll gcd(ll a, ll b)
{
return b == ? a : gcd(b, a%b);
} ll a, b, c, d, v, t; inline void RUN()
{
int cas;
scanf("%d", &cas);
while (cas--)
{
scanf("%lld %lld %lld %lld %lld %lld", &a, &b, &c, &d, &v, &t);
ll G = gcd(a, c);
G = a * c / G;
//cout << G << endl;
ll res =;
ll res1 = b - + d;
ll len = t / G;
ll M = t % G;
ll t1 = a;
ll t2 = c;
ll now = ;
while (t1 <= G && t2 <= G)
{
if (t1 < t2)
{
ll tmp = t1 - now;
if (tmp > v)
{
res += b - ;
if (t1 <= M)
{
res1 += b - ;
}
}
else
{
res += b;
if (t1 <= M)
{
res1 += b;
}
}
now = t1;
t1 += a; }
else if (t1 > t2)
{
ll tmp = t2 - now;
if (tmp > v)
{
res += d - ;
if (t2 <= M)
{
res1 += d - ;
}
}
else
{
res += d;
if (t2 <= M)
{
res1 += d;
}
}
now = t2;
t2 += c;
}
else if (t1 == t2)
{
ll tmp = t1 - now;
if (tmp > v)
{
res += b + d - ;
if (t1 <= M)
{
res1 += b + d - ;
}
}
else
{
res += b + d;
if (t1 <= M)
{
res1 += b + d;
}
}
now = t1;
t1 += a;
t2 += c; }
}
ll ans = res * len + res1;
printf("%lld\n", ans);
}
} int main()
{
#ifdef LOCAL_JUDGE
freopen("Text.txt", "r", stdin);
#endif // LOCAL_JUDGE RUN(); #ifdef LOCAL_JUDGE
fclose(stdin);
#endif // LOCAL_JUDGE
return ;
}
K XOR Clique
题意：给出n个数，求选出一个点集，使得里面的点两两异或不超过这两个数中小的那个，求点集里面元素个数最大是多少
思路：枚举最高位
#include<bits/stdc++.h> using namespace std; typedef long long ll;
const double eps = 1e-;
const int INF = 0x3f3f3f3f;
const ll MOD = (int)1e9 + ;
const int maxn = (int)1e6 + ; int n, num;
int arr[]; inline void RUN()
{
int t;
scanf("%d", &t);
while (t--)
{
int ans = ;
scanf("%d", &n);
memset(arr, , sizeof arr);
for (int i = ; i <= n; ++i)
{
scanf("%d", &num);
int cnt = ;
while (num)
{
cnt++;
num >>= ;
}
arr[cnt]++;
ans = max(ans, arr[cnt]);
}
printf("%d\n", ans);
}
} int main()
{
#ifdef LOCAL_JUDGE
freopen("Text.txt", "r", stdin);
#endif // LOCAL_JUDGE RUN(); #ifdef LOCAL_JUDGE
fclose(stdin);
#endif // LOCAL_JUDGE
return ;
}