A - 口算训练
题意：询问 $[L, R]$区间内 的所有数的乘积是否是D的倍数
思路：考虑分解质因数
显然，一个数$x > \sqrt{x} 的质因子只有一个$
那么我们考虑将小于$\sqrt {x}$ 的质因子用线段树维护
其他质因子用vector 维护存在性
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define block 317
vector <int> fac[N], bigfac[];
int t, n, q;
int arr[N], pos[N], cnt; void init()
{
cnt = ;
memset(pos, , sizeof pos);
for (int i = ; i < N; ++i)
{
if (pos[i] || i > block) continue;
for (int j = i * i; j < N; j += i)
pos[j] = ;
}
for (int i = ; i < N; ++i) if (!pos[i]) pos[i] = ++cnt;
for (int i = ; i <= ; ++i)
{
int n = i;
for (int j = ; j * j <= n; ++j)
{
while (n % j == )
{
n = n / j;
fac[i].push_back(j);
}
}
if (n != ) fac[i].push_back(n);
sort(fac[i].begin(), fac[i].end());
}
} int T[];
struct SEG
{
#define M N * 300
int a[M], lson[M], rson[M], cnt;
void init() { cnt = ; }
void pushup(int id) { a[id] = a[lson[id]] + a[rson[id]]; }
void update(int &id, int l, int r, int pos)
{
if (!id)
{
id = ++cnt;
a[id] = lson[id] = rson[id] = ;
}
if (l == r)
{
++a[id];
return;
}
int mid = (l + r) >> ;
if (pos <= mid) update(lson[id], l, mid, pos);
else update(rson[id], mid + , r, pos);
pushup(id);
}
int query(int id, int l, int r, int ql, int qr)
{
if (!id) return ;
if (l >= ql && r <= qr) return a[id];
int mid = (l + r) >> ;
int res = ;
if (ql <= mid) res += query(lson[id], l, mid, ql, qr);
if (qr > mid) res += query(rson[id], mid + , r, ql, qr);
return res;
}
}seg; bool Get(int base, int need, int l, int r)
{
// printf("%d %d %d %d\n", base, need, l, r);
int have = ;
if (base < block)
{
have = seg.query(T[pos[base]], , n, l, r);
if (have < need) return false;
}
else
{
have = upper_bound(bigfac[pos[base]].begin(), bigfac[pos[base]].end(), r) - lower_bound(bigfac[pos[base]].begin(), bigfac[pos[base]].end(), l);
if (have < need) return false;
}
return true;
} bool work(int l, int r, int d)
{
if (d == ) return true;
int base = fac[d][], need = , have = ;
for (int i = , len = fac[d].size(); i < len; ++i)
{
if (fac[d][i] != base)
{
if (Get(base, need, l, r) == false) return false;
base = fac[d][i];
need = ;
}
else ++need;
}
return Get(base, need, l, r);
} int main()
{
init();
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &q);
for (int i = ; i < ; ++i) bigfac[i].clear();
for (int i = ; i <= n; ++i) scanf("%d", arr + i);
seg.init(); memset(T, , sizeof T);
for (int i = ; i <= n; ++i)
{
for (auto it : fac[arr[i]])
{
if (it < block)
seg.update(T[pos[it]], , n, i);
else
bigfac[pos[it]].push_back(i);
}
}
for (int i = ; i <= cnt; ++i) sort(bigfac[i].begin(), bigfac[i].end());
for (int i = , l, r, d; i <= q; ++i)
{
scanf("%d%d%d", &l, &r, &d);
puts(work(l, r, d) ? "Yes" : "No");
}
}
return ;
}
B - 缺失的数据范围
题意：给出$a, b, k$ 求一个最大的n 使得 $n^{a} \cdot log ^b n <= k$
思路：二分 但是要注意用高精度，求log的时候 平方逼近
import java.io.BufferedInputStream;
import java.util.Scanner;
import java.math.*; public class Main { public static BigInteger Get(BigInteger x, int a, int b)
{
BigInteger two = BigInteger.valueOf();
BigInteger tmp = BigInteger.ONE;
BigInteger cnt = BigInteger.ZERO;
while (tmp.compareTo(x) < )
{
tmp = tmp.multiply(two);
cnt = cnt.add(BigInteger.ONE);
}
BigInteger res = x.pow(a).multiply(cnt.pow(b));
return res;
} public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
int t = in.nextInt();
int a, b; BigInteger k, l, r, mid, ans, zero, two, one;
zero = BigInteger.ZERO;
two = BigInteger.valueOf();
one = BigInteger.valueOf();
while (t-- != )
{
a = in.nextInt();
b = in.nextInt();
k = in.nextBigInteger();
l = one;
r = k;
ans = zero;
while (r.subtract(l).compareTo(zero) >= )
{
mid = l.add(r).divide(two);
if (Get(mid, a, b).compareTo(k) <= )
{
ans = mid;
l = mid.add(one);
}
else
r = mid.subtract(one);
}
System.out.println(ans);
}
in.close();
}
}
C - 寻宝游戏
留坑。
D - 奢侈的旅行
题意：经过一条路的花费为$log_2^{\frac {level + a_i}{level}}$ 并且 $cost < b_i$ 时不能经过这条路，求$1 -> n$ 的最短路径
思路：考虑等式两边取2的幂次 比如
考虑 $log_2^a + log_2^b = log_2^{ab}$
那么 cost 为
$log_2^{\frac{1 + a_1}{a_1}} + log_2^{\frac {1 + a_1 + a_2}{1 + a_1}} + log_2^{\frac{1 + a_1 + a_2 + a_k}{1 + a_1 + a_2}}$
等价于
$log_2^{1 + a_1 + a_2 + a_k}$
再取2的幂次
$2^{cost} = 2^{log_2 ^{1 + a_1 + a_2 + a_k}}$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define INFLL 0x3f3f3f3f3f3f3f3f
#define N 100010
int t, n, m;
struct Edge { int to; ll a, b; };
vector <Edge> G[N]; struct dnode
{
int u; ll w;
dnode () {}
dnode (int u, ll w) : u(u), w(w) {}
bool operator < (const dnode &r) const { return w > r.w; }
}; ll dist[N]; bool used[N];
void Dijkstra()
{
for (int i = ; i <= n; ++i) dist[i] = INFLL, used[i] = ;
priority_queue <dnode> q; q.emplace(, ); dist[] = ;
while (!q.empty())
{
int u = q.top().u; q.pop();
if (used[u]) continue;
used[u] = ;
for (auto it : G[u])
{
int v = it.to; ll a = it.a, b = it.b;
if (!used[v] && dist[v] > dist[u] + a && a / dist[u] >= b - )
{
dist[v] = dist[u] + a;
q.emplace(v, dist[v]);
} }
}
} int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i) G[i].clear();
for (int i = , u, v, a, b; i <= m; ++i)
{
scanf("%d%d%d%d", &u, &v, &a, &b);
G[u].push_back(Edge{ v, a, 1ll << b});
}
Dijkstra();
if (dist[n] == INFLL) puts("-1");
else printf("%lld\n", (ll)(log2(dist[n]))); }
return ;
}
E - 对称数
题意：找树上一条路径中最小的出现次数为偶数的数
思路：树分块+数字分块 找数字的时候分块统计 $O(1)$更新
好像卡了树上路径莫队。
#include <bits/stdc++.h>
using namespace std; #define N 200010
#define block 450
#define INF 0x3f3f3f3f
int t, n, m;
int arr[N];
vector <int> G[N];
int deep[N], fa[N], top[N], son[N], sze[N], cnt;
int szeblock[N], Belong[N], dfn[N], dfscnt, dfssize;
stack <int> sta; void DFS(int u)
{
dfn[u] = ++dfscnt;
sta.push(u);
szeblock[u] = ;
sze[u] = ;
for (auto v : G[u]) if (v != fa[u])
{
fa[v] = u;
deep[v] = deep[u] + ;
DFS(v); sze[u] += sze[v]; szeblock[u] += szeblock[v];
if (son[u] == - || sze[v] > sze[son[u]]) son[u] = v;
if (szeblock[u] >= block)
{
szeblock[u] = ;
++dfssize;
while (!sta.empty() && sta.top() != u) { Belong[sta.top()] = dfssize; sta.pop(); }
}
}
++szeblock[u];
} void getpos(int u, int sp)
{
top[u] = sp;
if (son[u] == -) return;
getpos(son[u], sp);
for (auto v : G[u]) if (v != son[u] && v != fa[u])
getpos(v, v);
} int querylca(int u, int v)
{
int fu = top[u], fv = top[v];
while (fu != fv)
{
if (deep[fu] < deep[fv])
{
swap(fu, fv);
swap(u, v);
}
u = fa[fu]; fu = top[u];
}
if (deep[u] > deep[v]) swap(u, v);
return u;
} struct qnode
{
int u, v, id, lca;
qnode() {}
qnode(int u, int v, int id, int lca) : u(u), v(v), id(id), lca(lca) {}
bool operator < (const qnode &r) const
{
return Belong[u] == Belong[r.u] ? dfn[v] < dfn[r.v] : Belong[u] < Belong[r.u];
}
}que[N]; int ans[N]; int used[N], cnt_num[N], num_block[block];
void work(int x)
{
if (used[x]) --cnt_num[arr[x]];
else ++cnt_num[arr[x]];
num_block[(arr[x] - ) / block] += * ((cnt_num[arr[x]] & ) ? : -);
used[x] ^= ;
} void update(int u, int v)
{
while (u != v)
{
if (deep[u] > deep[v]) swap(u, v);
work(v);
v = fa[v];
}
} int Get()
{
for (int k = ; k < block; ++k) if (num_block[k] != block)
{
int l = k * block + , r = (k + ) * block;
for (int j = l; j <= r; ++j) if (cnt_num[j] % == )
return j;
}
} int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
memset(son, -, sizeof son);
cnt = ; dfssize = ; dfscnt = ;
for (int i = ; i <= n; ++i) G[i].clear();
memset(num_block, , sizeof num_block);
memset(cnt_num, , sizeof cnt_num);
memset(used, , sizeof used);
for (int i = ; i <= n; ++i) scanf("%d", arr + i);
for (int i = , u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
DFS(); getpos(, );
while (!sta.empty()) { Belong[sta.top()] = dfssize; sta.pop();}
for (int i = , u, v; i <= m; ++i)
{
scanf("%d%d", &u, &v);
if (Belong[u] > Belong[v]) swap(u, v);
que[i] = qnode(u, v, i, querylca(u, v));
}
//divide on tree
sort(que + , que + + m);
update(que[].u, que[].v);
work(que[].lca);
ans[que[].id] = Get();
work(que[].lca);
for (int i = ; i <= m; ++i)
{
update(que[i - ].u, que[i].u);
update(que[i - ].v, que[i].v);
work(que[i].lca);
ans[que[i].id] = Get();
work(que[i].lca);
}
for (int i = ; i <= m; ++i) printf("%d\n", ans[i]);
}
return ;
}
F - 赛题分析
水。
#include <bits/stdc++.h>
using namespace std; #define N 1010
#define INF 0x3f3f3f3f
int t, n, m;
int arr[N], brr[N]; int main()
{
scanf("%d", &t);
for (int kase = ; kase <= t; ++kase)
{
printf("Problem %d:\n", kase + );
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i) scanf("%d", arr + i);
if (n == ) puts("Shortest judge solution: N/A bytes.");
else printf("Shortest judge solution: %d bytes.\n", *min_element(arr + , arr + + n));
for (int i = ; i <= m; ++i) scanf("%d", brr + i);
if (m == ) puts("Shortest team solution: N/A bytes.");
else printf("Shortest team solution: %d bytes.\n", *min_element(brr + , brr + + m));
}
return ;
}
G - quailty算法
留坑。
H - SA-IS后缀数组
题意：求每对相邻的后缀字符的字典序大小
思路：从后面往前推，只考虑最高位，如果最高位相同，那么问题转化为一个子问题
比如 cm 和 acm 考虑最高位 如果最高位相同 问题转化为 m 和 cm 的大小关系
#include <bits/stdc++.h>
using namespace std; #define N 1000010
int t, n;
char s[N];
int ans[N]; int main()
{
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d%s", &n, s);
int len = strlen(s);
if (s[len - ] != s[len - ]) ans[len - ] = s[len - ] > s[len - ];
else ans[len - ] = ;
for (int i = len - ; i >= ; --i)
{
if (s[i] != s[i + ]) ans[i] = s[i] > s[i + ];
else ans[i] = ans[i + ];
}
for (int i = ; i < len - ; ++i) printf("%c", ans[i] ? '>' : '<');
puts("");
}
return ;
}
I - 回文树
Upsolved.
因为数据随机，所以答案不会很大，期望为$O(n)级别$ 那么直接考虑暴力枚举，不满足了立即掐掉
可以先排个序，再双指针加速一下
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define pii pair <int, int>
int t, n, res, a[N];
vector <pii> G[N]; void DFS(int fx, int x, int fy, int y)
{
if (a[x] != a[y]) return;
if (fx && x == y) return;
if (x <= y) ++res;
for (int i = , j = , k = , len = G[x].size(); i < len; ++i) if (G[x][i].second != fx)
{
while (j < G[y].size() && G[y][j].first < G[x][i].first) ++j;
while (k < G[y].size() && G[y][k].first <= G[x][i].first) ++k;
for (int o = j; o < k; ++o) if (G[y][].second != fy) DFS(x, G[x][i].second, y, G[y][o].second);
}
} int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = ; i <= n; ++i) G[i].clear();
for (int i = ; i <= n; ++i) scanf("%d", a + i);
for (int i = , u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
G[u].push_back(pii(a[v], v));
G[v].push_back(pii(a[u], u));
}
for (int i = ; i <= n; ++i) sort(G[i].begin(), G[i].end());
res = ;
for (int i = ; i <= n; ++i) DFS(, i, , i);
for (int i = ; i <= n; ++i) for (auto it : G[i]) DFS(it.second, i, i, it.second);
printf("%d\n", res);
}
return ;
}
J - 代码派对
留坑。
K - CCPC直播
按题意模拟即可。
#include <bits/stdc++.h>
using namespace std; int t;
char s[], sta[];
int Rank, x, pro; int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%s%d%s", &Rank, s, &pro, sta);
printf("%3d|%-16s|%d|[", Rank, s, pro);
if (strcmp(sta, "Running") == )
{
scanf("%d", &x);
for (int i = ; i < x; ++i) putchar('X');
for (int i = x; i < ; ++i) putchar(' ');
printf("]\n");
}
else
{
if (strcmp(sta, "FB") == ) strcpy(sta, "AC*");
printf(" ");
printf("%-6s]\n", sta);
}
}
return ;
}