首页 > 其他分享 >2022.11.22 模拟赛小结

2022.11.22 模拟赛小结

时间：2022-12-02 21:26:11浏览次数：58  
标签：return 22 int void ret getchar 小结 2022.11 define

2022.11.22 模拟赛小结

目录

更好的阅读体验戳此进入

赛时思路

T1

给定序列区间查询区间内是否所有数字各不相同。

$ n, q \le 5 \times 10^5 $。

看完题就想到莫队了。。然后发现数据范围刚好卡莫队，根号过不去，不过一下子还是没想出来线段树写法，糊完莫队写完后面的回来对拍发现莫队寄了，调了十多分钟没调出来，又想了一下然后突然想到线段树怎么写了。

记录每个点的值上一次出现的位置，挂到线段树上，区间查询最大值，如果最大值小于 $ l $ 一定合法，反之不合法。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template < typename T = int >
inline T read(void);

int N, K;
int a[510000];
int lst[510000];

class SegTree{
private:
    int tr[510000 << 2];
    #define LS (p << 1)
    #define RS (LS | 1)
    #define MID ((gl + gr) >> 1)
public:
    void Pushup(int p){
        tr[p] = max(tr[LS], tr[RS]);
    }
    void Build(int p = 1, int gl = 1, int gr = N){
        if(gl == gr)return tr[p] = a[gl = gr], void();
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
        Pushup(p);
    }
    int Query(int l, int r, int p = 1, int gl = 1, int gr = N){
        if(l <= gl && gr <= r)return tr[p];
        if(gr < l || r < gl)return 0;
        return max(Query(l, r, LS, gl, MID), Query(l,r, RS, MID + 1, gr));
    }
}st;

