NOIP模拟4

标签：ch NOIP int top mid maxn ans 模拟

当连续寄掉的时候真是没什么心情写博客……然而还是得记录一下……

开始怀疑自己的水平了……难道这才是Catherine的正常发挥？？……

承认自己菜但还不想承认自己菜到了这种地步……

马上就考试了一天天的炸心态玩儿……

错的：打算把题意转化成路径上最大值<=len并且pre<=dep[lca]，发现这个pre在修改的时候需要涉及整棵子树，并且还需要记录每个有可能成为pre的值，nxt可以省略因为nxt在范围内对于这个nxt一定有不合法的pre。

最后只有特判有分，2.5*1e5的数据范围让我开了个2e5的数组提交了好几次，把.5不知道扔哪去了……

正解是用随机权值hash一下。

code


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 5e5 + 2;

ull f[maxn], val[maxn], s[maxn];
int fa[maxn], dep[maxn], son[maxn], siz[maxn], rnk[maxn], top[maxn], dfn[maxn], ntime; 
int T, n, q;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct node 
{
    int next, to;
}a[maxn<<1];
int head[maxn], len;

void add(int x, int y)
{
    a[++len].to = y; a[len].next = head[x];
    head[x] = len;
}

struct seg 
{
    struct tree
    {
        ull sum;
    }t[maxn<<2];
    void pushup(int x)
    {
        t[x].sum = t[x<<1].sum + t[x<<1|1].sum;
        //printf("%d %d %d\n", x, x<<1, x<<1|1);
        //printf("%llu %llu %llu\n", t[x].sum, t[x<<1].sum, t[x<<1|1].sum);
    }
    void build(int x, int l, int r)
    {
        if(l == r)
        {
            t[x].sum = val[rnk[l]]; 
            //printf("t[%d].sum = %llu\n", x, t[x].sum);
            return;
        }
        int mid = (l + r) >> 1;
        build(x<<1, l, mid);
        build(x<<1|1, mid+1, r);
        pushup(x);
    }
    void update(int x, int l, int r, int pos, ull val)
    {
        if(l == r)
        {
            t[x].sum = val; 
            //printf("t[%d].sum = %llu\n", x, t[x].sum);
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) update(x<<1, l, mid, pos, val);
        else update(x<<1|1, mid+1, r, pos, val);
        pushup(x);
        //printf("t[%d].sum = %llu\n", x, t[x].sum);
    }
    ull query(int x, int l, int r, int L, int R)
    {
        if(L <= l && r <= R) return t[x].sum;
        int mid = (l + r) >> 1;
        ull ans = 0;
        if(L <= mid) ans += query(x<<1, l, mid, L, R);
        if(R > mid) ans += query(x<<1|1, mid+1, r, L, R);
        return ans;
    }
}t;

void find_heavy_edge(int u, int fat, int depth)
{
    fa[u] = fat;
    dep[u] = depth;
    son[u] = 0;
    siz[u] = 1;
    int maxsize = 0;
    for(int i=head[u]; i; i=a[i].next)
    {
        int v = a[i].to;
        if(v == fat) continue;
        find_heavy_edge(v, u, depth+1);
        siz[u] += siz[v];
        if(siz[v] > maxsize)
        {
            maxsize = siz[v];
            son[u] = v;
        }
    }
}

void connect_heavy_edge(int u, int ancestor)
{
    top[u] = ancestor;
    dfn[u] = ++ntime;
    rnk[ntime] = u;
    if(son[u])
    {
        connect_heavy_edge(son[u], ancestor);
    }
    for(int i=head[u]; i; i=a[i].next)
    {
        int v = a[i].to;
        if(v == fa[u] || v == son[u]) continue;
        connect_heavy_edge(v, v);
    }
}

int LCA(int x, int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    return x;
}

