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

【CF487C】Prefix Product Sequence

构造题都是脑洞嘤嘤嘤。
首先考虑什么时候有解,答案是当n为4或者是质数的时候,之所以4有解是因为,4只能被分解成4=2·2,其他的合数都可以被分解成两个比他小的因数,那么这样在mod \; n意义下就是0了,所以不可能。
那么继续考虑,1不能放在除了第一个地方以外的其他地方,因为放在其他的地方就会出现前缀积相等的情况,n只能放在最后,因为前缀积加入n以后在mod \; n意义下就是0了。
至于中间那些数,我们考虑放入\frac{2}{1},\frac{3}{2},\frac{4}{3}……这样的,显然他们统一减去1以后也不会在mod \; n意义下相等,并且这样的前缀积因为不停抵消实际上就是2,3,4,5……,并不会重复。

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

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

int main()
{
    re(n);
    if(n == 4)
        printf("YES\n1\n3\n2\n4");
    else
    {
        bool f = 1;
        for(ri i = 2; i * i <= n; i ++)
            if(n % i == 0)
            {
                f = 0; break;
            }
        if(!f)
            printf("NO");
        else
        {
            puts("YES");
            printf("1\n");
            for(ri i = 2; i < n; i ++)
                printf("%lld\n", (lo)i * ksm(i - 1, n - 2, n) % n);
            if(n > 1)
                printf("%lld", n);
        }
    }
    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;
}

【CF226D】The table

这个题有一个很显然的贪心想法,每次扫描到某一行或者某一列的时候如果发现和为负数就进行修改。这样的复杂度和正确性是对的,因为显然对于整个表格,你的总权值和是在不断增加的,除了这一行/列以外,其他的点是没有变化的,每次至少增加2,而点权绝对值只有100以内。
注意你还得输出修改次数最小的方案,对于某一行/列,如果修改了偶数次,那么它就是废操作

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

int n, m, a[110][110], ta1, ta2, sta1[10010], sta2[10010], cnt1[110], cnt2[110];

inline bool check()
{
    for(ri i = 1; i <= n; i ++)
    {
        int su = 0;
        for(ri j = 1; j <= m; j ++)
            su += a[i][j];
        if(su < 0)
            return 1;
    }
    for(ri i = 1; i <= m; i ++)
    {
        int su = 0;
        for(ri j = 1; j <= n; j ++)
            su += a[j][i];
        if(su < 0)
            return 1;
    }
    return 0;
}

inline void print()
{
    for(ri i = 1; i <= n; i ++, printf("\n"))
        for(ri j = 1; j <= m; j ++)
            printf("%d ", a[i][j]);
    printf("\n");
}

int main()
{
    re(n), re(m);
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
            re(a[i][j]);
    while(check())
    {
        for(ri i = 1; i <= n; i ++)
        {
            int su = 0;
            for(ri j = 1; j <= m; j ++)
                su += a[i][j];
            if(su < 0)
            {
                for(ri j = 1; j <= m; j ++)
                    a[i][j] = -a[i][j];
                cnt1[i] ++;
                //print();
            }
        }
        for(ri i = 1; i <= m; i ++)
        {
            int su = 0;
            for(ri j = 1; j <= n; j ++)
                su += a[j][i];
            if(su < 0)
            {
                cnt2[i] ++;
                for(ri j = 1; j <= n; j ++)
                    a[j][i] = -a[j][i];
                //print();
            }
        }
    }
    for(ri i = 1; i <= n; i ++)
        if(cnt1[i] & 1)
            sta1[++ ta1] = i;
    for(ri i = 1; i <= m; i ++)
        if(cnt2[i] & 1)
            sta2[++ ta2] = i;
    printf("%d ", ta1);
    for(ri i = 1; i <= ta1; i ++)
        printf("%d ", sta1[i]);
    printf("\n");
    printf("%d ", ta2);
    for(ri i = 1; i <= ta2; i ++)
        printf("%d ", sta2[i]);
    system("pause");
}

【JXOI2018 题解】

本来以为是信心场,结果被jls整自闭了,还是我菜。
luogu P4562 [JXOI2018] 游戏
个人觉得这个题目的转化挺有意思的。
考虑这个序列里面有多少数是不作为别人的倍数的,假设这样的数有sum个,那么这种数最后一次出现的位置就是t(p)
因此我们可以考虑枚举最后一个特殊数出现在什么地方,假设出现在x,那么x这里对答案的贡献就是x·sum·A_{x – 1}^{tot – 1}·(n-sum)!
至于sum,可以通过线性筛找出所有“除以他的最小质因子就小于L”的数。
总时间复杂度O(n)

// luogu-judger-enable-o2
#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 lo mo = 1e9 + 7;

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

bool flag[10000010];

int n, l, r, tot, mi[10000010], prime[700000], ans, cnt, su, inv[10000010], fac[10000010];

inline lo ask(lo x, lo y)
{
    return x < y ? 0 : (lo)fac[x] * (lo)inv[x - y] % mo; 
}

int main()
{
    re(l), re(r);
    fac[0] = 1, inv[0] = 1;
    for(ri i = 1; i <= r; i ++)
        fac[i] = (lo)fac[i - 1] * (lo)i % mo;
    inv[r] = ksm(fac[r], mo - 2);
    for(ri i = r - 1; i >= 1; i --)
        inv[i] = (lo)inv[i + 1] * (lo)(i + 1) % mo;
    int d; mi[1] = 1;
    for(ri i = 2; i <= r; i ++)
    {
        if(!flag[i])
            prime[++ cnt] = i, mi[i] = i;
        for(ri j = 1; j <= cnt && (d = i * prime[j]) <= r; j ++)
        {
            flag[d] = 1, mi[d] = prime[j];
            if(i % prime[j] == 0)
                break;
        }
    }
    n = r - l + 1;
    for(ri i = l; i <= r; i ++)
        if(i / mi[i] < l)
            tot ++;
    if(l == 1)
        tot = 1;
    for(ri i = tot; i <= n; i ++)
        ans += (lo)i * (lo)tot % mo * ask(i - 1, tot - 1) % mo * fac[n - tot] % mo, ans %= mo;
    printf("%d", ans);
}

luogu P4563 [JXOI2018] 守卫
这个题开始以为什么凸包乱搞,后来发现是自己煞笔了。
考虑最朴素的状态dp_{l,r}表示目前左端点是l,右端点是r时候要想看全的最小代价,那么r根据题意是一定要放的,而r伸出去又能看见很多个点,将整个大区间划分成很多小的,那么固定右端点,这个时候r产生的影响就是一定的了。
那么从右往左走,每次发现一个r能看见的点,更新一下小区间的和。这个小区间的和是由dp_{l + 1, las-1},dp_{l + 1, las}更新的,las就是上一个能被r看见的点,可以画图得知,r能看见的点,与r的斜率是单调递减的。这样更新也很好理解,就是通过往山头放来减少代价。

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

int n, ans, dp[5050][5050], h[5050];

