首页 > 其他分享 >CSP-S模拟12

CSP-S模拟12

时间:2022-09-26 21:45:01浏览次数:79  
标签:ch int ll mex 12 maxn ans CSP 模拟

喜欢写博客的前提是得会改题……好难啊

如果明天能收到生日礼物,或者一句生日快乐的话,我会非常快乐的,并且祝福你rp++

 

A. 开挂

发现改变之后的得到的结果是唯一确定的,为了让答案尽量小,就要让移动结果尽量不平均。于是我想到了伪做法:找到结果序列并让初始序列与结果序列一一匹配,每次最大的匹配最小的。

但是正确的匹配方式应该是每个数找到最相近的,倒序循环只因为lower_bound对更大值造成了影响,可是匹配之前的序列不应该被影响过。

  //所以我的写法为什么不对呢?
    //先把相等的取出来大概没有问题,然后我似乎不能保证移动步数尽量不平均
    //因为我的取出顺序大概不是按照移动步数(差值)来找的
    //但是让最小值去匹配最大值为什么不是同一个意思?
    /*Answer:
    于是我们发现:虽然最大值和最小值可以一一对应,但是让每一个最小值都选择了最大的可填位置
    他不能保证最优因为在最小值匹配最大值的同时我也让最大值匹配了最小值
    可能让最大值无数可填,比如到了最大的这个数300000002它只剩下12了,于是不合法!
    所以它连正确都不能保证,更别说优了!!!!!!!
    */

除此之外,对2^64取模就相当于ull自然溢出,注意输出应该是%llu。

code


#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;
const int maxn = 1e6 + 3;
//const ll mod = (1ll << 64);

ll n, a[maxn], b[maxn], c[maxn], d[maxn], e[maxn], num;
ll ans;
set<ll> s;
set<ll>::iterator it;

inline ll read()
{
    ll 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;
}

int main()
{
    //freopen("sample_openhook6.in", "r", stdin);
    
    n = read();
    for(int i=1; i<=n; i++) 
    {
        a[i] = read();
    }
    for(int i=1; i<=n; i++) b[i] = read();
    sort(a+1, a+1+n);
    sort(b+1, b+1+n);
    ll Mx = 0;
    for(int i=1; i<=n; i++)
    {
        c[i] = max(c[i-1]+1, a[i]);
        s.insert(c[i]);
    }
    /*错误写法
    for(int i=1; i<=n; i++)
    {
        if(s.find(a[i]) != s.end()) s.erase(a[i]);
        else d[++num] = a[i];
    }
    for(int i=1; i<=num; i++)
    {
        ll t = *(--s.end());
        s.erase(t);
        e[i] = t - d[i];
        printf("pipei %llu -> %llu\n", d[i], t);
    }*/
    for(int i=n; i>=1; i--)
    {
        it = s.lower_bound(a[i]);
        ll t = (*it)-a[i];
        if(t != 0) e[++num] = t;
        //printf("pipei %llu -> %llu\n", a[i], t);
        s.erase(it);
    }
    sort(e+1, e+1+num);
    for(int i=num,j=1; i>=1; i--,j++)
    {
        ans += e[i]*b[j];
    }
    printf("%llu\n", ans);
    
    return 0;
}

 

B. 叁仟柒佰万

30pts 可以预处理任意子区间的mex(我用的是set),转移时枚举每一种mex,mex相同的可以相加。

code


#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;
const int maxn = 3003;
const ll mod = 1e9 + 7;

int T, n, a[maxn], maxlas, mex[maxn][maxn];
ll f[maxn][maxn], ans;
set<int> s;

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

inline void add(ll &x, ll y) {x = (x + y) % mod; }
inline bool checkSame()
{
    int pk = a[1];
    for(int i=2; i<=n; i++)
    {
        //printf("cmp : %d %d\n", pk, a[i]);
        if(a[i] != pk) return 0;
    }
    return 1;
}
inline bool checkIszero()
{
    for(int i=1; i<=n; i++)
    {
        if(!a[i]) return 0;
    }
    return 1;
}
inline 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 solveSame()
{
    ans = qpow(2, n-1);
    printf("%lld\n", ans);
}

