定义1：删去该点后最大子树最小的点定义2：删去该点后所有子树大小均不超过n/2的点两个定义是等价的。如果一个点有超过n/2的子树，那么往这个方向走一步，其最大子树会变小。性质：一棵树最多有2个重心且相邻重心到所有点距离和最小可以用调整法证明（相当于换根），P2986[USACO1

题面原题链接思路先从特殊性质入手，考虑\(s=0\)的情况。不难发现，路径是已经确定的，那么我们可以考虑手搓几步。\[0000\longrightarrow0001\longrightarrow0011\longrightarrow0010\longrightarrow0000\longrightarrow0100\longrightarrow0101\cdots\]可以看出似乎是两个二进

SS241121B.Soso的模法矩阵（modmat）题意给你长度为\(n\)的\(\{a_i\}\)，长度为\(m\)的\(\{b_i\}\)，设\(a_i'=\prod_{j=1}^ia_i,b_i'=\prod_{j=1}^ib_i\)，对所有\(i\in[1,n],j\in[1,m]\)，求\[(a_i'\bmodb_j')\bmod998244353

A点击查看代码#include<iostream>#include<algorithm>usingnamespacestd;constintN=105;#definelllonglongllt,shu[N],n;intmain(){cin>>t;shu[1]=1;shu[0]=1;for(inti=2;i<82;i++)shu[i]=s

ABC379题解目录ABC379题解目录A CyclicB StrawberriesC SowingStonesD HomeGardenE SumofAllSubstringsA Cyclicmanwhatcanisay?#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingull=unsignedlonglong;usingld=l

对于一个x我们发现最多只有\(\log\)次有效取模，但没啥用。我们发现\(dp\)数组(函数)是一个分段一次函数(等差数列)，然后从第一个\(a_i\)开始考虑，发现每次只会多出一条线段(就是\(a_i-1\)这条)其他线段会翻折到下面，对于一条线段只会进行\(\loga\)次翻折，所以对线段的操作总次数

B.osu!mania题面：\(pp=\max\left(0,\frac{320a+300b+200c+100d+50e+0f}{320(a+b+c+d+e+f)}-80\%\right)\times5\timesppmax\)输入：输入的第一行包含一个正整数$T$，表示数据组数。保证$1\leqT\leq100$。对于每组测试数据：输入

**[POI2004]PRZ****考察内容：二进制子集遍历，DP转移**#include<bits/stdc++.h>usingnamespacestd;intn,W;structdata1{ intt,w;}a[20];intdp[(1<<20)],tt[(1<<20)],ww[(1<<20)];intmain(){ scanf("%d%d",&W,&n); for(

ARC060C.TakandCards*1583简单题。考虑一个非常非常常见的Trick。把区间平均值为\(k\)转化为区间和为\(0\)只需要将每个数都减去\(k\)即可。然后就是一个朴素的背包求和为\(0\)方案数。注意处理负数下标就好了。#include<bits/stdc++.h>usingnamespacestd;typ

ARC059C.BeTogether签到题。枚举要改成哪个，因为值域只有\([-100,100]\)。然后对总代价取个\(\min\)即可。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constLLMAXN=105;LLn,A[MAXN];intmain(){ ios::sync_with_stdio(false); cin.ti

ARC058C.Iroha'sObsession*1174\(n\)再大一点的就是巨大恶心分类讨论。但我们注意到\(n\leq10^4\)，所以我们可以直接暴力枚举然后写个check。首先我们先把被ban掉的数存标记一下。然后从\(n\)开始往上查，一直查到\(10^6\)基本就可以了。然后每次检查一下有没有数位被

AtCoderBeginnerContest380总结A用桶统计\(1\)，\(2\)，\(3\)出现的次数，判断即可。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<queue>#include

一签三计数，罚坐了。草莓简单贪心，随便贪就过了。点此查看代码#include<bits/stdc++.h>usingnamespacestd;#definerep(i,s,t,p)for(inti=s;i<=t;i+=p)#definedrep(i,s,t,p)for(inti=s;i>=t;i-=p)#ifdefLOCAL FILE*InFile=freopen("in.in","r

多校A层冲刺NOIP2024模拟赛24\(T1\)A.选取字符串\(100pts\)考虑建出失配树，然后等价于询问\(\sum\limits_{S\sube\{0,1,2,\dots,n\},|S|=k}dep_{\operatorname{LCA}\{S\}}^{2}\)。不妨从\(\operatorname{LCA}\)的角度考虑，统计\(x\)能作为多少个\(|S|\)

[NOIP2012提高组]借教室题目描述在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来\(n\)

在Linux系统中，命令行为的差异是常见现象，尤其是当不同用户对相同操作的反馈不一致时：用户A使用ll和ls命令可以查看目录内容。用户B使用ll显示ll:commandnotfound，但ls命令正常工作。  基础概念：ll与ls的区别ls命令：ls是一个标准的Linux系统命

【刷题笔记】[BalticOI2024]Portal\(Solution\)先注意到，题目中的图形是许多的自相似图形，要求能满足要求的单位图形的最大面积先考虑只有一维的情况，设几个传送门的坐标为\((a_i,0)\)```发现将整个图形平移后答案不会改变，所以不妨把一个传送门移动到\((0,0)\)可以发现单

A.SumofThree枚举即可，是否可行只与\(a,b,c\)模三的余数有关，所以随便小范围枚举一下\(a,b\)就行了（只枚举\(1,2,3\)可能会因为两数相同而误判），这样最不容易错。点击查看代码#include<cstdio>usingnamespacestd;intmain(){ intT;scanf("%d",&T); while(T--)

在数组中想要找到一个元素，我们最先想到的就是遍历数组，用if语句判断它们是否相等，但时间复杂度太高，我们也不想遍历数组中的每个元素，感觉太麻烦了。这时就可以用二分查找的方法：先将数组排序，然后不断折中数组，只需比较中值与目标值的大小，更新中值的大小就行了，这样可以大大减少时间

P1314[NOIP2011提高组]聪明的质监员#[NOIP2011提高组]聪明的质监员题目描述小T是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有个矿石，从到逐一编号，每个矿石都有自己的重量以及价值。检验矿产的流程是：给定个区间；选出一个参数；对于一个区间，计

A-Frog1线性DP。状态转移方程为\[f_i=\min(f_{i-1}+\lverth_i-h_{i-1}\rvert,f_{i-2}+\lverth_i-h_{i-2}\rvert)\]，注意边界。代码#include<iostream>#include<cstdio>usingnamespacestd;constintN=1e5+5;intn,a[N];intf[N];inline

Rank大奋场，T3没切有点菜A.草莓和前天多校T3很像，所以一眼鉴定为贪心，从大到小选比从小到大选一眼优，代价一样时横竖无所谓先后，然后sort一遍就做完了，复杂度\((n+m)\log(n+m)\)。10min切的。点击查看代码#include<bits/stdc++.h>#definefo(x,y,z)for(registerint

首先扔出一个结论，如果\(Q\)中没有\(-1\)，那么答案是\(2^k\)，其中\(k=\sum_{i=2}^n[Q_i=\max(P_{1\simi})]\)。考虑证明。设\(Q_i=\max(P_{1\simi})\)的位置（包含\(i=1\)）是\(a_1\sima_{k+1}\)。那么设\(f_i\)为\(1\sima_i\)的答案，显然\(f_1=1\)。考虑\(Q_{a_i}\)

比赛链接：https://ac.nowcoder.com/acm/contest/95928#question这次D题小细节搞了好久，越界了好几次，没想到赛后做E，发现还更简单的A.三途川的摆渡人（二）题面：小红这天来到了三途川，发现这里有一个摆渡人，名字叫小町。小町的职责是将一些灵魂运送到冥界。但小町非常喜欢偷懒，她经常在上

Solved：5/13Penalty:707Rank：101Rank（ucup）：200比赛链接A.TheFool题意：给一个\(n\timesm\)的字符串矩阵，有一个字符串和其他不同，求这个字符串的位置。直接模拟即可。#include<bits/stdc++.h>usingnamespacestd;constintN=205;stringa[N];intmain(){ios::s