【luoguP3792】由乃与大母神原型和偶像崇拜

这个题目……佛了。
有一个一定不会被hack但是我写不出来的做法,考虑离散化+插入中间空位里面不存在的数,这个时候查询区间max,min和后继的min就可以做到一定正确,但是这样会被卡空间……cnbb
然后我们考虑随机化贪心,考虑给每个权值随机一个数,然后查询区间的异或和是否和我们预处理的一样即可。

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned long long ulo;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = gch();
    if(b == 1)
        x = - x;
}

const int ms = 5e5 + 10;

int n, m, lx, ly, lz, a[ms], tmpa[ms << 2], ta;

ulo p[ms << 2], su1[ms << 2], su2[ms << 2], P[ms << 2];

mt19937 rnd(time(0));

struct node
{
    int opt, x, y;
}poi[ms];

inline int lowbit(int x)
{
    return x & (-x);
}

inline void change1(int x, ulo v)
{
    while(x <= n)
        su1[x] += v, x += lowbit(x);
}

inline void change2(int x, ulo v)
{
    while(x <= n)
        su2[x] ^= v, x += lowbit(x);
}

inline ulo ask1(int x)
{
    ulo rt = 0;
    while(x)
        rt += su1[x], x -= lowbit(x);
    return rt;
}

inline ulo ask2(int x)
{
    ulo rt = 0;
    while(x)
        rt ^= su2[x], x -= lowbit(x);
    return rt;
}

int main()
{
    re(n), re(m);
    for(ri i = 1; i <= n; i ++)
        re(a[i]), tmpa[++ ta] = a[i], tmpa[++ ta] = a[i] + 1;
    for(ri i = 1; i <= m; i ++)
    {
        re(lx), re(ly), re(lz), poi[i] = (node){lx, ly, lz};
        if(lx == 1)
            tmpa[++ ta] = lz, tmpa[++ ta] = lz + 1;
    }
    sort(tmpa + 1, tmpa + 1 + ta);
    ta = unique(tmpa + 1, tmpa + 1 + ta) - tmpa - 1;
    p[0] = time(0);
    for(ri i = 1; i <= ta; i ++)
        p[i] = rnd(), P[i] = p[i] ^ P[i - 1];
    for(ri i = 1; i <= n; i ++)
        a[i] = lower_bound(tmpa + 1, tmpa + 1 + ta, a[i]) - tmpa, change1(i, a[i]), change2(i, p[a[i]]);
    for(ri i = 1; i <= m; i ++)
        if(poi[i].opt == 1)
            poi[i].y = lower_bound(tmpa + 1, tmpa + 1 + ta, poi[i].y) - tmpa;
    for(ri i = 1; i <= m; i ++)
    {
        if(poi[i].opt == 1)
            change1(poi[i].x, poi[i].y - a[poi[i].x]), change2(poi[i].x, p[poi[i].y] ^ p[a[poi[i].x]]), a[poi[i].x] = poi[i].y;
        else
        {
            ulo mid; 
            int l, r;
            mid = (ask1(poi[i].y) - ask1(poi[i].x - 1)) / (poi[i].y - poi[i].x + 1);
            l = mid - (poi[i].y - poi[i].x) / 2;
            if ((poi[i].y - poi[i].x) & 1)
                r = mid + (poi[i].y - poi[i].x) / 2 + 1;
            else
                r = mid + (poi[i].y - poi[i].x) / 2;
            if(l <= 0 || r > ta)
                puts("yuanxing");
            else if((ask2(poi[i].y) ^ ask2(poi[i].x - 1)) == (P[r] ^ P[l - 1]))
                puts("damushen");
            else
                puts("yuanxing");
        }
    }
    system("pause");
}

【CF618F】Double Knapsack

这个题目甚是神仙啊QAQ。
假设a数组算到最后总和比b大,我们现在考虑对于每一个i,找出最大的ta满足sa_i>=sb_{ta},其中saa数组的前缀和,sbb数组的前缀和。
这个不等式可以写成0 \leq sa_i – sb_{ta} < n,因为只要大于等于n我们就可以继续向前移动ta
我们从0开始统计这个sa_i – sb_{ta} 的值,那么根据鸽巢原理,一共n+1个数字分配在n个笼子里,至少有两对是相等的,也就说不存在无解的情况。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e6 + 10;

