首页 > 其他分享 >csp模拟12[开挂，叁仟柒佰万, 超级加倍, 欢乐豆 ]

csp模拟12[开挂，叁仟柒佰万, 超级加倍, 欢乐豆 ]

时间：2022-09-28 11:23:10浏览次数：37  
标签：开挂 fr 12 int LL maxn 柒佰万 mex define

今日总结 : 卢本伟nb，我卢本伟没有开挂

T1 开挂

人类智慧题....可我不够智慧

  • 我们考虑最终答案的和一定是一个定值，因为如果我将最终的序列再加一个一的话，他还是合法的，但是它不优,所以一定是定值,那么我原来的和也是定值,所以我做差,那么我操作数就是定值,显然.
  • 那么根据排序不等式，我操作数越多的应该用最小的\(b\)值,所以我应该处理出所有操作数,排序和\(b\)对冲一下就行,当然,我填数应该是一条条包含的线段,不能是交叉，我要让最小的\(b\)配的最大,所以我显然应该包含,最小配最大,次小配次大...
  • 具体操作就用栈维护一下,不明白的可以模拟一下代码,不长
here 


#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x --)
#define delfr(x, y, z)for(Re x = y; x < z; x ++)
#define delfp(x, y, z)for(Re x = y; x > z; x --)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr(x, y) pair<x, y>
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define re(x) return x
#define sec second
#define fst first


using namespace std;
namespace kiritokazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template  <typename T> fuc(void, write)(T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10); putchar(x % 10 | '0');
    }
}

using namespace kiritokazuto;



const int maxn = 1e6 + 10;

const LL Inf = 0x7ffffffffffffff;
int n;
unsigned LL ans = 0;
unsigned LL a[maxn], b[maxn];
stack <int> stk;
int num[maxn], tot;
int tmp;
int top;
signed main() {
    n = read();
    fr(i, 1, n)a[i] = read();
    fr(i, 1, n)b[i] = read();
    sort(b + 1, b + n + 1);
    sort(a + 1, a + n + 1);
    a[n + 1] = 222222222222ull;
    fr(i, 1, n + 1) {
        if(a[i] != a[i - 1]) {
            while(tmp < a[i] && stk.size()) {
                num[++top] = tmp - stk.top();
                stk.pop();
                tmp++;
            }
            tmp = a[i] + 1;
        }else stk.push(a[i]);
    }
    sort(num + 1, num + 1 + top, greater<int>()) ;
    fr(i, 1, top){
        ans += b[i] * num[i];
    }
    write(ans);
    return 0;
}

T2 叁仟柒佰万

  • 又是一道十分智慧的 \(dp\) ,所以在它之后看到\(mex\)这玩意想的都是 \(dp\) ，然后我就寄了
  • 首先可以发现一个性质，一个合法区间的 \(mex\) 值一定是原序列的 \(mex\) 值
    • 我们考虑证明：
      • 因为对于一个区间来说，肯定它的 \(mex\) 不能大于原序列的 \(mex\)，这个比较显然
      • 那么如果有一个区间，他的 \(mex\) 小于我原序列的 \(mex\)，那么至少存在一个区间里是有我这个更小的 \(mex\) 的，那么这两个区间的 \(mex\) 就是不能相等的。所以他就寄了。
  • 然后考虑 \(dp\)， 我们设 \(dp_{i}\) 表示我\(1 \sim i\)区间里合法划分的方案数。
  • 对于暴力，我们显然是枚举 \(1 \sim i\) 里所以合法的 \(j\) (合法即\(j \sim i\)这一段的区间的 \(mex\) 值是我原序列的 \(mex\))暴力转移。
  • 但是考虑到一个性质，因为我的右端点单调右移，所以我的\(mex\)是只增不降的，所以我只有从右到左第一个满足 \(mex\) 的右端点的左边才有可能产生贡献,所以，我可以前缀和维护一下。这个题就过了。
here 


#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x --)
#define delfr(x, y, z)for(Re x = y; x < z; x ++)
#define delfp(x, y, z)for(Re x = y; x > z; x --)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr(x, y) pair<x, y>
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define re(x) return x
#define sec second
#define fst first


using namespace std;
namespace kiritokazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template  <typename T> fuc(void, write)(T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10); putchar(x % 10 | '0');
    }
}

using namespace kiritokazuto;



