WORIA

  题意：给出张带权联通无向图。要求两点间路径上的最大边权最小。 这就引出了最小瓶颈路，即最小瓶颈生成树上的路径。最小瓶颈生成树指一棵最大边权最小的生成树。 最小瓶颈生成树不一定是最小生成树，最小生成树一定是最小瓶颈生成树。 那么本题就是要求最小瓶颈生成树上任意两点路径的最大边权。 由于询问次数很多，每次最多 O(log⁡n)O(\log n)O(logn) 地查询。 容易发现树上任意两点路径与这两点到他们的LCA的路径有关，因此可以采用倍增求LCA的思想，在找LCA的同时，确定出两点分别到LCA的路径上的边权最大值。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104#include<bits/stdc++.h>usi ...

  可以证明若从A点到B点时走不动了，则从A到B的途中的那些点也都到达不了B。 假设A点后是C点，则A点到达C点时只有两种情况：有剩余的油量，或者没有剩余。这两种情况都比直接从C点出发只好不差。所以在更好的情况下无法到达B点，那么更坏的情况更无法到达B点。 那么可以进行剪枝，枚举一个点A作为起点，若该点在途中某一点B停止了，那么下一次直接从B点开始枚举。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<bits/stdc++.h>using namespace std;typedef pair<int, int> pii;#define ll long longconst int INF = 0x3f3f3f3f;const int maxn = 1e5 + 5;int T, n;int has[maxn], need[maxn];int check(int u) { int sum = has[u]; fo ...

  题意：给定一个有向图，求边权平均值最小的环的边权平均值。 二分 若环平均值等于mid，则 w1+w2+⋯+wk≥mid⋅kw_1+w_2+\cdots +w_k\geq mid\cdot kw1​+w2​+⋯+wk​≥mid⋅k，即 (w1−mid)+(w2−mid)+⋯+(wk−mid)≥0(w_1-mid)+(w_2-mid)+\cdots +(w_k-mid)\geq 0(w1​−mid)+(w2​−mid)+⋯+(wk​−mid)≥0，即没有负环，所以如果有负环，则表明该环平均值小于mid。 用Bellman判负环即可。 注意有负环和有负权边是不同的！ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include<bits/stdc++.h>using namespace std;#define ...

  dp dp[T] [N]表示在时间 i 时已经在第 j 个车站了，还需要等的时间。 由于dp[i] [j]只会与时间大于 i 的结果有关，所以 i 从后往前更新。 在T时间，如果在N站，则需要等的时间为0；如果不在N站，则永远不能到达，设置时间为INF，以便判断答案是否为“impossible”。 在更新之前，dp[i] [j] = dp[i+1] [j] + 1.这是最基础的，因为dp[i+1]已经全部更新完，所以dp[i] 可以在dp[i+1]的基础上更新。如果在 i 时刻没有方法减少等待时间的话，则只能等1s，以到达 i+1，则若无更好的方法，i 时刻等待时间绝不会少于dp[i+1] [j] + 1，且 i 时刻的等待时间也绝不会多于dp[i+1] [j] + 1，所以把dp[i] [j]先设置为 dp[i+1] [j] + 1 是正确的。 由于只有当 i 时刻 j 站有车发车时才会有优化的可能性，所以要预处理出每个时间点，每一站是否有发车。 接着就是 i 基于 i+1 更新，j 随便从哪个方向更新，因为 j 可能受到 j-1 方向的影响，也可能受到 j+1 方向的影响，两 ...

http://uoj.ac/problem/8 题意：一个程序输出它自己。 很经典的一个问题，虽然看上去是个无穷递归的不可解问题，但利用C语言字符串的特性或者编译器可以做到。 参考 https://www.cnblogs.com/xkfz007/archive/2012/03/27/2420162.html 1main(){char*s="main(){char*s=%c%s%c;printf(s,34,s,34);return 0;}";printf(s,34,s,34);return 0;} 以上代码中在运行printf时字符串s里的 %c%s%c 又被解析为34（双引号的ASCII码），s，双引号。那么为什么在第二个s里没有再解析呢？可能是编译器的设定吧。   12#define q(k)main(){return!puts(#k"\nq("#k")");}q(#define q(k)main(){return!puts(#k"\nq(&qu ...