int n, lx;

lo sa[ms], sb[ms];

struct in
{
    int x, y;
}pos[ms];

int main()
{
    re(n);
    for(ri i = 1; i <= n; i ++)
        re(sa[i]), sa[i] += sa[i - 1];
    for(ri i = 1; i <= n; i ++)
        re(sb[i]), sb[i] += sb[i - 1];
    for(ri i = 0; i <= n; i ++)
        pos[i] = (in){-1, -1};
    bool f = 0;
    if(sa[n] < sb[n])
        swap(sa, sb), f = 1;
    ri i, ta = 0; lo v;
    for(i = 0; i <= n; i ++)
    {
        while(sa[i] >= sb[ta + 1] && ta + 1 <= n)
            ta ++;
        v = sa[i] - sb[ta];
        //cout << i << ' ' << ta << ' ' << v << '\n';
        if(pos[v].x == -1)
            pos[v] = (in){i, ta};
        else
            break;
    }
    if(f)
        swap(sa, sb), swap(i, ta), swap(pos[v].x, pos[v].y);
    printf("%d\n", i - pos[v].x);
    for(ri j = pos[v].x + 1; j <= i; j ++)
        printf("%d ", j);
    printf("\n");
    printf("%d\n", ta - pos[v].y);
    for(ri j = pos[v].y + 1; j <= ta; j ++)
        printf("%d ", j);
    system("pause");
}

【CF209C】Trails and Glades

题目本身挺简单的,就是正常的构造欧拉回路就是了,还不需要输出方案,简单的一批,唯一需要的是,那些没有边并且单独一个的点是不需要联通他们的,仔细思考下,人家要的是欧拉回路,不是一个所有点都联通的欧拉回路。细节写在代码里。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e6 + 10;

int tot = -1, lx, ly, cnt, ans, head[ms], has, ji, n, m, du[ms];

bool flag[ms], vis[ms];

struct in
{
    int to, ne;
}ter[ms << 1];

inline void build(int f, int l)
{
    ter[++ tot] = (in){l, head[f]}, head[f] = tot;
    ter[++ tot] = (in){f, head[l]}, head[l] = tot;
}

void dfs(int no)
{
    flag[no] = 1, ji |= (du[no] & 1);
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(!flag[to])
            dfs(to);
    }
}

int main()
{
    re(n), re(m), memset(head, -1, sizeof(head));
    for(ri i = 1; i <= m; i ++)
    {
        re(lx), re(ly), vis[lx] = 1, vis[ly] = 1;
        if(lx == ly)//自环可以直接不考虑了,只要记录这个点有没有边就行了
            continue; 
        build(lx, ly), du[lx] ++, du[ly] ++;
    }
    vis[1] = 1;
    for(ri i = 1; i <= n; i ++)
    {
        if(du[i] & 1)//度数为奇数,存在另一个点与他相连接
            ans ++, has = 1;
        if((!flag[i]) && vis[i])//如果这里有边并且没被走过
        {
            cnt ++, ji = 0, dfs(i);
            if(!ji)//如果这个联通块没有偶数条边,则要增加重边(对于对面也是)
                ans += 2;
        }
    }
    if(cnt == 1 && has == 0)//如果只有一个联通块并且本来就存在欧拉回路
        ans -= 2;
    printf("%d", ans >> 1);//因为所有操作是对称的,所以直接/2没啥问题
    system("pause");
}

【CF468C】Hack it!

这个题好神仙啊qwq。
我们首先假设
\sum_{i=0}^{10^{18}-1}f(i) \equiv p (mod\; a)
那么
\sum_{i=1}^{10^{18}}f(i) = \sum_{i=0}^{10^{18}-1}f(i) + f(10^{18}) = \sum_{i=0}^{10^{18}-1}f(i) + f(0) + 1 \equiv p+1 (mod\; a)
这么推下去,你可以得到
\sum_{i=a-p}^{10^{18}+a-p-1}f(i) \equiv p + a – p(mod\; a)
所以l=a-p,r=10^{18}+a-p-1
那么p怎么算。
p = 45·10^{17}+45·10·10^{16}……45·10^{16}·10+45·10^{17}=81·10^{18}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

