数论,树的直径 + 优化建图,01trie 及其特殊操作
# A. 常中 20181205T1-Simple
刚开始以为是扩展欧几里得定理然后乱搞,然后去测了一发大样例,结果挂了……
于是重新观察题目,原式:,假设有一条数轴。
当 时,可以覆盖
当 时,可以覆盖
不难发现,覆盖的点中一定会有重复的,那么哪些重复了呢?
当 时会重复,此时 。
由于 为整数,且 要尽量小,所以 ,暴力枚举 即可。
#include <bits/stdc++.h> | |
#define ll long long | |
using namespace std; | |
namespace IO{ | |
inline ll read(){ | |
ll x = 0; | |
char ch = getchar(); | |
while(!isdigit(ch)) ch = getchar(); | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x; | |
} | |
template <typename T> inline void write(T x){ | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
int T; | |
ll n, m, q; | |
inline ll gcd(ll a, ll b){ | |
return !b ? a : gcd(b, a % b); | |
} | |
int main(){ | |
T = read(); | |
while(T--){ | |
n = read(), m = read(), q = read(); | |
ll d = n / gcd(n, m), ans = 0; | |
for(ll i = 0; i < d && q - i * m >= 0; ++i) ans += (q - i * m) / n + 1; | |
write(q - ans + 1), puts(""); | |
} | |
return 0; | |
} |
# B. 常中 20181205T2-Walk
考虑枚举权值 ,计算权值为 (或 的倍数)的路径中最长的长度是多少,计算最长长度直接跑个树的直径就完了。
但是如果每次都枚举所有边建图的话复杂度是过不去的,所以我们考虑优化建图过程。
类似于前向星的思想,我们用 记录是 倍数的边,然后建图的时候直接跑 即可。
#include <bits/stdc++.h> | |
#define int long long | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0; | |
char ch = getchar(); | |
while(!isdigit(ch)) ch = getchar(); | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x; | |
} | |
template <typename T> inline void write(T x){ | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 1e6 + 10; | |
const int M = 1e6; | |
int n, m; | |
struct node{ | |
int u, v, nxt; | |
}edge[N << 1], e[N << 1]; | |
int head[N], tot, h[N], cnt; | |
int stk[N << 1], top; | |
inline void Add(int x, int y, int z){ | |
e[++cnt] = (node){x, y, h[z]}; | |
h[z] = cnt; | |
} | |
inline void add(int x, int y){ | |
edge[++tot].v = y, edge[tot].nxt = head[x]; | |
head[x] = tot; | |
stk[++top] = x; | |
} | |
int maxl, tim = 1, vis[N]; | |
int dfs(int u) { | |
int maxc = 0; | |
vis[u] = tim; | |
for (int v, j = head[u]; j; j = edge[j].nxt) | |
if (vis[v = edge[j].v] != tim) { | |
int tmpc = dfs(v); | |
maxl = max(maxl, maxc + tmpc + 1); | |
maxc = max(maxc, tmpc + 1); | |
} | |
return maxc; | |
} | |
int ans[N]; | |
inline void solve(int val){ | |
for(int i = 1; i <= top; ++i) | |
if(vis[stk[i]] != tim) dfs(stk[i]); | |
ans[maxl] = val; | |
} | |
inline void clear(){ | |
for(int j = 1; j <= top; ++j) head[stk[j]] = 0; | |
tot = maxl = top = tot = 0; | |
} | |
signed main(){ | |
// freopen("B.in", "r", stdin); | |
// freopen("B.out", "w", stdout); | |
n = read(); | |
for(int i = 1; i < n; ++i){ | |
int u = read(), v = read(), w = read(); | |
Add(u, v, w), m = max(m, w); | |
} | |
for (int i = 1; i <= M; i++, tim++) { | |
for (int j = i; j <= M; j += i) | |
for (int k = h[j]; k; k = e[k].nxt) | |
add(e[k].u, e[k].v), add(e[k].v, e[k].u); | |
for (int j = 1; j <= top; j++) | |
if (vis[stk[j]] != tim) dfs(stk[j]); | |
ans[maxl] = i; | |
clear(); | |
} | |
for(int i = n - 1; i > 0; --i) ans[i] = max(ans[i], ans[i + 1]); | |
for(int i = 1; i <= n; ++i) write(ans[i]), puts(""); | |
return 0; | |
} |
# C. 树
这题就比较有意思了。
看到求异或和,肯定想到要用 ,我们需要支持子树加 1,合并 ,求区间异或和。
:表示权值。
:表示从当前点到根的 1 的个数的奇偶性。
# 子树加 1
左子树会变成右子树,右子树变成左子树,所以就交换一下即可。
如果交换之后左子树还有值,相当于需要进位,继续加即可。
# 合并 01trie
类似于线段树合并(甚至更简单)。
直接合并即可。
# 区间异或和
01trie 基操,不多说了吧。
#include <bits/stdc++.h> | |
#define ls(x) t[x].ch[0] | |
#define rs(x) t[x].ch[1] | |
#define ll long long | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0; | |
char ch = getchar(); | |
while(!isdigit(ch)) ch = getchar(); | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x; | |
} | |
template <typename T> inline void write(T x){ | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 6e5 + 10; | |
int n, cnt; | |
int a[N]; | |
vector <int> g[N]; | |
struct Trie{ | |
int val, cnt, ch[2]; | |
}t[N * 27]; | |
int rt[N]; | |
void update(int x) { | |
t[x].cnt = t[x].val = 0; | |
if(ls(x)) t[x].cnt ^= t[ls(x)].cnt, t[x].val ^= (t[ls(x)].val << 1); | |
if(rs(x)) t[x].cnt ^= t[rs(x)].cnt, t[x].val ^= (t[rs(x)].val << 1) | t[rs(x)].cnt; | |
} | |
inline void insert(int &x, int val, int dep){ | |
if(!x) x = ++cnt; | |
if(dep > 20) return t[x].cnt ^= 1, void(); | |
insert(t[x].ch[val & 1], val>> 1, dep + 1), update(x); | |
} | |
inline void add(int x){ | |
swap(ls(x), rs(x)); | |
if(ls(x)) add(ls(x)); | |
update(x); | |
} | |
inline int merge(int x, int y){ | |
if(!x || !y) return x | y; | |
t[x].val ^= t[y].val, t[x].cnt ^= t[y].cnt; | |
ls(x) = merge(ls(x), ls(y)); | |
rs(x) = merge(rs(x), rs(y)); | |
return x; | |
} | |
ll ans; | |
inline void dfs(int x){ | |
for(auto y : g[x]) dfs(y), rt[x] = merge(rt[x], rt[y]); | |
add(rt[x]), insert(rt[x], a[x], 0); | |
ans += 1ll * t[rt[x]].val; | |
} | |
signed main(){ | |
// freopen("P6623.in","r",stdin); | |
// freopen("P6623.out","w",stdout); | |
n = read(); | |
for(int i = 1; i <= n; ++i) a[i] = read(); | |
for(int i = 2; i <= n; ++i) g[read()].push_back(i); | |
dfs(1); | |
write(ans), puts(""); | |
return 0; | |
} |