| by XianKa | No comments

【线段树】Contention- Kick Start 2019 RoundA Problem C

原题传送门

中文题面


题意是有Q个区间询问,每次询问只能得到区间内未被覆盖的位置。
要求一种顺序,使得这Q个询问里的最小值最大。

必须首先发现:最后一个人所得到的座位数量,和前面Q-1个询问的顺序是没有关系的。
所以可以得到一个贪心策略:
1. 从最后一个人开始,枚举谁能得到最多的座位。假设是第X个询问。
2. 去掉第X个询问,再重复步骤一。
3. 重复以上步骤直到询问为空。从得到的答案里取一个最小值即是答案。

如果每一步都暴力枚举,离散化以后复杂度是O(Q^2)的(排序以后扫描)。
可以建立一颗长度为N的线段树,线段树上每个点存储当前区间被哪些询问完全覆盖,和区间内点的最少覆盖次数。
考虑到执行覆盖和撤销覆盖的操作都是成对出现的,当前线段被哪些区间完全覆盖可以不用下传懒标记,参考 亚特兰蒂斯 的做法。在往下走的时候,仅仅对第一次遇见的区间进行标记,撤销的时候也无需往下走。
以样例来解释,仅需要在这些有颜色的区间上记录有哪些线段对其进行了覆盖即可。

区间最小值就用普通的懒标记,优化到每次修改是NlogN
对于每次找答案,在线段树中往下走找到那些数值为1的点,同时把值赋成无穷大,以后不再访问这个点,在往上回溯的时候在那些只有一个线段覆盖的区间加上这些1的个数。
然后取得值最多的那个线段执行撤销操作。找到最多的区间这一步可以再用一颗线段树维护。
因为记录区间不需要任何顺序,所以用Hash表即可,STL里的unordered_set就能满足。
总的复杂度就成了Nlog(N+Q)

