WORIA

https://codeforces.com/gym/101933 J. Jumbled String   题意：有一个01串，有 a 个00子序列，b 个01子序列，c 个10子序列，d 个11子序列。构造出这个01串。 构造 通过00和11能知道 0 和 1 的个数，现在假设只有 0，每插入一个 1，就多出左边0的个数个01，右边0的个数个10，加起来恰等于所有0的个数。对每个1都是如此，所以总的 b+c 必须等于cnt[0]*cnt[1]。 左边都放1，接着放0，这样就有了 cn[1]*cn[0] 个10，还剩下一些10，可以再中间某处再放一个1，接着放剩下的0，再放剩下的1。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include <bits/stdc++.h>#define rep(i, l, r) for (int ...

https://namomo.top:8081/contest/4 String 题意：维护一些 01 串。四种操作：加入一个字符串，权值为 v；删掉所有字符串 s；输出所有以 s 为前缀的字符串的权值之和；把所有形如 sx 的字符串改为 tx，保证 s 与 t 最长公共前缀为空。如果不存在则输出"Not Exist"。 Trie+模拟 直接按照题意模拟。 由于串的长度比较大，所以为了防止下标不够用，可以循环利用删除了的点下标。 维护 val[i]val[i]val[i] 表示 Trie 上以 s 为前缀的所有串的权值和。 每次插入时沿路增加 val 值。删除时先判断如果 val 值等于两个儿子的 val 之和，说明串 s 并不存在。若存在则沿路删除 val。 查询时直接找到串 s ，输出它的 val。 最后一个操作需要先找到 s，再找到 t，并把 s 的子树合并到 t 去。所以先找到 s，得到 它的 val，需要把这个值加到 t 到根的路径上，由于 t 可能不存在，所以直接先建出 t，权值为 s 的 val。再合并 s，t，如果 s 有儿子而 t 没有，则直接把 ...

https://namomo.top:8081/contest/2 C. 序列 题意：给定一个数列，每次将一个区间 [l,r][l,r][l,r] 中所有数-1，代价 (r−l+1)2(r-l+1)^2(r−l+1)2，要求最终全变为0，问在用最少次数操作的前提下，最小代价与最大代价。 差分 考虑逆向操作，从全为 0 的数列，每次选一个区间+1，形成给定数列。 每次选一个区间全部加 1 ，可以差分完成，所以求出给定数列的差分数组，要求操作次数最少，所以差分数组中负数的位置一定是所选操作区间右端点+1，正数位置一定是所选操作区间的左端点，为 0 的位置一定不会作为差分时操作的位置。 所以差分数组相当于一个括号序列，在正数位置只能放左括号，负数只能放右括号。 设差分数组中正数位置为 a，负数位置为 b。 则总的代价 ∑(a[i]−b[i])2=∑(a[i]2+b[i]2)−2∑(a[i]∗b[i])\sum(a[i]-b[i])^2=\sum(a[i]^2+b[i]^2)-2\sum(a[i]*b[i])∑(a[i]−b[i])2=∑(a[i]2+b[i]2)−2∑(a[i]∗b[i])。 ...

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354import numpy as npimport requestsdef get_data(url): content=requests.get(url).content content=content.decode('utf-8') content=content.split("\n") X=[] Y=[] for line in content[:-1]: data=line.split() y=float(data[-1]) Y.append(y) x=data[:-1] for i in range(len(x)): x[i]=float(x[i]) X.append([1.0]+x) X=np.m ...