http://uoj.ac/problem/5 题意：对于字符串S，求出每个前缀子串各有几个等于前缀且不相交的后缀。 就是要求在求解KMP的过程中能经过几次压缩，然后多了一个子串长度不能超过一半的要求。 但是显然不能对每个子串重新求一遍。可以发现KMP的next中每个串的后续是唯一的，也就是说再往后求就是重复计算了，所以考虑把算完的存下来，每次找到第一个符合条件的就直接用它的答案。 下面的程序里有两个指针j和k，要注意j不等于k，为了减少时间，重复利用了k，保证k一直都在串的前半截移动，虽然每次都从nxt[i]开始答案没错，但是会超时。 12345678910111213141516171819202122232425262728293031#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1e6 + 10;const ll mod = 1e9 + 7;int T;char s[N];int nxt[N], cnt[N];int main() { scanf(& ...

http://uoj.ac/problem/3 题意：一个无向图，要从1到n，每条边有两个权值a,b，最终的花费a值，b值不能小于路径上的边权值，求最终最小a，b值之和。 有二维，肯定是要把一维排序，另一维求最小，最后再比较答案。 有两种做法。 做法一：分层图SPFA 把边按照a值从小到大排序，再逐个插到图里，每次都求从1到n的最大b值最小的路径，由于新增了边，所以要再把新增的边加进SPFA的队列里，让它继续跑，不要重新建图。有点类似分层图网络流。最后比较新的b值加a值是否更小，由于如果路径不走新边的话，就和上次答案一样，已经存下来了，所以只需要假设路径走新边即可。 然而这种做法被新加的数据卡了。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair& ...

http://uoj.ac/problem/2 题意：有 nnn 个关卡，主角手里有一个数 kkk 未定，且 k≤mk\leq mk≤m ，每关都有一种操作，与/或/异或 ttt 。问最终主角手里的数最大是多少。 bitset 每一位只会是0或1，而每一位经过的操作是已知的，所以只要把0和1经过一系列操作后的结果模拟出来，就能判断初始时这一位应该是0还是1. 如果0最终变成1，则显然这一位是要加入答案里的，而原始的k也只要在这一位取0即可。 如果1变成1，为了答案最大，也是要取的，但是这时要判断是否会使得原始的k超过m，因此要从高向低位遍历，这样遇到能加的就直接加上。 如果最终变成了0，显然不需要处理了。 由于bitset位运算能快64倍，所以用bitset优化。 1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<int, int> pii;const ...

拓扑序 有向无环图DAG，对每一个顶点给一个编号，第i号顶点叫做v，那么存在顶点 v~i~ 到顶点v~j~的边时，就有i<j成立，这样的编号方式叫做拓扑序。 拓扑排序 如果把图（a）中的顶点按照拓扑序从右到左排列，那么所有的边都是从左指向右的。求解拓扑序的算法叫做拓扑排序。 DFS算法 使用栈以使结果为正向排序，由于每个顶点和每条边都只访问了一次，因此复杂度时O(|V|+|E|). 已知为DAG的情况 对每一个节点设置属性visited为0或1，未访问过为0，访问过为1. dfs(u)其中n为节点，不断深入递归，当其所有子节点都已被访问过之后才会退出。 所以可以知道最先被访问的必定是拓扑序最大的，则先将其push至栈中，最后从栈中取出时即为正序。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <iostream>#include <stack>using namespace std;struct Edge & ...

sklearn.preprocessing.PolynomialFeatures 使用 sklearn.preprocessing.PolynomialFeatures 这个类可以进行特征的构造，构造的方式就是特征与特征相乘（自己与自己，自己与其他人），这种方式叫做使用多项式的方式。 例如：有 a、ba、ba、b 两个特征，那么它的 2 次多项式的次数为 [1,a,b,a2,ab,b2][1,a,b,a2,ab,b2][1,a,b,a2,ab,b2]。 PolynomialFeatures 这个类有 3 个参数： degree：控制多项式的次数； interaction_only：默认为 False，如果指定为 True，那么就不会有特征自己和自己结合的项，组合的特征中没有 a2a^2a2和 b2b^2b2； include_bias：默认为 True 。如果为 True 的话，那么结果中就会有 0 次幂项，即全为 1 这一列。 配合poly.fit_transform