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

2022.10.21 模拟赛小结

时间：2022-10-24 08:23:50浏览次数：78  
标签：return 21 int 2022.10 void ret getchar 小结 define

2022.10.21 模拟赛小结

目录

sssmzy AK 了，zpair 差一点 AK 了，我寄了。

一套难得的难度略低于 NOIP 的阳间模拟赛

虽然还是寄了

更好的阅读体验戳此进入

赛时思路

T1

有 $ f(x) = \lfloor \sqrt[4]{x} + \dfrac{1}{2} \rfloor \(，\) T $ 组询问，给定 $ n $，求 $ \sum_{i = 1}^n = \dfrac{1}{f(i)} $。强制在线。

原题 LG-P8574 「DTOI-2」星之影。

难得切掉的一道水题。

第一眼值域分块，然后发现不是，于是考虑对于 $ f(x) $ 显然取值是一段一段的，且段长递增，于是我们维护一下每一段的初始值，然后做个前缀和，考虑好加 $ 1 $ 减 $ 1 $ 的边界，每次询问 lower_bound $ O(\log n) $ 查询一下即可。题解里也有 $ 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;
// using namespace __gnu_pbds;

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

char buf_ans[114];
ll next_n(double last_ans=0,ll get_n=0){//last_ans<n<=1e18
sprintf(buf_ans,"%.6f",last_ans);
for(ll i=0,x=0;;i++){if(buf_ans[i]=='.')return get_n^x;if(i&1)x*=10;
else x=x*10+(buf_ans[i]^48);}}

const int mx = 34900;
ll blk[40000];
ll sum[40000];
double lans(0.0);