用途&复杂度 min25筛可用于计算一些积性函数的前缀和。 要求：f(p)f(p)f(p)，（ppp 为质数），是一个关于 ppp 的项数较少的多项式，或可以快速求值。f(pc)f(p^c)f(pc) 可以快速求值。 复杂度：O(n34log⁡n)O(\frac{n^\frac{3}{4}}{\log n})O(lognn43​​)。 min25筛与杜教筛都可以计算积性函数的前缀和，且新的min25筛复杂度也是 O(n23)O(n^{\frac{2}{3}})O(n32​)。但是使用杜教筛需要构造出一个积性函数 g(i)g(i)g(i)，使得 f∗gf*gf∗g 可以快速求出前缀和。而使用min25筛则只要满足上面的要求即可。   原理 设 f(i)f(i)f(i) 为题中需要求前缀和的积性函数，ppp 为某个质数。 分为两步： 对于所有 x=⌊nd⌋x=\lfloor \frac{n}{d}\rfloorx=⌊dn​⌋，（也就是数论分块里的那个数），求出不超过 xxx 的所有质数的 fff 值之和。即 ∑p≤xf(p)\sum_{p\le x} f(p)∑p≤x​f(p)。 ...

https://www.luogu.com.cn/problem/P5651 本题是假的最短路！ 以下设 wijw_{ij}wij​ 为边 (i,j)(i,j)(i,j) 的边权，d(u,v)d(u,v)d(u,v) 为点 uuu 到点 vvv 的最短异或路径值。   首先要说一个性质： 以上说的“最短异或路径”其实是任意路径。 即任意从 uuu 到 vvv 的路径异或和相等。 若从 uuu 到 vvv 有大于一条路径，则必定有环，如下图。 d1(1,7)=w1,2⨁w2,4⨁w4,5⨁w5,6⨁w6,3⨁w3,7d_1(1,7)=w_{1,2} \bigoplus w_{2,4} \bigoplus w_{4,5} \bigoplus w_{5,6} \bigoplus w_{6,3} \bigoplus w_{3,7}d1​(1,7)=w1,2​⨁w2,4​⨁w4,5​⨁w5,6​⨁w6,3​⨁w3,7​ d2(1,7)=w1,2⨁w2,3⨁w3,7d_2(1,7)=w_{1,2} \bigoplus w_{2,3} \bigoplus w{3,7}d2​(1,7)=w1,2​⨁ ...

  本题明显是网络流求最小割问题，但由于边数太多，不能直接用。 发现这是一个平面图，考虑转化为对偶图，求平面图最大流。 把每个三角形的面当作对偶图的点，两个三角形的公共边作为对偶图的连边，从S到T连一条线，形成一个附加面，把附加面作为对偶图的S，无界面作为对偶图的T，删去S和T的直接连边，求最大流。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293#include<bits/stdc++.h>using namespace std;#define ll long long#define REP(i,n) for(int i = 0; i < (n); i++)typedef pair<int, int> pii;const int INF = 0x3f3 ...

anaconda与python可能不共用库，在conda promote中pip install 从sklearn下载数据集 123from sklearn.datasets import load_breast_cancercancer=load_breast_cancer()print(cancer.keys()) 数据集中有多个key   KNN实例 用scikit-learn中的KNN算法 首先将数据分为训练集与测试集 12345from sklearn.model_selection import train_test_splitfrom sklearn.datasets import load_breast_cancercancer=load_breast_cancer()X_train,X_test,y_train,y_test=train_test_split(cancer.data,cancer.target,stratify=cancer.target,random_state=66) 然后导入类并将其实例化，并设置邻居个数 12from sklearn.nei ...

C. Evolution Game   123456789101112131415161718192021222324252627#include<bits/stdc++.h>using namespace std; typedef pair<int, int> Pair; const int maxn = 5e3+5;Pair p[maxn];int a[maxn], ans[maxn], n, w, mark; int main(){ cin >> n >> w; for (int i = 0; i < n; ++i) { cin >> a[i]; p[i].first = a[i]; p[i].second = i; } sort(p, p + n); for (int i = n - 1; i >= 0; --i) { for (int j = max(p[i].second - ...

A. Adrien and Austin   1234567891011121314#include<bits/stdc++.h>using namespace std;const int maxn = 1e5;int n, k;int main(){ cin >> n >> k; if (n == 0) cout << "Austin\n"; else if (k == 1) { if (n % 2) cout << "Adrien\n"; else cout << "Austin\n"; } else cout << "Adrien\n"; return 0;}   D. Country Meow   听说是红书上的板子 1234567891011121314151617181920212223242526272829303 ...