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

2022.10.19 模拟赛小结

时间:2022-10-24 08:22:59浏览次数:80  
标签:return 19 2022.10 void int auto first 小结 define

2022.10.19 模拟赛小结

目录

(一场难度稍微低 1丶丶的模拟赛,不过我太弱了,依然没多少分。。。)

更好的阅读体验戳此进入

赛时思路

T1

给定 $ n $ 个点 $ m $ 条无向边,删除一个点要消耗和这个点直接连接的所有点的权值和,求删除所有点最小的消耗。

原题是 CF437C The Child and Toy

想到了几个贪心,如按照节点对其它节点的贡献,或节点本身被贡献的去排序,亦或做差考虑最终的贡献排序,想了好多人类智慧,然后都假掉了。。。

至于为什么假了也能想到,这样的排序实际是一个动态的过程,是不能根据最开始的状态无脑排序的,然而动态的这玩意似乎难以维护,如果每次删除并插入难以实现,每次重排的话大概是 $ O(mn\log n) $ 的,和无脑暴力一样,所以最后 T1 寄了,只有 $ 20\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++;}

/******************************
abbr

******************************/

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 MAXSIZE 1000000
char buf[MAXSIZE],*p1,*p2;
#define gc() (p1 == p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1== p2)?EOF:*p1++)
inline int read(){int x=0,f=1;char c=gc();while(!isdigit(c)){if(c=='-') f=-1;c=gc();}while(isdigit(c)) x=x*10+(c^48),c=gc();return x*f;}

#define CMP [](int x, int y)->bool{return ctr[x] - cost[x] > ctr[y] - cost[y];}

// struct cmp{
//     bool operator ()(const int &x, const int &y){return ctr[x] - cost[x] > ctr[y] - cost[y];}
// };

int N, M;
int val[1100000];
int idx[1100000];
ll ctr[1100000];
ll cost[1100000];
ll ans(0);
vector < int > vt[1100000];
// vector < int > heap;
bool used[1100000];


int main(){
    freopen("candy.in", "r", stdin);
    freopen("candy.out", "w", stdout);
    // freopen("candy1.in", "r", stdin);
    N = read(), M = read();
    for(int i = 1; i <= N; ++i)val[i] = read(), idx[i] = i;
    for(int i = 1; i <= M; ++i){
        int s = read(), t = read();
        ctr[s] += val[s], ctr[t] += val[t];
        cost[s] += val[t], cost[t] += val[s];
        vt[s].emplace_back(t), vt[t].emplace_back(s);
    }
    for(int i = 1; i <= N; ++i)ctr[i] -= cost[i];
    // sort(idx + 1, idx + N + 1, [](int x, int y)->bool{return ctr[x] == ctr[y] ? cost[x] < cost[y] : ctr[x] > ctr[y];});
    // sort(idx + 1, idx + N + 1, [](int x, int y)->bool{return cost[x] == cost[y] ? ctr[x] > ctr[y] : cost[x] < cost[y];});
    sort(idx + 1, idx + N + 1, [](int x, int y)->bool{return ctr[x] > ctr[y];});
    // for(int i = 1; i <= N; ++i)
        // heap.emplace(lower_bound(heap.begin(), heap.end(), i, CMP), i);
    for(int i = 1; i <= N; ++i){
        // sort(idx + 1, idx + N + 1, );
        // int p = heap.front();
        int p = idx[i];
        used[p] = true;
        // heap.erase(heap.begin());
        ans += cost[p];
        for(auto j : vt[p])
            if(!used[j])
                cost[j] -= val[p];
                // printf("%lld %lld (%d)\n", cost[j], ctr[j], j),
                // heap.erase(find(heap.begin(), heap.end(), j)),
                // heap.emplace(lower_bound(heap.begin(), heap.end(), j, CMP), j);
    }
    printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

T2

原题是 LG-P7152 [USACO20DEC] Bovine Genetics G

不会

T3

原题是 P7154 [USACO20DEC] Sleeping Cows P

不会

T4

给定 $ n $ 个节点以 $ 1 $ 为根的树,初始所有点权值为 $ 0 \(,\) m $ 次修改每次将 $ u $ 所在子树中距离 $ u $ 不大于 $ d $ 的点权值增加 $ v $,求最后每个点的权值。

原题是 CF1076E Vasya and a Tree

最开始想口糊一个在树上的动态建点的 ODT,然后发现建不出来。。然后尝试找了半天性质口糊了一个奇怪的做法:对于本题我的想法就是把子树覆盖转换成序列上的操作问题,然后最后想到了把树按照 bfs 序标号,这样的话每一层都会是一个连续的区间,然后我们记录每一个非叶子节点子树所在的下一层的区间,每次修改的时候这样跑一遍。。理论上在随机数据上都能过,但是一条链的话直接退化成比暴力常数还要大的暴力,而且我不知道咋想的区间操作的时候写了个没有 assign 的 ODT,结果基本全寄了,因为这玩意没有区间推平本身就完全用不了 ODT,一直在 Split,反应过来之后想改线段树没改完。。。在随机数据上基本都卡在了 1000ms 左右,刚好寄了。。链上的测试点直接过不了。最后 $ 30\texttt{pts} $ 到 $ 50\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++;}

