临近期末，各种大作业，期末复习啥的，所以上周没怎么训练
这周末有广东省赛，这周要训练一波，不能坑队友
搞起
周一 6.14
poj 3666(线性dp)
以前卡住的几道dp题目都是因为没有观察出一些性质
比如这道题，有一个性质就是由贪心，改变后的数肯定存在于原序列
所以表示前i个数，第i个数的高度是原数组中第j大的高度时的最小值
因为这道题要求高度从小到大，所以可以用另一个数组存一下数组，排个序
转移方程
因为转移方程之和i-1有关，所以可以滚动数组优化空间
#include <cstdio>
#include <algorithm>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 2000 + 10;
int a[N], b[N], n;
ll dp[2][N];ll solve()
{_for(i, 1, n) dp[1][i] = abs(a[1] - b[i]);_for(i, 2, n){ll mi = 1e18;_for(j, 1, n){mi = min(mi, dp[(i - 1) % 2][j]);dp[i % 2][j] = mi + abs(a[i] - b[j]);}}ll res = 1e18;_for(i, 1, n) res = min(res, dp[n % 2][i]);return res;
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]), b[i] = a[i];sort(b + 1, b + n + 1);ll ans = solve();reverse(b + 1, b + n + 1);ans = min(ans, solve());printf("%lld\n", ans);return 0;
}
M-Matrix Problem
昨天校内打了山东省赛
这道题我给了队友A左边全部填1，B右边全部填1的思路
然后队友后来想到了用奇偶。
我给的思路是根据样例来的
而恰好样例就是这个奇偶的思路
真的要研究样例，给了很多提示
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 500 + 10;
int a[N][N];int main()
{int n, m;scanf("%d%d", &n, &m);_for(i, 1, n)_for(j, 1, m)scanf("%1d", &a[i][j]);_for(i, 1, n){_for(j, 1, m){if(j != m && (j == 1 || a[i][j] || i & 1)) printf("1");else printf("0");}puts("");}_for(i, 1, n){_for(j, 1, m){if(j != 1 && (j == m || a[i][j] || !(i & 1))) printf("1");else printf("0");}puts("");}return 0;
}
B.Build Roads
我还是做题比较少
第一次遇见这种特地强调数据随机的题目
数据随机意味着没有一些特意构造的数据卡一些算法
对于这道题来说，数据比较大的时候，就会有比较多的互质的，答案直接就是n - 1
所以小范围数据暴力就好了
比赛的时候我们想到了这个，但是我写暴力的时候gcd(a[i], a[j])写成了gcd(i, j)
坑队友……………………………………
比赛的时候有点紧张了，静态查错没静下来看
吸取教训，写完代码后静下心认真查错，静态查错
我本来是有这个好习惯的，但是因为紧张了就没看得很仔细
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int n, L, R, a[200001], f[200001];
unsigned long long seed;unsigned long long xorshift64()
{unsigned long long x = seed;x ^= x << 13;x ^= x >> 7;x ^= x << 17;return seed = x;
}int gen()
{return xorshift64() % (R - L + 1) + L;
}int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }int find(int x)
{if(f[x] == x)return x;return f[x] = find(f[x]);
}struct node
{int u, v, w;
};
vector<node> Edge;bool cmp(node a, node b)
{return a.w < b.w;
}int main()
{scanf("%d%d%d%llu", &n, &L, &R, &seed);_for(i, 1, n) a[i] = gen();if(L == R){printf("%lld\n", 1LL * (n - 1) * L);return 0;}if(n <= 1000){_for(i, 1, n)_for(j, i + 1, n)Edge.push_back(node{i, j, gcd(a[i], a[j])});sort(Edge.begin(), Edge.end(), cmp);_for(i, 1, n) f[i] = i;long long ans = 0;int cnt = n;for(auto x: Edge){int u = find(x.u), v = find(x.v), w = x.w;if(u != v){ans += w;f[u] = v;if(--cnt == 1) break;}}printf("%lld\n", ans);}else printf("%d\n", n - 1);return 0;
}
J.Ants
最近打了好几场比赛，补一下题
这一场是最近牛客上的四川省赛
这道题比赛的时候我想了一个做法，就是先二分时间，求出刚好撞掉一个挡板的时间
然后根据这个时间求出每个蚂蚁的位置
然后再模拟蚂蚁，这时候就很好弄了，因为只有一个挡板
这个思路是可以做的，但是实际上写起来细节很多，很难调
比赛的时候我告诉主代码手这个思路，最后写了一个小时还是没调出来
我赛后也自己写了，发现挺不好写的，细节好多。
官方做法非常简洁，就是考虑周期
每一个蚂蚁经过2 * len又回到原来的位置，这是一个周期
那么就先把所有重复的部分弄完，然后蚂蚁还是在原来的位置
之后用两个队列模拟这个过程
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e6 + 10;
const int len = 1e9 + 1;
int n, a, b, p[N], d[N];int main()
{scanf("%d%d%d", &n, &a, &b);_for(i, 1, n) scanf("%d", &p[i]);_for(i, 1, n) scanf("%d", &d[i]);int round = min(a, b) / n;a -= round * n; b -= round * n;queue<ll> ql, qr; //队列要开long long_for(i, 1, n) if(!d[i]) ql.push(p[i]);for(int i = n; i >= 1; i--) if(d[i]) qr.push(len - p[i]); //这里要逆序遍历ll mx = 0;while(!ql.empty() || !qr.empty()){if(qr.empty() || !ql.empty() && ql.front() < qr.front()){ll t = ql.front();a--; ql.pop();if(a >= 0) qr.push(t + len);else mx = max(mx, t);}else{ll t = qr.front();b--; qr.pop();if(b >= 0) ql.push(t + len);else mx = max(mx, t);}}printf("%lld\n", mx + 1LL * round * (len * 2)); //注意lLLreturn 0;
}
周三 6.16
L.Spicy Restaurant (bfs)
这题队友告诉我题意的时候他说的无向图，我忽略掉了直接一波树形dp
把其当作树来考虑
最后又意识到是无向图，有非树边
我就想再多一个dfs考虑非树边
后来发现这样是错的，我一开始就走错了。
正解是bfs
注意到w很小只有100
所以可以bfs100次，对于当前辣度，以当前辣度的点为起点开始bfs，处理出
数组d[i][j]表示第i个点距离辣度j的最短距离
思路大致是这样
我一开始写完后T了
要有两个优化
(1)读入优化。这题的输出数据很大，重点是读入的时候询问有1e6了，这都一百万了， 要写个读书优化。好几十万一般都要写读入优化了
(2)提前把d数组处理一下，询问的时候直接输出
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
const int M = 1e2 + 10;
int w[N], d[N][M], n, m, q;
vector<int> g[N];void read(int& x)
{x = 0; char ch = getchar();while(!isdigit(ch)) ch = getchar();while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
}void bfs(int x)
{queue<int> q;_for(i, 1, n)if(w[i] == x){q.push(i);d[i][x] = 0;}while(!q.empty()){int u = q.front(); q.pop();for(int v: g[u]){if(d[v][x] < 1e9) continue;d[v][x] = d[u][x] + 1;q.push(v);}}
}int main()
{read(n); read(m); read(q);_for(i, 1, n) read(w[i]);while(m--){int u, v;read(u); read(v);g[u].push_back(v);g[v].push_back(u);}memset(d, 0x3f, sizeof(d));_for(i, 1, 100) bfs(i);_for(i, 1, n)_for(j, 1, 100)d[i][j] = min(d[i][j], d[i][j - 1]);while(q--){int p, a;read(p); read(a);printf("%d\n", d[p][a] >= 1e9 ? -1 : d[p][a]);}return 0;
}
I-Monster Hunter
这题还是很有东西的
首先答案是单调的，所以就可以二分答案
这样就转化为尽可能贪心，不浪费的去用1 2 3填
这个地方是一个难点
如果没有3的话，先把 >= 2的都模2，还有多的就1也填2
最后再全部填1
这个贪心比较简单
现在考虑3怎么填
总体思路是先填3再填1 2
不浪费的填3，同时使得后面的1和2尽可能不浪费
可以发现填1和2的时候，如果每个数是奇数就容易浪费2，如果是偶数就不容易浪费
所以我们填3的时候要尽可能保持偶数
一.把能填3的奇数都填一个3，化为偶数。也就是大于等于3的奇数都填一个3
二.如果能到这，说明全都是偶数了。为了继续保持偶数，就不能填1个3，需要填2 4 6个3
所以把所有大于等于6的数都尽可能填6（2个3）
三.如果还能到这，剩下的就是1 2 4 还有一些小于等于的0（这部分已经完成了）
接下来继续按照4 2 1依次去填
四.如果这时候还有剩的，就剩下1了。每个1都填一个3即可
填完3之后就转化为填2的情况了
其实这个是一个挺复杂的贪心了，核心的是尽量让填完后的数为偶数
注意要开long long 二分的左端点右端点，mid都要开
我后来发现要开long long，结果mid漏了，调了N久
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e5 + 10;
int a[N], h[N], t[N], s[5], n, m;void put_three(ll cnt)
{_for(i, 1, m)if(t[i] >= 3 && t[i] % 2 == 1){t[i] -= 3;if(--cnt == 0) return;}_for(i, 1, m)if(t[i] >= 6){ll k = min(1LL * t[i] / 6, cnt / 2);t[i] -= k * 6;cnt -= k * 2;if(cnt == 1) break;else if(cnt == 0) return;}sort(t + 1, t + m + 1, greater<int>());_for(i, 1, m){if(t[i] <= 0) break;t[i] -= 3;if(--cnt == 0) return;}_for(i, 1, m){if(t[i] <= 0) break; t[i] -= 3;if(--cnt == 0) return;}
}bool check(ll time)
{ll cnt[5] = {0};_for(i, 1, m) t[i] = h[i];_for(i, 1, 3) cnt[i] = time / n * s[i];time %= n;_for(i, 1, time) cnt[a[i]]++;if(cnt[3]) put_three(cnt[3]);_for(i, 1, m)if(t[i] >= 2) {ll k = min(1LL * t[i] / 2, cnt[2]);t[i] -= k * 2;cnt[2] -= k;if(!cnt[2]) break;}_for(i, 1, m) if(t[i] > 0){if(!cnt[2]) break;t[i] -= 2;cnt[2]--;}_for(i, 1, m)if(t[i] > 0){if(cnt[1] < t[i]) return false;cnt[1] -= t[i];}return true;
}int main()
{int T; scanf("%d", &T);while(T--){memset(s, 0, sizeof(s));scanf("%d", &n);_for(i, 1, n){scanf("%d", &a[i]);s[a[i]]++;}ll sum = 0;scanf("%d", &m);_for(i, 1, m) scanf("%d", &h[i]), sum += h[i];ll l = -1, r = sum;while(l + 1 < r){ll m = l + r >> 1;if(check(m)) r = m;else l = m;}printf("%lld\n", r);}return 0;
}