前言
由于时间过少，这里仅仅记录我自己的思路（给自己看的），如果你有兴趣可以看看原题，再看看我写的，但是一般情况下不会很友好，此类文章在以后都会标记“（记录型博客）”

A

我们发现，所有的剩余量一定是
a+2ba+\sqrt 2 ba+2​b或者是C−(a+2b)C-(a+\sqrt 2 b)C−(a+2​b)的形式
把所有这些形式的全部抽出来
分析一下种类好像不是很多，然后建图跑最短路即可

B

首先有个性质，就是这么生成的树的直径一定是小于等于$\mathcal{O}(logn)$的
然后考虑dp
设fu,lf_{u,l}fu,l​表示以$u$为根，直径不超过$d$，距离$u$的最远点距离不超过l的子树最多包含的点数
转移是对于每个fu,lf_{u,l}fu,l​，加入儿子，枚举儿子更新到的$l$，我们发现只需要$l+s+1\le d$即可，所以是一个前缀max形式，对于$s+1>l$的情况另外处理一遍即可
然后，在枚举删去点的数量的时候，我们只需要枚举剩余直径长度即可，所以要扫$\mathcal{O}(logn)$遍，每遍复杂度$\mathcal{O}(nlogn)$
综上总复杂度O(nlog2n)\mathcal O(nlog^2n)O(nlog2n)

C

排序后直接统计相邻两个数相差大于m的数量即可

D

感觉是构造题？
$n$是奇数的话
123⋅⋅⋅n−1nn12⋅⋅⋅n−2n−1n−1n1⋅⋅⋅n−3n−2⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅234⋅⋅⋅n1\begin{matrix} 1&2&3&···&n-1&n\\ n&1&2&···&n-2&n-1\\ n-1&n&1&···&n-3&n-2\\ ···&···&···&···&···&···\\ 2&3&4&···&n&1 \end{matrix} 1nn−1⋅⋅⋅2​21n⋅⋅⋅3​321⋅⋅⋅4​⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅​n−1n−2n−3⋅⋅⋅n​nn−1n−2⋅⋅⋅1​
就好了
然后若$n=4$
1234432121433412\begin{matrix} 1&2&3&4\\ 4&3&2&1\\ 2&1&4&3\\ 3&4&1&2\\ \end{matrix} 1423​2314​3241​4132​
之后就构造了
设已经求出答案为$n$的矩阵$A(n)$
沿着对角线翻转的矩阵为A′(n)A'(n)A′(n)
现在要对新的$n$求答案，设$n=2k$
A(2k)={A(k)+kA′(k)A(k)%k+1A(k)+k}A(2k)=\left\{ \begin{matrix} A(k)+k&A'(k)\\ A(k)\%k+1&A(k)+k \end{matrix}\right\} A(2k)={A(k)+kA(k)%k+1​A′(k)A(k)+k​}
由于$A(k)+k$本身不会不满足对称的性质
考虑$A(k)\%k+1$和A′(k)A'(k)A′(k)，原本$A(k)$和A′(k)A'(k)A′(k)是完全对称的，现在$A(k)$全部改了值，所以问题就解决了

E

建出所有免费走的地方之间的边，跑最短路即可
复杂度O(n2log2n)\mathcal O(n^2log^2n)O(n2log2n)

F

按照权值从小到大加边
新增点权为某个节点到当前点路径的xor
然后建trie，加边合并的时候启发式在trie里查询
总复杂度O(nlog2n)\mathcal O(nlog^2n)O(nlog2n)

G

如果没有最后的交换操作的话直接贪心取段，然后将最多的段数与k比较即可
然后考虑有交换的情况，这就非常麻烦了
我们考虑[a1,a2][b1,b2][c1,c2][d1,d2][e1,e2][f1,f2]⋅⋅⋅[a_1,a_2][b_1,b_2][c_1,c_2][d_1,d_2][e_1,e_2][f_1,f_2]···[a1​,a2​][b1​,b2​][c1​,c2​][d1​,d2​][e1​,e2​][f1​,f2​]⋅⋅⋅的情况
假设我们要交换两段，我们发现左段的左端点一定是某段的左端点，右段的右端点一定是某段的右端点（否则一定能分开新的段）
假设我们现在左段左端在x1x_1x1​，右段右端在y2y_2y2​
我们发现若$x\ne y$则交换之后一定不成立
所以$x=y$
于是我们相当于要把一段内部花一次交换的代价以分成更多段
我们发现只要确定第一段和最后一段的端点，中间的当成不能交换的问题做就好了
我们要把第一段和最后一段翻转，所以第一段一定要包含R，最后一段一定要包含L，然后我们通过贪心把所有可以作为第一段的右端点的点都搞出来，我们发现这些点也可以成为最后一段的左端点，考虑这些分的段，如果除了第一段与最后一段剩下大于1段的，这两段排序后将不有序，所以一定只有贪心出来的一段能继续再分，于是我们就将每一段求出最大值取max即可
这里的段的示意图[xk,n][xk−1,xk)⋅⋅⋅[x1,x2)[1,x1)[x_k,n][x_{k-1},x_k)···[x_1,x_2)[1,x_1)[xk​,n][xk−1​,xk​)⋅⋅⋅[x1​,x2​)[1,x1​)，我们每次算一个[xi,xi+1][x_i,x_{i+1}][xi​,xi+1​]的答案就好了
，总复杂度$\mathcal{O}(n)$
下面是AC代码
题目链接

#include
#include
#include
//#include
#define rg register
typedef long long ll;
template <typename T> inline T max(const T a,const T b){return a>b?a:b;}
template <typename T> inline T min(const T a,const T b){return a<b?a:b;}
template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;}
template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;}
template <typename T> inline T abs(const T a){return a>0?a:-a;}
template <typename T> inline void Swap(T&a,T&b){T c=a;a=b;b=c;}
//template  inline void swap(T*a,T*b){T c=a;a=b;b=c;}
template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);}
template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;}
template <typename T> inline T square(const T x){return x*x;};
template <typename T> inline void read(T&x)
{char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;
}
template <typename T> inline void printe(const T x)
{if(x>=10)printe(x/10);putchar(x%10+'0');
}
template <typename T> inline void print(const T x)
{if(x<0)putchar('-'),printe(-x);else printe(x);
}
int n,k,a[1000001],maxplace,las=1;
int ok[1000001],tot;
void rt(const bool fla)
{if(fla)puts("Yes");else puts("Poor Simon");exit(0);
}
int le,aaa[1000001];
int calc2()
{int ma=0,an=0;for(int i=1;i<=le;i++){maxd(ma,aaa[i]);if(i==ma)an++;}return an;
}
int len,A[1000001];
int calc1()
{maxplace=0;int ans=0,fst=0,la=1;for(int i=1;i<=len;i++){maxd(maxplace,A[i]);if(i==maxplace){fst++;if(fst!=1&&i!=len){le=i-la+1;for(int j=1;j<=le;j++)aaa[le-j+1]=A[la+j-1]-la+1;maxd(ans,calc2());}la=i+1;}}return ans+min(fst,2);
}
int check(int l,int r)
{len=r-l+1;for(int i=1;i<=len;i++)A[len-i+1]=a[l+i-1]-l+1;return calc1()-1;
}
int main()
{read(n),read(k);for(int i=1;i<=n;i++)read(a[i]);for(int i=1;i<=n;i++){maxd(maxplace,a[i]);if(i==maxplace)ok[i]=1,tot++;}if(tot>=k)rt(1);for(int i=1;i<=n;i++)if(ok[i]){if(tot+check(las,i)>=k)rt(1);las=i+1;}rt(0);return 0;
}

