| by XianKa | No comments

【单调栈】ZOJ-2642

传送门

最开始没想到这个模型。还贪心写了半天,发现是错的,贪不动。

这题关键在于模型的转化。转化后的题意就是求一个最长的区间,使得区间总和乘上区间最小数最小。

那其实和单调栈经典题目求最大矩形是差不多的,稍微有点不同的是本题可以看成矩形的宽度不是1,而是题目给定的数字……..

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 233;
typedef long long ll;
int n;
ll a[maxn], b[maxn], w[maxn], s[maxn];
int main()
{
    while(cin >> n)
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%lld",&a[i]);
        }
        a[n + 1] = 0;
        memset(s, 0, sizeof s);
        int p = 0;
        ll ans = 0, l = 1, r = 1;
        for(int i = 1; i <= n + 1; i++)
        {
            if(a[i] > 
Read the rest Read More
| by XianKa | No comments

【区间rmq/单调性问题】hdu3530

传送门

题意是找一个最长的区间,使得区间内最大值-最小值 max – min 属于[m,k]

最开始想的二分长度,但实际上并不具有单调性。。
比{1, 0, 1, 3} m = 3 这组数据,当长度为2的时候所有区间都不满足,但长度为3的时候就有一个区间满足了。也就是说不存在短的区间满足,并不代表不存在更长的区间不满足。

导致没有单调性的原因就是题目要求需要满足两个条件,就破坏了单调性,如果题目只有一个限制条件k,那么就是满足单调性的,不存在更短的区间不满足k那么也不存在更长的区间满足k,因为包含段区间的长区间最大值不可能更小,最小值也不可能更大。

因为包含不满足k的区间一定需要更小,而包含不满足m的区间可能变得更大,所以用队列来做。顺序读取数据,让读到一个连续区间不满足k,就从前面缩短区间,直到满足k,当满足m的时候用长度更新答案。

可以用ST表也可以用set。

//1 0 1 3 m = 3 小区间不满足,大区间不一定不满足,不可二分
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
int n, m, k;
int a[maxn];
int main()
{
    while(cin >> n >> m >> k)
    {
        multiset<int> st;
        int l = 1, ans = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            st.insert(a[i]);
            while(*st.rbegin() - *st.begin() > 
Read the rest Read More
| by XianKa | No comments

【化简】Lutece 175

传送门

题意是每个苍蝇有两个属性,a和b,前面的苍蝇要分别和后面的苍蝇决斗,每次的分数为max(ai-aj,bi-bj)-min(ai-aj,bi-bj) (i < j) 。

可以想到

  • res = ai – aj – bi + bj (ai – aj bi – bj)
  • -= (ai – bi) – (aj – bj) (ai – bi aj – bj)
  • 同理,当大小关系相反的时候,是Hj – Hi

所以可以先把 ai – bi 处理出来。

由于是前面的要和所有后面的决斗,所以把数据离线,从后面开始算,每加入一个点,找已经加入的点中,比他大的,比它小的,分别算入答案。

这里可以用离散化+普通权值rmq,也可以用动态开点线段树不用离散化

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 233;
int N;
unordered_map<int,int> ump,raw;
ll a[maxn];
ll c1[maxn], c2[maxn];
void add(int x, int v)
{
    for(; x <= 
Read the rest Read More
| by XianKa | No comments

【欧拉函数】acwing221

传送门

解法:欧拉函数

俗话说数论上来先打表,打完表智力就正常了

我先打了一张n为50的表
//1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 25 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 50
发现gcd好像有很多重复的数字

gcd为1的就是与50互质的数,个数为\phi{(N)}

gcd为2的个数怎么算?仔细想想,对于每一个gcd(i,N) = d的数对,都存在gcd(i/d , N/d) = 1
也就是说,对于每个数对,各自除以gcd和N都是互质的,那么很明显数对的个数为\phi{(N/d)}

有了以上结论,可以想到,N的所有gcd的可能性就是N的所有约数,对于每个约数,数对的个数为\phi{(N/d)}个,它们的和就是d\phi{(N/d)}

进一步总结,答案就是\sum_{d|N}d\phi{(N/d)}

这个函数是两个积性函数的迪利克雷卷积,所以是个积性函数,有xxxx的性质,可以线筛等等

然而我一看数据范围2^31那比不可能线筛,只能暴力算了。… Read the rest

Read More
| by XianKa | No comments

【莫比乌斯反演】acwing220

就当复习莫比乌斯反演了吧

传送门

解法:莫比乌斯反演

f(d) = [gcd = d],表示gcd为d的数的对数的个数

g(p) = \sum_{p|d}f(d),表示gcd为p的倍数的数对的个数,其中p代表的质数

易知g(p) = \lfloor n / p \rfloor \lfloor n / p \rfloor ,因为如果两个数都是p的倍数,那他们的gcd也一定是p的倍数。小于n的p的倍数的个数就是\lfloor n / p \rfloor,由于需要的是两个组成一个数对,所以乘法原理相乘一下。

g(p) = \sum_{p|d}f(d) = \lfloor n / p \rfloor \lfloor n / p \rfloor里的g是好求的,而我们需要的是f函数和的值,可以用莫比乌斯反演,将计数关系交换。

反演以后f(p) = \sum_{p|d} \mu(d/p) g(d)

将函数g展开即f(p) = \sum_{p|d} \mu(d/p) \lfloor n / p \rfloor \lfloor n / p \rfloor

其中mu为莫比乌斯函数,这一项可以在线筛的时候求和,后面下取整除法只有2\sqrt{n}种取法,所以可以分块计算。

计算一个质数的f函数复杂度O(\sqrt{N}),题目给出的N为1e7,根据素数定理,小于N的质数个数约为… Read the rest

Read More
| by XianKa | No comments

【区间dp】合并石头(连续k个)

传送门

设 f[l][r][k] 为 l, r, 里分成 k 段的代价。

  • 以长度为阶段。
  • f[l][r][k] = min(f[l][r][k], f[l][mid][k – 1] + f[mid + 1][r][1])
  • 答案就是f[l][r][1]

每个k只用从k-1和1转移,因为对于任何k-n,n,一定可以分解为k-1,1,1,1,..1;所以对于前面的状态都是被考虑过的,不用再重复考虑。

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int f[63][63][63], sum[33];
    int mergeStones(vector<int>& stones, int K) {
        memset(f, 0x3f, sizeof f);
        memset(sum, 0, sizeof sum);
        int s = stones.size();
        for(int i = 1; i <= s; i++) sum[i] = sum[i - 1] + stones[i - 1];
        while(s >= K)
        {
            s -= K;
            s++;
        }
        if(s > 1) 
Read the rest Read More
| by XianKa | No comments

【差分约束/tarjan缩点】BZOJ2330 银河

传送门

题目的五个条件转化为差分约束的不等式
再加:

  • 设d[0] = 0; d[i] – d[0] = 1 每个星球最低为1亮度
  • 再从0一个点往所有点连1的有向边

题目可能出现无解的情况,差分约束的图出现正环即无解。

但是题目数据量很大,直接在跑最长路的时候用spfa判正环会超时

先tarjan缩点。同一个强连通分量里面如果边权之和为正那么肯定存在正环直接无解。复杂度O(N)

最后把缩点后的图重新建图,是一个有向无环图,可以直接跑最长路。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 233;
int n, m;
int h[maxn], e[maxn], val[maxn], pre[maxn], cnt;
int hc[maxn], ec[maxn], valc[maxn], prec[maxn], cntc;
void add(int u, int v, int w)
{
    e[++cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt;
}
void addc(int u, int v, int w)
{
    ec[++cntc] = v; 
Read the rest Read More
| by XianKa | No comments

【差分约束/数据结构优化贪心】poj1201 区间

传送门

这个题目有两种做法

差分约束

设s [ i ]表示前i个里面取数的个数
* s[b] – s[a – 1] = ci
* s[k] – s[k – 1] = 0 (任何k要比k-1取得多)
* s[k] – s[k – 1] <= 1 (任何数只能取一次)

然后建图跑,从第一个点开始跑最长路。
注意最后只能用spfa来跑,因为djistra无法处理反边权的情况。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 233;
int h[maxn], e[maxn], pre[maxn], val[maxn], cnt;
void add(int u, int v, int w)
{
    e[++cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt; 
}
int dis[maxn], vis[maxn];
void dji()
{
    memset(dis, 
Read the rest Read More
| by XianKa | No comments

【CDQ分治】HDU1520-Tunnel Warfare

题目传送门

离线分治大法好啊!!

题意

区间有n<=50000个点,m<=50000次操作。一开始所有点都是相连的。有三种操作。1 断开某个点。2 恢复上次断开的点。 3 查询某个点属于的线段的长度。

这个题本来是在集训队的线段树作业里。今天学了CDQ分治突发奇想好像可以做…..然后就做了。虽然当时我也是用set做的

思路源于set的在线算法。

set本质平衡树。每次读到一次断开操作,在平衡树中加入这个节点。查询的时候在平衡树里查找第一个比它大的和第一个比它小的数字。其差值就是答案。

恢复操作需要用一个栈存起来。然后从平衡树里删除这个值。总复杂度NlogN,其中N指的操作总数

这里有个坑点。断开操作可能会有重复。比如先断开 3 再断开 4 然后再断开 3 。虽然对查询操作没有影响,但是恢复操作的时候第一个恢复的是 3 这个点…..我因为这个WA了好久


但是虽然STL里面有set,但如果不能用STL或者不会写平衡树怎么办呢。

重点来了:CDQ分治

CDQ分治是一种基于时间分治的离线算法。其核心思想就是基于前面的操作会对后面的查询造成影响。所以可以把查询离线,根据时间顺序,计算修改操作对之后每个查询的影响。

然而这题有点特别就是有撤销操作。每次修改对后面询问的影响都可能被撤销。如果单单按照操作顺序作为时间分治,还需要用到可持久化的数据结构。

但是换个思路。既然每个操作有撤销,那么就考虑每个操作的”存活时间”。

每个操作在撤销之前对其间的询问都会造成影响。考虑每个操作的存活时间,把询问根据存活时间分治。

比如”DDDRQDQ”,其中第三个D的存活时间为0,因为它没有对任何询问造成影响。第一、二个询问的存活时间都为2,考虑其出生时间,记为[1,2],最后一个D则是[2,2]。

接下来把相应的询问安排到相应的区间。有点类似于线段树的感觉。在每个断开操作造成影响的询问操作的区间加上它。

在每个区间分治的时候把修改和询问一起排序。因为CDQ分治的正确性,修改一定会对只后的询问造成影响,所以可以把坐标排序。然后从左往右,从右往左扫一次。依次找出每个询问最近的修改就可以啦。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 233;
struct dt{
    int x,l,r;
}a[maxn];
int n,m,q[maxn],ansl[maxn],ansr[maxn],vis[maxn];
pair<int,int> b[maxn];
vector<int> g[maxn * 4];
void cg(int k, int l, int r,int x,int y,int id)
{
    if(x > y) return;
    if(l > r || l > y || 
Read the rest Read More
| by XianKa | No comments

【莫比乌斯反演】牛客练习赛40E-小D的lemon

本题细节极多。WA题自闭两开花

传送门

解题方法打字太难了。手写算了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 250025;
ll p = 1e9 + 7;
ll primes[maxn], mu[maxn], g[maxn], f[maxn], invg[maxn], inv[maxn], s[maxn], cnt;
bool st[maxn];
ll ksm(ll n, ll m)
{
    ll res = 1;
    while(m)
    {
        if(m & 1LL) res = (res * n) % p;
        n = (n * n) % p;
        m >>= 1LL;
    }
    return res;
}
void get_primes(int n)
{
    mu[1] = 1; f[1] = 1; invg[1] 
Read the rest Read More