inline double slope(int x, int y)
{
    double X = h[y] - h[x], Y = y - x;
    return X / Y;
}

int main()
{
    re(n);
    for(ri i = 1; i <= n; i ++)
        re(h[i]);
    for(ri r = 1; r <= n; r ++)
    {
        int las = 0, sum = 1; ans ^= (dp[r][r] = 1);
        for(ri l = r - 1; l >= 1; l --)
        {
            if((!las) || slope(las, r) >= slope(l, r))
                sum += min(dp[l + 1][las - 1], dp[l + 1][las]), las = l;
            ans ^= (dp[l][r] = sum + min(dp[l][las - 1], dp[l][las]));
            //cout << l << ' ' << r << ' ' << dp[l][r] << '\n';
        }
    }
    printf("%d", ans);
}

luogu P4561 [JXOI2018] 排序问题
这个题要是jls不给样例解释可能还挺难的,可是jls把样例解释放上去就比较简单了
我们现在能加入一些数字进去,要求目的使得\frac{n!}{\prod cnt_i!}最小,其中cnt_i表示第i种数字出现的次数。
首先,对于那些值域在[l,r]之外的数我们没法改变它的出现次数,对此无能为力,所以直接统计起来。
因此,根据数值大小排序,统计出每种数字的出现次数,同时对于没出现的并且值域在[l,r]的数进行统计,然后把出现次数丢进个桶里面,因为这个桶里最多只要有n个值,所以直接一步步的推过去,假如落入两个数之间或者超出桶,我就进行2分最大的出现次数使得加入数字的次数不超过m,因为这个时候我是一口气推过去的。
那么这个时候又会出现有一部分要比二分值大1的情况,特殊处理就是……
别人写了2k3k,就我写了4.5k,大概是我思路比较垃圾qwq

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#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 = gch()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = gch();
    if(b == 1)
        x = - x;
}

const lo mo = 998244353;

const int ms = 4e5 + 10;

lo T, n, m, l, r, a[ms], fac[10200010], cnt[10200010], su[ms << 1], tmp[ms << 1], ta;

lo ans;

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()
{
    //freopen("sort9.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    re(T);
    fac[0] = 1;
    for(ri i = 1; i <= 10200000; i ++)
        fac[i] = (lo)fac[i - 1] * (lo)i % mo;
    while(T --)
    {
        re(n), re(m), re(l), re(r); ta = 0;
        for(ri i = 1; i <= n; i ++)
            re(a[i]);
        int las = 1; ans = 1;
        sort(a + 1, a + 1 + n); a[n + 1] = 0;
        for(ri i = 2; i <= n + 1; i ++)
            if(a[i] != a[i - 1])
            {
                if(a[i - 1] >= l && a[i - 1] <= r)
                {
                    cnt[i - las] ++, tmp[++ ta] = i - las;
                    if(a[i] >= l && a[i] <= r) 
                        cnt[0] += (i <= n) ? a[i] - a[i - 1] - 1 : 0;
                    else if(a[i] > r)
                        cnt[0] += (i <= n) ? r - a[i - 1] : 0;
                }
                else
                {
                    ans = ans * fac[i - las] % mo;
                    if(a[i - 1] < l && a[i] >= l && a[i] <= r)
                        cnt[0] += (i <= n) ? a[i] - l : 0;
                    else if(a[i - 1] < l && a[i] > r)
                        cnt[0] += r - l + 1;
                }
                las = i;
            }
        if(l < a[1])
        {
            if(r < a[1])
                cnt[0] += r - l + 1;
            else
                cnt[0] += a[1] - l;
        }
        if(r > a[n])
        {
            if(l > a[n])
                cnt[0] += r - l + 1;
            else
                cnt[0] += r - a[n];
        }
        if(cnt[0] > 0)
            tmp[++ ta] = 0;
        sort(tmp + 1, tmp + 1 + ta);
        ta = unique(tmp + 1, tmp + 1 + ta) - tmp - 1;
        int S = 0, pos = 1;
        for(ri i = 2; i <= ta; i ++)
        {
            if(S + (tmp[i] - tmp[i - 1]) * cnt[tmp[i - 1]] > m)
                break;
            S += (tmp[i] - tmp[i - 1]) * cnt[tmp[i - 1]], cnt[tmp[i]] += cnt[tmp[i - 1]], cnt[tmp[i - 1]] = 0;
            pos = i;
        }
        int mid, l = tmp[pos], r = tmp[pos + 1], tmpans = l;
        while(l <= r)
        {
            mid = (l + r) >> 1;
            if(S + cnt[tmp[pos]] * (mid - tmp[pos]) <= m)
                tmpans = mid, l = mid + 1;
            else
                r = mid - 1;
        }
        if(S + cnt[tmp[pos]] * (tmpans - tmp[pos]) < m && S + cnt[tmp[pos]] * (tmpans + 1 - tmp[pos]) > m)
        {
            if(tmpans != tmp[pos])
                cnt[tmpans] += cnt[tmp[pos]];
            cnt[tmpans] -= m - (S + cnt[tmp[pos]] * (tmpans - tmp[pos]));
            cnt[tmpans + 1] += m - (S + cnt[tmp[pos]] * (tmpans - tmp[pos]));
            ans = ans * ksm(fac[tmpans], cnt[tmpans]) % mo * ksm(fac[tmpans + 1], cnt[tmpans + 1]) % mo;
            cnt[tmp[pos]] = 0;
            cnt[tmpans + 1] = 0, cnt[tmpans] = 0;
            S = m;
        }
        else if(S + cnt[tmp[pos]] * (tmpans - tmp[pos]) == m)
        {
            if(tmpans != tmp[pos])
                cnt[tmpans] += cnt[tmp[pos]];
            ans = ans * ksm(fac[tmpans], cnt[tmpans]) % mo, cnt[tmpans] = 0, cnt[tmp[pos]] = 0, S = m;
        }
        else if(S < m)
        {
            l = tmp[ta] + 1, r = m + n, tmpans = l;
            while(l <= r)
            {
                int mid = (l + r) >> 1;
                if(S + cnt[tmp[ta]] * (mid - tmp[ta]) <= m)
                    tmpans = mid, l = mid + 1;
                else
                    r = mid - 1;
            }
            if(S + cnt[tmp[pos]] * (tmpans - tmp[pos]) < m && S + cnt[tmp[pos]] * (tmpans + 1 - tmp[pos]) > m)
            {
                if(tmpans != tmp[pos])
                    cnt[tmpans] += cnt[tmp[pos]];
                cnt[tmpans] -= m - (S + cnt[tmp[pos]] * (tmpans - tmp[pos]));
                cnt[tmpans + 1] += m - (S + cnt[tmp[pos]] * (tmpans - tmp[pos]));
                ans = ans * ksm(fac[tmpans], cnt[tmpans]) % mo * ksm(fac[tmpans + 1], cnt[tmpans + 1]) % mo;
                cnt[tmp[pos]] = 0;
                cnt[tmpans + 1] = 0, cnt[tmpans] = 0;
                S = m;
            }
            else if(S + cnt[tmp[pos]] * (tmpans - tmp[pos]) == m)
            {
                if(tmpans != tmp[pos])
                    cnt[tmpans] += cnt[tmp[pos]];
                ans = ans * ksm(fac[tmpans], cnt[tmpans]) % mo, cnt[tmpans] = 0, cnt[tmp[pos]] = 0, S = m;
            }
        }
        for(ri i = pos + 1; i <= ta; i ++)
            ans = ans * ksm(fac[tmp[i]], cnt[tmp[i]]) % mo;
        for(ri i = 1; i <= ta; i ++)
            cnt[tmp[i]] = 0, tmp[i] = 0;
        ans = fac[n + m] * ksm(ans, mo - 2) % mo;
        printf("%lld\n", ans);
    }
}
/*
1
7 6 4 8
8 8 4 8 2 2 7 
*/

