过程

T1 Inverse

虽然想出了 $O(n^3k)$ 但可能因为常数太大被安排了。

T2 Subsequence

看到了一个很显然的规律然后打表验证但是并想不出来是为什么

然后打了一个只要看出规律谁都能打得出的 $O(n^2)$ 暴力

明明应该只有 20 多分却给了 40 分，是良心吗。

T3 Convex

不能在取模的意义下进行纯 abs 运算，因为无法分辨取模后哪个大哪个小。

除了这个我倒是想了个 $O(n^2)$ 做法。总而言之还是 GG。

Summary

全面 GG，垫底。
省选这样 = 完蛋。

更正

T1 Inverse

好像一开始那样的做法不行了。也就是说我不能这样计算 $i< j$ 的方案数然后再乘上什么东西。反正如果是这样的话就只能这么做。

初始化 $f_{i,j}=[p_i>p_j]$，代表没有做操作的序对 $(i,j)$ 产生贡献的概率。然后分三种情况转移。第四种情况下转移需要计算的是 $(l+r-j, l+r-i)$ 不产生贡献的概率，因为在第四种情况下两个序对的相对大小会进行互换。

然后之后加起来就行了。

题神仙，我蠢。

T2 Subsequence

题解写得挺好的，据说是套路，但代码细节不少。

最近打代码打蠢了，代码实现能力越来越不行了。

// Code by ajcxsu
// Problem: temp

#include<bits/stdc++.h>
typedef int _int;
#define int long long
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(), pl=0; x=0;
    while(!isdigit(ch)) pl=(ch=='-'), ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}

const int N=1e5+10;

struct Node *nil, *rt;
struct Node {
    Node *ch[2], *f;
    int v, s, c, sum, t;
    Node(int val=0) { f=ch[0]=ch[1]=nil; t=0, s=c=1; v=sum=val; }
    void upd() {
        s=c+ch[0]->s+ch[1]->s;
        sum=v+ch[0]->sum+ch[1]->sum;
    }
    bool nroot() { return f!=nil; }
    int dir() { return nroot()?f->ch[1]==this:-1; }
    void cac(int x) { t+=x, v+=c*x; sum+=x*s; }
    void pud() {
        if(!t) return;
        ch[0]->cac(t), ch[1]->cac(t);
        t=0;
    }
} ;
void ini() { nil=new Node; nil->ch[0]=nil->ch[1]=nil->f=nil, nil->s=nil->c=0; }

void rot(Node *x) {
    Node *y=x->f, *z=y->f;
    int d=x->dir();
    y->ch[d]=x->ch[!d];
    if(x->ch[!d]!=nil) x->ch[!d]->f=y;
    x->f=z;
    if(y->dir()!=-1) z->ch[y->dir()]=x;
    x->ch[!d]=y, y->f=x, y->upd();
}
void splay(Node *x, Node *f) {
    Node *y;
    while(x->f!=f) {
        y=x->f;
        if(y->f==f) rot(x);
        else if(y->dir()==x->dir()) rot(y), rot(x);
        else rot(x), rot(x);
    }
    x->upd();
    if(x->f==nil) rt=x;
}
Node* kth(Node *x, int k) {
    x->pud();
    if(k<=x->ch[0]->s) return kth(x->ch[0], k);
    else if(k<=x->ch[0]->s+x->c) return x;
    else return kth(x->ch[1], k-x->ch[0]->s-x->c);
}
void div(Node *x, int &ts, int a, int t=0, int s=0) {
    x->pud();
    if(x==nil) return;
    if(t+x->ch[0]->sum+(s+x->ch[0]->s)*a>t+x->ch[0]->sum+x->v)
        ts=s+x->ch[0]->s, div(x->ch[0], ts, a, t, s);
    else div(x->ch[1], ts, a, t+x->v+x->ch[0]->sum, s+1+x->ch[0]->s);
}
void ins(Node *x, Node *y, int val) {
    splay(x, nil);
    if(x->ch[1]==nil) {
        x->ch[1]=y, y->f=x, y->v+=val, x->upd();
        return;
    }
    splay(kth(x->ch[1], 1), x);
    x->ch[1]->ch[0]=y, y->f=x->ch[1], x->ch[1]->cac(val);
    x->upd();
}

int a[N];

bool t;
void dfs(Node *x, int to=0) {
    x->pud();
    if(x==nil) return;
    dfs(x->ch[0], to);
    if(!t) t=1;
    else printf("%lld ", to+x->v+x->ch[0]->sum);
    dfs(x->ch[1], to+x->ch[0]->sum+x->v);
}

_int main() {
    freopen("subsequence.in","r",stdin);
    freopen("subsequence.out","w",stdout);
    int n, na;
    gn(n), ini();
    rt=new Node(0);
    int ts;
    for(int i=1; i<=n; i++) {
        gn(na);
        ts=i;
        div(rt, ts, na);
        ins(kth(rt, ts), new Node(na*(ts-1)), na);
    }
    dfs(rt);
    return 0;
}

T3 Convex

本文链接：https://pst.iorinn.moe/archives/jzsim-3-4.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议进行许可☆

网站

加入讨论吧...