| by XianKa | No comments

【权值线段树】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 = 
Read the rest Read More
| by XianKa | No comments

【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 + 100dish[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, 
Read the rest Read More
| by XianKa | No comments

【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 * 
Read the rest Read More
| by XianKa | No comments

【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 
Read the rest Read More
| by XianKa | No comments

【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

Read More
| by XianKa | No comments

【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 
Read the rest Read More
| by XianKa | No comments

【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 Read More
| by XianKa | No comments

【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 Read More
| by XianKa | No comments

【位掩码判团/二分】牛客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, 
Read the rest Read More
| by XianKa | No comments

【贪心】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 Read More