训练实录

ACM

记录

算法合集

疑问

  1. ecf51 F 中的环套环的问题不能解决吗

tips

  1. 图论：正难则反
  2. 读入不要混用！！
  3. poj不支持assert
  4. 注意数据范围，不要爆int
  5. 容斥：反过来想
  6. 图论题没有特殊的说明，要加是否有重边，是否连通
  7. cout输出long long会进行科学输出，用printf格式化输出

调整一下最近的计划

蓝书图论的例题，例题、习题已经刷了一半了，大概还需一星期
思维题，有一定代码量的题目，可以写蓝书的思维例题
dp

这一周的任务

  1. ~~结束蓝书上面的图论的例题，课后习题 ~~
  2. ~~记忆化搜索+game ~~
  3. 接着补dp

BM算法

想要刷的专题

cf的归纳总结很好啊
南京网络赛题解

  1. 背包九讲里面的问题 汪巨的数据结构，qko的dp专题
  2. 基础dp的设计思路
  3. 概率、期望
  4. kmp\exkmp\马拉车
  5. ac 自动机
  6. 后缀数组
  7. 搜索专题
  8. 数学，最起码要知道搞什么
  9. 一类环问题的总结

首先按照之前的计划打印出来计划的表格

每场cf都打，最重要的是提高自己的乱搞能力。上面的专题准备2~3个每周，可能会比较的累吧，
每天保持6题+的刷题量，自己的代码量太少了。

last 督促队友刷五个level的线段树

多校补题参考
dls的代码

contest name solve 补题链接 代填的坑
nowcoder contest2 3 补题链接
multi-university contest1 3 补题链接 1. RMQ Similar sequence
multi-university contest2 2 补题链接 1. H naive operation
nowcoder contest3 3 补题链接 1. C shuffle card
2. E 用hash搞一下
nowcoder contest4 2 补题链接 1. G模拟题
2. J hash function
multi-university contest3 3 补题链接 1.单调栈、单调队列
2.感觉要入dp的坑
multi-university contest4 3 补题链接 1. 矩阵的求和预处理和如何划分
nowcoder contest5 3 补题链接 1. subsequence
2.树状数组的总结
nowcoder contest6 4 补题链接 1. 权值线段树
2. 网络流的建图性质
3. 树上任意两点的距离
multi-university contest5 2 补题链接 1. 这场真的是太难了，导致很多题都补不了，于是愉快划了一天水
multi-university contest6 2 补题链接 1. 狼人杀
2. 基环树，树形dp
nowcoder contest7 1 补题链接 1.$ n^4 $扫描预处理降到$ n^3 $
2. 爆搜
3. 4元团的构造
nowcoder contest8 2 补题链接 1. bzoj4706
2.上面的四场都很毒，补题很困难
multi-university contest7 - 补题链接 1. hdu 6394 tree lct+rmq
2. GuGuFishtion
multi-university contest8 - 补题链接 1. taotao picks apples 乱搞能力
2. from ICPC to ACM
3. Pizza Hub
nowcoder contest9 1 补题链接 1. 毕姥爷的题目推荐
2.BM算法
3. FWT算法
4. 建trie图的正确用法
nowcoder contest10 2 补题链接 1. 类欧几里得算法
multi-university contest9 2 补题链接 1. Rikka with Nash Equilibrium
2. Rikka with Seam
3. Rikka with Time Complexity
multi-university contest10 4 补题链接 1. tea tree
2. CSGO

nowcoder contest2 solve 3
补题链接

multi-university contest1 solve 3
补题链接
待补题：

  1. RMQ Similar sequence

multi-university contest2 solve 2
补题链接
待补题：

  1. H naive operation

nowcoder contest3 solve 3
补题链接
待补题：

  1. C shuffle card
  2. E 用hash搞一下

nowcoder contest4 solve 2
补题链接
待补题：

  1. G模拟题
  2. J hash function

补题

枚举边求最短路

多校发现的坑

  1. 总结一个splay的板子， 还有线段树维护区间的最大子串问题
  2. fleury求欧拉路经的板子
  3. 笛卡尔树 rmq similar
  4. 上帝集合的正确用法
  5. 总结二项式反演
  6. 指数循环节问题
  7. 随机化三角形
  8. 基环树的建图部分
  9. 集训队的博弈问题
  10. 任老师讲课：第k小生成树 poj 1639