【CTSC2018 部分题解】

能做的传统题我都做了,但是d2t2和t3就算了emmmmmmm,一个错题一个题答。
再做一次这个还挺有感触的,时隔9个月,还是觉得很难啊qwq……awsl。
UOJ 399 D1T1 假面
D1T1我都不会,太败犬了嘤嘤嘤。你问我为啥不用luogu……谁让他数据损坏了。
考虑第一个操作锁定,设hp_{i,j,k}表示目前考虑到第i个人,他还剩j滴血,总共攻击了k次(不一定每次都对着它放技能)的概率,当i在这次攻击中活着的时候
hp_{i,j,k}=p·hp_{i,j+1,k-1} + (1-p)hp_{i,j,k-1}
其中p是攻击成功的概率
当这次攻击死掉也类似
hp_{i,0,k}=p·hp_{i,1,k-1} + hp_{i,0,k-1}
那么第一个操作就这么维护完成了。这个东西显然可以不用k那一维,优化掉。
但是第二个操作是大头,我开始居然想2^n的枚举谁活谁死,煞笔了一波。
f_{i,j}表示目前考虑了前i个人,有j个活着的概率,因为顺序无关紧要,因此我们可以将每次所询问的人放在最后面,设g_{i,j}表示第i个人一定活下来并且还有j个活着的概率。
那么现在我们就可以通过f_{n-1}这个地方求出f_{i},每次把第i个人放在第n个位子上就是了。
那么问题就在于f_{i,j}的转移了,也挺简单的
f_{i,j}=hp_{i,0}f_{i-1,j}+(1-hp_{i, 0})f_{i-1,j-1}
那么每次我们对第i个人算一遍f数组,单次n^2一共n^3,现在我们有一个复杂度为O((Q-C)m+Cn^3)这么一个优秀的……优秀个鬼。这个复杂度你拿头过。
这个时候就有神仙大声跟你港道理,ntt又是拉格朗日插值……总之这群神仙能给你做到Cn^2logn的复杂度就是了……
但这个题有更优秀的性质。
考虑刚才那个f,其无论顺序如何,最后f_n的结果一定都是一样的,也就说,我们可以通过f_n还原f_{n-1}
f_{n-1}{j} = \frac{f_{n,j}-(1-hp_{n,0})f_{n-1,j-1}}{hp_{n,0}}
考虑那么hp_{n,0}=0的情况,这个时候你会发现实际上就是f_n集体移动了一位,f_{n,j+1}变到了g_{n,j}上就是了。
那么复杂度就变成了O((Q-C)m+Cn^2),这居然还算是CTSC的简单题,卧佛了。

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

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

int n, q, opt, num[220];

const lo mo = 998244353;

lo hp[220][110], f[220], g[220], h[220], mxhp[220], inv[220];

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

inline void attack(int pos, lo u, lo v)
{
    lo p = u * ksm(v, mo - 2) % mo, P = (1 - p + mo) % mo;
    for(ri i = 0; i <= mxhp[pos]; i ++)
    {
        if(i)
            hp[pos][i] = hp[pos][i] * P % mo;
        if(i < mxhp[pos])
            hp[pos][i] = (hp[pos][i] + hp[pos][i + 1] * p) % mo;
    }
}

inline void ask(int len)
{
    memset(f, 0, sizeof(f)), f[0] = 1;
    for(ri i = 1; i <= len; i ++)
    {
        lo p = hp[num[i]][0], P = (1 - hp[num[i]][0] + mo) % mo;
        for(ri j = i; j >= 0; j --)
            f[j] = (p * f[j] + ((j > 0) ? P * f[j - 1] : 0)) % mo;
    }
    for(ri i = 1; i <= len; i ++)
    {
        h[i] = 0;
        if(!hp[num[i]][0])
            for(ri j = 0; j < len; j ++)//如果这个人一定活着,那直接计算其他人活着的概率 
                h[i] += f[j + 1] * inv[j + 1];
        else
        {
            lo Inv = ksm(hp[num[i]][0], mo - 2);
            for(ri j = 0; j <= len; j ++)
                g[j] = (f[j] - (j ? g[j - 1] * (1 - hp[num[i]][0]) % mo : 0)) % mo * Inv % mo, h[i] += inv[j + 1] * g[j] % mo;
        }
        h[i] = h[i] % mo * ((1 - hp[num[i]][0] + mo)) % mo; 
    }
    for(ri i = 1; i <= len; i ++)
        printf("%lld ", h[i]);
    printf("\n");
}

int main()
{
    re(n);
    for(ri i = 1; i <= n; i ++)
        re(mxhp[i]), hp[i][mxhp[i]] = 1, inv[i] = ksm(i, mo - 2);
    re(q);
    int id; lo u, v;
    while(q --)
    {
        re(opt);
        if(opt == 0)
            re(id), re(u), re(v), attack(id, u, v);
        else
        {
            re(v);
            for(ri i = 1; i <= v; i ++)
                re(num[i]);
            ask(v);
        }
    }
    lo pri;
    for(ri i = 1; i <= n; i ++)
    {
        pri = 0;
        for(ri j = 1; j <= mxhp[i]; j ++)
            pri += (lo)j * hp[i][j] % mo;
        printf("%lld ", pri % mo);
    }
}

luogu P4565 D1T2 暴力写挂
这个题我给他跪了。
首先,你对于第一棵树,按照边分的思想将他重构,根据边分树的性质,“如果一棵包含 n 个结点的树中每个点的度均不大于 d,那么存在一条边,使得分出的两棵子树的结点个数在 [\frac{n}{(d+1)},\frac{nd}{(d+1)}]”,然后你通过加入一些虚拟点,将整个树重新构造成一个二叉树。
重新构造成二叉树之后,再用类似于点分的思想,将这个第一次得到的边分树重新构造一个,就像动态点分治一样做一个动态边分治。
最后这个东西就变成了类似于线段树一样的东西,我们对第二个树进行dfs,并且按照这个顺序进行线段树合并,将每次dfs到的点插起来,查询答案即可……
太tm神仙了,卧佛了。
到现在对正确性还迷迷糊糊的我。

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

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 N = 7e5 + 5e4, M = 8510000, T = N << 1;

