WORIA

本题需要将一张图分为两个顶点覆盖（vertex cover），并不需要最小，较简单。   dfs染色，任一点起，每个相连点染成不同颜色，若出现染过色，且该点颜色与当前应该染成的颜色不同，则出错。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<iostream>#include<vector>#include<map>using namespace std;const int maxn = 1e5 + 5;int vised[maxn];map<int, vector<int> >mp;struct Node{ vector<int>to;}nd[maxn];bool flg = 1;void paint(int s,int color) { if (vised[s] != 0) { if (vised[s] != ...

本题就是从一处storage找到最近的一处非storage。   先画图，再判断是storage的点少，还是非storage的点少（否则直接找会超时），接着从少的那一类点中，挨个查找每个点与另一类点的最近距离，最后答案为所有最近距离的最小值。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include<iostream>#include<queue>#include<algorithm>using namespace std;#define pii pair<int,int>const int maxn = 1e5 + 5;const int INF = 0x3f3f3f3f;vector<int>storage;struct cmp { bool op ...

本题需要在图中找到一个长度大于给定值 k 的环。   思路：  先将所有边存下来，画出图，再DFS找环，找到一个就计算它的长度，若长度满足条件，则跳出，否则继续。存图要用邻接表，矩阵会超内存。   DFS找环的方法：    首先要知道几个DFS中的概念：  在图的遍历中，往往设置了一个标记数组vis的bool值来记录顶点是否被访问过。但有些时候需要改变vis值的意义。令vis具有3种值并表示3种不同含义 vis = 0,表示该顶点没没有被访问 vis = 1,表示该顶点已经被访问，但其子孙后代还没被访问完，也就没从该点返回 vis = 2,，表示该顶点已经被访问，其子孙后代也已经访问完，也已经从该顶点返回  vis的3种值表示的是一种顺序关系和时间关系   DFS过程中，对于一条边u->v vis[v] = 0,说明v还没被访问，v是首次被发现，u->v是一条树边 vis[v] = 1,说明v已经被访问，但其子孙后代还没有被访问完（正在访问中），而u又指向v？说明u就是v的子孙后代，u->v是一条后向边，因此后向边又称返祖边 vis[v] = 3,z说明v已经被 ...

1234567891011121314151617181920212223242526272829303132333435363738int par[MAX_N];//每个节点的父节点int rank[MAX_N];//树的高度//初始化n个元素void init(int n) { for (int i = 0; i < n; i++) { par[i] = i;//初始时每个节点自成一树 rank[i] = 0; }}//查询树的根int find(int x) { if (par[x] = x) { return x; } else { return par[x] = find(par[x]);//递归向上查询，查询到之后直接连到根 }}//合并x和y所属的集合void unite(int x, int y) { x = find(x); y = find(y); ...

  本题与背包问题有些不同，主要记一下不同之处。 背包问题通常直接给出了物品的价值，我们要选择的只是选/不选。然而本题并未给出各个迷妹的价值，有人可能会认为这分数 aia_iai​ 就是价值，但显然每个人的价值还会受到追她的时间影响，例如，有个迷妹 A 为(100,1100),即分数100，耗时1100；迷妹 B 为(100,11)，这两者分数相同，B的耗时更少，显然 B 的价值更大，换句话说，选B的收益更大。   在本题中，还要考虑性价比的存在。   另一点不同在于，背包问题，尤其是01背包，选择的先后顺序与最后结果无关，在01背包中，选总价值相同的一些物品，不管是什么顺序选，最后背包中的总和是一样的，而本题不同，本题先选性价比高的比先选性价比低的更赚，这就是本题需要贪心的地方。   因此，需要先确定一个评判价值的标准，根据价值判断是否选择，以及选择顺序先后。由经验知，价值应该与分数正比，与耗时反比，因此猜测： 性价比=分数/耗时； 以下证明： 假设两人为(a1,t1),(a2,t2)(a_1,t_1) , (a_2,t_2)(a1​,t1​),(a2​,t2​) , ...

