多校联合训练
hdu 6067 6068 6069 6070 6071 6072 6073 6074 6075 6076 6077 6078 6079
##Counting Divisors##
一道全场一个钟后。从第3面一直排到第15面一直在怼的题。。lcy老师表示这道题很有区分度
题意：求公式所得的答案。。就是求[l,r]这个范围内枚举的i， i k i{^k} ik的因子数之和。
看到这种公式题第一感觉是。有规律。
所以。。跟hovees打表看了一个钟。
然后又推推推。最后发现对于一个数。他所作的贡献是他的每一个质因子数+1的积。
对于这个数的k次方。则是。每一个质因子数*k+1的积。
然后找出了大数因数分解的板。看了看时间是6000ms感觉可以试试n 5 / 4 ^{5/4} 5/4卡卡过了。。
结果就是。并不行。。然后绝望到放弃
思路：用素数筛的原理，作区间筛（Q神叫法）。
对于一个数r，我们可以用 r \sqrt{r} r?把[1,r]的合数都筛掉。
那么对于[l,r]我们每次只需要去枚举 r \sqrt{r} r?内所有素数。就可以把对于这个区间内每一个数可以做的贡献计算出来。筛到最后。数依然是素数的。他们所做的贡献为k+1，乘起来就好了。
orz学习到了区间筛（其实就是素数筛。。自己不会撸而已）
#include <bits/stdc++.h>#define MAXN 1000005
#define ll long long
#define MOD 998244353using 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们教育了一把分数划分。
题意：给一个序列要找一段区间，使得区间内不同种类的数量/区间长度最小。也就是 m i n ( s i z e ( l , r ) r ? l + 1 ) min(\frac{size(l,r)}{r - l + 1}) min(r?l+1size(l,r)?)
思路：
我们不妨假设一个分数c他满足。 m i n ( s i z e ( l , r ) r ? l + 1 ) > = c min(\frac{size(l,r)}{r - l + 1})>=c min(r?l+1size(l,r)?)>=c
将这个不等式转换一下
变成 s i z e ( l , r ) + l ? c > = ( r + 1 ) ? c size(l,r) + l * c >= (r + 1) * c size(l,r)+l?c>=(r+1)?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-6using 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 << 62using 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##
题意：题目中给一个二分图，两两边之间有权值。
现在让你求对于每一种完美匹配下。边权相乘后。对于所有情况数的权值之和%998244353。思路：对于每一条度为1的边，他们所做的贡献肯定是固定的。所以可以通过拓扑直接提出来倍数。
剩下的边组成的每张图，连着的边，肯定不在同一个完美匹配里。可以分开计算，最多只会出现两种匹配方式。dfs一次即可。
然后再将每个图计算出来的贡献组合一下即可。
这里要注意。每一个点要对应两个点。一共30000个点，要相互连接，需要2 * 2 * 30000条边。
#include <bits/stdc++.h>#define MAXN 300005
#define MOD 998244353
#define ll long long
#define DIS 300000using namespace std;struct edge {int nxt, to;ll w;bool mark;
}e[MAXN << 2];queue<int> que;
int du[MAXN + DIS];
bool mark[MAXN + DIS];
int head[MAXN + DIS];
int n, cnt;
ll part[2];void addEdge(int u, int v, ll w) {e[++cnt].nxt = head[u];e[cnt].to = v;e[cnt].w = w;e[cnt].mark = false;head[u] = cnt;
}void init() {memset(mark, false, sizeof(mark));memset(head, -1, sizeof(head));memset(du, 0, sizeof(du));cnt = 1;while (!que.empty()) {que.pop();}
}ll topol() {ll res = 1;for (int i = DIS; i <= n + DIS; i++) {if (du[i] == 1) {que.push(i);mark[i] = true;}}while (!que.empty()) {int u = que.front();mark[u] = true;que.pop();for (int i = head[u]; ~i; i = e[i].nxt) {if (e[i].mark) {continue;}e[i].mark = e[i ^ 1].mark = 1;mark[e[i].to] = true;(res *= e[i].w) %= MOD;for (int j = head[e[i].to]; ~j; j = e[j].nxt) {e[j].mark = e[j ^ 1].mark = true;du[e[j].to]--;if (du[e[j].to] == 1) {que.push(e[j].to);}}}}return res;
}void dfs(int u, int idx) {mark[u] = true;for (int i = head[u]; ~i; i = e[i].nxt) {if (!e[i].mark) {
// printf("from %d to %d %d\n", u, e[i].to, idx);e[i].mark = e[i ^ 1].mark = true;(part[idx] *= e[i].w) %= MOD;dfs(e[i].to, idx ^ 1);}}
}int main() {int T, v;ll w;scanf("%d", &T);while (T--) {init();scanf("%d", &n);for (int i = 1; i <= n; i++) {for (int j = 1; j <= 2; j++) {scanf("%d %lld", &v, &w);addEdge(i, v + DIS, w);addEdge(v + DIS, i, w);du[i]++;du[v + DIS]++;}}ll ans = topol();for (int i = 1; i <= n; i++) {if (!mark[i]) {part[0] = part[1] = 1;dfs(i, 0);(ans *= (part[0] + part[1]) % MOD) %= MOD;}}printf("%lld\n", ans);}
}
##Questionnaire##
题意：给n个数。需要你给出一个数m和k。使得这n个数%m==k的数目最多。
思路：m就取2就好了。如果奇数多k取1，奇数少k取0
orz为数不多的水题啊。
#include <bits/stdc++.h>using namespace std;int main() {int T, n, tmp;scanf("%d", &T);while (T--) {scanf("%d", &n);int cnt = 0;for (int i = 0; i < n; i++) {scanf("%d", &tmp);if (tmp & 1) {cnt++;}}printf("2 %d\n", cnt >= n - cnt ? 1 : 0);}
}
##Time To Get Up##
到这里了，是不是可以说。按图模拟即可。打张表花式过就好了
#include <bits/stdc++.h>#define MAXN 100using namespace std;int res[10][10] = {
{1, 2, 3, 5, 6, 7, 0, 0, 0, 0}, {3, 6, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 3, 4, 5, 7, 0, 0, 0, 0, 0}, {1, 3, 4, 6, 7, 0, 0, 0, 0, 0},{2, 3, 4, 6, 0, 0, 0, 0, 0, 0}, {1, 2, 4, 6, 7, 0, 0, 0, 0, 0}, {1, 2, 4, 5, 6, 7, 0, 0, 0, 0},{1, 3, 6, 0, 0, 0, 0, 0, 0, 0}, {1, 2, 3, 4, 5, 6, 7, 0, 0, 0}, {1, 2, 3, 4, 6, 7, 0, 0, 0, 0}};int graph[10];
char mapp[MAXN][MAXN];int sul[][2] = {0, 1, 1, 0, 1, 3, 3, 1, 4, 0, 4, 3, 6, 1};bool judge(int x, int y) {return mapp[x][y] == 'X';
}void init() {for (int i = 0; i < 10; i++) {for (int j = 0; j < 10; j++) {if (res[i][j]) {graph[i] += (1 << res[i][j]);}}}
}int getAns(int l) {int ans = 0;for (int i = 0; i < 7; i++) {if (judge(sul[i][0], sul[i][1] + l)) {ans += (1 << (i + 1));}}for (int i = 0; i < 10; i++) {if (graph[i] == ans) {return i;}}
}int main() {int T;scanf("%d", &T);getchar();init();while (T--) {for (int i = 0; i < 7; i++) {scanf("%s", &mapp[i]);}printf("%d%d:%d%d\n", getAns(0), getAns(5), getAns(12), getAns(17));}
}
##Wavel Sequence##
题意：
给两个序列a，b，需要你找出这两个序列中的公共子序列，且这个公共序列需要成波浪状。
也就是需要新创造出来的c序列满足 c 1 < c 2 > c 3 < c 4 > . . . c n c_1 < c_2 > c_3 < c_4 > ... c_n c1?<c2?>c3?<c4?>...cn?
必须以谷底开头，可以以谷峰或者谷底结束
思路：
其实很容易看出来是dp，状态也很好找出来
当a[i] == b[j]时
对于到了a串i点，b串j点，为谷峰的情况数为 d p [ i ] [ j ] [ 1 ] = ∑ k = 0 i ∑ l = 0 j d p [ k ] [ l ] [ 0 ] dp[i][j][1] = \sum_{k = 0}^{i}\sum_{l= 0}^{j}dp[k][l][0] dp[i][j][1]=∑k=0i?∑l=0j?dp[k][l][0]
对于到了a串i点，b串j点，为谷底的情况数为 d p [ i ] [ j ] [ 0 ] = ∑ k = 0 i ∑ l = 0 j d p [ k ] [ l ] [ 1 ] dp[i][j][0] = \sum_{k = 0}^{i}\sum_{l= 0}^{j}dp[k][l][1] dp[i][j][0]=∑k=0i?∑l=0j?dp[k][l][1]
但是这个时间复杂度是 n 2 ? m 2 n^2*m^2 n2?m2是远远不够的。我们需要优化一下
对于a[i] == b[j]时，若存在某k < i && l < j 满足 a[k] == b[l] 那么从 1 → i 1 \rightarrow i 1→i 和 1 → j 1 \rightarrow j 1→j
的数肯定已经统计过了。我们只需要统计 ∑ p = k + 1 i ∑ p = l + 1 j \sum_{p = k + 1}^{i}\sum_{p = l + 1}^{j} ∑p=k+1i?∑p=l+1j?
那么我们只需要用两个数组进行前缀和，直接获取答案即可。
而且我们可以减少一个维度。
只对dp[j][0]和dp[j][1]进行dp。 因为i和j不会相互影响，且外层枚举了i，无论i到哪里都可以把i当成固定的。
然后再用sum[j][0]和sum[j][1]分别表示，b串到第j位时，为谷底/谷峰已经有了多少种情况。
然后对于当前a[i]如果b[j]比他大，那么他一定是从b[j]往前的谷峰来的，反之同理。
#include <bits/stdc++.h>#define MAXN 2005
#define MOD 998244353
#define ll long longusing namespace std;int a[MAXN], b[MAXN];
int sum[MAXN][2];
int dp[MAXN][2];int main() {int T, n, m;scanf("%d", &T);while (T--) {memset(sum, 0, sizeof(sum));memset(dp, 0, sizeof(dp));scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}for (int i = 1; i <= m; i++) {scanf("%d", &b[i]);}ll cnt1, cnt0, ans = 0;for (int i = 1; i <= n; i++) {cnt0 = 0, cnt1 = 1; //cnt0记录从谷峰来的，cnt1记录从谷底来的 for (int j = 1; j <= m; j++) {dp[j][0] = dp[j][1] = 0;if (a[i] == b[j]) {dp[j][0] += cnt1;dp[j][1] += cnt0;(ans += (cnt1 + cnt0)) %= MOD;} else if (a[i] > b[j]) {(cnt0 += sum[j][0]) %= MOD;} else {(cnt1 += sum[j][1]) %= MOD;}}for (int j = 1; j <= m; j++) {(sum[j][0] += dp[j][0]) %= MOD;(sum[j][1] += dp[j][1]) %= MOD;}}printf("%lld\n", ans);}
}