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;
}