const int maxn = 4e7 + 10, maxm = 505, Mod = 1e9 + 7;
const LL Inf = 0x7ffffffffffffff;

int t;
int a[maxn];
int tp;
int dp[maxn];
int cnt[maxn];
int mex;
// mt19937 wmx(seed());
int n;
signed main() {
    tp = t = read();
    while(t --) {
        n = read();
        fr(i, 0, n)cnt[i] = 0;
     if( n < 37000000 ) fr(i, 1, n) a[i] = read(), cnt[a[i]] = 1;
     else {
      int x = read(), y = read();
      cnt[a[1] = 0] = 1;
            fr(i, 2, n) cnt[a[i] = (a[i - 1] * x + y + i) & 262143] = 1;
     }
        mex = 0;
        dp[0] = 1;
        while(cnt[mex])mex++;
        int j = 1, tmp = 0;
        fr(i, 0, n)cnt[i] = 0;
        fr(i, 1, n) {
            ++cnt[a[i]];
            while(cnt[tmp])++tmp;
            if(tmp == mex) {
                while((a[j] > mex || cnt[a[j]] > 1) && j < i)--cnt[a[j ++]];
                dp[i] = dp[j - 1] + dp[i - 1];//前缀和
                if(dp[i] >= Mod)dp[i] -= Mod;
            }else dp[i] = dp[i - 1];

        }
        write((dp[n] - dp[n - 1] + Mod) % Mod);
        ki;
    }
    return 0;
}

T3 超级加倍

笛卡尔树真神奇嘿嘿

  • 考虑建两颗树(都是有向的，因为有严格的父子关系)

    • 第一颗从根到叶子逐渐递减。
    • 第二颗从根到叶子逐渐递增。

  • 那么我满足条件的 \([x, y]\) 当且仅当 \(y\) 在第一颗树上是 \(x\) 的祖先， \(x\) 在第二颗树上是 \(y\) 的祖先。

  • 我们考虑怎样建树

    • 对于第一棵树，我们可以从 \(1 \sim n\) 枚举，对于每一个点去找 直接与他相连的比他小的点(注意原图是无向边)，如果有，就将我指向比我小的点(并查集上的)，同时合并一下并查集，将他们的爹换成我，这样就可以让之后的点链我了。
    • 对于第二颗树，则完全相反，从 \(n \sim 1\) 枚举，去找比我大的，同时合并并查集。

  • 对于样例
    image

    • 建第一颗树，我发现一直接相连三，比我大，跳过，二直接相连的都比它大，跳过，发现三，直接相连的二和一比我小，就将我指向一和二，同时合并并查集，之后发现四，连着二比我小，因为二此时并查集上的爹是三，所以我 四指向了三。以此类推可得一颗树
      image
    • 建造第二颗树就相反就行
      image

  • 有了这两颗树，我们可以考虑如何同时满足两对父子关系，我们可以在第一颗树上跑一边\(dfs\)并记录\(dfs\)序，然后在第二颗树上跑\(dfs\)的同时用\(BIT\)维护一下第一颗的\(dfs\)序，来了一个点就更新一下，然后查询答案就是查当前我在第一颗子树里有多少个一。

  • 因为我维护的是我第一颗树的\(dfs\)序，所以我能在树状数组上查到的点一定是我在第一颗树上的子树。又因为我是在用第二颗树更新，所以在我之前被设置成\(1\)的点一定是我在第二颗树上的祖先，所以就可以同时满足两对父子关系了。

here 


#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x --)
#define delfr(x, y, z)for(Re x = y; x < z; x ++)
#define delfp(x, y, z)for(Re x = y; x > z; x --)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr(x, y) pair<x, y>
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define re(x) return x
#define sec second
#define fst first


using namespace std;
namespace kiritokazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template  <typename T> fuc(void, write)(T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10); putchar(x % 10 | '0');
    }
}