#include<cstdio>
#include<algorithm>
#include<unordered_set>
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;
const int maxn = 1e6 + 23;
const int INF = 0x3f3f3f3f;
int n, q;
PII seg[30300];
struct NodeQ {
    int l, r;
    int v;
}trQ[30300 * 4];
void buildQ(int u, int l, int r)
{
    if (l == r) 
Read the rest Read More
| by XianKa | No comments

【DP】CCC ’19 S4 – Tourism

传送门


给定N个数,代表N个景点的权值,必须顺序参观完。每天最多参观K个景点,但是必须严格N/K+(N%K!=0)天参观完。当天的收获为当天景点的最大权值,问总收获最大是多少。
N和K都小于1E6


先考虑这样一种状态表示:
如果把每K个景点分成一份,最后一份可能会少K-N%K个。记为M。
假设每天的目标是一份。
f[i][j] 表示前 i 天偷了 j 天懒。也就是说本来应该走i * k 个景点,但是只走了i * k – j个。
很明显只要确定了偷懒天数,第x天停留的位置就固定了。所以第二维也可以换为停留的位置。
假设停留在下图的i点。
很明显f[x][i]=\max\limits_{j=i-k \to st} (f[x-1][j]+\max\limits_{k=j\to i}a[k])


由于每个阶段都是固定长度,所以很好判断当i%k==0的时候肯定是一个阶段的结束。
这样可以把dp状态优化到一维。

然后由于dp[j]+maxA[j+1,st]这一部分是不变的,可以在每个阶段结束的时候预处理出来。
用树状数组维护这个值的后缀区间最大。同时mxdp[x]记录dp[x,st]最大值和mxA[x]记录A[x+1,st]的最大值。下一个阶段可以直接使用。

当下一个阶段开始的时候,让a[i]mxA[j]进行比较,如果a[i]更大,那么更新[j,i]的树状数组。同时j往后退。

当i向前移动一步的时候,同样也是更新[j,i]的树状数组。

次数树状数组[j,i]的最大值就是dp[i]的值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 233;
ll c[maxn], 
Read the rest Read More
| by XianKa | No comments

Z-algorithm(Z函数)模板

这是个链接 -Z函数作用同扩展KMP

有字符串s,z[i]表示s[i]开始的字符串与s[0]开始的字符串的最长公共前缀

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 233;
char str[maxn];
int ne[maxn], z[maxn];
int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%s", str + 1);
        int len = strlen(str + 1);
        for(int i = 1; i <= len; i++) z[i] = 0;
        z[1] = len;
        for(int i = 2, l = 0, r = 0; i <= len; i++)
        {
            if(i <= r) z[i] = min(z[i - l + 1], r - 
Read the rest Read More
| by XianKa | No comments

【线段树】区间不重复覆盖

传送门

题目意思是依次给n个区间,长度为1或者2,让从里面选一些区间,使得1到m都被覆盖。并且选出区间的编号差要最小。

用双指针求取最短编号差。

难点在于怎么动态确定区间是否被覆盖了。

对于一个点,可能被三种区间覆盖,于是我们对于区间的端点进行分类。用_表示可以被填的方块类型。

“_LR” 代表区间左端点可以填为长度为1或者2的右端点,但右端点不超出。即可能向左超出
“LR_” 代表区间右端点可以填为长度为1或者2的左端点,但左端点不超出。即可能向右超出
“_LR_” 代表左右端点都有可能超出。
“L_R” 代表左右端点都不超出。

然后用线段树维护这四个值。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 23;
struct Node{
    int l, r;
    int s, sl, sr, sn, lv, rv;
}tr[maxn * 4];
void pushup(Node &u, Node &l, Node &r)
{
    u.lv = l.lv;
    u.rv = r.rv;
    int mv = l.rv & (1 << 1);
    u.s = (l.s && r.s) || (l.sl && r.sr && mv);
    u.sl = (l.s && r.sl) || (l.sl 
Read the rest Read More
| by XianKa | No comments

股票问题集合

股票问题汇总

股票问题,指给定一系列数列,可以在某些天以当天价格买入,也可以在某些天以当天价格卖出。

按照买卖规则,可以分为:
1. 不能进行多笔交易;买股票之前只能先把手上的股票卖出。一般此类题是dp。
2. 可以进行多笔交易;手里可以同时持有多只股票。一般要贪心。

股票问题的核心是发现如何使得手里的资产最多。

无论是哪种模型,都可以看成如果第二天价格更高就卖,大不了可以反悔(可以以这天的价格再把卖掉的股票再买回来)。

问题1

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
int w[maxn], f[maxn][110][2];
int main()
{
    int n, k; scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    memset(f, 0xcf, sizeof f);
    for(int i = 0; i <= n; i++) f[i][0][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            f[i][j][0] = max(f[i - 
Read the rest Read More
| by XianKa | No comments

【2017四川省赛/牛客】2017 Revenge【数论/指标】

传送门

题意是说给2e6个数,每个数都小于2017,从中选取一些数字使得乘积模2017等于给定的r,问方案数%2输出

DP,f[i][ja[i]%2017]=f[i-1][j]+f[i-1][ja[i]],因为答案只需要奇偶,所以考虑异或操作。

不过这样的复杂度是2017n的。

考虑把乘法变成加法,5是2017的原根,并且2017是质数,剩余系是完全剩余系。所以把1-2016的指标存下来到I[]里面。

f[i][j+I[a[i]]]=f[i-1][j]+f[i-1][j+I[a[i]]]

可以把f开成一个bitset,f[i]表示第i个指标的方案数。所有的状态j每次加一个数I,就相当于循环左移了I位。再用异或滚动状态就可以了。

f^=(f<<I[a[i]])^(f(2016-a[i]))

#include<bits/stdc++.h>
using namespace std;
bitset<2016> f;
int a[2000002], I[2020];
int main()
{
    int n, r;
    int g = 1;
    for(int i = 1; i <= 2016; i++) 
    {
        g = g * 5 % 2017;
        I[g] = i;
    }
    // I[1] = 0;
    while(~scanf("%d%d", &n, &r))
    {
        f.reset();
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        f.set(0);
        for(int i = 1; i <= n; i++)
        {
            f 
Read the rest Read More
| by XianKa | No comments

【最短路/拆点】ACwing176

传送门

把每个点拆成100个点,分别表示到这个点的时候油量剩余的状态。跑最短路即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int p[maxn], val[maxn], e[maxn], pre[maxn], h[maxn], cnt;
void add(int u, int v, int w)
{
    e[cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt++;
}
struct Ver{
    int a, b, c;
    bool operator<(const Ver &W)const 
    {
        return c > W.c;
    }
};
int dis[1010][110];
bool vis[1010][110];
int dijkstra(int cost, int start, int end)
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis,0, sizeof vis);
    priority_queue<Ver> pq;
    pq.push({start, 
Read the rest Read More
| by XianKa | No comments

【min_25筛】筛欧拉函数、莫比乌斯函数、积性函数

传送门:欧拉函数、莫比乌斯函数

花了一下午学了一下min25筛。

一知半解。不过还是学会了套板子。

mu函数要看成质数个数取反,在预处理g的时候不能带负数(我也不知道为什么)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
ll primes[maxn], cnt;
bool st[maxn];
ll sp1[maxn], sp2[maxn], g1[maxn], g2[maxn], sm[maxn], g[maxn], w[maxn], wcnt;
ll id1[maxn], id2[maxn];
ll inv2, inv6, qn;
ll ksm(ll n, ll k)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = res * n;
        n = n * n ;
        k >>= 1;
    }
    return res;
}
void get_primes(int n)
{
    for(int i = 
Read the rest Read More
| by XianKa | No comments

【树状数组】query

传送门

题意是给一个长度为n的排列。给出m个询问,每次询问一个区间。

问区间内所有数一个数是另一个数的倍数的对数。

l \le i < j \le r 而且 \min(p_i,p_j) = \gcd(p_i,p_j )

由于是排列,n<=1e5,所以用pos[i]存下i这个数的为位置。

nlogn的时间里可以找出所有pair的对数,并以(l,r)的二元组表示。

再把询问L,R以二元组的形式离线。

问题转化成了二维偏序问题:L \le l \ \text{and}\ r \le R

用树状数组即可解决

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
typedef pair<int,int> pii;
int pos[maxn], a[maxn];
vector<pii> v;
vector<pair<pii,int> > q;
int c[maxn];
int n, m;
void add(int x)
{
    for(; x <= n; x += x & -x) c[x] ++ ;
}
int ask(int x)
{
    int res = 0;
    
Read the rest Read More
| by XianKa | No comments

【博弈】HDU 1079 Calendar Game

传送门

题意是说,给定一个日期,每个人可以轮流操作,要么将日期+1变为下一天,要么将日期变为下个月的同一天。

当下个月没有同一天的时候,只能讲日期变为下一天。

谁把日期变为2001.11.4即胜利。

是用sg函数做的。

当局面的sg=1的时候必胜。

//#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int gap[2020];
int ms[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int sg[2010][13][33];
bool check(int y, int m, int d)
{
    if(y > 2001) return 0;
    else if(y == 2001 && m > 11)  return 0;
    else if(y == 2001 && m==11 && d > 4) return 0;
    return 1;
}
int getsg(int y, int m, int d)
{
    //cerr << y << ":" << m << ":" << d << 
Read the rest Read More