int main()
{
    //freopen("sample_clods3.in", "r", stdin);
    
    T = read();
    while(T--)
    {
        n = read();
        for(int i=1; i<=n; i++) a[i] = read();
        /*for(int i=1; i<=n; i++)
        {
            printf("%d ", a[i]);
        }
        printf("\n");*/
        if(checkSame() || checkIszero())
        {
            //printf("exic!!!\n");
            solveSame(); continue;
        }
        //s.clear();
        for(int i=maxlas; i<=n; i++)
        {
            s.insert(i);
        }
        maxlas = max(maxlas, n);
        for(int i=1; i<=n; i++)
        {
            for(int j=i; j<=n; j++)
            {
                /*printf("qvjian: %d %d\n", i, j);
                for(int x : s)
                {
                    printf("%d ", x);
                }
                printf("\n");*/
                if(s.find(a[j]) != s.end()) s.erase(a[j]);
                mex[i][j] = *s.lower_bound(0);
                //printf("mex[%d][%d] = %d\n", i, j, mex[i][j]);
            }
            //if(a[i] <= n) s.insert(a[i]);
            for(int j=i; j<=n; j++)
            {
                if(a[j] <= n) s.insert(a[j]);
            }
        }
        //exit(0);
        memset(f, 0, sizeof(f));
        //f[0][0] = 1; f[1][mex[1][1]] = 1;
        for(int i=1; i<=n; i++)
        {
            f[i][mex[1][i]] = 1;
        }
        for(int j=0; j<=n; j++)
        {
            for(int i=1; i<=n; i++)
            {
                for(int k=1; k<i; k++)//以0分界的预处理过了
                {
                    //printf("cmp: mex[%d][%d] %d %d\n", k+1, i, mex[k+1][i], j);
                    if(mex[k+1][i] == j && f[k][j])
                    {
                        add(f[i][j], f[k][j]);
                        //printf("contain: f[%d][%d] = %lld\n", k, j, f[k][j]);
                        //printf("f[%d][%d] = %lld\n", i, j, f[i][j]);
                    }
                }
            }
        }
        ans = 0;
        for(int i=0; i<=n; i++)
        {
            add(ans, f[n][i]);
        }
        printf("%lld\n", ans);
    }
    
    return 0;
}

(然后正解说)发现mex在整个序列都没有出现过,所以mex一定是整个序列的mex,所以只有一种取值,但是关于合法性的判断当然不能用原来那种预处理的方式,可以用单调指针**

以下直接引用:

不过用一个tot吧a数组复制一遍似乎比较多余,所以Cat把它去掉了。sum[f-1]是当前dp值因为最后一段有了明显的界限只有一种情况,加成前缀和是为了给后面。

code


#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;
const int maxn = 37000002;
const ll mod = 1e9 + 7;

int T, n, a[maxn], mex, vis[maxn];
int f[maxn], ans;//懂了,不让开ll
set<int> s;

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

inline void add(int &x, ll y) {x = (x + y) % mod; }
inline bool checkSame()
{
    int pk = a[1];
    for(int i=2; i<=n; i++)
    {
        //printf("cmp : %d %d\n", pk, a[i]);
        if(a[i] != pk) return 0;
    }
    return 1;
}
inline bool checkIszero()
{
    for(int i=1; i<=n; i++)
    {
        if(!a[i]) return 0;
    }
    return 1;
}
inline 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 solveSame()
{
    ans = qpow(2, n-1);
    printf("%d\n", ans);
}

int main()
{
    //freopen("sample_clods4.in", "r", stdin);
    
    T = read();
    while(T--)
    {
        n = read(); mex = 0;
        if(n == 37000000)
        {
            int x = read(), y = read(); a[1] = 0; vis[0] = 1;
            for(int i=2; i<=n; i++)
            {
                a[i] = (a[i-1]*x+y+i)&262143;
                vis[a[i]] = 1;
            }
        }
        else for(int i=1; i<=n; i++) a[i] = read();
        for(int i=0; i<=n; i++) vis[i] = 0;
        for(int i=1; i<=n; i++)
        {
            //if(a[i] > n) continue;
            vis[a[i]] = 1;
            while(vis[mex]) mex++;//1.找到区间的mex
        }
        //mex一定是整个序列的mex,所以我不需要枚举mex!!
        //但问题是我依然需要子区间的mex,所以时间复杂度并不能降!!!
        //所以问题是怎么用指针来维护mex的合法性!
        if(mex == 0) {solveSame(); continue;}
        int pos = 1, meex = 0;
        for(int i=0; i<=mex; i++) vis[i] = 0;
        while(1)
        {
            //printf("cmp : %d %d\n", meex, mex);
            if(a[pos] < mex) 
            {
                if(!vis[a[pos]]) meex++;
                vis[a[pos]]++; 
            }
            if(meex == mex) break;
            pos++;
        }
        //printf("--pos = %d\n", pos);
        int from = pos;
        //while(pos < n) {pos++; num++; a[num] = a[pos];}
        //for(int i=1; i<=num; i++) printf("%d ", a[i]);
        //printf("\n");
        memset(f, 0, sizeof(f));
        for(int i=0; i<from; i++) f[i] = 1;
        f[from] = 2; int las = 1; //从1而不是from,表示区间起点,也就是上一个边界的下一个
        for(int i=from+1; i<=n; i++)
        {
            if(a[i] < mex) vis[a[i]]++;
            while(a[las] >= mex || vis[a[las]] > 1)
            {
                if(a[las] < mex) vis[a[las]]--; 
                las++;//That is为什么上文用的是起点
            }
            add(f[i], (ll)f[i-1]+f[las-1]);
            //printf("f[%d] = %lld\n", i, f[i]);
        }
        printf("%d\n", f[las-1]);
    }
    
    return 0;
}

 