using namespace kiritokazuto;
const int maxn = 2e6 + 10, maxm = 4e6 + 10;
#define int long long
int n;
struct Node {
    int next, to;
}wmx[maxm];
int head[maxn], len = 0;
int ans = 0;
int fa[maxn];
fuc(void, Qian)(int from, int to) {
    wmx[++len].next = head[from];
    wmx[len].to = to;
    head[from] = len;
}
int dfn[maxn], low[maxn];
/*
正手一个外挂秒杀，
反手一个超级加倍。
*/
int tim = 0;
struct BIT{
    int c[maxn];
    fuc(int, lowbit)(int x){return x & (-x);}
    fuc(void, add)(int x, int val){
        while(x <= n){
            c[x] += val;
            x += lowbit(x);
        }
    }
    fuc(int, ask)(int x) {
        int res = 0;
        while(x) {
            res += c[x];
            x -= lowbit(x);
        }
        return res;
    }
}T;


#define getsum(l, r) T.ask(r) - T.ask(l - 1)

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


fuc(void, dfs1)(int x){
    dfn[x] = ++tim;
    for(Re i = head[x]; i; i = wmx[i].next) {
        int to = wmx[i].to;
        dfs1(to);
    }
    low[x] = tim;
}
fuc(void, dfs2)(int x) {
    ans += getsum(dfn[x], low[x]);
    T.add(dfn[x], 1);
    for(Re i = head[x]; i ; i = wmx[i].next) {
        int to = wmx[i].to;
        dfs2(to);
    }
    T.add(dfn[x], -1);
}
vector<int> wmxx[maxn];
signed main() {
    n = read();
    fr(i, 1, n){
        int x = read();
        if(x != 0)wmxx[i].pb(x), wmxx[x].pb(i);
        fa[i] = i;
    }
    fr(i, 2, n) {
        for(auto j : wmxx[i]) {
            if(j < i)Qian(i, find(j)), fa[fa[j]] = i;
        }
    }
    dfs1(n);
    len = 0;
    fr(i, 1 ,n) {
        fa[i] = i;
        head[i] = 0;
    }
    fp(i, n - 1, 1) {
        for(auto j : wmxx[i]) {
            if(j > i)Qian(i, find(j)), fa[fa[j]] = i;
        }
    }
    dfs2(1);
    write(ans);
    re(0);
}

T4 欢乐豆

搞了我一下午的题,可算是弄明白了
注意,原图是有向图！！！！！！！！！！！！！！！！！！

  • 对于原来的完全图,显然我们可以分成两种部分
    • 边权被修改过的点
    • 边权没有被修改过的点
  • 对于第二种情况,我们显然可以直接统计答案\((n - 1) \times \sum a_{i}\)，因为我到其他点的距离都是相等的,并且我直接一步到是最优的,所以我除去我自己，对答案的贡献就是这些。
  • 那么处理完上边的点,我们现在就只剩\(2 \times m\)个点了(一条边连着两个)
  • 因为我们要的是所有点对的最短距离,所以显然我们得给这些点全跑一遍\(Dij\)，我们定义联通块是被修改过的边连的点所组成的图,这个联通块可能有好多,因为我不一定是连续修改的,我可以改了\(1 -> 2\)，改了\(2 -> 3\)然后就去改\(11 -> 12\)，那么显然他们是不联通的
  • 那么我们考虑一些况

    • 如果我们更新联通块里边的点,显然，有两种情况，一种是直接走联通块里边的点，另一种是如果我的一条边被更改的很大,显然我可以去联通块外一个点然后再回来是更优秀的，那么这样我们现在所保留的\(2 \times m\)是不够的,因为还需要一个外边的点,我们考虑保留一个怎样的点

      • 因为对于现在要跑\(Dij\)的点,它对于我联通块外的点的最短距离是相同的,它对于块外的点没被改过边,都是它的\(a_{u}\)，所以我只需要考虑一个点，让他回到联通块的距离最小,那么我走块外的距离就是最小的。
        image
      • 例如这个图,显然我应该从\(2\)那个点开始走\(4\)这条边更优秀

    • 如果我们更新联通块外边的点,那么显然也有两种情况

      • 直接走我的\(a_{u}\)边到它
      • 走我联通块里边的点,然后再通过那个点(假设这个点为\(j\))走出去
      • 那么我们可以为了压缩\(Dij\)的松弛时间,将优先队列里直接塞入\(dis[j] + a_{j}\)，这样我直接从优先队列里拿出来的第一个就是最优秀的松弛条件,那么一个点只需要被更新一次就\(ok\)了
  • 考虑松弛的过程
    image
    • 对于一个点的出边,他可以将\([1, n]\)分成若干段,对于端点处(\(v_{1}, v_{2}, v_{3}\))我可以直接用\(dis[u] + a_{1} / a_{2} / a_{3}\)来更新(因为我现在使用\(u\)更新,所以相对于它来说,最短距离就是这些,当然还会通过其他的去松弛,他是一层一层的类似)
    • 对于两个端点之间所夹着的地方(波浪线),显然是等价的,如果是用线段树来维护的话就可以直接区间修改了(维护最小值)。
    • 如果是并查集的话就只需要在每个点被更新后将他指向它加一的位置即可，因为每个点只被更新一次，下次就不用更新了，可以直接跳，所以并查集可以做到让你一直跳需要更改的点。