int main(){
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
    N = read(), K = read();
    for(int i = 1; i <= N; ++i){
        int v = read();
        a[i] = lst[v];
        lst[v] = i;
    }st.Build();
    while(K--){
        int l = read(), r = read();
        printf("%s\n", st.Query(l, r) < l ? "Yes" : "No");
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

T2

给定序列 $ a_n $，求其中长度为 $ k $ 的上升子序列个数。

DP 比较好想，然后居然没想到用树状数组或者线段树优化。。最后加上一些玄学剪枝，最坏复杂度 $ O(n^2k) $，显然过不了，最后只拿了 $ 40\texttt{pts} $，题本身挺水的，没写过我这确实很 sb。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MOD (ll)(1e9 + 7)

template < typename T = int >
inline T read(void);

int N, K;
ll ans(0);
int a[11000];
ll dp[11000][110];
basic_string < int > nxt[11000];

int main(){
    freopen("B.in", "r", stdin);
    freopen("B.out", "w", stdout);
    N = read(), K = read();
    for(int i = 1; i <= N; ++i)a[i] = read();
    for(int i = 1; i <= N; ++i)
        for(int j = i + 1; j <= N; ++j)
            if(a[j] > a[i])nxt[i] += j;
    for(int i = 1; i <= N; ++i)dp[i][1] = 1;
    for(int i = 1; i <= N - 1; ++i)
        for(int j = 1; j <= K; ++j)
            for(auto nx : nxt[i])
                (dp[nx][j + 1] += dp[i][j]) %= MOD;
    for(int i = 1; i <= N; ++i)(ans += dp[i][K]) %= MOD;
    printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

T3

坐标系中从 $ (0, 0) $ 到 $ (n, m) $，每次只能向右或向上，同时存在 $ k $ 个障碍，求到达终点的方案数。

容斥 + exCRT + exLucas，奇怪题，暴力分和性质分拿到了，容斥部分想到了一大半吧，最后用 DP 容斥转移过程没想出来，最终也只拿了 $ 40\texttt{pts} $，寄。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;



template < typename T = int >
inline T read(void);

ll N, M, K, MOD;
bool blk[1100][1100];
bool inq[1100][1100];
int cnt[1100][1100];

ll ans(0);

void bfs(void){
    cnt[0][0] = 1;
    queue < pair < int, int > > unex;
    unex.push({0, 0});
    inq[0][0] = true;
    for(int i = 1; i <= N + M; ++i){
        queue < pair < int, int > > tmp;
        while(!unex.empty()){
            auto tp = unex.front(); inq[tp.first][tp.second] = false; unex.pop();
            int tx = tp.first + 0, ty = tp.second + 1;
            if(tx <= N && ty <= M && !blk[tx][ty]){
                (cnt[tx][ty] += cnt[tp.first][tp.second]) %= MOD;
                if(!inq[tx][ty])inq[tx][ty] = true, tmp.push({tx, ty});
            }
            tx = tp.first + 1, ty = tp.second + 0;
            if(tx <= N && ty <= M && !blk[tx][ty]){
                (cnt[tx][ty] += cnt[tp.first][tp.second]) %= MOD;
                if(!inq[tx][ty])inq[tx][ty] = true, tmp.push({tx, ty});
            }
        }while(!tmp.empty())unex.push(tmp.front()), tmp.pop();
    }printf("%lld\n", cnt[N][M] % MOD);
}

ll fact[1100000], inv[1100000];
ll qpow(ll a, ll b){
    ll ret(1), mul(a);
    while(b){
        if(b & 1)ret = ret * mul % MOD;
        b >>= 1;
        mul = mul * mul % MOD;
    }return ret;
}
void Init(void){
    fact[0] = 1;
    for(int i = 1; i < MOD; ++i)fact[i] = (fact[i - 1] * i) % MOD;
    inv[MOD - 1] = qpow(fact[MOD - 1], MOD - 2);
    for(int i = MOD - 2; i >= 0; --i)inv[i] = inv[i + 1] * (i + 1) % MOD;
}

ll GetMinC(int n, int m){
    if(n < m)return 0;
    return fact[n] * inv[m] % MOD * inv[n - m] % MOD;
}

ll Lucas(__int128_t n, __int128_t m){
    if(n < m)return 0;
    if(n <= MOD && m <= MOD)return GetMinC(n, m);
    return Lucas(n / MOD, m / MOD) * Lucas(n % MOD, m % MOD) % MOD;
}

int main(){
    freopen("C.in", "r", stdin);
    freopen("C.out", "w", stdout);
    N = read < ll >(), M = read < ll >(), K = read(), MOD = read();
    Init();
    if(!K){
        printf("%lld\n", Lucas((__int128_t)N + M, (__int128_t)N));
        // bfs();
    }else{
        // if(N <= 1000 && M <= 1000){
            for(int i = 1; i <= K; ++i){int x = read(), y = read(); blk[x][y] = true;}
            bfs();
        // }else{
            // (ans += Lucas((__int128_t)N + M, (__int128_t)N)) %= MOD;
            // for(int len = 1; len <= K; ++len){
            //     ans += Lucas((__int128_t))
            // }
        // }
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}



template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

T4

对树染色，要求相邻两点颜色不同，每个节点有一个序列表示可能被染的颜色，颜色共有 $ k $ 种，求合法染色方案数。

很 sb 的树形 DP，做过好几次类似题了，居然只糊了一个 $ O(n^2k) $ 的 DP，然后没对拍，还似乎写挂了，直接爆零。

稍微动点脑子基本就能想到不用 $ O(n^2k) $ 枚举，直接加上所有的减去颜色相同的即可 $ O(1) $。。。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MOD (ll)(1e9 + 7)

template < typename T = int >
inline T read(void);

struct Edge{
    Edge* nxt;
    int to;
    OPNEW;
}ed[11000];
ROPNEW(ed);
Edge* head[5100];

int N, K;
unordered_set < int > exist[5100];
ll dp[5100][5100];

void dfs(int p = 1, int fa = 0){
    for(auto i = head[p]; i; i = i->nxt)
        if(SON != fa)dfs(SON, p);
    if(!head[p]->nxt && p != 1)
        for(auto ex : exist[p])dp[p][ex] = 1;
    else{
        for(auto ex : exist[p])
            for(auto i = head[p]; i; i = i->nxt)
                if(SON != fa)
                    for(auto exs : exist[SON])
                        if(exs != ex)
                            (dp[p][ex] += dp[SON][exs]) %= MOD;
    }
}

int main(){
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
    N = read(), K = read();
    for(int i = 1; i <= N; ++i){
        int c = read();
        while(c--)exist[i].insert(read());
    }
    for(int i = 1; i <= N - 1; ++i){
        int s = read(), t = read();
        head[s] = new Edge{head[s], t};
        head[t] = new Edge{head[t], s};
    }dfs();
    ll ans(0);
    for(auto ex : exist[1])(ans += dp[1][ex]) %= MOD;
    printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

正解

T2

$ O(n^2k) $ 的 DP 十分显然，用树状数组优化一下转移即可。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MOD (ll)(1e9 + 7)

template < typename T = int >
inline T read(void);

int N, K;
ll ans(0);
int a[11000];
ll dp[11000][110];
basic_string < int > data;
// basic_string < int > nxt[11000];

class BIT{
private:
    int tr[11000];
public:
    int lowbit(int x){return x & -x;}
    void Modify(int x, int v = 1){while(x <= N)(tr[x] += v) %= MOD, x += lowbit(x);}
    ll Query(int x){ll ret(0); while(x)(ret += tr[x]) %= MOD, x -= lowbit(x); return ret;}
}bit[110];

int main(){
    freopen("B.in", "r", stdin);
    freopen("B.out", "w", stdout);
    N = read(), K = read();
    for(int i = 1; i <= N; ++i)a[i] = read(), data += a[i];
    sort(data.begin(), data.end());
    data.erase(unique(data.begin(), data.end()), data.end());
    for(int i = 1; i <= N; ++i)a[i] = distance(data.begin(), upper_bound(data.begin(), data.end(), a[i]));
    for(int i = 1; i <= N; ++i)dp[i][1] = 1;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= K; ++j)
            (dp[i][j] += bit[j - 1].Query(a[i] - 1)) %= MOD,
            bit[j].Modify(a[i], dp[i][j]);
    // for(int i = 1; i <= N; ++i)printf("dp[%d][%d] = %lld\n", i, K, dp[i][K]);
    for(int i = 1; i <= N; ++i)(ans += dp[i][K]) %= MOD;
    printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

T3

先把前面题补一补然后刷刷 exLucas 之类的再补这道题吧。。

Code

//TODO

T4

树形 DP，设 $ dp(i, j) $ 表示染完 $ i $ 子树，其根节点颜色为 $ j $ 的合法方案数，转移很显然，加上所有颜色和减去不合法的然后把所有子树乘起来即可。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MOD (ll)(1e9 + 7)

template < typename T = int >
inline T read(void);

struct Edge{
    Edge* nxt;
    int to;
    OPNEW;
}ed[11000];
ROPNEW(ed);
Edge* head[5100];

int N, K;
basic_string < int > exist[5100];
ll sum[5100];
ll dp[5100][5100];

void dfs(int p = 1, int fa = 0){
    for(auto i = head[p]; i; i = i->nxt)
        if(SON != fa)dfs(SON, p);
    if(!head[p]->nxt && p != 1)
        for(auto ex : exist[p])dp[p][ex] = 1, sum[p]++;
    else{
        for(auto ex : exist[p]){
            dp[p][ex] = 1;
            for(auto i = head[p]; i; i = i->nxt)
                if(SON != fa)
                    (dp[p][ex] *= (sum[SON] - dp[SON][ex] + MOD) % MOD) %= MOD;
            (sum[p] += dp[p][ex]) %= MOD;
        }
    }
}

int main(){
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
    N = read(), K = read();
    for(int i = 1; i <= N; ++i){
        int c = read();
        while(c--)exist[i] += read();
    }
    for(int i = 1; i <= N - 1; ++i){
        int s = read(), t = read();
        head[s] = new Edge{head[s], t};
        head[t] = new Edge{head[t], s};
    }dfs();
    // for(int i = 1; i <= N; ++i)printf("sum[%d] = %lld\n", i, sum[i]);
    printf("%lld\n", sum[1]);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_11_22 初稿

标签：return,22,int,void,ret,getchar,小结,2022.11,define
From： https://www.cnblogs.com/tsawke/p/16945635.html

相关文章

  • 2022.11.10 模拟赛小结
    2022.11.10模拟赛小结目录2022.11.10模拟赛小结更好的阅读体验戳此进入赛时思路T1CodeT2T3T4Code正解T2T3T4CodeUPD更好的阅读体验戳此进入赛时思路T1原题LG-P3970......
  • 2022-2023-1 20221421 《计算机基础与程序设计》第十四周学习总结
    作业信息班级链接：https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP作业要求：https://www.cnblogs.com/rocedu/p/9577842.html#WEEK14作业正文：2022-2023-120221312......
  • Ubuntu22.04安装CUDA深度学习环境&&cuda principle
    environment:neofetch&&uname-a|lolcatinstallnvidiaGPUdriver:sudoadd-apt-repositoryppa:graphics-drivers/ppa#加入官方ppa源sudoaptupdate#检查软件包......
  • day22 --> (AJAX、JSON)
    AJAX:概念：ASynchronousJavaScriptAndXMl 异步的JavaScript和XML1.异步和同步：客户端和服务器端相互通信的基础上  AJAX是一种无需重新加载整个页面的情况......
  • 2022.10.28 模拟赛小结
    2022.10.28模拟赛小结目录2022.10.28模拟赛小结更好的阅读体验戳此进入赛时思路T1CodeT2T3T4正解T1CodeT2T3T4UPD最惨的一场，基本所有题都挂了，最终得分$20\texttt{pts......
  • #yyds干货盘点#【愚公系列】2022年12月 微信小程序-项目篇(公交查询)-02周边站点-获取
    前言1.相关API逆地址解析：提供由经纬度到文字地址及相关位置信息的转换能力，广泛应用于物流、出行、O2O、社交等场景。服务响应速度快、稳定，支撑亿级调用。可以满足以下相......
  • 2022-2023-1 20221404 《计算机基础与程序设计》第十四周学习总结
    2022-2023-120221404《计算机基础与程序设计》第十四周学习总结作业信息班级链接（2022-2023-1-计算机基础与程序设计）作业要求（2022-2023-1计算机基础与程序设......
  • 2022年度总结
    目标NOIP20231d省选知识点全部学完并掌握省选争取E类CF1900，争取2100分析当前处境知识进度：提高内容已学完，已开始学习省选内容。学习状态：难度适中，但每周专项练......
  • CSP-S 2022 游记
    CSP-S2022游记目录CSP-S2022游记更好的阅读体验戳此进入Day-2022.10.28Day-2022.10.29Day-2022.10.30Day-2022.10.31UPD更好的阅读体验戳此进入Day-2022.......
  • Ubuntu22.04 Server安装
    本篇主要记录在OracleVmVirtualBox中安装Ubuntu22.04Server,并设置静态IP1.下载VirtualBox下载地址https://www.virtualbox.org/wiki/Downloadsubuntu下载地址ht......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99