cf-936-div-2 5/6
比赛链接：Dashboard - Codeforces Round 936 (Div. 2) - Codeforces
C
题意：给一棵有 $n$ 个节点的树，找到最大的 $x$ ，使得这棵树删去 $k$ 条边后剩下的每个联通块的大小至少为 $x$ 。
可以二分答案。
在每次check时，dfs统计以每个节点为根的子树大小，当以某个节点为根的子树大小大于等于 $x$ 时就删去这条边，同时将size清零，不影响父节点的儿子统计。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include <iostream>#include <vector>#include <algorithm>using namespace std;vector<int> adj[100001]; int n, k;int res;int dfs(int x,int u,int fa) ...
多层感知机(2)-mlp一些概念
K折交叉验证
将原始训练数据分成k个不重叠的子集，，进行k次模型训练和验证，每次在k-1个子集上训练，并在剩余的一个子集进行验证。最后通过k次实验的结果取平均来估算训练和验证误差。
正则化：权重衰减
在训练集较小时为了防止训练过拟合，采用权重衰减正则化的方法，也叫做 $L_2$ 正则化。具体为，在损失函数中加入范数一项。
$$
loss=L(w,b)+\frac{\lambda}{2}||w||^2
$$
更新公式为：
$$
w\leftarrow (1-\eta\lambda)w-\frac{\eta}{|\beta|}\sum x^{(i)}(w^\mathrm Tx^{(i)}+b-y^{(i)})
$$
通常偏置不会被正则化。
12345678910###定义网络，wd表示系数lambdanet = tf.keras.models.Sequential()net.add(tf.keras.layers.Dense(1,kernel_regularizer=tf.keras.regularizers.l2(wd)))......###正则化损失存储在losses中，要手动加入fo ...
3-21
比赛链接：Dashboard - The 2023 ICPC Asia Jinan Regional Contest (The 2nd Universal Cup. Stage 17: Jinan) - Codeforces
A
题意：有一个合法的由 $(\ ),[\ ]$ 组成的括号序列，现在括号的左右反了，如 $($ 可能写成了 $)$ ，求能不能根据现有的序列找到一个唯一的初始括号序列。
先不考虑括号的左右，对同种括号操作。
将括号分层，如 $(\ )\ [\ ]\ (\ )$ 均属于第一层，而 $(\ [\ ]\ [\ ]\ )$ 中，小括号属于第一层，中括号属于第二层；若同种符号出现在了同一层，那么可以调转两个靠内的符号使其生成两种不同的序列，如 $(\ (\ [\ ]\ )\ )$ ， $(\ [\ [\ ]\ ]\ )$ 。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include<bits/s ...
多层感知机(1)-mlp原理
mlp原理
多层感知机，简称mlp，通过在网络中加入一个或多个隐藏层来实现。设矩阵 $\pmb X\in R^{n\times d}$ 表示 $n$ 个小样本，设 $\pmb H\in R^{n\times h}$ 表示有 $h$ 个输出的隐藏层输出，有：
$$
\pmb H=\pmb X\pmb W^{(1)}+b^{(1)}
$$
$$
\pmb O=\pmb H\pmb W^{(2)}+b^{(2)}
$$
设置激活函数 $\sigma$：
$$
\pmb H=\sigma(\pmb X\pmb W^{(1)}+b^{(1)})
$$
$$
\pmb O=\pmb H\pmb W^{(2)}+b^{(2)}
$$
常用的激活函数有 $ReLU,sigmoid$ 等。
mlp改进softmax回归
在定义模型部分改为：
12345###添加输出为256的隐藏层，激活函数为'relu'net = tf.keras.models.Sequential([ tf.keras.layers.Flatten(), tf.keras.layers.Dense(2 ...
mashups-1
链接：Dashboard - practice - Codeforces
3.18 A,B
题意：A有 $a_i$ 个颜色为 $i$ 的弹珠，B有 $b_i$ 个颜色为 $i$ 的弹珠，现在游戏规则如下：从A开始，两人轮流进行，每次选择一种大家都有的颜色，然后自己丢弃一颗该颜色的弹珠，对方丢弃所有该颜色的弹珠。定义最终分数为A的所有弹珠和与B的所有弹珠和的差。A想最大化分数，B想最小化分数，求最终的分数。
当A选择时，对于 $i$ 和 $j$ ，若A选择了 $i$ ，B选择了 $j$ ，那么必有：
$$
(a_i-1)-(b_j-1)>(a_j-1)-(b_i-1)
$$
即：
$$
a_i+b_i>a_j+b_j
$$
故按照 $a_i+b_i$ 降序排列，依次操作即可。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include<bits/stdc++.h>using namespace std;bool cmp ...
manacher
给定一个字符串，$O(n)$ 时间内找出以每一个字符为回文中心时的最大回文长度。
1234567891011121314151617181920212223242526vector<int> manacher(string s){ string t; for(auto c:s) { t+=string("#")+c; } t+=string("#"); int n=t.length(); vector<int>p(n+2); t="$"+t+"%"; int l=1,r=1; for(int i=1;i<=n;i++) { p[i]=max((int)0,min(r-i,p[l+r-i])); while(t[i+p[i]+1]==t[i-p[i]-1])p[i]++; if(i+p[i]& ...
权值线段树
给出 $n$ 个数，每次有两种操作：
$1 \ i\ x $ ：把第 $i$ 个数改成 $x$ 。
$2\ sum$ ：求最少的前 $k$ 大数，使之和大于等于 $sum$ 。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081# include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 200010, M = 2 * N;const int inf=1e9+1;int n,m;int a[N];struct Node{ int l,r,num; LL sum;}tr[4 * M + M * 19];int tot;void update(int &id,int l,int r,int pos, ...
cf-934-div-2 4/7
比赛链接：Dashboard - Codeforces Round 934 (Div. 2) - Codeforces
B
题意：有长度为 $2n$ 的数组 $a$ ，由 $1-n$ 的每个整数组成，每个整数出现两次。需要找出两个长度为 $2k$ 的数组 $l$ ，$r$ ，使得 $l$ 是 $[a_1,a_2,…,a_n]$ 的子集， $r$ 是 $[a_{n+1},a_{n+2},…,a_{2n}]$ 的子集，且 $l_1\bigoplus l_2\bigoplus …\bigoplus l_{2k}=r_1\bigoplus r_2\bigoplus …\bigoplus r_{2k}$ 。
将前 $n$ 个元素和后 $n$ 个元素分别排序，先考虑数组 $l$ ，即前 $n$ 个元素：若有连续的相同元素，那么都选，且数组 $r$ 需要选的两个相同元素的数量+1；然后再考虑单个的元素，那么必然是两个元素一个在 $l$ ，一个在 $r$ ，都统计上即可。
123456789101112131415161718192021222324252627282930313233343536 ...
线性神经网络(2)-softmax回归的实现
原理
对于分类问题，我们希望的是输出一个标签，表示属于哪一类，因此对于每一个标签都应输出一个概率，概率最大的即为标签。采用softmax进行归一化：
$$
\hat {\pmb y}=softmax(\pmb o),\hat y_j=\frac{e^{o_j}}{\sum_{k}e^{o_k}}
$$
因此softmax的矢量计算表达式为：
$$
\pmb O=\pmb X\pmb W+\pmb b,\hat{\pmb Y}=softmax(\pmb O)
$$
定义损失函数为交叉熵：
$$
l(y,\hat y)=-\sum y_j log\hat{y_j}
$$
然后每次利用梯度对参数进行更新。
softmax回归的实现(TensorFlow的高级API)
读取数据集；
定义模型；
定义损失函数、优化器；
设置超参数进行训练
导入数据集
1234import tensorflow as tffrom d2l import tensorflow as d2lbatch_size = 256train_iter, test_iter = d2l.load_data_fashion_ ...
3.17
比赛链接：Dashboard - 3.17 周赛 - Codeforces
B
水题
12345678910#include<bits/stdc++.h>using namespace std;int main(){ int n; cin>>n; if(n<=3)cout<<1; else cout<<n-2; return 0;}
D
字符串模拟水题
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include<bits/stdc++.h>using namespace std;int n,m;string s[30];map<string,pair<int,int>>mp;//映射的序号、有几个翻译set<string>ppp;int cnt=0;st ...