lo a, l, r, p = 1e18;

int main()
{
    re(a);
    p = 9 * p % a * 9 % a;
    l = a - p, r = 1e18 + a - p - 1;
    cout << l << ' ' << r;
}

【luogu CF720A】Closing ceremony

这个题目显然网络流过不了,所以需要考虑贪心,考虑对于从(0,0)出发的点,每一个都尽可能的去选择自己能到达,并且距离(0, m+1)尽可能远的格子。然后就完了……

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e4 + 10;

int n, m, k, l, lx, a[ms], tot;

struct node
{
    int x, y, z, dis;
    inline bool operator < (const node &a) const
    {
        return z < a.z;
    }
}tmp[ms];

priority_queue <node> qwq;

inline bool cmp(node a, node b)
{
    return a.dis < b.dis;
}

int main()
{
    re(n), re(m), re(k);
    for(ri i = 1; i <= k; i ++)
        re(a[i]);
    sort(a + 1, a + 1 + k);
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
            tmp[++ tot] = (node){i, j, m + 1 - j + i, i + j};
    sort(tmp + 1, tmp + 1 + tot, cmp);
    int ta = 1; bool fl = 0;
    for(ri i = 1; i <= k; i ++)
    {
        while(a[i] >= tmp[ta].dis && ta <= tot)
            qwq.push(tmp[ta]), ta ++;
        if(qwq.empty())
        {
            fl = 1; break;
        }
        //cout << qwq.top().z << '\n'; 
        qwq.pop();
    }
    while(ta <= tot)
        qwq.push(tmp[ta]), ta ++;
    re(k);
    for(ri i = 1; i <= k; i ++)
        re(a[i]);
    sort(a + 1, a + 1 + k);
    for(ri i = k; i > 0; i --)
    {
        if(a[i] < qwq.top().z)
        {
            fl = 1; break;
        }
        //cout << qwq.top().z << '\n'; 
        qwq.pop();
    }
    printf("%s", fl ? "NO" : "YES");
    system("pause");
}

【codevs2382】挂缀

这个题……服气了
我们假设之前已经选择了\(w\)重量的珠子,现在我们要考虑a挂b上比较优还是b挂a上比较优
b挂a上的时候,\(c_{a} \geq w_{b} + w, c_{b} \geq w\)
a挂b上的时候,\(c_{b} \geq w_{a} + w, c_{a} \geq w\)
所以如果a挂b上比较优的话\(c_{b} – (w_{a} + w) \geq c_{a} – (w_{b} + w)\),既\(c_{b} + w_{b} \geq c_{a} + w_{a}\)
反之\(c_{b} – (w_{a} + w) \leq c_{a} – (w_{b} + w)\),既\(c_{a} + w_{a} \geq c_{b} + w_{b}\)
我们要留尽可能多的承重力挂别的珠缀,这样我们降序排序即可,但是并不好处理。所以我们正着排,如果\(c_{a} \geq w\),就直接往上挂,否则从里面调出一个最重的踢出去就行了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

lo n, w, lx, ly, ans;

struct in
{
    lo c, w, s;
}ter[200020];

inline bool cmp(in a, in b)
{
    return a.s < b.s;
}

priority_queue <lo> qwq;

int main()
{
    re(n);
    for(ri i = 1; i <= n; i ++)
        re(lx), re(ly), ter[i] = (in){lx, ly, lx + ly};
    sort(ter + 1, ter + 1 + n, cmp);
    for(ri i = 1; i <= n; i ++)
    {
        if(w <= ter[i].c)
            w += ter[i].w, ans ++, qwq.push(ter[i].w);
        else
        {
            lo qaq = qwq.top();
            if(qaq > ter[i].w)
                w += ter[i].w - qaq, qwq.pop(), qwq.push(ter[i].w); 
        }
    }
    printf("%lld\n%lld", (lo)qwq.size(), w);
}

【luoguP4364】 [九省联考2018]IIIDX

