ABC254
C题：给定一个长为n的数列，给定k，可以进行的操作是：交换a[i]和a[i+k]，可以进行任意多次，问能否sort成一个非递减数列？
我当时的思路：因为我们是知道最后的数列的样子的，然后就思考：“这个数怎么变过来？可以变吗？” 然后就发现好像只需要最后的非递减数列的每一个数在原数列中的对应下标和变换完成后的下标相差k就行了
formally thinking之后就发现可以把原数列相等切割成k份 每一份中每一个数的个数相等即可
implementation: 我们需要判断是否每个数在两集合中出现的次数都相等 本来想用两个unordered_map<int,int> mp1[k],mp2[k] 来分别表示sort前和sort后的每个数的个数 然后判断是否相等（任意i 任意j mp1[i][j] == mp2[i][j]）后来发现不需要这么复杂 可以只用一个unordered_map即可（任意i,j mp[i][j] == 0）
反思：熟知结论：如果任意相邻两项可以swap，那么一定可以变成ascending 于是此题就相当于一个小特例 虽然当时没有看出来QwQ
D题：给定一个数N （2e5）求有多少个正整数对<i,j>满足i*j为平方数
其实思路是和题解一致的 就是这样的i和j满足条件等价于把他们的平方因子（不妨记为s[i]和s[j]）去除之后的i'和j'有完全一样的素因子集合 所以只要对每一种集合记录有多少个i会变成同一个集合
然而vp的时候花了大把时间在思考“如何表示这一个去除所有平方因子后剩下的素因子集合”（想着用一个map<set,int>……） tmd看题解才发现 原来只需要i/s[i] == j/s[j]？？？？？？？ 我直接晕倒（就是说这个状态考可以完全等价于把所有素因子乘起来用一个数表示）e.g.140 → 5、7 → mp[35]++
思考：学到了一种新的表示状态的方法：如果有很多元 那就找一个生成函数（或许是这么叫的？）映射过去（有点hash的意味了hh）
E题：暴力bfs/dfs
implementation: 需要多次使用搜索（但是每次搜索量都不大）因此需要反复重置st数组 如果每次都memset，会set 2e5*2e5个导致TLE，解决方案是每次bfs的时候用vector记录visited的点，然后把这些点重置即可
F题：不会TVT 有两个长度为n的数列a[1]a[n]；b[1]b[n] 有一个n*n的长方形，g[i][j] = a[i]+b[j]；有Q个询问 询问(l1,r1),(l2,r2)围成的长方形的gcd
残破的思路：如果要是长方形的gcd那么就需要是a[i]-a[i-1]; a[i-1]-a[i-2]；……；b[j]-b[j-1]的公因子 然后就只需要再是左上角元素的因子就可以啦！ 感觉很像前缀和但是前缀不出来w 反正就是感觉思路就是正确的 但怎么预处理就不晓得了
看完题解………… md要用segment tree……思路正确但tm真的不会线段树（哭） 爬去学惹
G题：好吧 大概想法是贪心但题解没咋看懂 先放放w
ABC324
C题：可以说是今日最让我感到惊艳的题目了！对一个字符串S 如果可以经过0或1次操作变换成T 那么称为二者等价 操作consist of（在任意位置 删除一个字符/增加一个字符/更改一个字符）（易知满足对称性） 给定模式字符串T （5e5） 和好多个S[i]（总长5e5） 求出和T等价的S[i]的个数及具体下标
解答：桃花影落飞神剑！ 答案把“等价”这一个模糊的概念转化成了一个完美的充要条件！ 简直太精彩了！具体就是：如果T删除了一个元素变成S 那么s.size() == t.size()-1 && pre(s,t) + suf(s,t) >= s.size()（其中pre代表s和t共用的前缀（连续） suf为后缀） 同理另外两种等价关系也可以这样描述
反思：反正就是……太厉害了……只能赞叹…… 或许有一点divide and conquer的想法在里面？反正这个分类就很妙（莫名联想到最优贸易那一道题 分成点1到点k路径中的最小值 & 点k到点n路径中的最大值）
D题：给定一个长度为N的字符串S（13位） 可以将它以任意顺序排列 判断能排成几个完全平方数
implementation: 枚举所有平方数 判断是否和原字符串有相同的multiset 但是实际上不需要用set这么麻烦
首先是对S进行一个sort ** ranges::sort(S) 或者 sort(S.begin(),S.end());
然后枚举i*i 然后使用to_string方法变成string T（*这个方法其实也可以对double使用！） 然后T.resize(N,'0') ** 然后ranges::sort(T) 然后判断S==T?
比我的方法好太多hh
F题：有向图 每个边: u[i] → v[i] 有两个权值b[i]和c[i] 寻找从1到n的path使得Σb[i] / Σc[i]最大 求最大值（精确到1e-9） extra条件：每个有向边都是从小的点射向大的点
残破的想法：dijkstra？但是怎么搞呢……不会w
解答：我们可以二分答案qaq 然后如果Σb[i] / Σc[i] >= x ===== Σ(b[i]-xc[i]) >= 0 !!!这样就可以变成最短路问题了！！！（非常巧妙 本来b[i]和c[i]之间是独立的 这样一下子变成了每个b[i]只要和c[i]亲就可以了！！ 奇妙的数学等价法！！）
implementation：此题如果用spfa+二分依然会爆（没试dijkstra但感觉也会/哭） 然后题目给了一个非常非常精妙的求最短路的方法！（时间是O(m)）也就是用dp！！ 反正我是想不到qwq
G题先放放ovo
标签：sort,数列,一个,可以,笔记,因子,3.25,然后,刷题 From： https://www.cnblogs.com/BladeWaltz/p/18095125