Blog

【权值线段树】HDU6703-array

传送门

题意是说给定一个排列，长度1e5，要求支持两种操作：
1. 把某个位置的数字+1e7
2. 给定r, k.查询与前r个数字不同的，并且大于等于k的，最小的数字。

经过分析，答案最大不可能超过n+1。这样的话，操作1其实相当于把这个数字从排列中删去。

用两棵权值线段树，每个点上存的是位置。

对每次2操作，在[k,n]区间里找最靠左的并且val[x]大于r的数。

对每次1操作，最开始是初始化一颗每个点值都是n+1的权值线段树，删掉一个数代表这个数字在区间内可以被使用了。所以在线段树上把点改为该位置。

同时2操作也要找[k,n]区间里最靠左而且val2[x]小于等于r的数。

两个数取最小就是答案。

同时还需记录区间最大最小值，以用来在查询的时候剪枝。

没有这个剪枝，查询会退化为n^2log(n)的，因为区间里可能每个数都会递归到底。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define min(a,b) (a)<(b)?(a):(b)
const int maxn = 1e5 + 233;

struct Node{
    int l, r, v;
}t1[maxn * 4], t2[maxn * 4];
int a[maxn], pos[maxn];
int n;
void build(int p, int l, int r)
{
    if(l == r)
    {
        t1[p].l = l, t1[p].r = 

【19HDU多校】Rikka with Coin，贪心

传送门

题意是说有面值10 20 50 100的钱，有n个价格给定的菜，要求用最少的硬币数量，使得所有n个菜品的价格都能被凑出来。

贪心：直观想法是先用大的面值，依次用小的面值。

这样的话可以发现10， 20， 20， 50四个面值能凑出所有100以内的价格。

但是有个例外：90 110 这样的数据，如果按照上面的贪法是100 50 20 20 10五个硬币，实际上只需要50 20 20 20四个硬币就可以拼出来。

所以进一步发现用10 20 20 20 50五个硬币可以包含所有最优方案。两个10肯定能用一个20代替，四个20肯定能用一个50 20 10代替。

所以做一个10 20 20 20 50的子集生成。然后暴力判断dish[i] % 100 + 100和dish[i] % 100在某个组合的子集生成里有没有。（有先后顺序，第一个如果有了第二个就不用判断。因为既然零钱数量是固定的，那么100圆的越少约好）如果有，100圆的数量就分别是(dish[i] - （dish[i] % 100 + 100）/ 100) ，和dish[i] / 100。

对于100圆判断是个重要细节。
比如1000 90 110这样的数据，1000其中的100圆可以用零钱拼出来，所以100圆个数只有9个。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5] = {10, 20, 20, 20, 

【19牛客多校9_J】Symmetrical Painting【另类扫描线】

传送门

题意是说给n<=3e5条宽度为1的线段，长度不定。

要求一个对称轴，使得将图按照对称轴处理以后剩下的线段最多。

首先猜到的就是对称轴必定出现在某个线段的正中央。但是枚举对称轴以后需要用数据结构维护两边的长度。

有一种离线的做法，更为简单。

1. 预处理出每条线的 下边线(l)、中线(l+r1)、上边线(r)。

2. 对于这些预处理出的线，仅仅记录一个y坐标，按照坐标从小到大排序。

3. 枚举这些线当作对称轴，从下往上做扫描线。线性讨论当前这条线和上一条线之间的线段产生的贡献。也就是当前线为对称轴，上一条线为下半段。按照扫描线一层一层的计算面积贡献。

4. 在某个线段遇到中线之前，他的面积贡献都是存在的。因为他按照当前扫描线往上翻折，扫描线下方的面积肯定小 于上方，所以贡献是下方面积的两倍 ，于是下边界的贡献flag = 1。

5. 当扫描线遇到中线的时候，肯定是之前某个线段的中线，此时这条线段在扫描线下方的面积大于等于上方面积，同时这条线段已经达到最大的面积贡献，当扫描线再往上走的时候会减少贡献，每当中线网上移动距离 k 的时候，这条线段就应该减去 2k 的面积贡献。当遇到上边界的时候负贡献消失，变成 0 贡献。于是中线的贡献flag = -2，上边界的flag = 1。

6. 所以用变量cnt对当前层做出贡献的线段条数，面积和sum每次都+=cnt*(i-last)。然后cnt+=当前层数的贡献。因为兑成轴的只可能产生0.5这种小数，于是为了代码方便，把坐标都扩大两倍，同时计算面积的时候不用乘2。

其实最核心的点就是每当对称轴向上移动k距离的时候，整条线就应该缩短2k的距离，这样才能保证图形是对称的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 3e5 + 233;
int n;
vector<pii> a;
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        ll l, r;
        cin >> l >> r;
        a.push_back({l * 

【19HDU多校】HDU-6638 Snowy Smile 扫描线/区间连续最大和

传送门

题意很简单，就是求矩阵的最大子矩阵。

数据范围是坐标很多，但是点最多有2000个。100组数据。

根据x坐标排序。对y坐标进行离散化。

枚举x坐标作为左边界，再依次加入某些x相同的点，这样就确定了右边界。

用线段树维护y方向的区间连续最大和。

总体来说就是枚举左右边界，用区间连续最大和来“确定”上下边界。

联动ACWING126

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2002;
typedef long long ll;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define max(a, b) (a) > (b) ? (a) : (b)
struct Node{
    ll l, r, lsum, rsum, sum, dat;
}t[maxn * 4];
void build(ll p, ll l, ll r)
{
    t[p].l = l; t[p].r = r;
    if(l == r) {t[p].lsum = 0, t[p].rsum = 0, t[p].sum 

【19HDU多校】HDU-6651 Final Exam(田忌赛马问题)

传送门

题意是说有n个问题，总共有m分。你如果想通过某个问题，你就需要复习大于该问题分数的时间。
但是你不知道每个问题是多少分。问题是你至少要复习多少时间才能保证通过至少K个问题。

解法是反向思考。

如果我是老师，那么我假设知道了学生的复习计划。那么我肯定会把他复习最多的 k – 1 个问题都设置为0分。这样我就有 m 分去尝试卡掉剩下的 n – k + 1 个问题。而这 n – k + 1 个问题也肯定是学生复习时间最少的几个问题。因为复习时间最长的 k – 1 个问题我已经设置为难度为0。

这也就是田忌赛马策略。

而对于剩下的 n – k + 1个问题。如果老师想都卡掉，那么最好的办法就是对于每一个问题，都设置为他复习时间那么多分，使得他刚刚无法通过。如果最后我 m 分刚好用完，或者还剩余。那么学生就被老师卡掉了。

反之，如果每道题设置复习时间那么多分数，m 分不够。那么学生就无法被卡掉。

这样看来，对于学生来说。只要最少的 n – k + 1 个复习时间，的总复习时间 m 那么就无法被卡掉。剩下的 n – 1 个时间都是 最少的 n – k + 1 个复习时间的。那么这些时间最稳最少是m + 1。

那么问题就变成了：有 n – k + 1 个数之和为 m + 1,且要求这些数里面最大的数字最小。

很明显这个最大的数字最小的时候就是平均分配 m + 1 分的时候。

所以，答案公式即ceil((m + 1) / (n … Read the rest

【2019多校】HDU6627 equation

传送门

题意是给出若干个一次函数的绝对值，问方程的所有解

把函数按照零点排序，在零点左边的函数都取负，右边都取正。

然后把若干个一次函数看成一个一次函数，用公式直接求解

有个坑点是ax+b=c判断无穷解的时候，除了a等于0以外。还需要b=c，否则是无解，不是无穷解。

#include<bits/stdc++.h>
using namespace std;
typedef __int128 lll;
typedef long long ll;
const int maxn = 1e6 + 233;
typedef pair<ll,ll> pii;
pii v[maxn];
bool cmp(const pii &x, const pii &y)
{
    if( y.first * x.first > 0) return  -x.second * y.first <  -y.second * x.first;
    else return  -x.second * y.first >  -y.second * x.first;
}
bool cmp2(const pii &x, const pii &y)
{
    if( x.second * y.second > 0) return  x.first * y.second <  y.first 

【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 < 

【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 

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

传送门

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

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

输入
2 3
1 2
01
10
输出
2

首先，直接求前 k 大的团不好做，因为团的个数最多可以有2^{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, 

【贪心】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}});