int n, tt, cnt, Sum, sz[N], son[N] = {N}, val[T], ch[T][2], fa[T], de[N];

int lm[M], rm[M], rt[N / 2], id[M]; 

lo ans, fl[M], fr[M], f[N][20], dis[N], D;

struct in
{
    int to, co;
    in() {}
    in(int X, int Y)
    {
        to = X, co = Y;
    }
}q[N];

vector <in> G1[N], G2[N / 2];

inline void add(int f, int l, int c, vector <in> *G)
{
    G[f].push_back((in){l, c}), G[l].push_back((in){f, c});
}

void build(int no, int las)
{
    for(ri i = 0; i < G1[no].size(); i ++)
    {
        int to = G1[no][i].to;
        if(to == las)
            continue;
        dis[to] = dis[no] + G1[no][i].co, build(to, no);//预处理出根到每个节点的距离
    }
    int l = 1, r = 0; in u, v;
    for(ri i = 0; i < G1[no].size(); i ++)
    {
        int to = G1[no][i].to;
        if(to == las)
            continue;
        q[++ r] = G1[no][i];
    }
    while(l + 2 <= r)
    {
        int w = ++ cnt;
        u = q[l ++], v = q[l ++];
        add(w, u.to, u.co, G1), add(w, v.to, v.co, G1);
        q[++ r] = (in){w, 0};
    }
    vector <in>().swap(G1[no]);//清空no这个点并不意味着边分树被清空了,只是为了保证二叉?
    while(l <= r)
        add(no, q[l].to, q[l].co, G1), l ++;
}

void askdis(int no, int las, int d)//处理出边分树上的dis
{
    for(ri i = 0; i < G1[no].size(); i ++)
    {
        int to = G1[no][i].to;
        if(to == las || to == -1)
            continue;
        f[to][d] = f[no][d] + G1[no][i].co, askdis(to, no, d);
    }
}

void askedge(int no, int las, int &ex, int &ey)//找出最中间的那个边,然后把它断开
{
    sz[no] = 1;
    for(ri i = G1[no].size() - 1; i >= 0; i --)
    {
        int to = G1[no][i].to;
        if(to == las || to == -1)
            continue;
        askedge(to, no, ex, ey), sz[no] += sz[to];
        if(son[to] < son[ey])
            ey = to, ex = no;
    }
    son[no] = abs(Sum - (sz[no] << 1));
}

int solve(int no, int S, int d)//再用类似于点分的方式,一层层断开查询
{
    if(S == 1)
    {
        de[no] = d; return no;
    }
    int ex = 0, ey = 0, w = ++ cnt;
    askdis(no, no, d), Sum = S, askedge(no, no, ex, ey);
    for(ri i = 0; i < G1[ex].size(); i ++)
    {
        int to = G1[ex][i].to;
        if(to == ey)
        {
            val[w] = G1[ex][i].co, G1[ex][i].to = -1; break;
        }
    }
    for(ri i = 0; i < G1[ey].size(); i ++)
    {
        int to = G1[ey][i].to;
        if(to == ex)
        {
            G1[ey][i].to = -1; break;
        }
    }
    fa[ch[w][0] = solve(ex, S - sz[ey], d + 1)] = w;//按照查询的顺序第二次建了一个新的边分树?不知如何称呼
    fa[ch[w][1] = solve(ey, sz[ey], d + 1)] = w;
    return w;
}

inline int insert(int no)//按照第二个树的顺序,对第一个树第二次建立的边分树的答案进行合并
{//fl维护的是左儿子的最长链,fr右儿子
    for(ri i = de[no], u = no, las = no; i >= 1; i --)
    {
        id[++ tt] = fa[no], fl[tt] = -1ll << 60, fr[tt] = fl[tt];
        if(ch[fa[no]][0] == no)
            fl[tt] = max(fl[tt], dis[u] + f[u][i]), lm[tt] = las;//这里类似于点分树查询信息
        if(ch[fa[no]][1] == no)
            fr[tt] = max(fr[tt], dis[u] + f[u][i]), rm[tt] = las;
        las = tt, no = fa[no];
    }
    return tt;
}

int merge(int x, int y)//类似于线段树的合并来合并
{
    if((!x) || (!y))
        return x + y;
    ans = max(ans, (fl[x] + fr[y] + val[id[x]]) / 2 - D);//val维护的是边分树上儿子到父亲的距离
    ans = max(ans, (fl[y] + fr[x] + val[id[x]]) / 2 - D);
    fl[x] = max(fl[x], fl[y]), fr[x] = max(fr[x], fr[y]);
    lm[x] = merge(lm[x], lm[y]), rm[x] = merge(rm[x], rm[y]);
    return x;
}

void dfs(int no, int las, lo d)
{
    rt[no] = insert(no), ans = max(ans, dis[no] - d);//-d是因为我们把这个点当做lca
    for(ri i = 0; i < G2[no].size(); i ++)
    {
        int to = G2[no][i].to;
        if(to == las)
            continue;
        dfs(to, no, d + G2[no][i].co);
        D = d; rt[no] = merge(rt[no], rt[to]);
    }
}

int main()
{
    re(n), cnt = n; int x, y, z; son[0] = 1e9 + 7;
    for(ri i = 1; i < n; i ++)
        re(x), re(y), re(z), add(x, y, z, G1);
    for(ri i = 1; i < n; i ++)
        re(x), re(y), re(z), add(x, y, z, G2);
    build(1, 1), solve(1, cnt, 0), dfs(1, 1, 0);
    printf("%lld", ans);
}

luogu P4566 D1T3 青蕈领主
又是tm一个神仙题,持续自闭(做ctsc&apio&noi可不是找着自闭)
首先有个结论,两个最长连续区间,除了包含和被包含以外,都是独立的,即不存在相交这种东西。
考虑证明,从连续区间的交和并,都是连续区间开始。

如图,假如红色部分不是连续区间,则存在一个数x,出现在黑色或者黄色部分,那么这样一定有一个不是连续区间,因为缺少了一个数,所以连续区间的交,都是连续区间。
同理,并也是连续区间。
那么现在,如果两个极长的连续区间相交但不存在完全包含,这两个极长连续区间是可以合并的,与初始条件不合,得证。
因此我们可以根据包含和被包含的关系,建立一个属性结构,这个结构的根节点一定是最后一个点,因为最后一个点构成了一个长度为n的连续区间,将所有的区间都包含了。
接下来就是魔术的关键了。
考虑一个点x,将他所有儿子的子树全缩成儿子自己,那么这个树内的l_j一定都是1 1 1 1 1……n这样的形式。
这是因为对于每个儿子,缺了谁也不能成为连续区间。
也就说我们找到了问题的突破口(盲生你发现了华点!)
f(x)表示有一个长度为xl_j形如1 1 1 1……n这样的序列的方案数。
那这个东西有没有递推式呢。答案是有的。
f_n=(n-1)f_{n-1}+\sum_{i=2}^{n-2}((i-1)f_if_{n-i})
证明呢?
a tql wsl(雾)
对于一个长度为n的序列,如果删除里面的最小数,并且剩下的序列合法,那么除了最小值两边都可以插入,n+1-2
对于不合法的序列,枚举合并的区间长度,那么考虑先现在有一个长度为i的连续值域,因为不能包含最大值,所以共有n-i-1也就是i-1个,然后破坏这个长度为i的方案数正好是f_i,因为对于每个合法序列带走一个就好,剩下的合法方案数是f_{n-i}
然后这个式子可以用多项式科技,分治ntt一下。就做完了……

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#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;

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 = 2e5 + 10;

