题意简述给定一个序列a，其长度为n,(a_i。然后有这样一个生成矩阵S，S的第i行有n-i+1个元素。第一行的元素就是a，对于后面几行，满足：S[i][j]=S[i-1][j]\ and \ S[i-1][j+1]，其中and表示位运算&，即按位取且。 支持两种操作： 修改a某一个位置的值 ...

题意简述给你一个[1,n]的排列，长度为n，多次查询一段区间中有多少对数满足其中一个是另一个的倍数。n是1e5，复杂度大约是log^2的，当然如果您能想出一个带根号的算法，那我开心死了。私信3348064478@qq.com，或者评论。 思路框架离线询问，然后用合理的遍历顺序加上一个完美的树状数组维 ...

题意简述给定四个正整数k,n,maxb,t。（$k<=10$，$n,maxb<=1e5,n\times maxb<=2e7$，$t<=1e9$）。k组数据，每次给定一个长度为n的序列a1,a2…an，每个数都在[0,maxb]之间。把a序列重复写t遍，求最长严格上升子序列长度 ...

题意简述有n(个鱼，其中第i个鱼把第j个与吃掉的概率是a[i][j]，保证a[i][j]+a[j][i]=1,a[i][i]=0。会有n-1轮，每一轮会等概率随机选择两个鱼来比♂拼，然后直到最后只剩下一个鱼。对于每个鱼，求最后剩下它的概率。 顺便膜鱼，鱼tql%%% 思路框架状压DP。对于每个状态， ...

震惊！一sb少年被一个A题卡了半天！题意简述给定两个字符串$a,b$，求有多少对有序对$(x,y)$使得$x$是$a$的子串，$y$是$b$的子序列。两字符串长度$<=5000$，空间$5000\times 5000\times 5$是够的。 思路框架裸的$DP$。 具体思路$dp[i][j] ...

题意简述构造一个r行c列的矩阵，r,c<=500，满足：不存在1<=i<=r，1<=j<=c，使得第i行所有数的gcd=第j列所有数的gcd（即：行，列gcd两两不同）多解输出任意一个。无解输出0。 思路框架 只有1x1的矩阵是无解的 r=1的情况，显然只要令矩阵为[2 ...

题意简述定义“支配数组”：长度>=2，且出现次数最多的那个数字唯一。 给定一个数组，请你求出这个数组中，长度最小的是“支配数组”的连续子序列的长度。 数组长度<=2e5。 思路最短的“支配连续子序列”，显然是：最左边和最右边两个数字相同，中间的数组两两不同。 设pre[i]表示a中上一个 ...

题意简述多组数据。有$n<=2e5$个人，每个人有$m_i,p_i$。如果有$m_i$个人投给了你，那么这个人也会投你。否则你珂以用$p_i$块钱贿赂它。求所有人都投你的最小花费。 思路框架先贿赂$m$大的，$p$小的。 具体思路首先，$m$值更大的显然需要更多的人投，才能免费。所以，大一些的 ...

题意简述给定一个有$n$个节点的树，$n<=5e5$。每个点只能染精确的$k$种颜色，有无限种颜色珂供选择，但是每种颜色不能出现超过两次。如果一条边连接的两个点的两个颜色中有至少一个共同的，这条边就会产生它边权的权值。合理分配使权值最大，输出最大的权值。 思路框架设$dp[i][0/1]$表示 ...

题意简述n首歌循环播放。每首歌有一个欢乐值。播放到一首歌，如果这首歌的欢乐值的两倍小于放过的最大值，则停止。对于每首歌，求出从这首歌开始播放，能放几首歌。n<=1e5。 思路框架如果全局最小值的两倍>=全局最大值，直接全部输出-1。 数组开三倍。维护一个单调递减的单调队列。现在考虑到$i ...