有技巧的建图

NRREC J
这道题的操作很骚，算法如下：
遍历每条边x，并把图中所有的边的权值都减去该边的权值x，如果变成负数，那么就置0，并将跑出来的值dis[n]+k∗x就是这次的答案，对所有的答案取最小值，并且与原始图的dis[n]取最小值，得到的结果就是最终答案。

正确性证明：

  1. 假设最终的最短路中有大于等于k条边，并设第k大的边长度为x。
    那么该路径上所有的边减去x，之后跑最短路得到dis[n]，那么dis[n]+k∗x就是该路径的“长度”，就是最终答案，并且这个数一定会出现在比较中。
    而对于其他的路径，如果减去的x不是该路径的第k大的边的时候，该路径的值dis[n]+k∗x一定不会比该路径的“长度”小，出现在比较中不会对最终答案造成影响。
  2. 假设最短路中有小于k条边，那么原图中跑最短路的dis[n]一定是最小的。

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 3007;
vector<int> G[maxn];
typedef long long ll;
typedef pair<ll,int> pii;
const ll inf = 1e18;
int U[maxn],V[maxn];long long W[maxn];
int n,m,k;
int vis[maxn];ll dis[maxn];
#define pr(x) cout<<#x<<":"<<x<<endl
ll dij(ll x){
    priority_queue<pii,vector<pii>,greater<pii> > Q;
    for(int i = 1;i <= n;++i) dis[i] = inf;
    dis[1] = 0;
    //第一维为距离，第二维为编号
    Q.push({0,1});
    while(!Q.empty()){
        pii p = Q.top();Q.pop();
        int u = p.second;
        if(p.first > dis[u]) continue;
        for(int i = 0; i<G[u].size(); i++){
            int e = G[u][i];
            //亦或取点很巧妙
            int v = u^V[e]^U[e];
            ll w = W[e] - x;
            w = max(0ll,w);
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                Q.push({dis[v],v});
            }
        }
    }
    return dis[n];
}
int main(){
    cin>>n>>m>>k;
    for(int i = 0;i < m;++i){
        int u,v;long long w;
        scanf("%d %d %lld",&u,&v,&w);
        U[i] = u,V[i] = v,W[i] = w;
        G[u].push_back(i);
        G[v].push_back(i);
    }
    ll ans = dij(0);
    for(int i = 0;i < m;++i){
        ll res = dij(W[i])+k*W[i];
        ans = min(ans,res);
    }
    printf("%lld\n",ans);
    return 0;
}

Floyd求环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void floyd(){
    int ans = INF;
    memcpy(d, dis, sizeof(dis));
    for(int k=1; k<=4*n; k++){
        for(int i=1; i<k; i++){
            for(int j=i+1; j<k; j++){
                if(d[i][j]+dis[j][k]+dis[k][j]<ans){
                    ans = d[i][j]+dis[j][k]+dis[k][i];
                    path.clear();
                    path.push_back(i);
                    get_path(i, j);
                    path.push_back(j);
                    path.push_back(k);
                }
            }
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(d[i][j]>d[i][k]+d[k][j]){
                    d[i][j] = d[i][k]+d[k][j];
                    pos[i][j] = k;
                }
            }
        }
    }
    if(ans == INF){
        return ;
    }
    cout<<ans<<endl;
    for(int i=0; i<path.size(); i++){
        cout<<path[i]<<" ";
    }
    cout<<endl;
}

8.9记录

  1. 网络流将流量设为1，一般是为了限制流经的路径数。
  2. 费用流来解决一类最小的问题
  3. 二分答案来设置容量
  4. 一道提及的题 青岛现场赛题目
  5. 最小点覆盖的文章

未解决的问题

本文标题:训练实录

文章作者:Babydragon

发布时间:2018-07-21, 00:40:55

最后更新:2019-09-18, 19:25:23

原始链接:http://baolintian.github.io/2018/07/21/训练实录/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 疑问
  2. 2. tips
  3. 3. 调整一下最近的计划
  4. 4. 这一周的任务
  5. 5. 想要刷的专题
  6. 6. 补题
  7. 7. 多校发现的坑
  8. 8. 有技巧的建图
    1. 8.1. ac code
  9. 9. Floyd求环
  10. 10. 8.9记录
  11. 11. 未解决的问题
{{ live2d() }}