const lo mo = 998244353;

int n, t, sta[ms], ta, len, num, pos[ms], val[ms];

lo f[ms], inv[ms], po[ms], inv3, a[ms], b[ms];

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

inline void ntt(lo *a, int f)
{
    for(ri i = 1; i < len; i ++)
        if(i < pos[i])
            swap(a[i], a[pos[i]]);
    lo la, lb;
    for(ri i = 1; i < len; i <<= 1)
    {
        lo wn = (f == 1) ? po[i] : inv[i];
        for(ri j = 0; j < len; j += (i << 1))
        {
            lo w = 1;
            for(ri k = j; k < j + i; k ++)
            {
                la = a[k], lb = w * a[k + i] % mo;
                w = w * wn % mo, a[k] = (la + lb) % mo, a[k + i] = (la - lb + mo) % mo;
            }
        }
    }
    if(f == -1)
    {
        lo invlen = ksm(len, mo - 2);
        for(ri i = 0; i < len; i ++)
            a[i] = a[i] * invlen % mo;
    }
}

inline void mul(lo *a, lo *b)
{
    ntt(a, 1), ntt(b, 1);
    for(ri i = 0; i < len; i ++)
        a[i] = a[i] * b[i] % mo;
    ntt(a, -1);
}

void merge(int l, int r)
{
    if(l == r)
    {
        if(l == 2)
            f[l] = 2;
        else
            f[l] += f[l - 1] * (lo)(l - 1), f[l] %= mo;
        //cout << l << ' ' << f[l] << '\n';
        return;
    }
    int mid = (l + r) >> 1;
    merge(l, mid);
    len = 1, num = 0;
    while(len <= (r - l + 1))
        len <<= 1, num ++;
    //cout << len << ' ' << num << '\n'; 
    for(ri i = 1; i < len; i ++)
        pos[i] = ((pos[i >> 1] >> 1) | ((i & 1) << (num - 1)));
    for(ri i = l; i <= mid; i ++)
        a[i - l] = f[i] * (lo)(i - 1) % mo;
    for(ri i = mid + 1 - l; i < len; i ++)
        a[i] = 0;
    for(ri i = l; i <= r; i ++)
        b[i - l] = f[i - l];
    for(ri i = r - l + 1; i < len; i ++)
        b[i] = 0;
    mul(a, b);
    for(ri i = mid + 1; i <= r; i ++)
        f[i] += a[i - l], f[i] -= ((f[i] >= mo) ? mo : 0);// cout << f[i] << ' ';
    if(l != 2 && r > l + 1)
    {
        for(ri i = l; i <= mid; i ++)
            a[i - l] = f[i];
        for(ri i = mid + 1 - l; i < len; i ++)
            a[i] = 0;
        for(ri i = l; i <= r; i ++)
            b[i - l] = f[i - l] * (lo)(i - l - 1) % mo;
        for(ri i = r - l + 1; i < len; i ++)
            b[i] = 0;
        mul(a, b);
        for(ri i = mid + 1; i <= r; i ++)
            f[i] += a[i - l], f[i] %= mo;
    }
    merge(mid + 1, r);
}

int main()
{
    re(t), re(n), inv3 = ksm(3, mo - 2);
    for(ri i = 1; i <= (n << 1); i <<= 1)
        po[i] = ksm(3, (mo - 1) / (i << 1));// cout << po[i] << ' ';
    //cout << '\n'; 
    for(ri i = 1; i <= (n << 1); i <<= 1)
        inv[i] = ksm(inv3, (mo - 1) / (i << 1));// cout << inv[i] << ' ';
    //cout << '\n';
    if(n > 2)
        merge(2, n - 1);
    f[0] = 1, f[1] = 2;
    while(t --)
    {
        for(ri i = 1; i <= n; i ++)
            re(val[i]), val[i] = i - val[i] + 1;
        if(val[n] != 1 || val[1] != 1)
        {
            puts("0"); continue;
        }
        bool fl = 0;
        lo ans = 1; ta = 0;
        for(ri i = 1; i <= n; i ++)
        {
            int cnt = 0;
            for(; ta && val[i] <= sta[ta]; )
            {
                if(val[i] > val[sta[ta]])
                {
                    fl = 1; break;
                }
                ta --, cnt ++;
            }
            if(fl)
                break;
            //cout << cnt << ' ' << f[cnt] << '\n';
            ans = ans * f[cnt] % mo, sta[++ ta] = i;
        }
        printf("%lld\n", fl ? 0 : ans);
    }
}

luogu P4602 D2T1 混合果汁
其实我对混合咖啡还是蛮有自信的

这题当时我有思路,但没想到主席树维护,然后就睿智如我了
这题,煞笔题(认真),CTSC2018唯一一个水题(不接受反驳)。
首先,我们可以想到二分答案,二分最小值,但怎么找出那些满足答案且代价最小的果汁,可以想到线段树,但是线段树会插入那些不满足答案的果汁,怎么办……
答案就是,按照d从大到小排序,然后按照d的顺序插入,这样就行了……复杂度O(nlog^2n)
我是弟弟。

// luogu-judger-enable-o2
#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 ++;
}

typedef long long lo;

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 = 1e5 + 10;

lo n, m, lx, ly, lz, tot, tad, tap, pos, cnt, d[ms], rot[ms];

struct in
{
    lo ls, rs, v, c;
}ter[ms << 5];

struct juice
{
    lo d, p, l;
}a[ms];

inline bool cmp(juice a, juice b)
{
    return a.d < b.d;
}

inline lo build(lo l, lo r)
{
    lo nrt = ++ tot, mid = (l + r) >> 1;
    if(l == r)
        return nrt;
    ter[nrt] = (in){build(l, mid), build(mid + 1, r), 0, 0};
    return nrt;
}

lo change(lo rrt, lo l, lo r, lo ll, lo v, lo c)
{
    lo nrt = ++ tot, mid = (l + r) >> 1; ter[nrt] = ter[rrt];
    ter[nrt].v += v, ter[nrt].c += c;
    if(l == r)
        return nrt;
    if(ll <= mid)
        ter[nrt].ls = change(ter[rrt].ls, l, mid, ll, v, c);
    else
        ter[nrt].rs = change(ter[rrt].rs, mid + 1, r, ll, v, c);
    return nrt;
}