这个题目当初我考场就是个智障,连55的贪心都没做对qwq
首先一个比较显然的思路,我们先建树,\(\lfloor{\frac{i}{k}}\rfloor\)即为\(i\)的父亲,然后我们从大到小排个序,按照中序遍历给他赋值
但是这样的贪心在\(d_{i}\)重复的时候就gg了,因为我们发现可以用子树内部较大的值去换掉其他子树上比较小的值,因此我们要换个思路贪心
我们还是排序,每次去寻找一个可以容纳的下子树大小的区间,比如9 9 9 8 7 7 6 6 6 5,这个时候我们要插入一棵大小为7的子树。这个时候我们很显然会找到第7个数——6。然后我们再一直移动到第九个数——还是6。这是为了保证和我同一层的子树根尽可能的大,所以在我这棵子树的根并不会变小的时候,我多留点空为后面的子树。
这个时候我们为了防止别的树占用我们的预定好了的区间,所以我们需要设置一个辅助数组。设mi[i]表示权值大于等于i的数还有多少是可以选择的,那么排序过后mi[i]就可以转化为i左边还剩下多少数字可以使用。这个东西显然是满足单调不降的。那么我们就可以线段树去维护,每次预定的时候就区间减法
然而大多数人都选择了将减法变为加法,将被选取的区间和整个一段取了个补集,让他们进行区间加。这也就是为什么网上这么多题解嘴上都在说减法实际上一个减法都没有的原因。
每次变更父亲的时候提前钦定一波,每个子树选完了就再减回去。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

const int ms = 5e5 + 10;

int n, a[ms], fa[ms], sz[ms], cnt[ms], pos[ms];

struct in
{
    int l, r, mi, add;
}ter[ms << 2];

double k;

inline bool cmp(int a, int b)
{
    return a > b;
}

inline void up(int w)
{
    ter[w].mi = min(ter[w << 1].mi, ter[w << 1 | 1].mi);
}

inline void build(int w, int l, int r)
{
    ter[w] = (in){l, r, l};
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build(w << 1, l, mid), build(w << 1 | 1, mid + 1, r);
}

inline void down(int w)
{
    int &add = ter[w].add;
    ter[w << 1].add += add, ter[w << 1 | 1].add += add;
    ter[w << 1].mi += add, ter[w << 1 | 1].mi += add;
    add = 0;
}

void change(int w, int l, int r, int v)
{
    if(ter[w].l == l && ter[w].r == r)
    {
        ter[w].mi += v, ter[w].add += v; return;
    }
    int mid = (ter[w].l + ter[w].r) >> 1; down(w);
    if(r <= mid)
        change(w << 1, l, r, v);
    else if(l > mid)
        change(w << 1 | 1, l, r, v);
    else
        change(w << 1, l, mid, v), change(w << 1 | 1, mid + 1, r, v);
    up(w);
}

int ask(int w, int l)
{
    if(ter[w].l == ter[w].r)
        return ter[w].mi >= l ? ter[w].l : ter[w].l + 1;
    int mid = (ter[w].l + ter[w].r) >> 1; down(w);
    if(ter[w << 1 | 1].mi >= l)
        return ask(w << 1, l);
    return ask(w << 1 | 1, l);
}

int main()
{
    re(n), scanf("%lf", &k);
    for(ri i = 1; i <= n; fa[i] = (int)i / k, sz[i] = 1, re(a[i ++]));
    sort(a + 1, a + 1 + n, cmp);
    for(ri i = n; i >= 1; i --)
        sz[fa[i]] += sz[i];
    for(ri i = n - 1; i >= 0; i --)
        cnt[i] = (a[i] == a[i + 1]) ? cnt[i + 1] + 1 : 0;
    build(1, 1, n);
    for(ri i = 1; i <= n; i ++)
    {
        if(fa[i] && fa[i - 1] != fa[i])
            change(1, pos[fa[i]], n, sz[fa[i]] - 1);
        int x = ask(1, sz[i]);  x += cnt[x], cnt[x] ++, x -= (cnt[x] - 1);
        change(1, x, n, - sz[i]), pos[i] = x;
    }
    for(ri i = 1; i <= n; printf("%d ", a[pos[i ++]]));
}

【洛谷P3266】[JLOI2015]骗我呢

