题意小红定义一个字符串是好串，当且仅当每个字母出现的次数均为偶数。小红拿到了一个字符串，她想知道该字符串有多少子序列是好串？思路题目里求的是满足xxx条件的子序列的个数，那每个字母的贡献都可以单独拿出来算了，比如题目样例的 ababa 字符串，a出现了3次，b出现了2次，那么对于a来说，从里面选偶数个都可以构成一种答案，对于b来说也同理。a和b的选择都是独立的，不难想到相乘就是答案。所以先用哈希表统计出每个字母出现的次数。对于一个字母来说，出现的次数为x，其对答案的贡献是c[x][0] + c[x][2] + c[x][4] + …… ，即组合数里所有的偶数项加起来，根据组合数的性质C(n,0...

题意给定一个仅包含'('、')'和'?'三种字符构成的字符串，'?'字符可以代替左括号或者右括号。请问该字符串可以代表多少种不同的合法括号序列？思路看基本上都写的dp，来个记忆化搜索的代码吧 每个?字符都有两种可能，填左括号或是填右括号，可以枚举填哪个进行记忆化搜索 如何判断是合法的括号序列？只需要维护左括号比右括号多了几个就可以，也就是当前没有配对的右括号个数。假设为val，如果当前是左括号，那么下一次dfs的参数肯定是val+1；如果当前是右括号，下一次dfs参数是val-1，表示可以配对一个左括号。注意这里其实会有不合法情况，就是其实左边是没有左括号的，也就是val为负数的情况，需要在d...

题意小欧拿到了两个正整数x和y，她想进行一些操作使得x不小于y，操作方式是：选择a数组中的一个元素ai，将x乘以ai，并删掉a数组中所有的ai。小欧想知道，自己最少进行多少次操作，可以使得x不小于y？思路根据题意，数组里的每个元素只能用一次，所以需要对数组进行去重，这里直接输入的时候加了个哈希表维护了。贪心地考虑，需要操作次数最少，那每次乘的元素肯定要尽量的大，这样一次操作产生的贡献才多，所以数组排序后，从大到小进行遍历，如果x>=y就跳出循环。最后记得判断一下x和y的关系，以判断-1的情况Go代码 package main import ( "fmt" &qu...

题意小欧正在扮演一个中世纪的皇帝。地图上有n个城市，其中有m条道路，每条道路连接了两个城市。小欧占领了其中一些城市。如果两个城市可以通过若干条道路互相到达，且这些道路经过的城市都是小欧占领的，那么这两个城市之间就可以通过经商获得收益1。请注意，每两个城市之间的收益只会被计算一次。现在，小欧准备占领一个未被占领的城市，使得总收益最大化。你能帮帮她吗？思路如果一个联通块的大小为x，那么可以获得的收益是C[x][2] ，也就是从这个联通块里选2个点的方案数，x*(x-1)/2 具体思路：用并查集找出所有的联通块和联通块大小维护当前能够得到的收益 枚举所有未占领的城市，看把这个城市占领后能得到的收益。...

题意小红在第三新北林市的学园城送外卖，学园城中有非常多的学校，学园城里有一个美食街。小红每次会接一些同一个学校的订单，然后从美食街取餐出发，再骑车将外卖送到学校，最后回到美食街，以此往复。学园城有 n 个结点， m 条道路，美食街为1号结点，剩下的结点都是学校，保证学园城中所有结点连通。给出小红每次要送外卖的学校，请计算小红最少需要骑行的距离。思路考察Dijkstra算法的性质当Dijkstra算法完成后，源点到所有已访问顶点的距离是最短的。然而，对于未访问的顶点，算法不能保证它们到源点的距离是最短的，因为算法一旦一个顶点被确定为已访问，就不会再考虑它。题目说 保证所有结点都是联通的，所以跑完...

题意游游准备去开车旅行，她初始在1号城市，准备前往n号城市。游游打开了携程，她查询到了地图上有若干城市，城市之间有一些道路连接。每条道路有承重限制，当游游的车重量超过了承重时，她就不能走这条道路。游游是一个贪心的人，她希望总路程不超过h的前提下，携带尽可能多的物品出行。游游想知道，自己的车最多重量能达到多少？思路题目求的是 车的重量的最大值 单调性：如果车的重量为10时，可以走到终点，那么车的重量为5的时候也一定可以走到终点，因为车的重量减少后，可走的道路只多不少。所以可以二分答案，考虑下如何check 当前的重量是x的话，对于每条道路u,v,w，如果w>=x的话，这条道路才能被作为可走...

题意给出v,x,y 求一个最小的t满足 y/(v+x*t) + t 最小 思路v,x,y都是已知的，那么这个式子可以转化为 m1/(m2+m3*t) + t比如样例的话实际上就是y=2/x+x，其中x>=0，这是一个凹函数，先下降再上升，可以用三分来求极值 Go代码 package main import ( "fmt" ) func main() { var v, x, y float64 fmt.Scan(&v, &x, &y) var l, r float64 = 0.0, 1_000_000_000 cul := func...

题意平面上有n个点，每个点有一个点权v。你现在可以以原点为圆心放置一个圆，请问要使圆能覆盖到的点的权值和达到x，圆的半径至少为多少？思路最小值问题 先考虑下单调性 点的点权为正整数，如果圆的半径增加，那么能覆盖的点会增大，权值和增大，具有单调性，所以可以二分圆的半径。对于check函数，需要判断在圆里的点的权值和。这里用的是点到原点的距离和半径的比较做的Go代码 package main import "fmt" type MyPoint struct { x, y, v int64 } func main() { var n int var x int64 ...

题意小红有n个朋友。她准备邀请一些朋友请他们吃饭。已知第ii个朋友的财富值为ai​，小红邀请他带来的愉悦值为bi​。如果小红邀请的两个朋友的财富值为x和y，那么他们之间就会产生∣x−y∣的隔阂。小红这桌饭局的隔阂值为隔阂最大的那一对朋友的隔阂，这桌饭局的愉悦值为所有受邀朋友的愉悦值总和。小红希望这桌饭局的愉悦值至少达到kk。她想知道最终饭局隔阂的最小值是多少？思路隔阂值的定义是隔阂最大的那一对朋友的隔阂，求最后满足xx条件的隔阂的最小值是多少？这其实可以理解为一个最大值最小化问题，一般推一下单调性的话可以用二分来求。单调性说明：先按财富值从小到大排序，权值都是正整数，假设现在的饭局是朋友i~j...

题意定义一个数组为“稳定的”，当且仅当数组相邻的两个元素之差的绝对值不超过1。求出该数组的最长的“稳定的”连续子数组的长度思路一次遍历即可，维护两个变量，其中ans表示答案，tmp表示当前的稳定的连续子数组的长度，如果第i个元素可以和第i-1个元素构成稳定子数组，tmp加1；否则，维护ans。注意遍历后还要更新下ansGo代码 package main import ( "fmt" ) func abs(a int) int { if a < 0 { return -a } return a } func max(a, b int) int { ...

题意给定n个正整数组成的数组，求平均数正好等于 k 的最长连续子数组的长度。思路某个连续子数组的平均数等于k可以转化为区间和等于k*(j-i+1)如果用前缀和维护的话就是sum[j] - sum[i-1] = k * (j-i+1)这里有个很巧妙的地方就是把每个数都减去k，这样就变成了sum[j]-sum[i-1] = 0 可以用哈希表维护 mp[x]表示前缀和为x的最早出现的位置 代码 package main import ( "fmt" ) func main() { //sum[j] - sum[i-1] = k*(j-i+1) var ...

题意给出一个数组，求该数组所有的子序列中的逆序对数量之和是多少数组长度1e5思路这种求所有子序列/子数组xxx值的和一般都是考虑单个元素的贡献，这里考虑的是单个逆序对的贡献，对于每个逆序对来说，剩下的n-2个元素每个元素都有选或不选两种选择，可以构成的子序列个数为2^(n-2)，那么如果有x个逆序对的话，最后答案就是x*2^(n-2)求逆序对可以用归并排序或是树状数组，求次幂需要用到快速幂归并排序：大概的思想是分治，一个区间的逆序对数量=左边逆序对的数量+右边逆序对的数量+跨左右边界的逆序对的数量，前两个都可以在分治的子过程里计算，跨左右边界的话，其实就是考虑在合并2个已经排序的子数组的时候，...

题意有n个盒子，可以进行m次操作，每次操作有2种向编号为x的盒子里放一个小球向除了编号x的其他n-1个盒子里放一个小球求第几次操作后，所有盒子里至少都有一个小球思路答案是具有单调性的，因为每次都是往盒子里放小球，第x次操作后，所有的盒子里至少有一个小球的话，那么第x+1操作后，也肯定满足这个条件。而且这个操作的顺序是不会改变的，可以二分答案的方式做。对于二分的check函数，实际上就是判断执行了前mid次操作后，每个盒子里球的个数是否都大于0，操作1和操作2都可以看成对区间的操作，所以可以用差分数组来维护盒子里球的个数，最后求和后判断是否所有的盒子球的个数都大于0就可以知道执行前mid操作能否...

思路数组a[i]表示编号为i+1的人要转给小红的钱数，要注意每次转账的钱是上取整，这里用的方法是判断了下c%k的值，如果不为0则答案再+1 Go代码 package main import ( "fmt" ) func main() { var n, m, k, c, x int fmt.Scan(&n, &m) a := make([]int, m) for i := 1; i <= n; i++ { fmt.Scan(&k, &c) now := c / k if c%k != 0 { now++ ...