lo ask(lo lrt, lo rrt, lo l, lo r, lo v)
{
    if(l == r)
        return min(v / l, ter[rrt].v - ter[lrt].v);
    lo mid = (l + r) >> 1, del = ter[ter[rrt].ls].c - ter[ter[lrt].ls].c;
    lo vv = ter[ter[rrt].ls].v - ter[ter[lrt].ls].v;
    if(del > v)
        return ask(ter[lrt].ls, ter[rrt].ls, l, mid, v);
    else
        return vv + ask(ter[lrt].rs, ter[rrt].rs, mid + 1, r, v - del);
}

inline lo solve()
{
    lo l = 1, r = pos;
    while(l < r)
    {
        lo mid = (l + r + 1) >> 1;
        if(ask(rot[d[mid] - 1], rot[n], 1, 1e5, lx) >= ly)
            l = mid;
        else
            r = mid - 1;
    }
    return ask(rot[d[l] - 1], rot[n], 1, 1e5, lx) >= ly ? a[d[l]].d : -1;
}

int main()
{
    re(n), re(m);
    for(ri i = 1; i <= n; i ++)
        re(lx), re(ly), re(lz), a[i] = (juice){lx, ly, lz};
    sort(a + 1, a + 1 + n, cmp);
    pos = 0; rot[0] = build(1, 1e5);
    for(ri i = 1; i <= n; i ++)
    {
        if(a[i].d != a[i - 1].d)
            d[++ pos] = i;
        rot[i] = change(rot[i - 1], 1, 1e5, a[i].p, a[i].l, a[i].l * a[i].p);
    }
    while(m --)
        re(lx), re(ly), printf("%lld\n", solve());
}

【luoguP3264】[JLOI2015]管道连接

又是一道斯坦纳树神题。
斯坦纳树就大体理解为维护一些点的联通性,方式一般就两种
同一个点两个集合,以及不同的点spfa转移。
考虑目前我们需要连接一些关键点,但是涉及到不同频率,所以我们需要考虑频率之间的合并问题。
那先套路求一遍斯坦纳树,然后我们枚举子集合并。

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

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 = 3e3;

int n, m, p, lx, ly, lz, head[ms], tot = -1, ans[1 << 11], dp[ms][1 << 11];

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

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

struct node
{
    int col, pos;
}poi[15];

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

bool flag[ms], vis[1 << 11];

queue <int> qwq;

inline void spfa(int s)
{
    for(ri i = 1; i <= n; i ++)
        if(dp[i][s] < dp[n + 1][0])
            qwq.push(i), flag[i] = 1;
    while(!qwq.empty())
    {
        int qaq = qwq.front();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(dp[to][s] > dp[qaq][s] + ter[i].co)
            {
                dp[to][s] = dp[qaq][s] + ter[i].co;
                if(!flag[to])
                    qwq.push(to), flag[to] = 1;
            }
        }
        qwq.pop(); flag[qaq] = 0;
    }
}

inline bool check(int s)
{
    for(ri i = 2; i <= p; i ++)
        if(poi[i].col == poi[i - 1].col && ((s >> (i - 1)) & 1) != ((s >> (i - 2)) & 1))
            return 0;
    return 1;
}

int main()
{
    re(n), re(m), re(p); memset(head, -1, sizeof(head));
    for(ri i = 1; i <= m; i ++)
        re(lx), re(ly), re(lz), build(lx, ly, lz);
    for(ri i = 1; i <= p; i ++)
        re(poi[i].col), re(poi[i].pos);
    sort(poi + 1, poi + 1 + p, cmp);
    poi[0] = (node){0, 0};
    int Cnt = 1;
    for(ri i = 2; i <= p; i ++)
        if(poi[i].col != poi[i - 1].col)
            Cnt ++;
    Cnt = (1 << Cnt);
    memset(dp, 63, sizeof(dp)), memset(ans, 63, sizeof(ans));
    for(ri i = 1; i <= p; i ++)
        dp[poi[i].pos][1 << (i - 1)] = 0;
    for(ri s = 0; s < (1 << p); s ++)
    {
        for(ri i = 1; i <= n; i ++)
            for(ri j = s; j; j = (j - 1) & s)
                dp[i][s] = min(dp[i][s], dp[i][j] + dp[i][s ^ j]);
        spfa(s);
    }
    for(ri s = 0; s < (1 << p); s ++)
        for(ri i = 1; i <= n; i ++)
            ans[s] = min(ans[s], dp[i][s]);
    for(ri s = 0; s < (1 << p); s ++)
        vis[s] = check(s); //cout << s << ' ' << vis[s] << '\n';
    for(ri s = 0; s < (1 << p); s ++)
        if(vis[s])
            for(ri S = s; S; S = (S - 1) & s)
                if(vis[S])
                    ans[s] = min(ans[s], ans[S] + ans[s ^ S]);
    printf("%d", ans[(1 << p) - 1]);
}

【luoguP4211】[LNOI2014]LCA

这个题想法好神仙啊qwq。
考虑问题转化,我们现在很难对一堆点的lca进行快速查询——事实上最多可以有n^2种可能性,所以这是不现实的。
那么我们就考虑把dep[lca(i,z)]转化成其他东西。
考虑对每个i到根的路径打一个区间+1的标记,然后统计从z到根的路径上的权值和。为了防止询问间的影响,我们离线进行差分,将询问变成1到r减去1到l-1,那么现在就可以线段树+树剖了,O(nlog^2n)

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

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 = 5e4 + 10;

const lo mo = 201314;

int n, q, tot = -1, cnt, ta, head[ms], de[ms], fa[ms], pos[ms], pre[ms], tp[ms], son[ms], sz[ms];

lo ans[ms];

struct node
{
    int num, pos, z, v;
}poi[ms << 1];

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 dfs1(int no)
{
    sz[no] = 1, de[no] = de[fa[no]] + 1;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == fa[no])
            continue;
        fa[to] = no, dfs1(to), sz[no] += sz[to];
        if((!son[no]) || sz[son[no]] < sz[to])
            son[no] = to;
    }
}

void dfs2(int no, int t)
{
    tp[no] = t, pos[no] = ++ cnt, pre[cnt] = no;
    if(son[no])
        dfs2(son[no], t);
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == fa[no] || to == son[no])
            continue;
        dfs2(to, to);
    }
}

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

struct Seg
{
    lo su[ms << 2], add[ms << 2], ds[ms << 2];

    inline void down(int w, int l, int r)
    {
        if(!add[w])
            return;
        int mid = (l + r) >> 1;
        add[w << 1] += add[w], su[w << 1] += add[w] * (mid - l + 1), su[w << 1] %= mo;
        add[w << 1 | 1] += add[w], su[w << 1 | 1] += add[w] * (r - mid), su[w << 1 | 1] %= mo;
        add[w] = 0;
    }

    lo ask(int w, int l, int r, int ll, int rr)
    {
        if(l == ll && r == rr)
            return su[w];
        down(w, l, r); int mid = (l + r) >> 1;
        if(rr <= mid)
            return ask(w << 1, l, mid, ll, rr);
        else if(ll > mid)
            return ask(w << 1 | 1, mid + 1, r, ll, rr);
        else
            return (ask(w << 1, l, mid, ll, mid) + ask(w << 1 | 1, mid + 1, r, mid + 1, rr)) % mo;
    }