1.注册比特币钱包     注意不要挂VPN，挂了也不要开负载均衡，不然以后要不停的更换IP，每次都要邮件确认！   1.登陆官网 https://bitcoin.org/zh_CN/，若是英文网站，在右上角可选语言。   2.建议先看完 “比特币入门指南”。   3.看完后回到首页，点击 “选择钱包”。   4.此时在导航栏中有多个平台可选，有条件的可以选择“桌面”，“硬件”，或“手机”。此处以“网页”为例。   5.点击“网页”后，有三个可选项，以 “BitGo” 为例。   6.点击“BitGo”后，点击 “访问网站”。进入BitGo官网。   7.点击右上角“SIGNUP”注册账号，已有账号的直接点“LOGIN”登陆即可。注册时密码一定要足够复杂，确保密码框下有绿色直线，否则无法通过。   8.之后邮箱中会收到确认邮件，点进去后登陆，开始认证。   9.有三种认证方式，以“Google Authenticator”为例，手机下载该软件，网页上给出了下载链接，可通过App Store或Google Play下载，Google Play要翻墙。   10.下载好之后，点击之前 ...

1.逻辑回归    1.1 logistic分布 ​  定义 1.1： ​   设有连续随机变量 X，X 服从logistic分布是指 X 有以下的分布函数和密度函数： ​   $$F(x)=P(X\leq x)=\frac{1}{1+e^{-(x-\mu)/ \gamma}}$$ ​   $$f(x)=F’(x)=\frac{e^{-(x-\mu)/\gamma}}{\gamma(1+e^{-(x-\mu)/\gamma})^2}$$ ​   式中，μ\muμ 为位置参数，γ>0\gamma>0γ>0 为形状参数。    1.2 二项logistic回归模型 ​   定义 1.2： ​    随机变量 Y 取值为1或0。 ​     $$P(Y=1|x)=\frac{exp(w\cdot x+b)}{1+exp(w\cdot x+b)}$$ ​      $$P(Y=0|x)=1-P(Y=1|x)$$ ​     将偏置 b 并入 w 中，得 x=(1,x(1),x(2),⋯ ,x(n))x=(1,x^{(1)},x^{(2)},\cdot ...

注意几点： 二分停止的条件是上下边界的差值小于 eps ，而非时间的值与t的差值小于 eps 。 cout的double只能输出小数点后 6 位，要输出更多需在输出语句前加 1cout << setprecision(t); 便可输出小数点后 t 位 代码： 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<iostream>#include<vector>#include<cmath>#include <iomanip>using namespace std;typedef pair<int, int> pii;int n, t;const double eps = 1e-9;double c=0;double ed, st;vector<pii>vc;double solve() { double ans = 0.0; for (auto it : ...

想到的解法比较rz，就是一层层地进入罐头，当遇到 ’ { ‘，’ [ ‘，’ ( ’ 时进入下一层罐头，当遇到 ’ } ‘，’ ] ‘，’ ) '时检查与罐头开头是否相匹配，若不匹配则彻底false，反之，继续检查。 代码： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include<iostream>#include<string>#include<map>using namespace std;const int maxn = 1005;string s;int now = 0; //检查到下标为now的点map<char, char>mp; //对应情况bool ok = true; //是否正确void solve(int len,int depth) { char st = s[now]; now++; while(now<len){ if (s[now] == &# ...

要用掉数量最多的硬币，则要尽量用面额小的硬币。 从面额最小的硬币开始凑起，上限为有的硬币数或付清P所需最大硬币数。 下限为 0 或上限减去（25/当前硬币面额），意为若用之后的面额的硬币凑不出某一数值，则必然也凑不出该数值加25。命题在该数值大于当前面额时成立。 确定上下限后，对每种面额搜索。 1234567891011121314151617181920212223#include<bits/stdc++.h>using namespace std;int p,v[4]={1,5,10,25},n[4];int dfs(int i,int sum,int ans)//第i种硬币,已经兑换总额, 已经用的i-1种硬币的数量 { if (sum==p) return ans; if (i==4) return -1; int high=min((p-sum)/v[i],n[i]),low=max(0,high-25/v[i]); for(int j=high;j>=low;j--) { int tem=dfs(i+1,sum+j ...