C. 超级加倍

部分引用自Chen_jr:建立两棵笛卡尔树,一棵满足大根堆,一棵满足小根堆(但是建出来的不是二叉树),类比数组建立笛卡尔树按照权值顺序加的那种,建立的过程和kruskal重构树类似但是不一样,主要利用了笛卡尔树lca(u, v)为u,v间路径上的最值的性质,所以u,v合法的条件为一个树上u是v的祖先,另一棵树上v是u的祖先。

不过关于为什么这样建树就能保证这些性质,中间的原理还有待研究***

按其中一棵树的dfs序建立树状数组,在另一棵树上查询对应子树区间得到答案,把他加进BIT对其子树贡献。可以在树状数组上查到的点首先要满足在第二棵树上当祖先,因为值的加入按照一定的顺序,同时他在第一棵树上当儿子,因为加入的只有儿子。

code




#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e6 + 3;
const ll mod = 993244853;

int n, ntime, fa[maxn], dfn[maxn], out[maxn];
vector<int> e[maxn];
ll ans;

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[maxn];
    void update(int x, int val)
    {
        while(x <= n)
        {
            c[x] += val;
            x += (x&-x);
        }
    }
    int query(int l, int r)
    {
        int ans = 0; l--;
        while(r > l)
        {
            ans += c[r];
            r -= (r&-r);
        }
        while(l > r)
        {
            ans -= c[l];
            l -= (l&-l);
        }
        return ans;
    }
}t;
int find(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
struct node
{
    int next, to;
}a[maxn];
int head[maxn], len;
void add(int x, int y)
{
    a[++len].to = y; a[len].next = head[x]; 
    head[x] = len;
}
void dfs1(int u)
{
    dfn[u] = ++ntime;
    for(int i=head[u]; i; i=a[i].next) dfs1(a[i].to);
    out[u] = ntime;
}
void dfs2(int u)
{
    ans += t.query(dfn[u], out[u]); t.update(dfn[u], 1);
    for(int i=head[u]; i; i=a[i].next) dfs2(a[i].to);
    t.update(dfn[u], -1);
}

int main()
{
    //freopen("sample_charity2.in", "r", stdin);
    n = read();
    for(int i=1; i<=n; i++)
    {
        int x = read();
        if(x) 
        {
            e[i].push_back(x); e[x].push_back(i);
        }
    }
    for(int i=1; i<=n; i++) fa[i] = i;
    for(int i=2; i<=n; i++)
    {
        for(auto j : e[i])
        {
            if(j < i) add(i, find(j)), fa[fa[j]] = i;
        }
    }
    dfs1(n);
    len = 0;
    for(int i=1; i<=n; i++)
    {
        fa[i] = i; head[i] = 0;
    }
    for(int i=n-1; i>=1; i--)
    {
        for(auto j : e[i])
        {
            if(j > i) add(i, find(j)), fa[fa[j]] = i;
        }
    }
    dfs2(1);
    printf("%lld\n", ans);
    
    return 0;
}

 

D. 欢乐豆

emmm***并不十分透彻……魔改dij真是越来越高级了……我以后(没准明天)再跑回来好好更新??

code


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int long long
const int maxn = 1e5 + 3;
const ll mod = 993244853;
const ll inf = 1e18;

int n, m, mn = inf, mnid, ans, cnt, dis[maxn], stk[maxn], id[maxn], s[maxn], fa[maxn];
bool 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 node
{
    int pos, dat, can;
    bool friend operator < (node x, node y) 
    {
        return x.dat > y.dat;
    }
};
vector<pair<int, int> > v[maxn];
bool cmp(node x, node y) {return x.dat < y.dat;}
priority_queue<node> q;
int find(int x) {if(x == fa[x]) return x; return fa[x] = find(fa[x]);}
void New(int x) {if(id[x]) return; stk[++cnt] = x; id[x] = cnt;}
void insert(int x, int val)
{
    if(fa[x] != x) return; fa[x] = x + 1; dis[x] = val;
    q.push((node){x, dis[x]+s[stk[x]], true});
    for(auto it: v[x]) 
    {
        if(dis[it.first] > dis[x] + it.second)
        {
            q.push((node){it.first, dis[it.first]=dis[x]+it.second});
        }
    }
}
void solve(int fro)
{
    for(int i=1; i<=cnt+1; i++) dis[i] = inf, fa[i] = i;
    dis[fro] = 0; q.push((node){fro, 0, false});
    while(!q.empty())
    {
        node tmp = q.top(); int x = tmp.pos; q.pop();
        if(!tmp.can) {insert(x, tmp.dat); continue;}
        for(auto it : v[x]) vis[it.first] = 1;
        for(int i=find(1); i<=cnt; i=find(i+1))
        {
            if(!vis[i]) insert(i, tmp.dat);
        }
        for(auto it : v[x]) vis[it.first] = false;
    }
}
#undef int
int main()
{
    //freopen("sample_happybean2.in", "r", stdin);
    #define int long long
    n = read(); m = read();
    for(int i=1; i<=n; i++) s[i] = read();
    for(int i=1,x,y,val; i<=m; i++)
    {
        x = read(), y = read(), val = read(); New(x); New(y);
        v[id[x]].push_back(make_pair(id[y], val));
    }
    for(int i=1; i<=n; i++) 
    {
        if(!id[i] && s[i]<mn) mn = s[i], mnid = i;
    }
    if(mn != inf) New(mnid);
    for(int i=1; i<=n; i++) if(!id[i]) ans += (n-1)*s[i];
    for(int i=1; i<=cnt; i++)
    {
        int minn = inf; solve(i);
        for(int j=1; j<=cnt; j++) ans += dis[j], minn = min(minn, dis[j]+s[stk[j]]);
        ans += (n-cnt)*minn;
    }
    printf("%lld\n", ans);
    
    return 0;
}

标签:ch,int,ll,mex,12,maxn,ans,CSP,模拟
From: https://www.cnblogs.com/Catherine2006/p/16732613.html

相关文章

  • 42ed 2022/9/10&2021/9/17 纪中CSP.S组第一轮训练
    第一次(2022/9/10:陕西2020)得分70,不高不低,略有不足,因为还有一些题目的分能拿但没拿到,考试共进行了2h,原本应该是4h,仍然都能做完,还进行了两次检查首先是在选择题上,一道栽在......
  • 41st 2022/9/2 CSP前思想准备
    面临虽说上次过了第一轮,但是仍然很慌因为上次只是第一次过了第一轮,虽然有些把握,但却不是百分百怎么说呢,我不太相信自己第二轮会多烂,但是如果烂在了第一轮,那就真的是哑巴......
  • 40th 2022/8/17 模拟赛总结29
    这次能接受,因为T1是唯一能简单拿分的,但是我对状压DP的这一类,反而是最板子的题目不熟悉状压DP,需复习并进行简单提升其实今天是看出来了是状压,但就是打不出来,一直算空间时......
  • 38th 2022/8/13 模拟赛总结27
    这次哈!前一天我就不该喝咖啡的!但后悔也来不及了!!!睡很晚,这次再次让我体会到了睡眠的重要性痛苦,比赛时有力没法使,就很好,甚至还去拉虚脱了因为既着凉,又没精神,直接崩溃然后......
  • 37th 2022/8/12 模拟赛总结26
    这次真不可理喻这次T1是差分约束,这次,得完全弄懂T1,因为之前考过差分约束,但一直都不会,改了题后却没有印象,这次做出总结:就是一个将输入改为一条形同松弛原理的式子,如:\(X_i-X......
  • 39th 2022/8/16 模拟赛总结28
    这次又有人在D,真的烦,随便AK没什么意思的,尤其是赛后当然,不快归于耳后,先看自己这次不是很好,T2离正解只有1微米,DP的顺序错误,追悔莫及的是还在发呆,浪费了宝贵的时间然后......
  • CSP-S模拟11
    A.回文经典\(dp\),两边同时走,三维状态表示走了几步,左上出发走到哪行,右下出发走到哪行code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;......
  • 32nd 2022/8/5 模拟赛总结21
    这次问题所在是卡常,优化以及DP,和组合数嗯,还有如T3样子的DP,一脸懵逼,因为根本看不出来是DP,只觉得与组合数有些联系还有阔别已久的矩阵乘法,再次回归,需要复习,可以将前面的矩......
  • 35th 2022/8/9 模拟赛总结24
    这次可还行?又是发呆2h,然后亿脸懵逼,但是居然没有掉下去难道我的实力真的上来了?!!这一个暑假眼看就在机房中见到了尽头——8/17,然后作业也直接选择“鬼压床”,上来硬刚,规划......
  • 34th 2022/8/8 模拟赛总结23
    这次赛时不错,因为这次T1直接拿下,T3常数小也拿到了最高暴力然后T2大家都懵逼,T4也get到了暴力,于是——rk1只能说NB了当然还是戒骄戒躁,其实这次是真的不错,因为还有几个DJ......