ull get_ans(int x, int y)
{
    ull ans = 0;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += t.query(1, 1, n, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    ans += t.query(1, 1, n, dfn[x], dfn[y]);
    return ans;
}

void solve()
{
    n = read(), q = read();
    memset(head, 0, sizeof(head)); len = 0;
    ntime = 0;
    for(int i=1; i<=n; i++) f[i] = rand();
    for(int i=1; i<=n; i++) 
    {
        int x = read(); val[i] = f[x];
    }
    for(int i=1; i<=n; i++) s[i] = s[i-1] + f[i];
    for(int i=1; i<n; i++)
    {
        int u = read(), v = read();
        add(u, v); add(v, u);
    }
    find_heavy_edge(1, 1, 1);
    connect_heavy_edge(1, 1);
    t.build(1, 1, n);
    while(q--)
    {
        int opt = read();
        if(opt == 1)
        {
            int x = read(), y = read();
            int lca = LCA(x, y), len = dep[x]-dep[lca]+dep[y]-dep[lca]+1;
            if(get_ans(x, y) == s[len]) printf("Yes\n");
            else printf("No\n");
        }
        else 
        {
            int x = read(), v = read();
            t.update(1, 1, n, dfn[x], f[v]);
        }
    }
}

int main()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    
    T = read();
    while(T--)
    {
        solve();
    }

    return 0;
}

大原题这次我终于没有错题重错。

code

 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 2;
const int mod = 1e9 + 7;

typedef pair<int, int> pii;
map<pii, int> mp;
int n, m, ans[maxn], fa[maxn], siz[maxn];
ll now = 1;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

ll qpow(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

struct edge 
{
    int u, v, l, r;
}e[maxn];
int cnt;

struct Stack
{
    int u, v, tim;
}st[maxn];
int top;

int find(int x) {return fa[x] == x ? x : find(fa[x]);}

struct seg 
{
    vector<int> t[maxn<<2];
    void update(int x, int l, int r, int L, int R, int id)
    {
        if(L <= l && r <= R)
        {
            t[x].push_back(id); return;
        }
        int mid = (l + r) >> 1;
        if(L <= mid) update(x<<1, l, mid, L, R, id);
        if(R > mid) update(x<<1|1, mid+1, r, L, R, id);
    }
    void addedge(int x)
    {
        for(int i : t[x])
        {
            int u = find(e[i].u), v = find(e[i].v);
            if(u == v) continue;
            if(siz[u] < siz[v]) swap(u, v);
            now = now * qpow(siz[v], mod-2) % mod * qpow(siz[u], mod-2) % mod;
            fa[v] = u; siz[u] += siz[v];
            now = now * siz[u] % mod;
            st[++top].tim = x; 
            st[top].u = u; st[top].v = v;
        }
    }
    void del(int x)
    {
        while(st[top].tim == x)
        {
            int u = st[top].u, v = st[top].v;
            fa[v] = v; 
            now = now * qpow(siz[u], mod-2) % mod;
            siz[u] -= siz[v];
            now = now * siz[u] % mod * siz[v] % mod;
            top--;
        }
    }
    void query(int x, int l, int r)
    {
        addedge(x);
        if(l == r)
        {
            ans[l] = now; del(x);
            return;
        }
        int mid = (l + r) >> 1;
        query(x<<1, l, mid);
        query(x<<1|1, mid+1, r);
        del(x);
    }
}t;

int main()
{
    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);
    
    n = read(), m = read();
    for(int i=1; i<=n; i++) fa[i] = i, siz[i] = 1;
    for(int i=1; i<=m; i++)
    {
        int opt = read();
        if(opt == 1)
        {
            int u = read(), v = read();
            if(u > v) swap(u, v);
            e[++cnt] = {u, v, i, m};
            mp[pii(u, v)] = cnt;
        }
        else 
        {
            int u = read(), v = read();
            if(u > v) swap(u, v);
            int id = mp[pii(u, v)];
            e[id].r = i-1;
        }
    }
    for(int i=1; i<=cnt; i++)
    {
        t.update(1, 1, m, e[i].l, e[i].r, i);
    }
    t.query(1, 1, m);
    for(int i=1; i<=m; i++)
    {
        printf("%d\n", ans[i]);
    }

    return 0;
}