/******************************
abbr

******************************/

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 MAXSIZE 1000000
char buf[MAXSIZE],*p1,*p2;
#define gc() (p1 == p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1== p2)?EOF:*p1++)
inline int read(){int x=0,f=1;char c=gc();while(!isdigit(c)){if(c=='-') f=-1;c=gc();}while(isdigit(c)) x=x*10+(c^48),c=gc();return x*f;}

int N, M;
int idx[310000]; //real => my
int ridx[310000]; //my => real
ll ans[310000];

int dsl[310000], dsr[310000];//i-1-depth-subtree-l / r

struct Node{
    int l, r;
    mutable ll val;
    friend const bool operator < (const Node &x, const Node &y){return x.l < y.l;}
};

class ODT{
private:
    set < Node > tr;
public:
    auto Insert(Node p){return tr.insert(p);}
    auto Split(int p){
        auto it = tr.lower_bound(Node{p});
        if(it != tr.end() && it->l == p)return it;
        --it;
        if(p > it->r)return tr.end();
        auto l = it->l, r = it->r;
        auto val = it->val;
        tr.erase(it);
        Insert(Node{l, p - 1, val});
        return Insert(Node{p, r, val}).first;
    }
    void Assign(int l, int r, ll val){
        // printf("assigning %d-%d : %lld\n", l, r, val);
        auto itR = Split(r + 1), itL = Split(l);
        for(auto it = itL; it != itR; ++it)it->val += val;
    }
    void SetAns(void){
        for(auto p : tr)for(int i = p.l; i <= p.r; ++i)ans[ridx[i]] = p.val;
    }
}odt;

// class SegT{
// private:
//     #define LS (p << 1)
//     #define RS ((p << 1) + 1)
//     #define SIZ (gr - gl + 1)
//     #define SIZZ(l, r) (r - l + 1)
//     #define MID ((gl + gr) >> 1)
//     ll tr[310000 << 2];
//     ll lt[310000 << 2];
// public:
//     void Pushdown(int p, int gl, int gr){
//         tr[LS] += lt[p] * SIZZ(gl, MID);
//         tr[RS] += lt[p] * SIZZ(MID + 1, gr);
//         lt[LS] += lt[p], tr[RS] += lt[p];
//         lt[p] = 0;
//     }
//     void Pushup(int p){
//         tr[p] = tr[LS] + tr[RS];
//     }
//     void Modify(int p, int l, int r, ll val, int gl = 1, int gr = N){
//         if(l <= gl && gr <= r)tr[p] += SIZ * val, lt[p] += SIZ
//     }
// }

struct Edge{
    Edge* nxt;
    int to;
    OPNEW;
}ed[610000];
ROPNEW(ed);
Edge* head[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});
                // tmp.push_back({SON, p.first});
        // for(auto i = tmp.rbegin(); i != tmp.rend(); ++i)q.push(*i);
        if(!dsl[idx[p.second]])dsl[idx[p.second]] = dsr[idx[p.second]] = idx[p.first];
        else dsr[idx[p.second]] = idx[p.first];
        // if(!head[p.first]->nxt)dsl[p.first] = dsr[p.first] = cnt;
    }
}
void modify(int dep, int p, ll val){
    int l(p), r(p); odt.Assign(l, r, val);
    while(dep--){
        while(!dsl[l] && l <= r)++l;
        while(!dsr[r] && l <= r)--r;
        if(l > r)return;
        l = dsl[l], r = dsr[r];
        // if(l > r)return;
        odt.Assign(l, r, val);
    }
}

int main(){
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    N = read();
    odt.Insert(Node{1, N, 0});
    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};
    }bfs();
    // for(int i = 1; i <= N; ++i)swap(dsl[i], dsr[i]);
    // for(int i = 1; i <= N; ++i)if(dsl[i] > dsr[i])printf("ERROR! at%d\n", i), exit(0);
    M = read();
    for(int i = 1; i <= M; ++i){
        int p = read(), dep = read(), val = read();
        modify(dep, idx[p], (ll)val);
    }
    odt.SetAns();
    for(int i = 1; i <= N; ++i)printf("%lld%c", ans[i], i == N ? '\n' : ' ');
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

正解

T1

考虑把删点变成删边,对于删除每条边,显然其贡献为两个端点中的一个的权值,所以遍历每条边答案加上两个端点中的最小值即可。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.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);

ll ans;
ll v[1100];