    void change(int w, int l, int r, int ll, int rr, lo v)
    {
        if(l == ll && r == rr)
        {
            add[w] += v, su[w] += v * (r - l + 1), su[w] %= mo; return;
        }
        down(w, l, r); int mid = (l + r) >> 1;
        if(rr <= mid)
            change(w << 1, l, mid, ll, rr, v);
        else if(ll > mid)
            change(w << 1 | 1, mid + 1, r, ll, rr, v);
        else
            change(w << 1, l, mid, ll, mid, v), change(w << 1 | 1, mid + 1, r, mid + 1, rr, v);
        su[w] = (su[w << 1] + su[w << 1 | 1]) % mo;
    }
}seg;

inline void change(int x)
{
    while(tp[x] ^ tp[1])
        seg.change(1, 1, cnt, pos[tp[x]], pos[x], 1), x = fa[tp[x]];
    seg.change(1, 1, cnt, pos[1], pos[x], 1);
}

inline lo ask(int x)
{
    lo rt = 0;
    while(tp[x] ^ tp[1])
        rt += seg.ask(1, 1, cnt, pos[tp[x]], pos[x]), x = fa[tp[x]], rt %= mo;
    rt += seg.ask(1, 1, cnt, pos[1], pos[x]); rt %= mo;
    return rt;
}

int main()
{
    re(n), re(q), memset(head, -1, sizeof(head));
    for(ri i = 2; i <= n; i ++)
        re(fa[i]), fa[i] ++, build(fa[i], i);
    dfs1(1), dfs2(1, 1);
    int l, r, z;
    for(ri i = 1; i <= q; i ++)
    {
        re(l), re(r), re(z), r ++, z ++;
        poi[++ ta] = (node){i, l, z, -1};
        poi[++ ta] = (node){i, r, z, 1};
    }
    sort(poi + 1, poi + 1 + ta, cmp);
    int no = 0; //seg.build(1, 1, cnt);
    for(ri i = 1; i <= ta; i ++)
    {
        while(no < poi[i].pos)
            no ++, change(no);
        ans[poi[i].num] += ask(poi[i].z) * poi[i].v;
        ans[poi[i].num] %= mo;
    }
    for(ri i = 1; i <= q; i ++)
        ans[i] = (ans[i] + mo) % mo, cout << ans[i] << '\n';
}

【luoguP4119】[Ynoi2018]未来日记

这个题太tm神仙了,我是佛了,推荐题解 P4119 【[Ynoi2018]未来日记】
首先这个题你可以套数据结构简单的达到O(n\sqrt{n}logn)级别,但是……你算算复杂度会发现,这tm完全t的飞起。套logn的数据结构基本是不可行的。
那么有没有什么办法不用那个logn呢,答案是有的。我们不仅对原来的序列进行分块,同时还对值域进行分块。
设置三个数组id, iv, colid表示每个数字离散化之后某个位置的下标(相当于染色),iv表示染色下标真正的值,col表示目前这个位置经过离散化+1e5的结果
那么就会有这么几个等式:
iv[id[col[i]]]=i的真实数字,id[col[i]]是id[i这个位置真实数字],id[不存在]=0
思考下会发现这是对的……
我们再设置两个数组
su_{i,j}表示目前权值是i并且在原序列第j个块,cnb_{i,j}表示目前权值所在块是i并且这个数在原序列第j个块。
那么操作1的时候我们暴力修改就是了,根据刚才的博文可以得出均摊是O((n+m)\sqrt{n})
对于操作2呢?
因为对于值域进行分块并处理前缀和,每次都是\sqrt{n}的操作。
然后这个题目做完了,但是代码非常难写……我基本就是抄的神仙代码……而且为啥多开了好几个库代码总用时多了1000ms……我佛了

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

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 N = 1e5 + 10, B = 317, B1 = 350;

int n, m, lx, opt, bk[N], bi1[N], cnb[N / B1 + 3][N / B + 3], su[N][N / B + 3], bi[N];
//su用来统计某个数字在这个块里面出现了多少次,cnb用来统计某个权值块在这个真实的块里面出现多少次 
int bj[N], tr[N], trb[N / B1 + 3], msu[N / B + 3], trs[N];

struct Block
{
    int id[N + B], iv[3 + B], col[B + 3], sz, u, _cnt, rcol[B + 3];
    //id表示每个数字离散化之后的下标,iv表示每个下标真正的值,col表示离散化了的值 
    inline int& operator[] (const int& x)
    {
        return col[x];
    }

    inline int find(const int& x)
    {
        return iv[id[col[x]]];
    }

    inline void build()//建块 
    {
        for(ri i = 1; i <= sz; i ++)//给数字染色? 
            trs[i] = bk[col[i]] = (!bk[col[i]]) ? ++ _cnt : bk[col[i]];
        for(ri i = 1; i <= sz; i ++)//清空数组…… 
            bk[col[i]] = 0;
        for(ri i = 1; i <= sz; i ++)
            iv[trs[i]] = col[i];//trs是离散化的结果
        for(ri i = 1; i <= sz; i ++)
            id[col[i]] = trs[i];//col目前还是原来的数,所以不动
        for(ri i = 1; i <= sz; i ++)
            col[i] = trs[i] + 100000;//col现在变成了离散化后的数了
        for(ri i = 1; i <= sz; i ++)
            id[col[i]] = trs[i];
    }

    inline void rebuild(int x, int y, int l, int r)
    {
        if(su[x][u] == su[x][u - 1])//如果这个块里面没有x这个数字 
            return;
        for(ri i = 1; i <= sz; i ++)//重新找回原来的数字 
            col[i] = iv[id[col[i]]];
        int cntx = 0;
        for(ri i = l; i <= r; i ++)
            if(col[i] == x)
                col[i] = y, cntx ++;
        _cnt = 0, build(), msu[u] = cntx;
    }

    inline void rebuild(int x, int y)
    {
        for(ri i = 1; i <= sz; i ++)//重新找回原来的数字 
            col[i] = iv[id[col[i]]];
        for(ri i = 1; i <= sz; i ++)
            col[i] = (col[i] == x) ? y : col[i];
        _cnt = 0, build();
    }
    //iv[id[col[i]]] = i的真实数字,id[col[i]]是id[i这个位置真实数字],id[不存在]=0 
    inline void lb_md(int x, int y)
    {
        id[y] = id[x], iv[id[x]] = y, id[x] = 0;
    }

    inline void change(int x, int y)
    {
        if(su[x][u] == su[x][u - 1])
            return;
        if(su[y][u] != su[y][u - 1])
            rebuild(x, y);
        else
            lb_md(x, y);
        msu[u] = su[x][u] - su[x][u - 1];
    }

    inline void add_tr(int l, int r)//加入零碎的块 
    {
        for(ri i = l; i <= r; i ++)
            rcol[i] = find(i);
        for(ri i = l; i <= r; i ++)
            tr[rcol[i]] ++, trb[bi1[rcol[i]]] ++;
    }