闲话：

找合法的数对数量让我看成了上升子序列的个数，上次那个“序理想”和差分优化dp让人印象...好吧也不是那么深刻，差点就想开始dp了是方程忘干净了阻止了我，那题根本就不是三维偏序，然后奇奇妙妙的是我居然由求上升子序列个数想到了cdq分治并且真的写了个cdq分治并且还成功地用归并排序优化了一下，并且依然以为自己求的是上升子序列！？！！！

害怕cdq分治会写错所以拿二维树状数组写的小数据，并且依然以为自己求的是上升子序列！？！！！

不会生成数据手造数据并且通过拆分终端“对拍”了一下认为很没问题没有发现忘了取模。

正解:

把三维偏序两两分组拆成二维的计算偏序对数量，偏序关系指的是相对大小关系相同，任意选出两个[结构体]要么有两个数是偏序关系会被统计1次，要么是三个会被统计3次。

如果有-1的话，合法值的个数/空缺个数是每一个位置合法的概率，有大于和小于两种情况，现在只考虑了数字和数字、数字个-1之间的个数，-1和-1单独算所有的-1对数/2，每一对有1/2的概率合法，拆成的三组偏序对中涉及-1的有两组，再*2，就是-1之间配对的总数。

code

 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 2;
const int mod = 998244353;
const int inv2 = 499122177;

