千题目标CategorySubscribe

传送门

题意是说给定长度为n的字符串A，长度为m的字符串B，q个询问

每次询问有A的所有后缀里有多少个使得与B的前缀匹配长度恰好为K

在对A字符串做匹配的时候，本来 f[i] = j 表示的是A中以A[i]结尾的后缀与B的前缀的最大匹配长度。现在要改一下定义。f[x]表示匹配长度至少为x的有多少个位置。

当A中以A[i]结尾的字符串与B的最大匹配长度为j的时候，证明产生了一个匹配长度至少为j的后缀，但是不一定是恰好为j，因为此时的A[i]结尾字串并不是A数组的后缀。然后需要发现：匹配长度至少为next[j]的后缀的数量也增加了。

于是f函数的各个函数值之间是拓扑的关系。f[k] = \sum\limits_{next[j]=k} f[j]

于是匹配长度恰好为x的数量就是f[ x ] – f[ x + 1 ]

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int n, m, q;
char a[maxn], b[maxn];
int ne[maxn], f[maxn];
int main()
{
    cin >> n >> m >> q;
    cin >> a + 1 >> b + 1;
    ne[1] = 0;
    for(int i =2, j = 0; i <= m; i++)
    {
        while(j > 

传送门

一般CDQ分治。

如果用二维BIT在线做的话，空间是不能承受的。所以考虑CDQ离线。

如果没有加数操作，只有询问，那么按照x排序，在y方向维护树状数组，就可以算出每个询问的答案。

现在有了加数操作，相当于时间变成了第三位。于是先按第三维排序，进行CDQ分治。每次分治之后把前一半的修改对后一半询问的影响看成一个离线询问。

然后玄学的地方出现了

把y坐标进行离散化。TLE

优化常数一，对每个y坐标改为它离散化后的相对大小，减小查询常数。TLE（甚至一组都过不了

优化常数二，把坐标离散化后再离线，对于每个下标 i 的坐标y，都存在idx[]数组里访问。TLE

优化常数三，把unorder_map改为了int数组，查询y坐标的时候直接访问数组，TLE

以上操作二和操作三是分开的，也就是说，两个理论查询复杂度O(1)的操作都是TLE

优化常数四，把操作二和操作三合并，理论上还是O(1)的而且常数还稍大了一点。AC……

#include<bits/stdc++.h>
using namespace std;
//unordered_map<int,int> ump;
const int maxn = 1e6 + 233;
struct Node{
    int x, y, t, v;
}q[maxn], b[maxn];
int ans[maxn], c[maxn], tot = 0, idx[maxn];
int ump[maxn * 2];
inline void add(int x, int v)
{
    for(; x <= tot; x += x & -x) c[x] += v;
}
inline int ask(int x)
{
    int res = 0;
    

传送门

最小表示这颗有根树，注意要加入哨兵元素

#include<bits/stdc++.h>
using namespace std;
string s1, s2;
string gao(string &s, int &i)
{
    vector<string> v;
    i++;
    while(s[i] == '0')
    {
        v.push_back(gao(s, i));  
    }
    i++;
    string res = "0";
    sort(v.begin(), v.end());
    for(auto &str: v) res += str;
    res += "1";
    return res;
}
int main()
{
    int T; cin >> T;
    while(T--)
    {
        cin >> s1 >> s2;
        s1 = '0' + s1 + '1';
        s2 = '0' + s2 + '1';
        int n = 0, m = 0;
        

传送门

题意是说给定一个序列，只能交换相邻的两个数。问最后形成单峰序列（单调也是单峰）所需要的最小交换步数。

首先如果只需要单调数列，那么排序后，每个数在原序列中的下标所形成的逆序对就是交换次数。

由这个性质可以知道，旧序列的下标在新序列的逆序对就是答案。

接下来考虑如何形成单峰，做法是贪心，尽量形成少的逆序对。可以用树状数组动态维护。最开始的想法是说把尽量小的数往两边扔。但这样并没有很好的性质继续贪。
正确的做法是先考虑最大的数字。因为最终序列每个数字的相对位置都是固定的，所以先考虑最高的数字。

此时还需要发现一个性质：在一个序列（无论这个序列如何调整顺序）的两端加入一个数，所形成的新的逆序对/顺序对是固定的

也就是说，考虑第k大数字的时候的时候，只需要比较加在第k – 1大的数字的左边还是右边。由于k – 1大的数字所形成的序列是连续的，那么就等于在序列两端加数字，使得产生尽量少的逆序对。而在序列内部的数字如何调整对于要新加入的数字在左边还是右边是没有影响的。此时可以发现贪心策略是正确的。

对于值一样大的数字，由于相同的值最后肯定是相对顺序的，所以在考虑逆序对的时候不需要考虑和相同数字所产生的逆序对。具体来说，就是把所有一样的数字的结果先算出来，再把他们加入树状数组。

#include<bits/stdc++.h>
using namespace std;
const int maxn  = 3e5 + 233;
typedef long long ll;
typedef pair<int,int> pii;
vector<pii> a;
int n; 
int c[maxn];
void add(int x)
{
    for(; x <= n; x += x & -x) c[x] += 1;
}
int ask(int x)
{
    int res = 0;
    for(; x; x -= x & -x) res += c[x];
    return res;
}
int main()
{
    cin 

传送门

题意是给一棵树，每个节点有颜色，只有白色和黑色，切成若干部分，使得每部分只有一个白色点。
求切割方案。

状态设计

f[i][0]代表i节点的儿子都符合条件，且 i 点所在的连通块有白色点。
f[i][1]代表i节点的儿子都符合条件，且 i 点所在的连通块没有白色点

1. 当 i 点是白色点的时候。f[i][1] = 0因为他不可能存在一个连通块内并且不包含白色。f[i][0]由其所有的儿子的方案累乘。具体来说，对于一个儿子j，可以选择切割这条边，+f[j][0]，也可以不切这条边 +f[j][1]

f[i][1] = 0

f[i][0]=\prod{(f[j][0] + f[j][1])}

2. 当 i 点是黑色点的时候。f[i][1]也是同理由其儿子选择切割与不切割转移来，f[i][0]则是由贡献白点的儿子转移，由于只能有一个儿子贡献白点，其他儿子贡献的是全黑点的连通块，所以各个儿子贡献之间是加法关系

f[i][1] = \prod{(f[j][0] + f[j][1])}

f[i][0] = \sum f[j][1] * \prod\limits_{i != j}{f[j][0]}

这里的由于需要 i != j 的乘法积，可以直接先全部乘起来，再分别除f[i][0]。但是由于有取模操作，并且模数很大且是一个质数，所以用逆元来代替除法。

不过xc大佬用的前缀后缀积，更简单但是开始的确是没想到。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
const ll mod = 1000000007; 
int e[maxn * 2], h[maxn], pre[maxn * 2], c[maxn], cnt;

传送门

题意是说个一个边长为n的等边三角形，由若干个边长为1的等边三角形拼起来。问有多少个点对，相连的直线经过交点。

把等边三角形看成一个等腰直角三角形，相当于变型一下。可以发现，当横纵坐标差值的gcd 1的时候，点对是符合条件的。

数据只有50。直接暴力塞点然后判断就好。
不过队友在比赛的时候写的搜索，不知为何炸了。

#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n + 1; i++) 
        for(int j = 1; j <= i; j++) a.push_back(i << 16 | j);
    long long ans = 0;
    for(int i = 0; i < a.size(); i++)
    {
        int x = a[i] >> 16, y = a[i] & ((1 << 16) - 1);
        for(int j = i; j < a.size(); j++)
        

就是区间众数。

一个数组num[x]存两个指针内有多少个x，一个数组cnt[y]存两个指针内数量为y的有多少个。

当一个数字x的num[x]即将变成0的时候，cnt[num[x]]-1。如果cnt[num[x]]为0，那么必定存在一个有某个数cnt[?] = cnt[num[x]] – 1；所以这样就可以完成O(1)的计算区间内的信息。

还是蛮有技巧的

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 2e5 + 233;
set<int> st;
unordered_map<int,int> ump;
int block, n, m, a[maxn], ans[maxn], cnt, p[maxn], num[maxn];
struct qs{
    int l, r, idx;
}b[maxn];
bool cmp(const qs &x, const qs &y)
{
    return (x.l / block) == (y.l / block) ? x.r < y.r : x.l < y.l;  
}
inline void pls(int x)
{ 
    num[p[a[x]]++]--;
    int t = p[a[x]];
    num[t] ++;
    if(t 

传送门

题意是每个节点有一个属性，取子树的最大或最小值。只有叶子节点有初始值，可以分别是1 – n(叶子节点个数)里面的任意一个值。问根节点最大值是多少。

很巧妙的思路。

对于每一个节点，在他及其子树中，相对大小都是确定了的。

比如在上图里。
节点{4}取最小，在{8, 9}里是第二大。
节点{2}取最大，在{8, 9, 5}里是第一大。
设f[i]表示i个节点的相对大小（第几大）。
对于每个节点，都需要尽量的大。所以f[i]需要尽量小。对于取\min的点，一定是子树的rank之和。而去\max的点，一定是子树的rank1.

最后拿总数减去根节点的rank就是根节点的取值

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 233;
vector<int> G[maxn];
int c[maxn], f[maxn], cnt;
void dfs(int x)
{
    if(c[x]) f[x] = 1e9;
    for(int i = 0; i < G[x].size(); i++)
    {
        int y = G[x][i];
        dfs(y);
        if(c[x]) f[x] = min(f[x], f[y]);
        else f[x] += f[y];
    }
    if(!G[x].size()) f[x] = 1, cnt++;
}
int main()
{
    int n ; 

传送门

题意让求一个排列，字典序最大而且使得逆序对数量为k，再对这个序列按照每位乘上(n + 1) ^ i求和

第一点 : 字典序最大的排列方式肯定为9876 3 12 45这样的有四段，第一段是贪心地拿字典序最大的变成最多的逆序对，如9876 12345这样有 (5 + 8) * 4 / 2 = 26 个逆序对，如果需要28个逆序对，肯定是把 3 放在尽量前面 9876 3 12 45 ，这样就组成了四段，第一段9降序，第二段是3，第三段1升序，第四段从3 + 1升序。

接下来就变成了序列求和的问题。观察到\sum{p[i] * (n + 1)^{i}}实际上是一个公差为 1 或者 -1 的等差数列和公比为（n + 1）的等差数列相乘的来。

引理：对于首项为a_1，公差为d_1，的等差数列a_n，首项b_1，公比q的等比数列b_n。
一定存在S_n = \sum{a_i b_i} = x_1b_1 – x_{n + 1}b_{n + 1}
其中 x 为等差数列 x_1 = \frac{a_1}{1 – q}+\frac{qd}{(1-q)^2} \quad … Read the rest