【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");
}

【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");
}

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

【luoguP4370】[Code+#4]组合数问题2

暑假数学班的题目能让我咕咕咕到现在也是可以的,现在列表里面一堆模板还没做,noip前应该也不会做了2333333
这个题目是当时长者给我们讲的,脑洞真是清奇2333333333
首先分析这个题目的话,难点就在于,我们取模以后没法判断数字的大小了。这个时候有一个比较显然的思路,用double类型去存储组合数。但是组合数太大了,double类型只能存20位左右的精准数字,剩下的全部以浮点数的形式存储,那么怎么比较大小呢?
这也就是这个题目的关键,我们利用对数函数来判断数字的大小。我们统一取log2函数值的大小,这样就可以保证精度的同时判断大小了2333333
代码实现并不难,就是有点小恶心,开始wa了发,后来看到网上dalao的偷懒写法写了一发

#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;
}

const lo ms = 1e6 + 10;

const lo mo = 1e9 + 7;

lo n, k, ans, fac[ms], inv[ms], fx[4] = {-1, 0, 1, 0}, fy[4] = {0, 1, 0, -1};

double fc[ms];

struct in
{
    lo x, y, c; double lg;
    inline in(lo a, lo b)
    {
        x = a, y = b, lg = fc[a] - fc[b] - fc[a - b];
        c = fac[a] * inv[b] % mo * inv[a - b] % mo;
    }
    inline bool operator < (const in &a) const
    {
        return lg < a.lg;
    }
};

priority_queue <in> qwq;

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

int main()
{
    re(n), re(k), fac[0] = inv[0] = 1;
    for(ri i = 1; i <= n; i ++)
        fac[i] = (fac[i - 1] * i) % mo, fc[i] = fc[i - 1] + log2(i);
    inv[n] = ksm(fac[n], mo - 2);
    for(ri i = n - 1; i > 0; i --)
        inv[i] = inv[i + 1] * (i + 1) % mo;
    for(ri i = 0; i <= n; i ++)
        qwq.push(in(n, i));
    while(k --)
    {
        in qaq = qwq.top(); qwq.pop();
        ans = (ans + qaq.c) % mo, qaq.x --;
        qwq.push(in(qaq.x, qaq.y));
    }
    printf("%lld", ans);
}

【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 ++]]));
}