2017 Multi-University Training Contest - Team 4

多校联合训练 hdu 6067 6068 6069 6070 6071 6072 6073 6074 6075 6076 6077 6078 6079

##Counting Divisors##

一道全场一个钟后。从第3面一直排到第15面一直在怼的题。。lcy老师表示这道题很有区分度

题意：求公式所得的答案。。就是求[l,r]这个范围内枚举的i，$i{}^k$的因子数之和。

看到这种公式题第一感觉是。有规律。 所以。。跟hovees打表看了一个钟。 然后又推推推。最后发现对于一个数。他所作的贡献是他的每一个质因子数+1的积。 对于这个数的k次方。则是。每一个质因子数*k+1的积。

然后找出了大数因数分解的板。看了看时间是6000ms感觉可以试试n${}^{5/4}$卡卡过了。。 结果就是。并不行。。然后绝望到放弃

思路：用素数筛的原理，作区间筛（Q神叫法）。 对于一个数r，我们可以用$\sqrt{r}$把[1,r]的合数都筛掉。 那么对于[l,r]我们每次只需要去枚举$\sqrt{r}$内所有素数。就可以把对于这个区间内每一个数可以做的贡献计算出来。筛到最后。数依然是素数的。他们所做的贡献为k+1，乘起来就好了。

orz学习到了区间筛（其实就是素数筛。。自己不会撸而已）

#include <bits/stdc++.h> #define MAXN 1000005 #define ll long long #define MOD 998244353 using namespace std; vector<ll> prime; ll prime_len; bool mark[MAXN]; ll l, r, k; ll f[MAXN], g[MAXN]; void getPrime() { for (ll i = 2; i < MAXN; i++) { if (!mark[i]) { prime.push_back(i); for (ll j = i * 2; j < MAXN; j += i) { mark[j] = true; } } } prime_len = prime.size(); } void filter(ll p) { for (ll i = l / p * p; i <= r; i += p) { if (i >= l) { ll tot = 0; while (f[i - l] % p == 0) { tot++; f[i - l] /= p; } g[i - l] = g[i - l] * (tot * k + 1); g[i - l] %= MOD; } } } int main() { getPrime(); int T; scanf("%d", &T); while (T--) { scanf("%lld %lld %lld", &l, &r, &k); for (ll i = 0; i <= r - l; i++) { f[i] = i + l; g[i] = 1; } for (ll i = 0; i < prime_len; i++) { if (prime[i] * prime[i] <= r) { filter(prime[i]); } } ll ans = 0; for (ll i = 0; i <= r - l; i++) { if (f[i] > 1) { g[i] = g[i] * (k + 1) % MOD; } ans += g[i] % MOD; ans %= MOD; } printf("%lld\n", ans); } }

##Dirt Ratio##

又是一个。。区间O(n^2)完全没思路。结果被dalao们教育了一把分数划分。

题意：给一个序列要找一段区间，使得区间内不同种类的数量/区间长度最小。也就是$min(\frac{size(l,r)}{r-l+1})$

思路： 我们不妨假设一个分数c他满足。$min(\frac{size(l,r)}{r-l+1})>=c$ 将这个不等式转换一下 变成$size(l,r)+l\ast c>=(r+1)\ast c$ 我们每次拿线段树去维护区间[l,r]内的最小值size(l,r)。 用二分去枚举c。每次check时枚举上一个出现同样数的后一位到r（就是枚举r就行了）是否全部满足上面那个不等式。直接得到答案。 l*c可以在建树的时候就直接维护。

#include <bits/stdc++.h> #define MAXN 60005 #define INF 1e5 #define EPS 1e-6 using namespace std; int num[MAXN]; double tree[MAXN << 2], add[MAXN << 2]; int lastpoint[MAXN]; int n; void push_up(int root) { tree[root] = min(tree[root << 1 | 1], tree[root << 1]); } void push_down(int root) { if (add[root] != 0) { tree[root << 1] += add[root]; tree[root << 1 | 1] += add[root]; add[root << 1] += add[root]; add[root << 1 | 1] += add[root]; add[root] = 0; } } void build(int l, int r, int root, double val) { add[root] = 0; if (l == r) { tree[root] = val * l; return ; } int mid = l + r >> 1; build(l, mid, root << 1, val); build(mid + 1, r, root << 1 | 1, val); push_up(root); } void update(int l, int r, int L, int R, double val, int root) { if (l >= L && r <= R) { tree[root] += val; add[root] += val; return ; } push_down(root); int mid = l + r >> 1; if (L <= mid) { update(l, mid, L, R, val, root << 1); } if (mid < R) { update(mid + 1, r, L, R, val, root << 1 | 1); } push_up(root); } double query(int l, int r, int L, int R, int root) { if (l >= L && r <= R) { return tree[root]; } push_down(root); int mid = l + r >> 1; double res = INF; if (L <= mid) { res = min(query(l, mid, L, R, root << 1), res); } if (R > mid) { res = min(query(mid + 1, r, L, R, root << 1 | 1), res); } return res; } bool check(double c) { build(1, n, 1, c); memset(lastpoint, 0, sizeof(lastpoint)); for (int i = 1; i <= n; i++) { update(1, n, lastpoint[num[i]] + 1, i, 1, 1); lastpoint[num[i]] = i; if (query(1, n, 1, i, 1) <= (i + 1) * c) { return true; } } return false; } double binary_search(double l, double r) { double mid = (r + l) / 2; while (r - l > EPS) { mid = (l + r) / 2; if (check(mid)) { r = mid; } else { l = mid; } } return r; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &num[i]); } printf("%.5lf\n", binary_search(0, 1)); } } /* 1 5 1 2 1 2 3 */

