#T1 因子差
Time Limit: 1s | Memory Limit: 512MiB
#题意简述
认为一个数是有趣的，当且仅当：
- 这个数是一个正整数；
- 这个数至少有 (4) 个不同的因子；
- 这个数的任意两个因子之间的差都不小于 (n(nleq10^5)) 。
问最小的有趣的数是多少。多组数据。
#大体思路
首先一个数 (x) 必然有两个因子 (1) 和 (x)，于是我们只需要让第一个因数 (p_1) 是大于等于 (n+1) 的第一个质数，(p_2) 是大于等于 (p_1+1) 的第一个质数，不难证明这样必然是最优的（考虑一个非质数的因子），于是我们可以提前预处理出质数，然后 lower_bound 即可。
#Code
const int N = 500010;
const int INF = 0x3fffffff;
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
int prm[N], nprm[N], ncnt;
inline void euler(int x) {
for (int i = 2; i <= x; ++ i) {
if (!nprm[i]) prm[++ ncnt] = i;
for (int j = 1; j <= ncnt; ++ j) {
if (prm[j] * i > x) break;
nprm[i * prm[j]] = 1;
if (!(i % prm[j])) break;
}
}
}
int t, n;
#define lb(l, len, x) lower_bound(l + 1, l + len + 1, x)
int main() {
euler(5e5); read(t);
while (t --) {
read(n);
int pos1 = lb(prm, ncnt, n + 1) - prm;
int prm1 = prm[pos1];
int pos2 = lb(prm, ncnt, prm1 + n) - prm;
int prm2 = prm[pos2];
printf("%lld
", 1ll * prm1 * prm2);
}
return 0;
}
#T2 生成树
Time Limit: 1s | Memory Limit: 512MiB
#题意简述
给定一个 (n(nleq1000)) 个点的完全图，每次删去一个生成树，问最多能删多少次，并给出方案。
(t(tleq500)) 组数据，保证满足 (sum nleq1000).
#大体思路
构造题，具体见代码。
#Code
const int N = 100010;
const int INF = 0x3fffffff;
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
int t, n, a[N];
inline void solve() {
int mid = 1 + n >> 1, l = mid, r = mid + 1;
for (int i = 1; i < n; ++ i) {
printf("%d %d
", a[l], a[r]);
if (i & 1) -- l; else ++ r;
}
}
inline void change() {
for (int i = n + 1; i > 1; -- i) a[i] = a[i - 1];
a[1] = a[n + 1];
}
int main() {
read(t);
for (int i = 1; i <= t; ++ i) {
read(n); printf("Case #%d: %d
", i, n / 2);
for (int i = 1; i <= n; ++ i) a[i] = i;
for (int k = 1; k <= n / 2; ++ k)
solve(), change();
}
return 0;
}
#T3 划分树
Time Limit: 3s | Memory Limit: 512MiB
#题意简述
给定一棵 (n(nleq10^5)) 的树，每个节点有一个权值 (w_i(w_ileq10^9))，给定 (K(Kleq n))，要求将整棵树通过断开 (K-1) 条边划分为 (K) 部分，使得到的森林的权值最小。
定义一棵树的权值为树上所有的节点的权值的和，一个森林的权值为森林中的所有树的权值中的最大值。
(t(tleq10^5)) 组数据，保证 (sum nleq2cdot10^5).
#大体思路
要求最大值最小，直接二分不亏，现在来考虑如何对于 (x) 进行判定。
设 (f_i) 表示以 (i) 为根的子树内满足条件至少需要断开多少条边，(g_i) 表示以 (i) 为根的子树与 (i) 相连的连通快的大小，然后对于每个 (i)，贪心地选其中 (g) 小的一定更优。
于是直接 sort() 后 DP 即可，时间复杂度为 (O(nlog^2n)).
#Code
#define ll long long
#define mset(l, x) memset(l, x, sizeof(l))
const int N = 300010;
const int INF = 0x3fffffff;
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
struct Edge {int u, v, nxt;} e[N << 1];
int t, k, n, w[N], head[N], ecnt(1), f[N]; ll sum, siz[N];
vector <ll> all_siz[N];
inline void reset() {mset(head, 0); ecnt = 1, sum = 0;}
inline void add_edge(int u, int v) {
e[ecnt].u = u, e[ecnt].v = v;
e[ecnt].nxt = head[u], head[u] = ecnt ++;
}
void solve(int x, int fa, ll lmt) {
f[x] = 0, siz[x] = 0; all_siz[x].clear();
int cnt = 0; siz[x] = w[x];
for (int i = head[x]; i; i = e[i].nxt) {
if (e[i].v == fa) continue;
solve(e[i].v, x, lmt); ++ cnt;
all_siz[x].push_back(siz[e[i].v]);
f[x] += f[e[i].v];
}
sort(all_siz[x].begin(), all_siz[x].end());
for (auto k : all_siz[x]) {
if (siz[x] + k <= lmt) siz[x] += k, -- cnt;
else break;
}
f[x] += cnt;
}
inline bool check(ll x) {
for (int i = 1; i <= n; ++ i) if (x < w[i]) return false;
solve(1, 0, x); return f[1] <= k - 1;
}
void MAIN() {
read(n), read(k); reset();
for (int i = 1; i < n; ++ i) {
int u, v; read(u), read(v);
add_edge(u, v), add_edge(v, u);
}
for (int i = 1; i <= n; ++ i) read(w[i]), sum += w[i];
ll l = 0, r = sum, res = sum;
while (l <= r) {
ll mid = l + r >> 1;
if (check(mid)) res = mid, r = mid - 1;
else l = mid + 1;
}
printf("%lld
", res);
}
int main() {read(t); for (int i = 1; i <= t; ++ i) {printf("Case #%d: ", i); MAIN();} return 0;}
#T4
巨大恶心的可持久化数组维护分块的字符串题，咕咕咕～