首页 > 其他分享 >Codeforces Round 881 Div2 A-F1题解

Codeforces Round 881 Div2 A-F1题解

时间：2023-07-02 17:23:41浏览次数：48  
标签：F1 881 int 题解 ll cin long rep define

codeforces round 881 div2 题解

马上要秋招了，自己本事全丢了，感觉如果这样的话今年就估计要饿死了。先打div3，7月份得开始收心了

A. Sasha and Array Coloring

题意，可以分任意组，每组的贡献是max - min，问最大贡献

显然是贪心，从大到小配对一下就行，不想放代码了’

B. Long Long

给出一个数列a，我们一次能反转一个区间的正负，问我们最少需要多少次操作才能使得a中所有的数都是正数

思路：
记录下标，贪心，然后expand一下，记得特判区间全是0的情况

AC代码 
#include <bits/stdc++.h>

using namespace std;
constexpr int limit =  (4e5  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
int n;
int a[limit];
void solve(){
    cin>>n;
    ll ans = 0;
    deque<int>v;
    rep(i, 1, n){
        cin>>a[i];
        ans += abs(a[i]);
        if(a[i] <= 0)v.push_back(i);
    }
    int res = 0;
    while(v.size()){
        auto cur = v.front();
        v.pop_front();
        bool is_negative = a[cur] < 0;
        while(v.size() and v.front() == cur + 1) {
            cur = v.front();
            is_negative |= a[cur] < 0;
            v.pop_front();
        }
        if(is_negative)res++;
    }
    cout<<ans<<" "<<res<<endl;





};
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    int kase;
    cin>>kase;
    while (kase--)
        invoke(solve);
     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

C.Sum in Binary Tree

给一个完全二叉树，bfs序就是weight，问给出一个node走到1的路径总和

思路：
稍加观察我们发现这完全就是 /2的过程，所以模拟就行

AC代码 
#include <bits/stdc++.h>

using namespace std;
constexpr int limit =  (4e5  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
int n;
int a[limit];
void solve(){
    ll x;
    cin>>x;
    ll ans = 0;
    while (x != 1){
        ans += x;
        x >>= 1;
    }
    cout<<ans+1ll<<endl;




};
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    int kase;
    cin>>kase;
    while (kase--)
        invoke(solve);
     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

D. Apple Tree

题意是给你一个树，然后你有两个苹果，每个苹果可能从子树的任何一个叶子节点掉下去，给出出生点，问你最后两个苹果会掉的位置的对数总和

这题很简单，就是题面真恶心，我看了半天才看懂题意，然后就是算一下每个点以下的叶子节点size就行

AC代码 
#include <bits/stdc++.h>

using namespace std;
constexpr int limit =  (4e5  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
int n;
int a[limit];
vector<int>g[limit];
int leaf[limit];
void dfs(int u,int pre){
    if(u != 1 and g[u].size() == 1){
        leaf[u] = 1;
        return;
    }
    for(auto v : g[u]) {
        if (v == pre)continue;
        dfs(v, u);
        leaf[u] += leaf[v];
    }
}
void solve(){
    cin>>n;
    rep(i,1,n)g[i].clear(), leaf[i] = 0;
    rep(i, 1, n - 1){
        int x, y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int q;
    cin>>q;
    dfs(1, -1);
    while(q--){
        int x, y;
        cin>>x>>y;
        ll ans = 1ll*leaf[x] * leaf[y];
        cout<<ans<<endl;
    }





};
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    int kase;
    cin>>kase;
    while (kase--)
        invoke(solve);
     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

E. Tracking Segments

这个题问给一个全0的序列和一些区间，然后给一个操作序列每次把一个位置set on，如果一个区间里面1的个数占绝对多数，就是beautiful区间，问你第一个beautiful区间出现最早时间

妈的，因为很久不写题了，直接想上主席树（事实上也完全没有错），但是主席树我没板子，抄别人的板子锅了，然后突然发现这不就一傻逼二分么，哎

AC代码 
#include <bits/stdc++.h>

using namespace std;
constexpr int limit =  (4e5  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
int n;
int a[limit];
vector<int>g[limit];
int pref[limit];
const int MAXN=2e5+50,SIZE=MAXN*20;
int N,M,K;
int A[MAXN],rt[MAXN];
int sz,lson[SIZE],rson[SIZE],sum[SIZE];
int init(int l,int r){
    int cur=++sz;
    if(l<r){
        int mid=(l+r)>>1;
        lson[cur]=init(l,mid);
        rson[cur]=init(mid+1,r);
    }
    return cur;
}
int modify(int pre,int l,int r,int x){
    int cur=++sz;
    lson[cur]=lson[pre];
    rson[cur]=rson[pre];
    sum[cur]=sum[pre]+1;
    int mid=(l+r)>>1;
    if(l<r){
        if(x<=mid)
            lson[cur]=modify(lson[pre],l,mid,x);
        else
            rson[cur]=modify(rson[pre],mid+1,r,x);
    }
    return cur;
}
int query(int x,int y,int l,int r,int k){
    if(l==r)
        return l;
    int ii=sum[lson[y]]-sum[lson[x]],mid=(l+r)>>1;
    if(ii>=k){
        return query(lson[x],lson[y],l,mid,k);
    }else{
        return query(rson[x],rson[y],mid+1,r,k-ii);
    }
}
void solve(){
    vector<pi(int, int)>p;
    int m;
    cin>>n>>m;
    sz = 0;
    rep(i,0,n){
        lson[i] = 0;
        rson[i] = 0;
        sum[i] = rt[i] = A[i] = 0;
        pref[i] = 0;
        a[i] = 0;
        A[i] = 0;
    }
    rep(i,1,m){
        int l,r;

        cin>>l>>r;
        p.push_back({l, r});
    }
    int q;
    cin>>q;
    rep(i, 1, q){
        int x;
        cin>>x;
        a[x] = i;
        A[i] = a[i];
    }
    auto check = [&](int x)->bool {
        rep(i,1,n){
            pref[i] = pref[i - 1] + (a[i] <= x and a[i]);
        }
        for(const auto &[l, r] : p){
            int one = pref[r] - pref[l - 1];
            int zero = r - l + 1 - one;
            if(one > zero){
                return true;
            }
        }
        return false;
    };
    int ans = -1;
    for(int l = 1, r = n; l <= r; ){
        int mid = l + (r - l) / 2;
        if(check(mid)){
            ans = mid;
            r = mid - 1;
        }else {
            l = mid + 1;
        }
    }
    cout<<ans<<endl;

};
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    int kase;
    cin>>kase;
    while (kase--)
        invoke(solve);
     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

F1.Omsk Metro (simple version)

这题题面和D一样屎，我读了半天才发现是个树，然后给一对节点，问这两个节点之间的路径上能否凑出来一个k的路径，possibly empty。节点是动态添加的。easy和hard区别是easy里面的两个节点在query里面有一个固定为1

然后这个题输入也很烦，不过很简单。就是拿DP判一下k是否在某个范围内就好了，既然是从1开始，那么久记录一下当前路径（i个节点被添加之后）最大最小值，然后判断一下范围，因为如果有k \(\in [l,r]\) 我们不需要知道具体方案，我们只需要知道max区间可以拓展得到k，而min区间同理

AC code 
#include <bits/stdc++.h>

using namespace std;
constexpr int limit =  (4e5  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
int n;
int a[limit];
vector<int>g[limit];
int dp[limit][2];
int minn[limit], maxx[limit];
void solve(){
    cin>>n;
    int tot = 1;
    dp[1][1] = dp[1][0] = 1;
    maxx[1] = 1;
    minn[1] = 0; //no opt
    rep(i,1,n){
        string op;
        cin>>op;
        if(op == "+"){
            int fa, x;
            cin>>fa>>x;
            ++tot; //增加新儿子
            auto fa_max = dp[fa][0];
            auto fa_min = dp[fa][1];
            auto&& self_max = dp[tot][0];
            auto&& self_min = dp[tot][1];
            self_max = max({x, fa_max + x, fa_min + x});
            self_min = min({x, fa_min + x, fa_max + x});
//            self_max = max(self_max, x);
//            self_min = min(self_min, x);
            minn[tot] = min({self_min, minn[fa], 0});
            maxx[tot] = max({self_max, maxx[fa], 0});
        }else {
            int u, v, x;
            cin>>u>>v>>x;
//            cout<<x<<" "<<maxx[v]<<" "<<minn[v]<<endl;
            if(x <= maxx[v] and x >= minn[v]){
                cout<<"YES"<<endl;
            }else{
                cout<<"NO"<<endl;
            }
        }
    }
};
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    int kase;
    cin>>kase;
    while (kase--)
        invoke(solve);
     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

F2我没看，因为我记得我写过一样的，很简单，就是树剖然后用线段树维护一下最大最小值，拼起来，但是好像找不到了，等下看看再。

标签：F1,881,int,题解,ll,cin,long,rep,define
From： https://www.cnblogs.com/tiany7/p/17521038.html

相关文章

  • 【CF1797F】Li Hua and Path
    于2023.5.10更新：更正了两处笔误。考虑如下定义：\(A\)表示满足第一种路径的\((u,v)\)集合。\(B\)表示满足第二种路径的\((u,v)\)集合。\(C\)表示满足前两种路径的\((u,v)\)集合。然后答案显然就是\(|A|+|B|-2|C|\)。先求出这一类的答案，再解决动态挂叶子的问......
  • 【CF1715E】Long Way Home
    这个\(k\)非常小，所以我们考虑全部依次飞这\(k\)次行程。这个飞来飞去是一个平方的形式，我们考虑优化这一形式。首先我们知道从\(u\)飞到\(v\)后就可以这样做：\[dis_u+(u-v)^2\todis_v\]\[dis_u+u^2+v^2-2uv\todis_v\]这里我们可以钦定\(u<v\)，然后斜率......
  • 【CF1146F】Leaf Partition
    这个题还是蛮有趣的，其实弄清楚这个染色的方案，这个题还是简单的。本质上只是对于考虑对于连通块染色，但是带有一些限制。所以我们考虑在LCA上拼接若干条根到叶子的路径。那我们就可以依据这一想法来设计状态。第一是这个点没有染色，那我们记这一状态为\(h\)。第二是这个点连......
  • JSON中，java.lang.NoClassDefFoundError: net/sf/ezmorph/Morpher问题解决
    使用JSON，在SERVLET或者STRUTS的ACTION中取得数据时，如果会出现异常：java.lang.NoClassDefFoundError:net/sf/ezmorph/Morpher是因为需要的类没有找到，一般，是因为少导入了JAR包，使用JSON时，除了要导入JSON网站上面下载的json-lib-2.2-jdk15.jar包之外，还必须有其它几个依赖包：commons-bean......
  • dpkg-reconfigure命令找不到问题解决
    作者： adminhttps://cloudbool.com/archive/dpkg-reconfigure-command-not-found.html今天在SSH远程连接到服务器时，遇到了dpkg-reconfigure命令找不到的问题，觉得很是奇怪，花了点时间研究下，这里做个记录，以备后用。前情提要我远程的服务器系统是自行使用DebiannetinstISO镜......
  • CF1804H Code Lock
    牛逼题，但是卡常。首先显然指针会从密码串第\(1\)个位置开始，因此我们需要关心的就是相邻两个位置的值。只需要求出\(c_{x,y}\)表示前一个是\(x\)，后一个是\(y\)的个数即可。考虑一般的按顺序填的状压，总是避免不了顺序的问题，总是与\(k!\)有关，我们需要一个合适的计算贡献的......
  • [ABC306] C/D 题解
    C.Centers 参考算法统计，排序\(\rmSyx\)给你\(3\timesN\)个数，其中\(\rmSyx\)可以保证：\(1\simN\)之间的所有数都出现了\(3\)次，请你将\(1\simN\)之间的数每个出现在第\(2\)个位置的下标进行排序，并从小到大输出原数。用\(\rmmap\)记录数出现的次数，......
  • 【题解】#119. 最大整数 题解（2023-07-01更新）
    #119.最大整数题解题目传送门更新日志2023-05-2617:20文章完成2023-05-3015:22文章审核通过2023-07-0116:04修改了代码题目知识点字符串+贪心题意说明设有n个正整数（$n<20$），将它们连接成一排，组成一个最大的多位整数。（题目简介明了，一看就是出题人懒得写题目背景）......
  • 【题解】P8679 [蓝桥杯 2019 省 B] 填空问题 题解
    P8679[蓝桥杯2019省B]填空问题题解题目传送门欢迎大家指出错误并联系这个蒟蒻更新日志2023-05-2521:02文章完成2023-05-2711:34文章通过审核2023-06-2021:03优化了文章代码格式试题A：组队【解析】本题是一道经典的DFS搜索题，每次对各号位的选手进行DFS，......
  • 【题解】P8741 [蓝桥杯 2021 省 B] 填空问题 题解
    P8741[蓝桥杯2021省B]填空问题题解题目传送门欢迎大家指出错误并联系这个蒟蒻更新日志2023-05-0923:19文章完成2023-05-0923:20通过审核2023-06-2021:03优化了文章代码格式试题A：空间【解析】本题考察计算机存储的基础知识，只要掌握空间存储的换算方法，就能......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99