2020.12.03(1)
[Huge 1
]
(RP)爆涨
刚刚把(T4)讲了一下
好久没有上黑板讲题了对吧
感觉开心极了
明天就要出征啦
早晨得知上午要核酸检测
下午考试
晚上整理
在ff的求助下被迫写了一道数论推柿子
感觉针不戳
天气还是蛮冷的
零下四度的样子
有白霜，哈气成雾
查了一下秦皇岛零下六度，，，，
换衣服
中午回去收拾一下
17745940319
2020.12.02(2)
[Huge 2
]
下雪了～
2020.12.01(3)
[Huge 3
]
这个阶段也结束了
自从开始集训
几乎没拿过脸
这最后了可好
一下俩脸
操作拉满
(RP)爆炸
这叫——土块
没想到没想到
不过现在好像也没有最一开始得到脸或者没有脸的高兴或是失落了
都不重要了
有很多话想说
但是现在还不是时候
控制住自己的情绪
别波动太大
还有三天的时间
压制住自己
一定要控制
别放松
静下来稳一点
开始调整心态，培养考试状态
安安稳稳的比啥都强
(RP++)
妈呀，转眼就十二月了
好快
感觉(CSP)刚过，(NOIP)就要来了
这两天，状态挺稳定的吧
没啥起伏好像
保持就行保持就行
2020.11.29(6)
[Huge 6
]
划水更新
2020.11.25(8)
[Huge 8
]
下午一个树剖+两个线段树写了一下午
第一次打
感觉真不戳
码量(220)行
纪念一下
整整齐齐
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define ls (u << 1)
#define rs (ls | 1)
#define max(a, b) ({register int AA = a, BB = b; AA > BB ? AA : BB;})
#define min(a, b) ({register int AA = a, BB = b; AA < BB ? AA : BB;})
using namespace std;
inline int read(){
int x = 0, w = 1;
char ch = getchar();
for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
const int ss = 1000010;
struct node{
int from, to, nxt, w, id;
inline bool operator < (const node &x) const {
return x.w > w;
}
}edge[ss << 1], g[ss];
int head[ss], tot;
inline void add(register int u, register int v, register int w){
edge[++tot].to = v;
edge[tot].nxt = head[u];
edge[tot].w = w;
head[u] = tot;
}
int ff[ss];
inline int find(register int x){
return ff[x] == x ? x : ff[x] = find(ff[x]);
}
bool vis[ss];
int sum, n, m, cnt;
inline void kruskal(){
for(register int i = 1; i <= n; i++)
ff[i] = i;
sort(g + 1, g + 1 + m);
for(register int i = 1; i <= m; i++){
register int x = g[i].from;
register int y = g[i].to;
x = find(x), y = find(y);
if(x == y) continue;
ff[y] = x;
sum += g[i].w;
add(g[i].from, g[i].to, g[i].w);
add(g[i].to, g[i].from, g[i].w);
cnt++;
vis[g[i].id] = 1;
if(cnt == n - 1) break;
}
}
int fa[ss], dep[ss], size[ss], son[ss];
inline void dfs(register int u, register int f){
size[u] = 1;
fa[u] = f;
for(register int i = head[u]; i; i = edge[i].nxt){
register int v = edge[i].to;
if(v == f) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
}
int dfn[ss], top[ss], tim, val[ss];
inline void dfs(register int u, register int t, register int w){
top[u] = t;
dfn[u] = ++tim;
val[tim] = w;
if(son[u]){
for(register int i = head[u]; i; i = edge[i].nxt){
register int v = edge[i].to;
if(v == son[u]){
dfs(v, t, edge[i].w);
break;
}
}
}
for(register int i = head[u]; i; i = edge[i].nxt){
register int v = edge[i].to;
if(v != fa[u] && v != son[u])
dfs(v, v, edge[i].w);
}
}
int tr[ss], lazy[ss];
inline void build(register int u, register int l, register int r){
if(l == r){
tr[u] = val[l];
return;
}
register int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
tr[u] = max(tr[ls], tr[rs]);
}
inline int query(register int u, register int l, register int r, register int s, register int t){
if(s <= l && t >= r) return tr[u];
register int mid = l + r >> 1;
if(t <= mid) return query(ls, l, mid, s, t);
if(s > mid) return query(rs, mid + 1, r, s, t);
return max(query(ls, l, mid, s, t), query(rs, mid + 1, r, s, t));
}
inline int Query(register int u, register int v){
register int res = 0;
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);
res = max(res, query(1, 1, n, dfn[top[u]], dfn[u]));
u = fa[top[u]];
}
if(u == v) return res;
if(dep[u] > dep[v]) swap(u, v);
res = max(res, query(1, 1, n, dfn[u] + 1, dfn[v]));
return res;
}
inline void build_tr(register int u, register int l, register int r){
tr[u] = 1000000000;
lazy[u] = -1;
if(l == r) return;
register int mid = l + r >> 1;
build_tr(ls, l, mid);
build_tr(rs, mid + 1, r);
}
inline void update(register int u, register int w){
tr[u] = min(tr[u], w);
if(lazy[u] == -1) lazy[u] = w;
else lazy[u] = min(lazy[u], w);
}
inline void pushdown(register int u){
if(lazy[u] == -1) return;
update(ls, lazy[u]);
update(rs, lazy[u]);
lazy[u] = -1;
}
inline void change(register int u, register int l, register int r, register int s, register int t, register int w){
if(s <= l && t >= r){
update(u, w);
return;
}
register int mid = l + r >> 1;
pushdown(u);
if(s <= mid) change(ls, l, mid, s, t, w);
if(t > mid) change(rs, mid + 1, r, s, t, w);
tr[u] = min(tr[ls], tr[rs]);
}
inline void modify(register int u, register int v, register int w){
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);
change(1, 1, n, dfn[top[u]], dfn[u], w);
u = fa[top[u]];
}
if(u == v) return;
if(dep[u] > dep[v]) swap(u, v);
change(1, 1, n, dfn[u] + 1, dfn[v], w);
}
inline int Query_tr(register int u, register int l, register int r, register int w){
if(l == r) return tr[u];
register int mid = l + r >> 1;
pushdown(u);
if(w <= mid) return Query_tr(ls, l, mid, w);
else return Query_tr(rs, mid + 1, r, w);
}
int ans[ss];
signed main(){
freopen("easy.in", "r", stdin);
freopen("easy.out", "w", stdout);
n = read(), m = read();
for(register int i = 1; i <= m; i++){
g[i].id = i;
g[i].from = read();
g[i].to = read();
g[i].w = read();
}
kruskal();
dfs(1, 0);
dfs(1, 1, 0);
build(1, 1, n);
for(register int i = 1; i <= m; i++){
if(!vis[g[i].id])
ans[g[i].id] = Query(g[i].from, g[i].to);
}
memset(tr, 0, sizeof tr);
build_tr(1, 1, n);
for(register int i = 1; i <= m; i++){
if(vis[g[i].id]) continue;
register int u = g[i].from;
register int v = g[i].to;
modify(u, v, g[i].w);
}
for(register int i = 1; i <= m; i++){
if(!vis[g[i].id]) continue;
register int u = g[i].from;
register int v = g[i].to;
if(dep[u] < dep[v]) swap(u, v);
ans[g[i].id] = Query_tr(1, 1, n, dfn[u]);
}
for(register int i = 1; i <= m; i++)
printf("%d
", ans[i]);
return 0;
}
泥谷好验证
2020.11.24(10)
[Huge 10
]
学军信友杯
20b-835
92ce880ad9971c1b
2020.11.23(11)
[Huge 11
]
线段树解锁新错误
今天考场没挂分
考试最后应该去看看(T1)的
(T2)玄学算法打了太久了
不过还好(120pts)全得到了
阶段总结
整体感觉考完csp回来考场状态好了很多
考场上心态很平稳
没有说看到题目没有思路就直接扔了跑路的情况
心也比较静，想出来就敢慢慢写
不担心一道题花费时间太久耽误其他的题目的话
反而时间会比较充裕
而且不会出现写了一半慌里慌张不写了的情况
即使写到一半发现前面有东西推错了也不会特别慌
重来一遍也是妥妥的能调过
上午大考的话基本上每天保持在九点半到十点钟能把暴力打个差不多
剩下时间磨一磨还能磨出个正解或者更高的部分分来
还是心要放平静
上次说完尝试思路的事情后来考试就一直在试
效果不错
最起码最近几天的考试考场上能不挂分了
甚至每天都能想出来一个正解
不仅仅停留在暴力上
感觉比之前进步很多
上次老姚说完改题自己改代码实现要死磕啥的后来也在坚持
果不其然代码实现能力有提升
之前考场上有思路但是觉得太麻烦不敢写的现在不管多复杂总能实现出来了
下午改题觉得稍有点吃力
多少有点改不动
四个题大部分能独立改出来两道半的样子
其余的就没有头绪不了了之了（实在是不会）
剩下时间学点随机算法SA啥的（狗头）
因为考场上打RAND的能力一直在飞涨（也不知道为啥有时候还能拿到意想不到的分）
还有巩固巩固前一段学的网络流（这玩意真的有用么……）
有时候要求写个题解就简单总结一下
感觉时间还是挺紧的
最好能保持这个状态吧
唯一的烦恼就是
晚上忽然开始失眠
今天是第三天了
特困想睡觉睡不着
有时候就坐一会儿
也不知道为啥
躺下去就特别累但是就是睡不着
翻来覆去得到十一点多有时候到十二点
第二天早晨困的一批
但是还好一上考场想题就清醒点
虽然有时候也会犯会儿困
迷惑也不知道咋办……
暂时好像想不到什么要说的了吧
以上
RP++
2020.11.22(12)
[Huge 12
]
晚上考试巨他妈的开心啊啊啊啊啊啊
考场上过的题屈指可数
哦哈哈哈哈
(T1)看着一个小于6的表硬是把正解推出来了
虽然有点绕远有点走弯路有点麻烦时间有点长
但是毕竟独立想出来了一道题
很满足(~~反正T2也不会~~)
考试快结束的时候暴力才把这个(7)跑出来
最起码对了心里吃了定心丸
增加了(AC)的信心
狂喜hahahahahahahahahaha～～～
最近两天一直在下雨有点冷
上羽绒服了QWQ
昨天上午考试状态真不戳
九点半打完暴力之后
就手玩了一会(T2)测数据发现了一些规律
然后yy想了一下这(40pts)线性递推一下不就行了？
打完(40pts)之后想到干嘛要一个一个乘
快速幂一次乘多个不就(A)了？
当时激动的不行
最后时间紧，测了一组极限数据报段错误
但是实在没时间看哪里错了就交上去了
果不其然RE滚粗
字符串数组按照部分分开的，，，
真的挂成前(40pts)
改过就A了
虽然挂了(60)但是还是挺开心的
毕竟好久没在考场上想到正解而且码出来了虽然码量及其小，最终还是打挂了
注重代码细节
加快打暴力的速度
打部分分如果能够开到更大的空间也尽量开
避免如果要打更高的分数爆出空间
以上
2020.11.19(15)
[Huge 15
]
| 名称 | 总分 | goods | merge | string | wall |
|---|---|---|---|---|---|
| HE-00050 | 90 | 10 | 30 | 0 | 50 |
回归之后的第一场模拟赛
估分90，实际得分90
虽然分不高
但是没挂分
挺知足的
(T2)考场上能做出来的
但是迫于(T4)占用调试时间太长了
而且最终也没调出来这个该死的暴力
导致(T2)没时间写正解了
注重代码实现能力+考场时间分配
焚化课结束了
回归集训
困
宿舍暖气烤的太厉害了
后半夜嗓子根本受不了
睡不好
md夜里暖和是真暖和
早晨起来困是真困
2020.11.16
改了四天终于调过了紧急疏散
费劲
建边好ex
不想上焚化课啊啊啊啊
焚化课不讲武德，用骗，用偷袭，焚化我这个16岁的少年
耗子尾汁
2020.11.13
emmmm
爬起来了
还是刚一下紧急疏散吧……
今天似乎又要开始上焚化课了啊啊啊
希望上课不要睡死过去
2020.11.12
今天写了一天网络流
感觉针不戳
中午睡觉脑子里面全是网络流的边乱指
竟然给我指醒了(QwQ)
紧急疏散建图好ex啊
想完思路就不想写了。。。
第五道网络流
[NOI2006]最大获利（网络最大流+最小割）
(ICPC)就这？？？
[ICPC-Beijing 2006]狼抓兔子
题库竟然卡了(Dinic)
没错是郭郭加强了数据
顺便把(spfa)也卡掉了
昨天说好了把卡(Dinic)的出题人挂在树上的
是不是线下物理解决一下(QWQ)
非常舒适的切掉了士兵占领
板子非常熟练了，锻炼建边的思维
下午来了状态极佳
一个小时切星际争霸
自己写过开心极了～
一上午调过了蜥蜴
早晨回来被老姚叫走喝茶谈人生
(RP++)
网络最大流(Dinic)加上无用点优化
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define min(a, b) ({register int AA = a, BB = b; AA < BB ? AA : BB;})
#define inf 0x7fffffff
using namespace std;
inline int read(){
int x = 0, w = 1;
char ch = getchar();
for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
const int ss = 10010;
struct node{
int to, nxt, w;
}edge[ss * 20];
int head[ss], tot = 1;
inline void add(register int u, register int v, register int w){
edge[++tot].to = v;
edge[tot].nxt = head[u];
edge[tot].w = w;
head[u] = tot;
}
int dis[ss], cur[ss];
int n, m, d, s, t;
bool vis[ss];
queue<int> q;
inline bool spfa(register int s){
for(register int i = 0; i <= n; i++)
vis[i] = 0, dis[i] = 0x3f3f3f3f, cur[i] = head[i];
dis[s] = 0;
q.push(s);
while(!q.empty()){
register int u = q.front();
q.pop();
vis[u] = 0;
for(register int i = head[u]; i; i = edge[i].nxt){
register int v = edge[i].to;
if(dis[v] > dis[u] + 1 && edge[i].w){
dis[v] = dis[u] + 1;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return dis[t] != 0x3f3f3f3f;
}
long long ans;
inline int dfs(register int u, register int flow){
register int res = 0, used = 0;
if(u == t) return ans += flow, flow;
for(register int i = cur[u]; i; i = edge[i].nxt){
cur[u] = i;
register int v = edge[i].to;
if(dis[v] == dis[u] + 1 && edge[i].w){
if(res = dfs(v, min(flow - used, edge[i].w))){
used += res;
edge[i].w -= res;
edge[i ^ 1].w += res;
if(used == flow) break;
}
}
}
return used;
}
inline long long dinic(){
register long long minflow = 0;
while(spfa(s)) dfs(s, 0x7fffffff);
return ans;
}
signed main(){
n = read(), m = read(), s = read(), t = read();
for(register int i = 1; i <= m; i++){
register int u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, 0);
}
printf("%lld
", dinic());
}
今天破天荒的不考试？？
学习网络流+改题
码了三遍(Dinic)最大流终于能够一遍过了
舒服～
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define min(a, b) ({register int AA = a, BB = b; AA < BB ? AA : BB;})
using namespace std;
inline int read(){
int x = 0, w = 1;
char ch = getchar();
for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
const int ss = 10010;
struct node{
int to, nxt, w;
}edge[ss * 20];
int head[ss], tot = 1;
inline void add(register int u, register int v, register int w){
edge[++tot].to = v;
edge[tot].nxt = head[u];
edge[tot].w = w;
head[u] = tot;
}
int dis[ss], cur[ss];
int n, m, s, t;
bool vis[ss];
queue<int> q;
inline bool spfa(register int s){
for(register int i = 1; i <= n; i++)
dis[i] = 0x3f3f3f3f, cur[i] = head[i], vis[i] = 0;
dis[s] = 0;
q.push(s);
while(!q.empty()){
register int u = q.front();
q.pop();
vis[u] = 0;
for(register int i = head[u]; i; i = edge[i].nxt){
register int v = edge[i].to;
if(dis[v] > dis[u] + 1 && edge[i].w){
dis[v] = dis[u] + 1;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return dis[t] != 0x3f3f3f3f;
}
inline int dfs(register int u, register int flow){
register int res = 0;
if(u == t) return flow;
for(register int i = cur[u]; i; i = edge[i].nxt){
cur[u] = i;
register int v = edge[i].to;
if(dis[v] == dis[u] + 1 && edge[i].w){
if(res = dfs(v, min(flow, edge[i].w))){
edge[i].w -= res;
edge[i ^ 1].w += res;
return res;
}
}
}
return 0;
}
long long maxflow;
inline long long dinic(){
register long long minflow = 0;
while(spfa(s)){
while(minflow = dfs(s, 0x7fffffff))
maxflow += minflow;
}
return maxflow;
}
signed main(){
n = read(), m = read(), s = read(), t = read();
for(register int i = 1; i <= m; i++){
register int u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, 0);
}
printf("%lld
", dinic());
return 0;
}
2020.11.11
今天双十一
但是不知道买啥，，，
随便吧
嗝，新(Mac)真香
上午开始了真正的(NOIP)模拟赛
没错我可以(A)掉一道题
但是本来不会(dfs)判环还迎着头皮上
于是挂成零分
下午来了随便码了一个(tarjan)就过了
刚刚跟小坤一起(yy)的(dfs)判环现在拍挂了
正在调～
2020.11.10
CSP结束了
回来搞学考课程
昨天，，，
一天上了7节地理
半天的时间把必修二整整一本书讲完了
建议改成地理奥赛
真就百家饭喂大的信息奥赛
一节课换一个老师
每一个学科的所有老师轮着给上课
感觉针不戳～