int main(){
    freopen("function.in", "r", stdin);
    freopen("function.out", "w", stdout);
    int T = read();
    blk[1] = 1; sum[1] = 5.0;
    for(int i = 1; i <= 35000; ++i)
        blk[i + 1] = (ll)ceil(powl((ld)i + 0.5, 4));
    for(int i = 1; i <= 34990; ++i)
        sum[i + 1] = sum[i] + (ld)1.0 / (ld)(i + 1) * (ld)(blk[i + 2] - blk[i + 1]);
    // for(int i = 1; i <= 100; ++i){
    //     printf("%lld : %lld\n", blk[i], sum[i]);
    // }
    while(T--){
        ll n = read<ll>();
        n = next_n(lans, n);
        // printf("%lld\n", n);
        int dist = lower_bound(blk + 1, blk + mx + 1, n) - blk;
        // printf("dis:%d\n", dist);
        // dist -= blk[dist] == n ? 1 : 2;
        --dist;
        // printf("new dis:%d\n", dist);
        // if(n == 89)printf("val: %lld + %.6Lf / %.6Lf\n", sum[dist - 1], (ld)(n - blk[dist] + 1), (ld)dist);
        ld ans = n == blk[dist + 1]
            ? (sum[dist] + (ld)(n - blk[dist + 1] + 1) / (ld)(dist + 1))
            : (sum[dist - 1] + (ld)(n - blk[dist] + 1) / (ld)dist);
        printf("%.6Lf\n", ans);
        lans = (double)ans;
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}



template<typename T>
inline T read(void){
    T ret(0);
    short 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

给定 $ n $ 个点以 $ 1 $ 为根的树，初始所有节点权值为 $ 0 \(，\) q $ 个操作或询问，操作为给定 $ v, x, k $，对 $ v $ 及其子树，记节点与 $ v $ 的距离为 $ dis $，则对每个节点的权值加上 $ x - dis \times k $，询问为给定 $ v $ 输出 $ v $ 的权值。

原题 CF396C On Changing Tree。

又把 10.19 口糊的那个通过 bfs 序转称序列上然后套线段树的塞上去了，大概可以认为是暴力 + 大剪枝，树越扁剪枝越大，树是链的话就退化成暴力。

本来应该能拿到一些分的，然后线段树的 query 忘了取模了，直接全寄爆零。

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;
// using namespace __gnu_pbds;

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 (1000000007)

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

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

int N, Q;
int idx[310000], ridx[310000];
int dsl[310000], dsr[310000];

void bfs(void){
    int cnt(0);
    queue < pair < int, int >/*vertex, father*/ > q;
    q.push({1, 0});
    while(!q.empty()){
        auto p = q.front(); q.pop();
        idx[p.first] = ++cnt;
        ridx[cnt] = p.first;
        vector < pair < int, int > > tmp;
        for(auto i = head[p.first]; i; i = i->nxt)
            if(SON != p.second)
                q.push({SON, p.first});
        if(!dsl[idx[p.second]])dsl[idx[p.second]] = dsr[idx[p.second]] = idx[p.first];
        else dsr[idx[p.second]] = idx[p.first];
    }
}

class SegTree{
private:
    ll st[310000 << 2];
    ll lz[310000 << 2];
    #define LS (p << 1)
    #define RS ((p << 1) + 1)
    #define MID ((gl + gr) >> 1)
public:
    // void Pushup(int p){st[p] = st[LS] + st[RS];}
    void Pushdown(int p){
        st[LS] = (st[LS] + lz[p]) % MOD, st[RS] = (st[RS] + lz[p]) % MOD;
        lz[LS] = (lz[LS] + lz[p]) % MOD, lz[RS] = (lz[RS] + lz[p]) % MOD;
        lz[p] = 0;
    }
    void Modify(int l, int r, ll val, int p = 1, int gl = 1, int gr = N){
        if(l <= gl && gr <= r)return st[p] = (st[p] + val) % MOD, lz[p] = (lz[p] + val) % MOD, void();
        Pushdown(p);
        if(l <= MID)Modify(l, r, val, LS, gl, MID);
        if(MID + 1 <= r)Modify(l, r, val, RS, MID + 1, gr);
    }
    ll Query(int idx, int p = 1, int gl = 1, int gr = N){
        if(gl == gr)return st[p];
        Pushdown(p);
        if(idx <= MID)return Query(idx, LS, gl, MID);
        else return Query(idx, RS, MID + 1, gr);
    }
}st;

void Mdf(int p, ll val, int k){
    int l(p), r(p), dis(0);
    st.Modify(l, r, (val - (ll)dis * k + MOD) % MOD);
    while(true){
        ++dis;
        while(!dsl[l] && l <= r)++l;
        while(!dsr[r] && l <= r)--r;
        if(l > r)return;
        l = dsl[l], r = dsr[r];
        st.Modify(l, r, (val - (ll)dis * k + MOD) % MOD);
    }
}

int main(){
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    N = read();
    for(int i = 2; i <= N; ++i){
        int fa = read();
        head[i] = new Edge{head[i], fa};
        head[fa] = new Edge{head[fa], i};
    }bfs();
    Q = read();
    while(Q--){
        int opt = read();
        if(opt == 1){
            int v = read(), x = read(), k = read();
            Mdf(idx[v], (ll)x, k);
        }else{
            int v = read();
            printf("%lld\n", (st.Query(idx[v]) + MOD) % MOD);
        }
    }

    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}



template<typename T>
inline T read(void){
    T ret(0);
    short 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

给定序列 $ a_n $，保证 $ 1 \le a_i \le 8 $，求一个最长子序列满足：1. $ \left[ 1, 8 \right] $ 任意两个整数出现次数之差不大于 $ 1 $。2. 每种数字必须连续出现。

原题 CF743E Vladik and cards。

没想出来，暴力 $ 10\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;
// using namespace __gnu_pbds;

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;
int arr[1100];
vector < int > cur;
int ans(0);

bool Check(void){
    int len[10];
    memset(len, 0, sizeof len);
    int lst(-1);
    for(auto i : cur){
        if(i == lst)++len[i];
        else if(len[i]++)return false;
    }
    int mn(INT_MAX), mx(INT_MIN);
    for(int i = 1; i <= 8; ++i)mn = min(mn, len[i]), mx = max(mx, len[i]);
    return mx - mn <= 1;
}

void dfs(int dep){
    if(dep > N){
        if(Check())ans = max(ans, (int)cur.size());
        return;
    }
    cur.emplace_back(arr[dep]);
    dfs(dep + 1);
    cur.pop_back();
    dfs(dep + 1);
}

int main(){
    freopen("card.in", "r", stdin);
    freopen("card.out", "w", stdout);
    N = read();
    for(int i = 1; i <= N; ++i)arr[i] = read();
    if(N <= 25)dfs(1), printf("%d\n", ans), exit(0);
    // while((double)clock() / CLOCKS_PER_SEC <= 0.95){
    //     int siz = rndd(1, N);
    //     for(int i = 1; i <= N; ++i){

        
    // }
    printf("%d\n", rndd(1, N));


    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}



template<typename T>
inline T read(void){
    T ret(0);
    short 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

原题 CF1051F The Shortest Statement。

寄了，写的暴力也挂了。

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;
// using namespace __gnu_pbds;

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, M;
int Q;
int lca[110000];
int dep[110000];
pair < int, int > ask[110000];
ll ans[110000];
pair < int, int /*vertex, val*/ > ffa[110000];

struct Edge{
    Edge* nxt;
    int to;
    int val;
    OPNEW;
}ed[310000];
ROPNEW(ed);
Edge* head[110000];

namespace Tree{
    vector < pair < int, int > /*vertex, query_idx*/ > query[110000];
    bool vis[110000];
    class UnionFind{
    private:
        int fa[110000];
    public:
        UnionFind(void){for(int i = 1; i <= N; ++i)fa[i] = i;}
        int Find(int x){return x == fa[x] ? x : (fa[x] = Find(fa[x]));}
        void Union(int s, int t){fa[t] = Find(s);}
    }uf;
    void Init(void){
        for(int i = 1; i <= Q; ++i){
            int u = read(), v = read();
            ask[i] = {u, v};
            query[u].emplace_back(v, i);
            query[v].emplace_back(u, i);
        }
    }
    void dfs(int p = 1, int fa = 0){
        vis[p] = true;
        for(auto i = head[p]; i; i = i->nxt)if(SON != fa && !vis[SON])dfs(SON, p), uf.Union(p, SON);
        for(auto q : query[p])if(vis[q.first])lca[q.second] = uf.Find(q.first);
    }
    void dfs_dep(int p = 1, int fa = 0){
        dep[p] = dep[fa] + 1;
        for(auto i = head[p]; i; i = i->nxt)if(SON != fa)ffa[SON] = {p, i->val}, dfs_dep(SON, p);
    }
}

int main(){
    freopen("statement.in", "r", stdin);
    freopen("statement.out", "w", stdout);
    N = read(), M = read();
    for(int i = 1; i <= M; ++i){
        int s = read(), t = read(), v = read();
        head[s] = new Edge{head[s], t, v};
        head[t] = new Edge{head[t], s, v};
    }Q = read();
    if(M == N - 1){
        Tree::Init();
        Tree::dfs();
        Tree::dfs_dep();
        for(int i = 1; i <= Q; ++i){
            ll anss(0);
            int cp(ask[i].first);
            while(cp != lca[i]){
                anss += ffa[cp].second;
                cp = ffa[cp].first;
            }
            cp = ask[i].second;
            while(cp != lca[i]){
                anss += ffa[cp].second;
                cp = ffa[cp].first;
            }
            printf("%lld\n", anss);
        }
        exit(0);
    }

    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}



template<typename T>
inline T read(void){
    T ret(0);
    short 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

考虑对于每次修改 $ v, x, k \(，\) v $ 子树（包括 $ v $）下的 $ u $，修改量为 $ x - dis(u, v) \times k $，因为是在树上，所以可以转化成 $ x - (dep_v - dep_u) \times k \(，展开一下：\) x + dep_u \times k - dep_v \times k $，然后发现式子里对于点 $ v \(，\) dep_v $ 是定值，所以开个线段树（或树状数组）维护一下 $ x + dep_u \times k $ 和 $ k $ 即可。然后这样的话每次修改就等于是对一整个子树的修改，考虑如何转到序列上，显然按照 dfs 序即可。

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;
// using namespace __gnu_pbds;

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 (1000000007)

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

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

int N, Q;
int idx[310000];
int dep[310000], siz[310000];

void dfs(int p = 1, int fa = 0){
    static int cnt(0);
    idx[p] = ++cnt;
    dep[idx[p]] = dep[idx[fa]] + 1;
    ++siz[idx[p]];
    for(auto i = head[p]; i; i = i->nxt)if(SON != fa)dfs(SON, p), siz[idx[p]] += siz[idx[SON]];
}

class BIT{
private:
    pair < ll, ll > tr[310000];
public:
    int lowbit(int x){return x & -x;}
    void add(int x, int u, ll base, ll k){
        while(x <= N)
            tr[x] = {
                ((tr[x].first + base + MOD) % MOD + (dep[u] * k + MOD) % MOD + MOD) % MOD,
                (tr[x].second + k + MOD) % MOD
            },
            x += lowbit(x);
    }
    void modify(int l, int r, int u, ll base, ll k){
        // printf("Modifying [%d, %d] => u = %d, x = %lld, k = %lld\n", l, r, u, base, k);
        add(l, u, base, k);
        add(r + 1, u, -base, -k);
    }
    ll query(int x){
        int rx = x;
        ll ret(0);
        while(x)ret = ((ret + tr[x].first) % MOD - tr[x].second * dep[rx] % MOD + MOD) % MOD, x -= lowbit(x);
        return ret;
    }
}bit;

int main(){
    N = read();
    for(int i = 2; i <= N; ++i){
        int fa = read();
        head[i] = new Edge{head[i], fa};
        head[fa] = new Edge{head[fa], i};
    }dfs();
    Q = read();
    while(Q--){
        // for(int i = 1; i <= N; ++i)printf("%lld%c", ta.query(i), i == N ? '\n' : ' ');
        int opt = read();
        if(opt == 1){
            int v = read(), x = read(), k = read();
            bit.modify(idx[v], idx[v] + siz[idx[v]] - 1, idx[v], x, k);
        }else{
            int v = read();
            printf("%lld\n", bit.query(idx[v]) % MOD);
        }
    }

    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template<typename T>
inline T read(void){
    T ret(0);
    short 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 T4

咕咕咕。

UPD

update-2022_10_21 初稿

标签：return,21,int,2022.10,void,ret,getchar,小结,define
From： https://www.cnblogs.com/tsawke/p/16820298.html

相关文章

  • 2022.10.19 模拟赛小结
    2022.10.19模拟赛小结目录2022.10.19模拟赛小结更好的阅读体验戳此进入赛时思路T1CodeT2T3T4Code正解T1CodeT2T3T4CodeUPD(一场难度稍微低1丶丶的模拟赛，不过我太弱了，......
  • 2022.10.14 模拟赛小结
    2022.10.14模拟赛小结目录2022.10.14模拟赛小结题面PDF链接更好的阅读体验戳此进入赛时思路T1T2CodeT3CodeT4正解T1CodeT2CodeT3T4UPD大概是相对来讲补的比较全的一场......
  • awd-web小结
    目录查看比赛信息、规则改密码下载源码，备份防御利用漏洞攻击最后查看比赛信息、规则注意赛方的限制比如说提交flag的间隔时间，flag的获取方式，通防的限制，对后门的处理要求......
  • 2022-2023-1 20221316《计算机基础与程序设计》第八周学习总结
    作业信息<班级的链接>首页-2022-2023-1-计算机基础与程序设计-北京电子科技学院-班级博客-博客园<作业要求的链接>：https://www.cnblogs.com/rocedu/p/9577842.h......
  • 2022-2023-1 20221312 《计算机基础与程序设计》第八周学习总结
    班级链接：首页-2022-2023-1-计算机基础与程序设计-北京电子科技学院-班级博客-博客园(cnblogs.com)作业要求：2022-2023-1《计算机基础与程序设计》教学进程-娄......
  • 2022-2023-1 20221313《计算机基础与程序设计》第八周学习总结
    2022-2023-120221313《计算机基础与程序设计》第八周学习总结作业信息这个作业属于哪个课程<班级的链接>https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP......
  • 2022-2023-1 20221328《计算机基础与程序设计》第八周学习总结
    作业信息班级：首页-2022-2023-1-计算机基础与程序设计-北京电子科技学院-班级博客-博客园(cnblogs.com)作业要求：2022-2023-1《计算机基础与程序设计》教学进程......
  • [2022.10.23]String的不可变性
    final关键字代表最终、不可改变的常见四种用法：1.可以用来修饰一个类（不能有任何子类）2.可以用来修饰一个方法（最终方法，不能被覆盖重写）3.还可以用来修饰一个局部变量（对......
  • 2022.10.23每日一题
    任务分配题目描述你有\(n\)个任务，其中第\(i\)个任务，在\(s_i\)开始，\(e_i\)时刻结束，如果做这个任务，你能获得\(w_i\)的收益。但是你在一个时刻只能做一个任务，问选......
  • dairy-20221023
    preface今天准备开始进行有计划的代码训练，今天开始的是50projects50days计划,这个时间段肯定是不能每天做这个的，有时间就弄一弄吧。<!DOCTYPEhtml><htmllang="en"><h......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99