here 


#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x --)
#define delfr(x, y, z)for(Re x = y; x < z; x ++)
#define delfp(x, y, z)for(Re x = y; x > z; x --)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr(x, y) pair<x, y>
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define re(x) return x
#define sec second
#define fst first


using namespace std;
namespace kiritokazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template  <typename T> fuc(void, write)(T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10); putchar(x % 10 | '0');
    }
}

using namespace kiritokazuto;


const int maxn = 5e5 + 5, maxm = 6e5+ 5, Mod = 993244853;
const LL Inf = 0x7fffffffffff;
#define int long long
int n, m;
int a[maxn];
LL ans = 0;
LL dis[maxn];
int stk[maxn], id[maxn];
int is[maxn],cnt;
int Min = Inf;
int tmpid;
int vis[maxn];
vector <pr(int , LL) > wmx[maxm];
struct Node {
 int pos;LL data;bool type;//是否更新过了联通块外的点
 Node(){};
 Node(LL x, LL y, LL z){pos = x,  data = y, type = z;};
 friend bool operator < (Node A, Node B){return A.data > B.data;}
};
priority_queue <Node> q;
int fa[maxn];
fuc(int, find)(int x){return (x == fa[x]) ? x : fa[x] = find(fa[x]);}
fuc(void, insert)(int x, LL val){
 if(fa[x] != x)return;//已经更新过了
 dis[x] = val;
 fa[x] = x + 1;
 q.push(Node{x, dis[x] + a[stk[x]], 1});//可以进行松弛
 for(auto i : wmx[x])if(dis[x] + i.sec < dis[i.fst])q.push(Node{i.fst, dis[i.fst] = dis[x] + i.sec, 0});
}
fuc(void, Dij)(int x) {
 mes(dis, 0x3f);
 fr(i, 1, cnt)fa[i] = i;
 fa[cnt + 1] = cnt + 1;
 q.push(Node{x, dis[x] = 0, 0});
 while(!q.empty()) {
  auto tp = q.top();
  q.pop();
  if(!tp.type)insert(tp.pos, tp.data);
  else {
   for(auto i : wmx[tp.pos])vis[i.fst] = 1;
   for(Re i = find(1); i <= cnt; i = find(i + 1)) {
    if(!vis[i])insert(i, tp.data);
   }
   for(auto i : wmx[tp.pos])vis[i.fst] = 0;
  }
 }
}


signed main() {
 n = read(), m = read();
 fr(i, 1, n)a[i] = read();
 fr(i, 1, m) {
  int x = read(), y = read(), z = read();
  // stk[++cnt] = x;
  // id[x] = cnt;
  // stk[++cnt] = y;
  // id[y] = cnt;
  if( !id[x] ) id[ stk[++cnt] = x ] = cnt;
  if( !id[y] ) id[ stk[++cnt] = y ] = cnt;
  wmx[id[x]].pb(mk(id[y], z));
 }
 a[0] = Inf;
 fr(i, 1, n) {
  if(!id[i] && a[i] < Min) {
   Min = a[i];
   tmpid = i;
  }
 }
 if(Min != Inf)stk[++cnt] = tmpid, id[tmpid] = tmpid;
 fr(i, 1, n) if(!id[i])ans += (n - 1ll) * a[i];
 fr(i, 1, cnt) {
  Dij(i);
  Min = Inf;
  fr(j, 1, cnt) {
   ans += dis[j];
   Min = min(Min, dis[j] + a[stk[j]]);
  }
  ans += (n - cnt) * Min;
 }
 write(ans);
 return 0;
}

标签：开挂,fr,12,int,LL,maxn,柒佰万,mex,define
From： https://www.cnblogs.com/kiritokazuto/p/16734938.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99