##Lazy Running##

题意： 小Q要跑步，每次从2点开始，至少需要跑K米。所跑的距离分别是d12,d23,d34,d41，就四个点。四条边。可以两点之间来回跑。但是一定在这四条边上。最后一定跑回2点。现在问要满足至少跑K米。那小Q最少需要跑多少米。

思路： 赛后看到Q群某dalao枚举了13种情况过了这题。先%一下。 这题。。真的主要就是要%一下。 我们可以假设。如果小Q乱跑。再跑回2点一共跑了x米。然后发现他并不够。那他可以选择。就靠着2最近的那个点（假设距离为w）。来回跑。跑2w * y次。恰好能满足至少K米 那么对于所有距离我们都可以拆成2w* y + x 那么我们可以假设。dp[i][j % 2w]表示，从2这个点到第i这个点。已经跑了j，然后我们压缩成j % 2w。 也就是dp[i][j % 2w] = min(j, dp[i][j % 2w])。 因为j太大了。但是都改成2w * y + x后。其实都一样。

假设我们一种跑法跑回到2是10，另一种跑法跑回到2是14，离2这个点最近那条边的距离是2 那么他们都可以拆分成4 * 2 + 2，4 * 3 + 2。 那其实对于14的花费。我们只需要再跑一次最近那条边的来回就好了。

所以我们只需要对于整个42w的图。进行一次最短路即可。然后枚举j%2w

#include <bits/stdc++.h> #define MAXN 10 #define ll long long #define mp(a,b) make_pair(a,b) #define INF 1LL << 62 using namespace std; typedef pair<ll, ll> pll; struct node { ll to, w; }; vector<node> vec[MAXN]; priority_queue<pll, vector<pll>, greater<pll> > que; ll dp[MAXN][100000]; ll m; void addEdge(ll u, ll v, ll w) { vec[u].push_back((node){v, w}); vec[v].push_back((node){u, w}); } void init(ll d12, ll d23, ll d34, ll d41) { while (!que.empty()) { que.pop(); } for (int i = 0; i < MAXN; i++) { vec[i].clear(); } for (ll i = 0; i < MAXN; i++) { for (ll j = 0; j < 100000; j++) { dp[i][j] = INF; } } addEdge(1, 2, d12); addEdge(2, 3, d23); addEdge(3, 4, d34); addEdge(4, 1, d41); } void dijskra(ll s) { que.push(mp(0LL, s)); while (!que.empty()) { ll to = que.top().second; ll weight = que.top().first; que.pop(); if (weight > dp[to][weight % m]) { continue; } for (ll i = 0; i < vec[to].size(); i++) { ll dis = vec[to][i].w + weight; ll y = vec[to][i].to; if (dis >= dp[y][dis % m]) { continue; } dp[y][dis % m] = dis; que.push(mp(dis, y)); } } } int main() { int T; scanf("%d", &T); ll d12, d23, d34, d41, k; while (T--) { scanf("%lld %lld %lld %lld %lld", &k, &d12, &d23, &d34, &d41); init(d12, d23, d34, d41); m = 2 * min(d12, d23); ll ans = INF; dijskra(2); for (ll i = 0; i < m; i++) { ll tmp = k - dp[2][i]; if (tmp < 0) { ans = min(ans, dp[2][i]); } else { ans = min(ans, dp[2][i] + tmp / m * m + (tmp % m ? 1 : 0) * m); } } printf("%lld\n", ans); } }

Matching In Multiplication##

题意：题目中给一个二分图，两两边之间有权值。 现在让你求对于每一种完美匹配下。边权相乘后。对于所有情况数的权值之和