int n, p[12], q[12], tot, invt;
ll ans;
int vum, vef[12], lef[12], num, vis[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct BIT 
{
    int c[12][12];
    inline int lowbit(int x) {return x & -x;}
    void add(int x, int y)
    {
        for(int i=x; i<=n; i+=lowbit(i))
        {
            for(int j=y; j<=n; j+=lowbit(j))
            {
                c[i][j]++;
            }
        }
    }
    int query(int x, int y)
    {
        int ans = 0;
        for(int i=x; i; i-=lowbit(i))
        {
            for(int j=y; j; j-=lowbit(j))
            {
                ans += c[i][j];
            }
        }
        return ans;
    }
}t;

ll jc(int n)
{
    ll ans = 1;
    for(int i=2; i<=n; i++)
    {
        ans = ans * i % mod;
    }
    return ans;
}

ll qpow(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

void solve1()
{
    for(int i=1; i<=n; i++) p[i] = read();
    for(int i=1; i<=n; i++) q[i] = read();
    for(int i=1; i<=n; i++)
    {
        if(q[i] == -1) lef[++num] = i;
        else vis[q[i]] = 1;
    }
    for(int i=1; i<=n; i++)
    {
        if(!vis[i]) vef[++vum] = i;
    }
    do 
    {
        for(int i=1; i<=num; i++)
        {
            int id = lef[i];
            q[id] = vef[i];
        }
        memset(t.c, 0, sizeof(t.c));
        for(int i=1; i<=n; i++)
        {
            if(p[i]-1 && q[i]-1) ans = (ans + t.query(p[i]-1, q[i]-1)) % mod;
            t.add(p[i], q[i]);
        }
    }while(next_permutation(vef+1, vef+1+vum));
    ans = ans * qpow(jc(num), mod-2) % mod;
    printf("%lld\n", ans);
    exit(0);
}

struct node 
{
    int p, q;
    bool operator < (const node &T) const 
    {
        return p < T.p;
    }
}e[maxn], tmp[maxn];

int c[maxn];
void add(int x, int v)
{
    while(x <= n)
    {
        c[x] += v;
        x += (x & -x);
    }
}
int query(int x)
{
    int ans = 0;
    while(x)
    {
        ans += c[x];
        x -= (x & -x);
    }
    return ans;
}

void cdq(int l, int r)
{
    if(l == r) return;
    int mid = (l + r) >> 1;
    cdq(l, mid); cdq(mid+1, r);
    int k = l-1, i=mid+1, j=l;
    for(i=mid+1,j=l; i<=r; i++)
    {
        while(j <= mid && e[j].p < e[i].p)
        {
            tmp[++k] = e[j]; add(e[j].q, 1);
            j++;
        }
        tmp[++k] = e[i];
        ans += query(e[i].q);
        ans %= mod;
    }
    for(int o=l; o<j; o++) add(e[o].q, -1);
    while(i <= r) tmp[++k] = e[i], i++;
    while(j <= mid) tmp[++k] = e[j], j++;
    for(int i=l; i<=r; i++) e[i] = tmp[i];
}

void solve2()
{
    cdq(1, n);
    printf("%lld\n", ans);
    exit(0);
}

void CDQ(int l, int r)
{
    if(l == r) return;
    int mid = (l + r) >> 1;
    CDQ(l, mid); CDQ(mid+1, r);
    int i = mid+1, j = l, k = l-1;
    for(i=mid+1; i<=r; i++)
    {
        while(j <= mid && e[j].p < e[i].p) 
        {
            if(e[j].q > 0) add(e[j].q, 1);
            tmp[++k] = e[j]; j++;
        }
        if(e[i].q > 0) ans = (ans + query(e[i].q)) % mod;
        tmp[++k] = e[i];
    }
    for(int o=l; o<j; o++) if(e[o].q > 0) add(e[o].q, -1);
    while(i <= r) tmp[++k] = e[i], i++;
    while(j <= mid) tmp[++k] = e[j], j++;
    for(int i=mid+1,j=l,cnt=0; i<=r; i++)
    {
        while(j <= mid && e[j].p < e[i].p) cnt += (e[j].q == -1), j++;
        if(e[i].q != -1) ans += 1ll*(e[i].q-vis[e[i].q])*invt%mod*cnt%mod;
        else ans += 1ll*cnt*inv2%mod;
        ans %= mod;
    }
    for(int i=mid,j=r,cnt=0; i>=l; i--)
    {
        while(j >= mid+1 && e[j].p > e[i].p) cnt += (e[j].q == -1), j--;
        if(e[i].q != -1) ans += 1ll*(tot-e[i].q+vis[e[i].q])*invt%mod*cnt%mod;
        ans %= mod;
    }
    for(int i=l; i<=r; i++) e[i] = tmp[i];
}

void solve3()
{
    for(int i=1; i<=n; i++) e[i].p = read();
    for(int i=1; i<=n; i++)
    {
        e[i].q = read();
        if(e[i].q > 0) vis[e[i].q] = 1;
    }
    for(int i=1; i<=n; i++) vis[i] += vis[i-1];
    tot = n - vis[n]; invt = qpow(tot, mod-2);
    for(int i=1; i<=n; i++)
    {
        ans = (ans + query(e[i].p)) % mod;
        add(e[i].p, 1);
    }
    for(int i=1; i<=n; i++) c[i] = 0;
    int cnt = 0;
    for(int i=1; i<=n; i++)
    {
        if(e[i].q == -1) {cnt++; continue;}
        ans = (ans + query(e[i].q)) % mod;
        add(e[i].q, 1);
        ans = (ans+1ll*(e[i].q-vis[e[i].q])*invt%mod*cnt%mod)%mod;
        ans = (ans+1ll*(tot-e[i].q+vis[e[i].q])*invt%mod*(tot-cnt)%mod)%mod;
    }
    for(int i=1; i<=n; i++) c[i] = 0;
    sort(e+1, e+1+n); cnt = 0;
    for(int i=1; i<=n; i++)
    {
        if(e[i].q == -1) {cnt++; continue;}
        ans = (ans + query(e[i].q)) % mod;
        add(e[i].q, 1);
        ans = (ans+1ll*(e[i].q-vis[e[i].q])*invt%mod*cnt%mod)%mod;
        ans = (ans+1ll*(tot-e[i].q+vis[e[i].q])*invt%mod*(tot-cnt)%mod)%mod;
    }
    ans = (ans+1ll*tot*(tot-1)%mod*inv2%mod)%mod;
    ans = (ans-1ll*n*(n-1)%mod*inv2%mod+mod)%mod*inv2%mod;
    printf("%lld\n", ans);
    exit(0);
}

int main()
{
    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout);
    
    n = read(); 
    solve3(); bool sp = 1;
    if(n <= 10) solve1();
    for(int i=1; i<=n; i++) e[i].p = read();
    for(int i=1; i<=n; i++) 
    {
        e[i].q = read();
        if(e[i].q == -1) sp = 0;
    }
    if(sp) solve2();
    for(int i=1; i<=n; i++) if(e[i].q > 0) vis[e[i].q] = 1;
    for(int i=1; i<=n; i++) vis[i] += vis[i-1];
    tot = n - vis[n]; invt = qpow(tot, mod-2);
    CDQ(1, n);
    printf("%lld\n", ans);

    return 0;
}

cdq也可以过，假设把-1填成一个q算概率，分为左边序列的-1和右边序列的-1，-1和-1的只需要加一次。

以上代码中把solve3(鹤自SoyTony)去掉就是cdq，鹤自Chen_jr。

%%%APJifengc 讲题讲得非常清楚然而Cat依然不会实现……

对于一方想让结果最大另一方想让结果最小的最优决策不好确定的博弈论的题，可以二分处理。

剩下的->引流1 引流2

鹤了code连总结都想鹤的Cat现在真想批判一下自己……

code

 //鹤了……
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 2;

int n, t, s, fa[maxn], deg[maxn], sufdeg[maxn], f[maxn], cnt;
vector<int> g[maxn], vec;
bool in[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

void dfs(int u)
{
    int mx = 0, cmx = 0;
    for(int v : g[u])
    {
        if(v == fa[u]) continue;
        fa[v] = u;
        dfs(v);
        if(f[v] > mx) {cmx = mx; mx = f[v];}
        else cmx = max(cmx, f[v]);
    }
    f[u] = cmx + deg[u] - 1;
}

bool check(int mid)
{
    int res = 0, sum = 0, now = 0;
    for(int u : vec)
    {
        res++; now++;
        int las = sum;
        for(int v : g[u]) if(!in[v])
        {
            if(f[v] + sufdeg[now] > mid - las)
            {
                if(res <= 0) return 0;
                res--; sum++;
            }
        }
    }
    return sum <= mid;
}

int main()
{
    freopen("d.in", "r", stdin);
    freopen("d.out", "w", stdout);
    
    n = read(); t = read(); s = read();
    for(int i=1; i<n; i++)
    {
        int u = read(), v = read();
        g[u].push_back(v); g[v].push_back(u);
        deg[u]++; deg[v]++;
    }
    dfs(s);
    in[t] = 1; int u = t;
    while(fa[u])
    {
        u = fa[u]; in[u] = 1;
        vec.push_back(u);
    }
    reverse(vec.begin(), vec.end());//把reverse都给鹤丢了……
    for(int x : vec) sufdeg[++cnt] = deg[x] - 2;
    for(int i=cnt; i>=1; i--) sufdeg[i] += sufdeg[i+1];
    sufdeg[1]++;
    int l = 0, r = n + n;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l);

    return 0;
}

标签：ch,NOIP,int,top,mid,maxn,ans,模拟
From： https://www.cnblogs.com/Catherine2006/p/16897466.html

A. 树上排列

B. 连任

C. 排列

D. 追逐

相关文章

赞助商

阅读排行