int main(){
    int N = read(), M = read();
    for(int i = 1; i <= N; ++i)v[i] = read();
    for(int i = 1; i <= M; ++i)ans += min(v[read()], v[read()]);
    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);
    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

咕咕咕。

T3

咕咕咕。

T4

考虑把修改离线,记录每个点上的所有修改,然后做一个奇怪的树上差分,搜索的时候考虑把每一个深度记录在当前搜索的子树内对应的差分值,然后每搜到一个点先加上对应的差分值,把它的修改加到答案里,然后在对应的差分的结束的地方减去这个值,当搜完节点所在子树的时候,要搜其它的子树了,这个节点子树的差分桶就不再有效了,所以此时将之前的修改回退一下即可。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.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 MAXN 310000

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

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

int N, M;
ll ans[MAXN];
ll d[MAXN];
int dep[MAXN];
vector < pair < int, int > /*depth, value*/ > mdf[MAXN];

void dfs(int p = 1, int fa = 0, ll cur = 0){
    dep[p] = dep[fa] + 1;
    cur += d[dep[p]];
    for(auto m : mdf[p])
        cur += m.second,
        (dep[p] + m.first + 1 < MAXN) ? (void)(d[dep[p] + m.first + 1] -= m.second) : void();
    ans[p] = cur;
    for(auto i = head[p]; i; i = i->nxt)
        SON != fa ? dfs(SON, p, cur) : void();
    for(auto m : mdf[p])
        if(dep[p] + m.first + 1 < MAXN)d[dep[p] + m.first + 1] += m.second;
}

int main(){
    N = 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};
    }M = read();
    for(int i = 1; i <= M; ++i){
        int vt = read(), dep = read(), val = read();
        mdf[vt].push_back({dep, val});
    }dfs();
    for(int i = 1; i <= N; ++i)printf("%lld%c", ans[i], i == N ? '\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;
}

UPD

update-2022_10_19 初稿

标签:return,19,2022.10,void,int,auto,first,小结,define
From: https://www.cnblogs.com/tsawke/p/16820304.html

相关文章

  • 2022.10.14 模拟赛小结
    2022.10.14模拟赛小结目录2022.10.14模拟赛小结题面PDF链接更好的阅读体验戳此进入赛时思路T1T2CodeT3CodeT4正解T1CodeT2CodeT3T4UPD大概是相对来讲补的比较全的一场......
  • awd-web小结
    目录查看比赛信息、规则改密码下载源码,备份防御利用漏洞攻击最后查看比赛信息、规则注意赛方的限制比如说提交flag的间隔时间,flag的获取方式,通防的限制,对后门的处理要求......
  • [2022.10.23]String的不可变性
    final关键字代表最终、不可改变的常见四种用法:1.可以用来修饰一个类(不能有任何子类)2.可以用来修饰一个方法(最终方法,不能被覆盖重写)3.还可以用来修饰一个局部变量(对......
  • 2022.10.23每日一题
    任务分配题目描述你有\(n\)个任务,其中第\(i\)个任务,在\(s_i\)开始,\(e_i\)时刻结束,如果做这个任务,你能获得\(w_i\)的收益。但是你在一个时刻只能做一个任务,问选......
  • 新高考对“水溶液中的离子反应与平衡”考查的研究 ——以2019、2021年全国乙卷和广东
    1.课程标准分析:1.1课标内容对比分析:1.1.12003版课标选修4“主题三:溶液中的离子平衡”的内容标准:能描述弱电解质在水溶液中的电离平衡,了解酸碱电离理论;知道水的离子积......
  • 【公告】布客社区公告 2022.10
    布客社区将花N年时间转型为DAO翻译和整理合并为一个工作流(同一段时间只做一个),并且按照编程、玄学、两性、财务顺序轮替。高校课件整理与备份计划正式开始,感谢github上各......
  • 【闲话】2022.10.23
    今天没有考试于是赫了些DP题每日一(?)图密码是咱最喜欢的番二度提示:我们一日日……记得第一个字母大写怎么登不上SPOJ啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊今......
  • 2022年10月23日19:15:08
    今天学院工作室竞选负责人,早上发的通知,看到了,没有多想,因为还在床上睡懒觉。想着等到起床再看,结果起床已经两点钟了。昨晚上搞我的博客,利用媒体查询完成了响应式布局,在P......
  • 2022.10.22
    总算能抽出点时间出去玩玩了睡完午觉,大概下午三点起床,又磨磨蹭蹭到4点。看了看等车来和地图,决定先坐15路到官渡桥东,然后坐5路车直达等车等到4点半,又坐车坐了一个多小时,大......
  • 2022-2023 20221319《计算机基础与程序设计》第八周学习总结
    作业信息这个作业属于那个班级:https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP作业要求:https://www.cnblogs.com/rocedu/p/9577842.html#WEEK06作业目标:《计算......