H

我们发现只要赢的次数最多，直接贪心即可，两行代码足矣

I

大概是经典的FFT题目，先转化为原根求和，变成加法问题后直接用FFT做卷积即可

J

我们发现，我们要求的是最长不上升子序列即$0\cdot \cdot \cdot 01\cdot \cdot \cdot 1$形式
要求所有的(sum0+sum1)sum0=sum02+sum1sum0(sum_0+sum_1)sum_0=sum_0^2+sum_1sum_0(sum0​+sum1​)sum0​=sum02​+sum1​sum0​
考虑枚举最右边的一个$0$
我们要求的是∑sum1\sum sum_1∑sum1​，并且要满足这是最右边的$0$，如果右边有更多就不优
考虑dp，fi,j,gi,jf_{i,j},g_{i,j}fi,j​,gi,j​分别表示到第i个数，1的数量，方案数推完即可，复杂度O(n2)\mathcal O(n^2)O(n2)（容易发现$1$的数量要一直大于$0$的数量）
再考虑求左侧的情况，要求∑sum0\sum sum_0∑sum0​非常方便，同理即可（不过这里容易发现$0$的数量要一直大于等于$1$的数量）
然后求∑sum02\sum sum_0^2∑sum02​好像也没啥区别，贡献的时候有个平方就好了
然后就做完了
复杂度O(n3)\mathcal O(n^3)O(n3)

K

容易发现，对于原序列，每一个左括号都有相应的有括号进行匹配，对于任何截取的一段$l,r$，括号匹配的要求是不变的，所以直接维护每个左括号匹配的右括号位置即可，每次询问用一个区间max即可
）厉害的人可以搞一个$\mathcal{O}(n)-\mathcal{O}(1)$rmq

L

根据扩展欧几里得可知x,y的通解
现在相当于求$ax(b+x)+cy(d+y)$
然后因为给出的系数都很小，好像枚举就好了

结语

完

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！