更正题面,对于\(1 \le i \le n\); \(1 \le j <m\) 满足 \(x_{i,j} < x_{i,j+1}\)
对于每一行,一共有m个数,值域为\([0, m]\),而且每行的数单调上升,很显然,\([0, m]\),这些只有一个数不出现。并且我们每次新加一行的时候,只需要考虑上一行的状态就行了,因此我们列出一个朴素的dp状态,设dp[i][j]表示当前已经放了i行,最后一行缺的是j,转移方程为\(dp_{i,j} = \sum_{k = min(0, j + 1)}^{j + 1}dp_{i – 1, k}\),这个东西我们可以算一下就知道了,当m = 4,的时候,目前为0134,上一行为0124,这样是合法的,但是上一行为0123的时候这样就不合法了
那么现在我们将方程式变一下形,\(dp_{i, j} = dp_{i, j – 1} + dp_{i – 1, j + 1}\),可以发现现在我们每次转移只会向右一格&向左下一格。在这里题目的美妙即将展开了。我们现在可以把式子转化成图。
就是这么一张图片,问你从平行四边形右下走到左上且不跨越A B两直线的方案数。这样我们有一个比较显然的思路,用总方案数减去不合法的方案数。那么我们用A表示这个方案跨越了左边的边界,用B表示这个方案跨越了右边的边界。我们设最左下角的为\((0, 0)\),左侧直线表达式为\(y_{A} = x + 1\),右侧表达式为\(y_{B} = x – (m + 2)\)
那么我们的目的是去除形如ABABBBBAAAABABABAAAB这些方案。对于刚才那个方案,我们发现连续的一段区间可以直接缩成一个字母——他一直在跨越同一个边界,没有意义。所以刚才那个可以缩水成ABABABABABAB这样的方案。接下来,我们令初始点为\((n+m+1,n)\),重复以下操作:
将当前点以直线A为对称轴翻转,然后将原点到当前点的方案数从答案中减去,再将当前点以直线B为对称轴翻转,把原点到当前点的方案给加上,一直重【复】复【读】,直到当前点的任意一维坐标小于0结束。
这样子我们就相当于将以A和AB为后缀的方案删除了,然后把BA和BAB为后缀的方案加回去……所以实际上我们到最后是把以A为前缀的方案删除了。
同理再对B做一遍这样的操作。总方案为//(C_{2 * n + m + 1}^{n})。
放代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

const lo mo = 1e9 + 7;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

lo n, m, d, ans, inv[3000010], fac[3000010];

lo c(lo x, lo y)
{
    if(x < y)
        return 0;
    return fac[x] * inv[y] % mo * inv[x - y] % mo;
}

lo cc(lo x, lo y)
{
    if(x < 0 || y < 0)
        return 0;
    return c(x + y, y);
}

inline void change(lo &x, lo &y, lo num)
{
    swap(x, y), x += num, y -= num;
}

inline lo ksm(lo x, lo k)
{
    lo rt = 1, a = x;
    while(k)
        rt = rt * ((k & 1) ? a : 1) % mo, a = a * a % mo, k >>= 1;
    return rt;
}

int main()
{
    re(n), re(m), d = max(n, m), inv[1] = inv[0] = fac[1] = fac[0] = 1;
    for(ri i = 2; i <= 3000000; i ++)
        fac[i] = fac[i - 1] * i % mo;
    inv[3000000] = ksm(fac[3000000], mo - 2);
    for(ri i = 2999999; i >= 2; i --)
        inv[i] = inv[i + 1] * (i + 1) % mo;
    lo lx = n + m + 1, ly = n;
    ans = cc(lx, ly);
    while(lx >= 0 && ly >= 0)
        change(lx, ly, -1), ans -= cc(lx, ly), change(lx, ly, m + 2), ans += cc(lx, ly), ans %= mo;
    lx = n + m + 1, ly = n;
    while(lx >= 0 && ly >= 0)
        change(lx, ly, m + 2), ans -= cc(lx, ly), change(lx, ly, -1), ans += cc(lx, ly), ans %= mo;
    ans = (ans % mo + mo) % mo, printf("%lld", ans);
    return 0;
}