    inline void clear_tr(int l, int r)//清空 
    {
        for(ri i = l; i <= r; i ++)
            tr[rcol[i]] = 0, trb[bi1[rcol[i]]] = 0;
    }
}bl[N / B + 3];

inline int subsolve(int t1, int t2, int k)//通过给值域分块查询 
{
    int rt = B1, cnt = 0, j = 1;
    for(cnt = cnb[j][t2] - cnb[j][t1] + trb[j]; cnt < k; j ++, rt = min(rt + B1, N - 10), cnt += cnb[j][t2] - cnb[j][t1] + trb[j]);
    for(; cnt >= k; cnt -= su[rt][t2] - su[rt][t1] + tr[rt], rt --);
    return rt + 1;
}

inline int kth(int l, int r, int k)
{
    if(bi[l] == bi[r])
    {
        bl[bi[l]].add_tr(bj[l], bj[r]);
        int rt = subsolve(0, 0, k);
        bl[bi[l]].clear_tr(bj[l], bj[r]);
        return rt;
    }
    int dl, dr;
    if(bj[l] != 1)
        bl[bi[l]].add_tr(bj[l], B), dl = bi[l];
    else
        dl = bi[l] - 1;
    if(bj[r] != B && r != n)
        bl[bi[r]].add_tr(1, bj[r]), dr = bi[r] - 1;
    else
        dr = bi[r];
    int rt = subsolve(dl, dr, k);
    if(bj[l] != 1)
        bl[bi[l]].clear_tr(bj[l], B);
    if(bj[r] != B && r != n)
        bl[bi[r]].clear_tr(1, bj[r]);
    return rt;
}

int main()
{
    for(ri i = 1; i <= N - 10; i ++)
        bi[i] = (i - 1) / B + 1, bi1[i] = (i - 1) / B1 + 1, bj[i] = (i - 1) % B + 1;
    re(n), re(m);
    for(ri i = 1; i <= n; i ++)
    {
        re(lx), bl[bi[i]][bj[i]] = lx;
        for(ri j = bi[i]; j <= bi[n]; j ++)
            su[lx][j] ++;
        lx = bi1[lx];
        for(ri j = bi[i]; j <= bi[n]; j ++)
            cnb[lx][j] ++;
    } 
    for(ri i = 1; i < bi[n]; i ++)
        bl[i].sz = B;
    bl[bi[n]].sz = (n % B == 0) ? B : n % B;
    for(ri i = 1; i <= bi[n]; i ++)
        bl[i].u = i, bl[i].build();
    ri l, r, x, y, dl, dr;
    while(m --)
    {
        re(opt), re(l), re(r), re(x);
        if(opt == 1)
        {
            re(y);
            for(ri i = bi[l]; i <= bi[n]; i ++)
                msu[i] = 0;
            if(bi[l] == bi[r])
                bl[bi[l]].rebuild(x, y, bj[l], bj[r]);
            else
            {
                if(bj[l] != 1)
                    bl[bi[l]].rebuild(x, y, bj[l], B), dl = bi[l] + 1;
                else
                    dl = bi[l];
                if(bj[r] != B && r != n)
                    bl[bi[r]].rebuild(x, y, 1, bj[r]), dr = bi[r] - 1;
                else
                    dr = bi[r];
                for(ri i = dl; i <= dr; i ++)
                    bl[i].change(x, y);
            }
            for(ri i = bi[l] + 1; i <= bi[n]; i ++)//msu存的修改数 
                msu[i] += msu[i - 1];
            for(ri i = bi[l]; i <= bi[n]; i ++)
                su[x][i] -= msu[i];
            for(ri i = bi[l], bv = bi1[x]; i <= bi[n]; i ++)
                cnb[bv][i] -= msu[i];
            for(ri i = bi[l]; i <= bi[n]; i ++)
                su[y][i] += msu[i];
            for(ri i = bi[l], bv = bi1[y]; i <= bi[n]; i ++)
                cnb[bv][i] += msu[i];
        }
        else
            printf("%d\n", kth(l, r, x));
    }
}

【luoguP3980】[NOI2008]志愿者招募

这个题rqy的做法好神仙啊
首先感觉上是要把ii+1连起来,流量无限,费用为0,但是怎么表示消耗工资呢
考虑第s_i天到t_i天加了x个志愿者,就相当于s_i天多出来x个志愿者,t_{i}+1少了x个志愿者,因此我们要从t_i+1s_i连接一条流量无限,费用为c_i的边,每流1下就相当于多一个志愿者回去。
但是还有一个限制,每天不少于a_i这个怎么办?
不少于那我们就从第i天抽出a_i的流量,从iT连接一条边,流量为a_i,费用为0。但是抽走了也得补回去,从Si连接一条流量为a_{i-1},费用为0的边,这是上一天用完了还能用的人在插回去,那么最开始从ii+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;

typedef long double ld;

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

int n, m, lx, ly, lz, tot = -1, head[1010], pre[1010], t, a[1010];

lo fl[1010], dis[1010], ans;

struct in
{
    int to, ne; lo co, fl;
}ter[100010];

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

queue <int> qwq;

bool flag[1010];

inline bool spfa()
{
    memset(dis, 63, sizeof(dis)), memset(fl, 0, sizeof(fl)), memset(flag, 0, sizeof(flag));
    qwq.push(0), dis[0] = 0, fl[0] = 3e9 + 7, flag[0] = 1;
    while(!qwq.empty())
    {
        int qaq = qwq.front(); qwq.pop();
        //cout << qaq << ' ' << fl[qaq] << '\n';
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].fl && dis[to] > dis[qaq] + ter[i].co)
            {
                dis[to] = dis[qaq] + ter[i].co, fl[to] = min(fl[qaq], ter[i].fl);
                pre[to] = i;
                if(!flag[to])
                    qwq.push(to), flag[to] = 1;
            }
        }
        flag[qaq] = 0;
    }
    return fl[t] > 0;
}

inline void change()
{
    ans += fl[t] * dis[t];
    //cout << fl[t] << ' ' << dis[t] << '\n';
    for(ri i = t; i; i = ter[pre[i] ^ 1].to)
        ter[pre[i]].fl -= fl[t], ter[pre[i] ^ 1].fl += fl[t];
}

int main()
{
    re(n), re(m); t = n + 3;
    memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
    {
        re(a[i]);
        if(a[i - 1] - a[i] > 0)
            build(0, i, 0, a[i - 1] - a[i]);
        else if(a[i - 1] - a[i] < 0)
            build(i, t, 0, a[i] - a[i - 1]);
        build(i, i + 1, 0, (lo)3e9 + 7);
    }
    build(0, n + 1, 0, a[n]);
    for(ri i = 1; i <= m; i ++)
        re(lx), re(ly), re(lz), build(ly + 1, lx, lz, (lo)3e9 + 7);
    while(spfa())
        change();
    printf("%lld", ans);
}