千题目标Category

【2019HDU多校】扩展kmp模板题

传送门

扩展KMP模板题

要你求对于每个后缀，与前缀匹配的最大长度

是我太菜了，居然不知道有这个算法。。。。。被签到题自闭十万年

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 233;
typedef long long ll;
bool vis[maxn];
char a[maxn], b[maxn];
int nxt[maxn], f[maxn];
int main()
{
    int T; cin >> T;
    while(T--)
    {
        scanf("%s" , a);
        int n = strlen(a);
        memset(nxt, 0, sizeof nxt);
        nxt[0] = n;
        int j = 0;
        while(j + 1 < n && a[j] == a[j + 1]) j++;
        nxt[1] = j;
        int p0 = 1;
        for(int i = 2; i <
… Read the rest

【2019HDU多校】HDU6579 线性基

传送门

题意是说会依次给m次操作，要么在序列后面加一个数，要么问你区间[L, R]里的最大异或和。

做法很有技巧。维护前缀的线性基。f[x][i]代表前x个数第i位的代表的基是哪个数。

但是不是一般的方法直接维护，而是只留下最靠后加入的。所以还需要一个pos[x][i]代表f[x][i]是第几个数。

这样在查询f[r][i]的时候如果第i位的pos是小于l的(pos[r][i] < l)，这一位就不合法舍去。

因为在插入的时候是在此位存在的情况下维护尽量靠后的。所以答案一定是最大的。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 233;
int f[maxn][33], pos[maxn][33];
inline int Read() 
{
    int x=0,f=1; char ch=getchar(); 
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f; ch=getchar();}
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
char s[30];
inline void writeln(int x)
{
    if (x<0) putchar('-'),x=-x; 
    if (!x) putchar('0'); else 
    {
        int len=0;  
        while (x) s[++len]=x%10+'0',x/=10;
          while (len) putchar(s[len--]);
    } 
    putchar('\n');
}
void add(int x, int v)
{
    for(int i = 30; i
… Read the rest

【位掩码判团/二分】牛客2019多校R2TD Kth minimum Clique

传送门

题目是说给出n<=100个点，和每个点的权值。再由邻接矩阵的方式给出点之间的连通性。
问其中第k小的团的点权和是多少。团就是指的任意两点间都有直接路径联通的联通分量。

n k
V1 V2 .. Vn
string1
string2
..
stringK

输入
2 3
1 2
01
10
输出
2

首先，直接求前 k 大的团不好做，因为团的个数最多可以有21002^{100}个。

所以可以转化为判断性问题，也就是说给定一个值 mid ，求再满足权值小于 mid 的情况下是否有 k 个或以上的团。由于k只有1e6，所以可以在搜索的时候进行可行性优化。

这也是常用的思想：将搜索前k大转化为二分判定问题。

想要在一个团的基础上找到下一个可能的点加入以后也成为团，只能暴力搜索。但是若每个点都判断一下和其他点是否联通复杂度会多n倍。

观察到每一行代表的是该点和其他点的连通性。例如第一行的01代表的就是1这个点和2是联通的。

那么需要想到的是，把任意m行的二进制数进行与运算，则得到的是和这m个数都联通的点，这样只要从这m个点里取就一定能形成一个团。

还需要对点权进行排序，加快搜索速度。排序后直接建立图：排名为 i 的点和排名为 j 的点的联通状态。搜索的时候每次取最低位就能保证相对团的大小是相对递增的。

100位的位运算可以用bitset，也可以用__int128

#include<bits/stdc++.h>
using namespace std;
const int maxn = 101;
typedef long long ll;
typedef __int128 lll;
typedef pair<int,int> pii;
const lll ONE = 1;
char s[maxn][maxn];
pii a[maxn];
lll G[maxn];
ll lmt, k,
… Read the rest

【贪心】HDU-6546 Function

传送门

题目中有一个条件特别关键：1 ≤ a ≤ 1, 000

这说明二次函数全部开口向上。当x增大的时候，如果不能变得更小，只能变得更大。

所以把所有f(x=1)加入答案，取x=2下降最多的函数，同理取x=3,x=4…直到吧m用完为止

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
typedef long long ll;
typedef pair<ll,ll> pii;
ll a[maxn], b[maxn], c[maxn];
set<pair<ll,pii> > st; // val, x, idx
int main()
{
    ll ans = 0;
    ll n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
        ans += a[i] + b[i] + c[i];
        st.insert({a[i] * 3 + b[i], {2, i}});
… Read the rest

【数论】线筛积性函数/莫比乌斯反演

传送门

题意：
设f(n)=∑in∑jnϕ(gcd(i,j))f(n) = \sum\limits_i^n\sum\limits_j^n\phi(gcd(i,j))，给定T<=5000组询问，每次n<=1e9

将公式化简可以得到(省略反演步骤)

ans=∑p∑p∣dμ(dp)⌊nd⌋⌊nd⌋ϕ(p)ans = \sum\limits_p\sum\limits_{p|d}\mu(\frac{d}{p})\lfloor\frac{n}{d}\rfloor\lfloor\frac{n}{d}\rfloor\phi(p)
ans=∑p∑d=1μ(d)⌊ndp⌋⌊ndp⌋ϕ(p)ans = \sum\limits_p\sum\limits_{d=1}\mu(d)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{n}{dp}\rfloor\phi(p)

此时将内层整除移动到外层，设dp=Tdp = T

ans=∑T⌊nT⌋⌊nT⌋∑p∣Tμ(Tp)ϕ(p)ans = \sum\limits_T\lfloor\frac{n}{T}\rfloor\lfloor\frac{n}{T}\rfloor\sum\limits_{p|T}\mu(\frac{T}{p})\phi(p)

设h(T)=∑p∣Tμ(Tp)ϕ(p)h(T) = \sum\limits_{p|T}\mu(\frac{T}{p})\phi(p)，想办法处理这个函数的前缀和，与前面整除分块一起计算

观察到这是莫比乌斯函数和欧拉函数的迪利克雷卷积，所以h也是一个积性函数。既然是积性函数，那么可由若互质的因子的函数值相乘得到。

考虑h(prix)h(pri^x)其中pri为T的一个质因子，x为质因子的个数。由于莫比乌斯函数的自变量只要有两个以上的相同质因子，函数值就为零。观察上面的卷积式子。那么只有当p=prixp = pri^x和p=prix−1p = pri^{x-1}的时候，μ\mu分别为1和-1。即此时Tp=1,Tp=p\frac{T}{p}=1,\frac{T}{p}=p。所以
h(prix)=ϕ(prix)–ϕ(prix−1)h(pri^x) = \phi(pri^x) – \phi(pri^{x-1})

此时就可以线筛了。

线筛的方法如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 233;
int st[maxn];
ll primes[maxn], f[maxn], h[maxn], phi[maxn], low[maxn], cnt;
void get_primes(ll n)
{
    f[1]
… Read the rest

【练习】#564 (Div. 2)

C传送门

题意是给定1-n的序列，附加n个0，每次a序列可以任意取出一张加入b序列尾部并且从b序列头部取出一张加入a序列。问最少多少步能完成排序。

分类贪心。第一类情况是b序列的尾部已经是一个完整的上升序列，并且a序列和b序列前部能顺序完成拼出上升序列，这种情况模拟一下，最后判断是否能成立。

另一种情况是必须把b序列取出一定的数。这种情况，对于每个取到的数子a[i] = k.他在第一个数字1加入a序列以后，最迟要在之后k步内取到，所以取如a序列的数字的步数就是tmp = max(tmp, i – a[i] + 1),在最大一个步数的数字取完后，就能保证顺序加入b序列的尾部时能完成排序，此时答案是tmp + n;因为加入n个数字需要n步。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int a[maxn], b[maxn], vis[maxn];
int n; 
int go()
{
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(b[i]) ans = max(ans, i - b[i] + 1);
    }
    return ans + n;
}
int go2()
{
    set<int> st;
    for(int i = 1; i <= n; i++) if(a[i]) st.insert(a[i]);
    int ans
… Read the rest

【最小区间覆盖】Minimal Segment Cover

传送门

题意是给定N个区间，询问M个区间最少能用多少个给定的线段覆盖，允许重合/超过。

首先很明显的是被某个区间完全覆盖的小区间是没有用的。

然后需要发现，对于每一个左端点，找到包含这个点而且右端点最远的一个区间肯定是最优解。

那么对于给定区间的右端点，按照降序排列。对排好序的每个区间 i ，这些点最远的右端点就是 i 这个区间的右端点。然后对于下一个区间 j ，小于上一个区间 i 左端点的那些点 的最远右端点就是当前区间 j 的右端点。

这样既消除了被完全覆盖的区间，又找到了包含每个点最远的区间。

然后按照上述关系建立图，实际上是一颗树。

对于每个询问[l, r]，通过树上倍增找到大于r最小的父亲。深度相减就是区间个数。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 233;
struct rec{int l, r;};
bool cmp(const rec &x, const rec &y)
{
    return x.r > y.r;
}
rec a[maxn], b[maxn];
int h[maxn], e[maxn], pre[maxn], cnt;
void add(int u, int v)
{
    e[cnt] = v; pre[cnt] = h[u]; h[u] = cnt++;
}
int mt[maxn];
int fa[maxn][20], d[maxn], t;
void
… Read the rest

【记录】Google KickStart 2019C

A题

注意到横坐标和纵坐标其实是独立不影响的。只要知道了某一列有哪些连续的格子，就可以知道某一步应该走到哪里。这种思想在很多题目都出现过。

接下来变成了维护一些不相交区间，要支持快速查询某个点的左边和右边是否有区间，并且插入/合并区间。用set来实现。注意使用哨兵元素处理迭代器运算异常减少代码量。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 233;
char op[maxn];
typedef set<pair<int,int> > spi;
spi r[maxn], c[maxn];
void add(spi &s, int pos)
{
    int l = pos, r = pos;
    auto it = s.lower_bound({pos, pos});
    auto jt = it--; // jt: >=   it <=
    if(it->second == pos - 1) l = it->first;
    if(jt->first == pos + 1) r = jt->second;
    s.insert({l, r});
    if(l != pos) s.erase(it); 
    if(r != pos) s.erase(jt); 
}
void move(spi &s,
… Read the rest

【整体二分】AcWing268

传送门

其实整体二分就是在二分答案的同时把询问也二分了。排除询问不可能的值域。

树状数组可以区间更新单点查询，不要傻傻地去写区间更新区间查询的树桩上数组。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 233;
int o[maxn], b[maxn], lb[maxn], rb[maxn];
vector<int> pos[maxn];
ll p[maxn];
int ans[maxn];
int n, m, k;
struct rec{
    int l, r; ll v;
}a[maxn];
ll c[2][maxn];
void add(int t, int x, ll v)
{
    for(; x <= m; x += x & -x) c[t][x] += v;
}
ll ask(int t, int x)
{
    ll res = 0;
    for(; x; x -= x &
… Read the rest

【整体二分】ZOJ2112 – 动态区间第k大

传送门

我永远喜欢离线分治算法

题意不多说，带修改的区间第k大。

整体二分。

整体二分也叫基于值域的分治算法。

二分答案，先将整个序列的值域二分得mid。对于整个操作序列1~M，可以依次知道在操作区间Mi ：[ l , r ] <= mid 的值有多少个。具体来说就是利用一个树状数组，如果A[ i ] <= mid 那么树状数组add( i , 1)。 如果带有修改操作，那么就把修改拆成在位置 i 加一个数和减一个数。

如果对于第k大查询Mi，有cnt个数在区间内小于k，很明显如果cnt = k的话答案就在左值域里面。否则就在右值域里面。(注意，二分值域的意义就是二分查询的答案)

然后，对于这些询问进行分类。在左值域的询问和操作分一堆，在右值域的询问和操作分一堆。这是个分治的过程，继续往下递归这两类询问。直到值域二分的边界，所剩下的询问的答案就是这个值。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
struct rec{
    int t, x, y, z;
}a[maxn], lb[maxn], rb[maxn];
unordered_map<int,int> ump, rg;
set<int> st;
int n, m;
int seq[maxn];
int c[maxn], tot;
void add(int x, int v)
{
    for(; x <= n; x += x & -x)
… Read the rest