【luoguP3770】[CTSC2017]密钥

这个题之前想了个非常不正确的贪心,然后一看题解就是……woc……
这个题首先显然我们要考虑每次x向前移动后对答案的影响,那么现在这个题就变成了两个操作
1、将序列最前面的一个b放到最后
2、将序列最前面一串a放在最后
那么我们再将a分成两种情况考虑,一种是没动的a,一种是动了的a
然后我做的时候就想到这里,没有头绪
但事实上我们可以转化成前缀和问题
对于所有的a,只有它前缀和大于0,那么它才会作为答案,所以我们要动态维护一个前缀和
对于没有移动的a,进行2操作,假设有x个a被移动了,那么就是令未移动a的前缀和减少x,进行1操作,就是令所有a的前缀和+1
那么这个东西显然可以线段树/树状数组维护,时间复杂度O(nlogn)
显然过不了100%数据对吧,所以我们需要优化
仔细想一下,每次真正需要修改的只有被移动的a,剩下的我们可以统统用一个标记维护啊,每次我们暴力修改被移动的,然后剩下的修改标记就好啊,总复杂度O(n+n)
第三问看起来和前两问差不多,事实上我们可以和第一第二问一起做的,当强a数目为k-s个的时候,这就是第三问答案
证明也很好证明,我们把问题变换下,当强a数目为s的时候,强b的数目就是k-s个(很显然),而第三问就是将ab互换,因此当求第一位的时候,强a数目为k-s的时候,就相当于第一问强b数目为s,那么就相当于第三问强a数目为s
这个题就这么愉快的解决了,注意细节

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio> 
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

int p[20000005], seed, n, k, S;

int getrand() 
{
    seed = ((seed * 12321) ^ 9999) % 32768;
    return seed;
}

const int N = 10000007;

int a, b, c, add, cnt, num;

void generateData() 
{
    scanf( "%d%d%d", &k, &seed, &S );
    int t = 0;
    n = k * 2 + 1;
    memset(p, 0, sizeof(p));
    for( int i = 1; i <= n; ++i ) {
        p[i] = (getrand() / 128) % 2;
        t += p[i];
    }
    int i = 1;
    while( t > k ) {
        while ( p[i] == 0 ) ++i;
        p[i] = 0;
        --t;
    }
    while( t < k ) {
        while( p[i] == 1 ) ++i;
        p[i] = 1;
        ++t;
    }
}

int ci[20000040];

inline void change(int x)
{
    int na = add - (x - 1);
    for(ri i = 1; i <= x; i ++)
        ci[i - add + N] --;
    /**/for(ri i = -add + 1; i <= -na; i ++)//从-add+1一直到-na,因为add是标记,i-add+1 
        num -= ci[i + N];
    for(ri i = -na + 1; i <= -add; i ++)
        num += ci[i + N];
    for(ri i = 1; i <= x; i ++)
        ci[-x + i - na + N] ++;
    num -= x, add = na; /**/
}

inline void ask1()
{
    int s = 0, pos = 0, cnt = 0;
    for(ri i = 1; i <= n; i ++)
    {
        if(p[i] == 0)
        {
            pos = i; break;
        }
    }
    for(ri i = pos + 1; i <= n; i ++)
    {
        s += p[i] ? 1 : -1;
        if(p[i])
            ci[s + N] ++;
    }
    for(ri i = 1; i < pos; i ++)
    {
        s += p[i] ? 1 : -1;
        if(p[i])
            ci[s + N] ++;
    }
    for(ri i = 1 + N; i <= N + k; i ++)
        num += ci[i];
    if(num == 0)
        a = pos;
    if(num == S)
        b = pos;
    for(ri i = pos + 1; i <= n; i ++)
    {
        if(p[i] == 1)
            cnt ++;
        else
        {
            change(cnt), cnt = 0, pos = i;
            if(num == 0)
                a = pos;
            if(num == S)
                b = pos;
            if(num == k - S)//如果num为k-s,那么就对了 
                c = pos;
            if(a > 0 && b > 0 && c > 0)
                return;
        }
    }
}

int main()
{
    generateData(); ask1();
    printf("%d\n%d\n%d\n", a, b, c);
}