10.5 周一
国庆浪了好久
其实浪完了我真的不知道要干啥了
这种生活其实是很空虚的
我以前以为算法竞赛占据了我太多时间，没有时间享受其他事情
其实这说明我还不热爱它
这是编程这件事使我的生活变得充实
这也是我感兴趣，有天赋，有前景的东西
为什么不全力以赴呢
找回对编程的热爱，而不是为了保研
想起了我以前看得《驱动力》这本书
现实的利益这样外在驱动力其实是不长久，不稳定的。
真正强大，稳定的驱动力是内在驱动力。
对于我，就是热爱，享受解题的乐趣
我不会花这么多时间在我不热爱的事情
我编程，只因为我爱它
大学找到自己热爱的事情并为之奋斗，是多快乐的事情
接下来三天开启集训模式，自我集训。上午3小时，下午晚上一起3小时。
洛谷 P1080 国王游戏
#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 MAXN = 1e4 + 10;
struct node
{int l, r;
}a[MAXN];bool cmp(node x, node y)
{return x.r * x.l < y.r * y.l;
}struct bignum
{int s[MAXN], len;bignum() { memset(s, 0, sizeof(s)); len = 0; } //初始化
};bignum ma(bignum a, bignum b)
{if(a.len > b.len) return a;if(a.len < b.len) return b;for(int i = a.len; i >= 1; i--){if(a.s[i] > b.s[i]) return a;if(a.s[i] < b.s[i]) return b;}return a;
}bignum operator * (bignum a, int b) //注意这个先乘再进位再位数。不要从0开始弄位数，因为可能中间有0
{int& len = a.len;_for(i, 1, len) a.s[i] *= b;_for(i, 1, len) a.s[i+1] += a.s[i] / 10, a.s[i] %= 10; while(a.s[len+1]){len++; //先加再处理进位 a.s[len+1] += a.s[len] / 10;a.s[len] %= 10;}return a;
}bignum operator / (bignum a, int b) //这种重载运算符的写法非常的爽。同时复习高精度除以低精度，其实不难，自己写个竖式模拟一下就好了
{int yu = 0;bignum res; res.len = a.len;for(int i = a.len; i >= 1; i--){int t = yu * 10 + a.s[i]; //把握好余数 res.s[i] = t / b;yu = t % b;}while(!res.s[res.len] && res.len > 0) res.len--;return res;
}bignum init(int x) //int初始化成bignum
{bignum res;int& len = res.len; //&主要是偷懒，不用写那么长 while(x){len++;res.s[len] = x % 10;x /= 10;}return res;
}void print(bignum x) //输出
{for(int i = x.len; i >= 1; i--) printf("%d", x.s[i]);
}int main()
{ int n, x, y;scanf("%d%d%d", &n, &x, &y);REP(i, 0, n) scanf("%d%d", &a[i].l, &a[i].r);sort(a, a + n, cmp);bignum ans = init(0), sum = init(x);REP(i, 0, n){ans = ma(ans, sum / a[i].r);sum = sum * a[i].l;}print(ans);return 0;
}这题的价值太大了，真的非常锻炼我。独立做出，非常爽。这样的难度刚好
这题有两个难点，一个是如何贪心，一个是如何高精度
贪心方面可以拿两个大臣谁前谁后做个比较来得出
高精度的话，这道题高精度搞懂，以后遇到题目里面有高精度就完全不怂了
其实我大部分时间都在写高精度。以后遇到写个bignum就好
诚实说绿题的难度比较适合我。也就是提高的难度比我水平高一点。多做绿题以及其之前的题
10.6 周二
每天训练结束都问自己有没有独立思考，有没有抄题解
洛谷P2392 kkksc03考前临时抱佛脚
#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 ans, s[10], a[30], sum, res;void dfs(int x, int s, int n)
{if(s > sum / 2) return;res = max(res, s);if(x == n + 1) return;dfs(x + 1, s + a[x], n);dfs(x + 1, s, n);
}int f(int n)
{sum = res = 0;_for(i, 1, n) sum += a[i];dfs(1, 0, n);return sum - res;
}int main()
{scanf("%d%d%d%d", &s[1], &s[2], &s[3], &s[4]);_for(i, 1, 4){_for(j, 1, s[i]) scanf("%d", &a[j]);ans += f(s[i]);//printf("## %d\n", f(s[i]));}printf("%d\n", ans);return 0;
}#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 ans, s[10], a[30], sum, res;int f(int n)
{sum = res = 0;_for(i, 1, n) sum += a[i];REP(k, 0, pow(2, n)){int t = k, now = 0, p = 0;while(t){p++;if(t & 1) now += a[p];t >>= 1;}//printf("## now: %d\n", now);if(now <= sum / 2) res = max(res, now);}return sum - res;
}int main()
{scanf("%d%d%d%d", &s[1], &s[2], &s[3], &s[4]);_for(i, 1, 4){_for(j, 1, s[i]) scanf("%d", &a[j]);ans += f(s[i]);}printf("%d\n", ans);return 0;
}很容易想到最接近一半就行
数组范围小，直接爆搜
后来我试了一下用二进制枚举子集，也可以过，但时间复杂度要多乘一个n
这道题还可以用01背包，不过太久我已经忘记，以后会复习动态规划的
洛谷 P1443 马的遍历
#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 MAXN = 500;
struct node{ int x, y; };
int Map[MAXN][MAXN], n, m, sx, sy;
int dir[8][2] = {1, 2, 1, -2, -1, 2, -1, -2, 2, 1, 2, -1, -2, 1, -2, -1};void bfs()
{memset(Map, -1, sizeof(Map));Map[sx][sy] = 0;queue<node> q;q.push(node{sx, sy});while(!q.empty()){node u = q.front(); q.pop();REP(i, 0, 8){int x = u.x + dir[i][0], y = u.y + dir[i][1];if(Map[x][y] != -1 || x < 1 || x > n || y < 1 || y > m) continue;Map[x][y] = Map[u.x][u.y] + 1;q.push(node{x, y});}}
}int main()
{scanf("%d%d%d%d", &n, &m, &sx, &sy);bfs();_for(i, 1, n){_for(j, 1, m)printf("%-5d", Map[i][j]);puts("");}return 0;
}复习bfs
洛谷 P1135 奇怪的电梯
#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 MAXN = 250;
int step[MAXN], k[MAXN], n, a, b, s[2] = {1, -1};void bfs()
{memset(step, -1, sizeof(step));step[a] = 0;queue<int> q;q.push(a);while(!q.empty()){int u = q.front(); q.pop();REP(i, 0, 2){int v = u + k[u] * s[i];if(v < 1 || v > n || step[v] != -1) continue;step[v] = step[u] + 1;if(v == b) return;q.push(v);}}
}int main()
{scanf("%d%d%d", &n, &a, &b);_for(i, 1, n) scanf("%d", &k[i]); bfs();printf("%d\n", step[b]);return 0;
}bfs可以用来解决像这样a到b最短需要多少步的题目。这是bfs的优势所在，因为第一个搜到的一定是最短的
复习的速度比我想的要快
争取在寒假前把自己以前比较熟悉的部分全部掌握，加油
复习一二维前缀和差分
这个博客写的很好前缀和与差分
一维前缀和
支持O（1）查询[l,r]的和
#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 MAXN = 100;
int a[MAXN], n, s[MAXN];int main()
{scanf("%d", &n);_for(i, 1, n){scanf("%d", &a[i]);s[i] = s[i-1] + a[i];}while(1){int l, r;scanf("%d%d", &l, &r);printf("%d\n", s[r] - s[l-1]);}return 0;
}一维差分
支持O（1）使[l,r]上加上一个p，最后输出每一个元素
#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 MAXN = 100;
int a[MAXN], n, d[MAXN];int main()
{scanf("%d", &n);_for(i, 1, n){scanf("%d", &a[i]);d[i] = a[i] - a[i-1];}while(1){int l, r, p;scanf("%d%d%d", &l, &r, &p);if(l == 0 && r == 0) break;d[l] += p; d[r+1] -= p;}_for(i, 1, n) d[i] += d[i-1];_for(i, 1, n) printf("%d ", d[i]); return 0;
}二维前缀和
#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 MAXN = 100;
int a[MAXN][MAXN], s[MAXN][MAXN], n, m;int main()
{scanf("%d%d", &n, &m);_for(i, 1, n)_for(j, 1, m){scanf("%d", &a[i][j]);s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];}while(1){int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);printf("%d\n", s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]);}return 0;
}二维差分
d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
洛谷 P3397 地毯
#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 MAXN = 1e3 + 10;
int d[MAXN][MAXN], n, m;int main()
{scanf("%d%d", &n, &m);while(m--){int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);d[x1][y1]++;d[x1][y2+1]--;d[x2+1][y1]--;d[x2+1][y2+1]++;}_for(i, 1, n){_for(j, 1, n){d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1]; printf("%d ", d[i][j]);}puts("");}return 0;
}
洛谷 P1551 亲戚
#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 MAXN = 5000 + 10;
int f[MAXN], n, m, p;int find(int x)
{if(f[x] == x) return x;return f[x] = find(f[x]);
}void Union(int x, int y) { f[find(x)] = find(y); }int main()
{scanf("%d%d%d", &n, &m, &p);_for(i, 1, n) f[i] = i;while(m--){int x, y;scanf("%d%d", &x, &y);Union(x, y);}while(p--){int x, y;scanf("%d%d", &x, &y);if(find(x) == find(y)) puts("Yes");else puts("No");}return 0;
}复习并查集。并查集代码好短，也很好理解，用来做集合的问题
洛谷 P1102 A-B 数对
#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 MAXN = 2e5 + 10;
int a[MAXN], n, c;
map<int, int> s;int main()
{scanf("%d%d", &n, &c);_for(i, 1, n){scanf("%d", &a[i]);s[a[i]+c]++;}long long ans = 0;_for(i, 1, n) ans += s[a[i]];printf("%lld\n", ans);return 0;
}复习了map，一次操作复杂度logn
大致规划
整个10月，接下来复习树状数组线段树，图论，数学，杂项
11月复习动态规划
12月1月大量刷题，刷绿题
10.7 周三
洛谷 P3374 【模板】树状数组 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 MAXN = 5e5 + 10;
int c[MAXN], n, m;int lowbit(int x) { return x & (-x); }void add(int x, int p)
{while(x <= n){c[x] += p;x += lowbit(x);}
}int s(int x)
{int res = 0;while(x){res += c[x];x -= lowbit(x);}return res;
}int sum(int x, int y) { return s(y) - s(x-1); }int main()
{int k, x, y;scanf("%d%d", &n, &m);_for(i, 1, n){scanf("%d", &x);add(i, x);}while(m--){scanf("%d%d%d", &k, &x, &y);if(k == 1) add(x, y);else printf("%d\n", sum(x, y));}return 0;
}复习树状数组。单点修改，区间查询
洛谷 P3368 【模板】树状数组 2
#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 MAXN = 5e5 + 10;
int c[MAXN], n, m;int lowbit(int x) { return x & (-x); }void add(int x, int p)
{while(x <= n){c[x] += p;x += lowbit(x);}
}int sum(int x)
{int res = 0;while(x){res += c[x];x -= lowbit(x);}return res;
}int main()
{int k, x, y, t = 0;scanf("%d%d", &n, &m);_for(i, 1, n){scanf("%d", &x);add(i, x - t);t = x;}while(m--){scanf("%d", &k);if(k == 1) {scanf("%d%d%d", &x, &y, &t);add(x, t); add(y + 1, -t);}else{scanf("%d", &x);printf("%d\n", sum(x));}}return 0;
}区间修改，单点查询。用差分转化一下就好了
二维树状数组也挺简单，也是支持单点修改区间查询，区间修改，单点查询
#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e4;
int f[MAXN][MAXN], n, m, p;inline int lowbit(int x) { return x & (-x); }inline void add(int x, int y, int q)
{while(x <= n){for(int i = y; i <= m; i += lowbit(i)) //注意for循环的写法 f[x][i] += q;x += lowbit(x); }
}inline int sum(int x, int y)
{int res = 0;while(x){for(int i = y; i; i -= lowbit(i))res += f[x][i];x -= lowbit(x);}return res;
}inline int ans(int x1, int y1, int x2, int y2)
{ return sum(x1, y1) + sum(x2-1, y2-1) - sum(x1, y2 - 1) - sum(x2 - 1, y1);
}int main()
{scanf("%d%d%d", &n, &m, &p);_for(i, 1, n) _for(j, 1, m){int x; scanf("%d", &x);add(i, j, x);}while(p--){int k, x, y, q, a, b;scanf("%d%d%d", &k, &x, &y);if(k == 1) scanf("%d", &q), add(x, y, q);else {scanf("%d%d", &a, &b);printf("%d\n", ans(a, b, x, y));}}return 0;
}洛谷 P3397 地毯
#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 MAXN = 1e3 + 10;
int c[MAXN][MAXN], n, m, k;int lowbit(int x) { return x & (-x); }int add(int x, int y, int p)
{while(x <= n){for(int i = y; i <= m; i += lowbit(i))c[x][i] += p; x += lowbit(x);}
}int sum(int x, int y)
{int res = 0;while(x){for(int i = y; i; i -= lowbit(i))res += c[x][i];x -= lowbit(x);}return res;
}void updata(int x1, int y1, int x2, int y2)
{add(x1, y1, 1); add(x1, y2+1, -1); add(x2+1, y1, -1); add(x2+1, y2+1, 1);
}int main()
{scanf("%d%d", &n, &k); m = n;while(k--){int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);updata(x1, y1, x2, y2);}_for(i, 1, n){_for(j, 1, n)printf("%d ", sum(i, j));puts("");}return 0;
}
洛谷 P1908 逆序对
#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 MAXN = 5e5 + 10;
int c[MAXN], a[MAXN], b[MAXN], n;void read(int& x)
{int sign = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') sign = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= sign;
}int lowbit(int x) { return x & -x; }void add(int x, int p)
{while(x <= MAXN){c[x] += p;x += lowbit(x);}
}int sum(int x)
{int res = 0;while(x){res += c[x];x -= lowbit(x);}return res;
}int main()
{scanf("%d", &n);REP(i, 0, n) read(b[i]), a[i] = b[i];sort(b, b + n);int t = unique(b, b + n) - b;REP(i, 0, n) a[i] = lower_bound(b, b + t, a[i]) - b + 1;ll ans = 0;REP(i, 0, n){ans += i - sum(a[i]);add(a[i], 1);}printf("%lld\n", ans);return 0;
}独立做出，爽！
学到了蛮多
一 是复习了读入优化
二 我做道题时很快就想到了树状数组的解法。但是1e9空间显然会炸。于是我用了map，因为map一次操作是logn，所以超时了50分
后来我就想到了离散化，因为只有大小关系有价值，绝对大小没有价值
离散化有两种方法，我用的是存在另外一个数组，排序去重，然后用原来的数组二分找出。
还可以用结构体的方法，但是结构体的离散化不能去重，也就是说如果有重复的元素，绝对大小相同的会赋予不同的值。这种情况需要额外处理。
洛谷 P3372 【模板】线段树 1
#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) ((k << 1) + 1)
#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 MAXN = 1e5 + 10;
struct node
{ll f, w;int l, r;int len() { return r - l + 1; }int m() { return (l + r) >> 1; }
}t[MAXN << 2];void lazy(int k, ll p) { t[k].f += p; t[k].w += t[k].len() * p; }void up(int k) { t[k].w = t[l(k)].w + t[r(k)].w; }void down(int k)
{lazy(l(k), t[k].f);lazy(r(k), t[k].f);t[k].f = 0;
}void build(int k, int l, int r)
{t[k].l = l; t[k].r = r; t[k].f = 0;if(l == r){scanf("%lld", &t[k].w);return;}int m = t[k].m();build(l(k), l, m);build(r(k), m + 1, r);up(k);
}void add(int k, int x, ll p)
{if(t[k].len() == 1){t[k].w += p;return;}if(t[k].f) down(k);int m = t[k].m();if(x <= m) add(l(k), x, p);else add(r(k), x, p);up(k);
}void change(int k, int L, int R, ll p)
{if(L <= t[k].l && t[k].r <= R){lazy(k, p);return;}if(t[k].f) down(k);int m = t[k].m();if(L <= m) change(l(k), L, R, p);if(R > m) change(r(k), L, R, p);up(k);
}ll sum(int k, int L, int R)
{if(L <= t[k].l && t[k].r <= R) return t[k].w;if(t[k].f) down(k);ll res = 0;int m = t[k].m();if(L <= m) res += sum(l(k), L, R);if(R > m) res += sum(r(k), L, R);return res;
}int main()
{int n, m, q, x, y, k;scanf("%d%d", &n, &m);build(1, 1, n);while(m--){scanf("%d%d%d", &q, &x, &y);if(q == 1){scanf("%d", &k);change(1, x, y, k);}else printf("%lld\n", sum(1, x, y));}return 0;
}线段树复习。这个代码量挺大的。今明两天每次做线段树题都从头开始打代码。
10.9 周五
加油，今天把线段树复习完
每道难题至少想两三个小时，在想的过程中进步
线段树每个数乘一个x的操作想半天想不出
停一下，复习一下快速幂
理解本质，其实就是b化为二进制而已
#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 cal(int a, int b, int p)
{int res = 1 % p; a %= p;while(b){if(b & 1) res = res * a % p;b >>= 1;a = a * a % p; }return res;
}int main()
{int a, b, p;scanf("%d%d%d", &a, &b, &p);printf("%d\n", cal(a, b, p));return 0;
}复习Floyd模板。可以用来找最小权值环和判断连通性
_for(i, 1, n)_for(j, 1, n)f[i][j] = (i == j ? 0 : 1e9)_for(k, 1, n)_for(i, 1, n)_for(j, 1, n)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);复习堆优化dijstra。复杂度mlogn 只能用于没有负权边的情况
#include<bits/stdc++.h>
#define pb push_back
#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 MAXN = 1e4 + 10;
struct node
{int v, w;bool operator < (const node& rhs) const{return w > rhs.w;}
};
vector<node> g[MAXN];
int d[MAXN], n, m, s;void work()
{_for(i, 1, n) d[i] = 1e9; d[s] = 0;priority_queue<node> q;q.push(node{s, 0});while(!q.empty()){node x = q.top(); q.pop();int u = x.v;if(d[u] != x.w) continue;REP(i, 0, g[u].size()){int v = g[u][i].v, w = g[u][i].w;if(d[v] > d[u] + w){d[v] = d[u] + w;q.push(node{v, d[v]});}}}
}int main()
{scanf("%d%d%d", &n, &m, &s);while(m--){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].pb(node{v, w});}work();_for(i, 1, n) {if(d[i] == 1e9) d[i] = (1 << 31) - 1;printf("%d ", d[i]);}return 0;
}spfa，有负权边的情况
#include<bits/stdc++.h>
#define pb push_back
#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 MAXN = 1e4 + 10;
struct node { int v, w; };
vector<node> g[MAXN];
int d[MAXN], vis[MAXN], n, m, s;void work()
{_for(i, 1, n) d[i] = 1e9; d[s] = 0;queue<int> q;q.push(s); vis[s] = 1;while(!q.empty()){int u = q.front(); q.pop();vis[u] = 0;REP(i, 0, g[u].size()){int v = g[u][i].v, w = g[u][i].w;if(d[v] > d[u] + w){d[v] = d[u] + w;if(!vis[v]){q.push(v);vis[v] = 1;}}}}
}int main()
{scanf("%d%d%d", &n, &m, &s);while(m--){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].pb(node{v, w});}work();_for(i, 1, n) {if(d[i] == 1e9) d[i] = (1 << 31) - 1;printf("%d ", d[i]);}return 0;
}
洛谷 P1629 邮递员送信
卡了好久
其实很快就想到了建反图
但是想不清楚觉得没用
后来我在纸上随便画了一下发现画反图就是答案
所以一定一定要在草稿纸上画图，把脑子里的想法形象化，清晰化
#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 MAXN = 1e3 + 10;
struct node
{int v, w;bool operator < (const node& rhs) const {return w > rhs.w;}
};
vector<node> g[MAXN], k[MAXN];
int d[MAXN], n, m;void work1()
{_for(i, 1, n) d[i] = 1e9; d[1] = 0;priority_queue<node> q;q.push({1, 0});while(!q.empty()){node x = q.top(); q.pop();int u = x.v;if(d[u] != x.w) continue;REP(i, 0, g[u].size()){int v = g[u][i].v, w = g[u][i].w;if(d[v] > d[u] + w){d[v] = d[u] + w;q.push(node{v, d[v]});}}}
}void work2()
{_for(i, 1, n) d[i] = 1e9; d[1] = 0;priority_queue<node> q;q.push({1, 0});while(!q.empty()){node x = q.top(); q.pop();int u = x.v;if(d[u] != x.w) continue;REP(i, 0, k[u].size()){int v = k[u][i].v, w = k[u][i].w;if(d[v] > d[u] + w){d[v] = d[u] + w;q.push(node{v, d[v]});}}}
}int main()
{scanf("%d%d", &n, &m);while(m--){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].push_back(node{v, w});k[v].push_back(node{u, w});}int ans = 0;work1(); _for(i, 2, n) ans += d[i];work2(); _for(i, 2, n) ans += d[i];printf("%d\n", ans);return 0;
}10.10 周六
今天怒干支持每一个数支持乘法的线段树，灵光一闪有了突破的进展，但交上去只有30分，但比0分好多了
然后实在不知错哪里，就放一放
复习了一下最小生成树
生成树就是用n-1条边联通
Kruskal其实很简单
贪心，边权从小到大连，能连就连
#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 MAXN = 5e3 + 10;
struct node
{int u, v, w;bool operator < (const node& rhs) const{return w < rhs.w;}
};
vector<node> Edge;
int f[MAXN], n, m;int find(int x)
{if(f[x] == x) return x;return f[x] = find(f[x]);
}int main()
{scanf("%d%d", &n, &m);while(m--){int u, v, w;scanf("%d%d%d", &u, &v, &w);Edge.push_back(node{u, v, w});}_for(i, 1, n) f[i] = i;sort(Edge.begin(), Edge.end());int ans = 0, cnt = 0;REP(i, 0, Edge.size()){int u = find(Edge[i].u), v = find(Edge[i].v);if(u != v){f[u] = v;ans += Edge[i].w;cnt++;}}if(cnt != n - 1) puts("orz");else printf("%d\n", ans);return 0;
}
明天刚线段树那道题以及最小生成树的一些题目
加油
10.11 周日
洛谷 p1194 买礼物
为何要用最小生成树呢
贪心加边，加完为止，这个过程就是最小生成树
我写完交上去90分
后来想到会不会kij还大于a，然后建边处理了一下，就ac了
其实这组数据加的毫无必要，因为这组数据不符合题意，题目说了很清楚是优惠，就不可能存在这种情况
#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 MAXN = 1e3 + 10;
struct node
{int u, v, w;bool operator < (const node& rhs) const{return w < rhs.w;}
};
vector<node> Edge;
int f[MAXN], a, n, cnt, ans;int find(int x)
{if(f[x] == x) return x;return f[x] = find(f[x]);
}int main()
{scanf("%d%d", &a, &n);_for(i, 1, n) f[i] = i;_for(i, 1, n)_for(j, 1, n){int w; scanf("%d", &w);if(w != 0 && j > i && w <= a) Edge.push_back(node{i, j, w});}cnt = n;sort(Edge.begin(), Edge.end());REP(i, 0, Edge.size()){int u = find(Edge[i].u), v = find(Edge[i].v);if(u != v){f[u] = v;ans += Edge[i].w;cnt--; }}ans += cnt * a;printf("%d\n", ans); return 0;
} p1991 无线通讯网
二分+最小生成树
审题时看到最大值最小或最小值最大要想到二分答案
注意逆向思考，有时反过来想就对了
#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 MAXN = 1e3 + 10;
struct node
{int u, v;double w;bool operator < (const node& rhs) const{return w < rhs.w;}
};
vector<node> Edge, ans;
int f[MAXN], vis[MAXN], k, n;
double x[MAXN], y[MAXN];int find(int x)
{if(f[x] == x) return x;return f[x] = find(f[x]);
}double dist(int a, int b)
{return sqrt(pow(x[a]-x[b], 2) + pow(y[a]-y[b], 2));
}bool check(double key)
{_for(i, 1, n) f[i] = i;memset(vis, 0, sizeof(vis));int cnt = 0;REP(i, 0, Edge.size()){int u = find(Edge[i].u), v = find(Edge[i].v);if(u != v){f[u] = v;if(Edge[i].w > key){cnt += !vis[u] + !vis[v];vis[u] = vis[v] = 1;}}}return cnt <= k;
}int main()
{scanf("%d%d", &k, &n);_for(i, 1, n) scanf("%lf%lf", &x[i], &y[i]);_for(i, 1, n)_for(j, i + 1, n) Edge.push_back(node{i, j, dist(i, j)});sort(Edge.begin(), Edge.end());double l = 0, r = 2e4;while(l + 1e-4 < r){double mid = (l + r) / 2;if(!check(mid)) l = mid;else r = mid;}printf("%.2lf\n", r);return 0;
}