首页 > 其他分享 >Codeforces Round 881 (Div

Codeforces Round 881 (Div

时间:2023-06-23 21:45:07浏览次数:49  
标签:10 881 const idx int Codeforces cin fmax Div

E. Tracking Segments

给定初始长度为n,且全为0的序列a,然后给出m个线段,如果一个线段中1的个数严格大于0的个数,那么该线段称为一个漂亮线段,现在给出q次操作,每次操作使得序列a中位置x上的0变为1,请你求出第一次使得所有线段中出现漂亮线段的询问

题解:二分答案

  • 容易发现答案具有单调性,所以我们可以考虑二分答案
  • 我们发现在check的时候只要提前预处理好10个数前缀和数组即可,然后即可\(O(m)\)检验合法性
  • 分析其时间复杂度为:\(O(m\times logq)\)
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;

int n, m, q;
int L[N], R[N];
int qry[N];

bool check(int mid)
{
    vector<int> a(n + 10), pre0(n + 10), pre1(n + 10);
    for (int i = 1; i <= mid; ++i)
        a[qry[i]] = 1;
    for (int i = 1; i <= n; ++i)
    {
        pre1[i] = pre1[i - 1] + (a[i] == 1);
        pre0[i] = pre0[i - 1] + (a[i] == 0);
    }
    for (int i = 1; i <= m; ++i)
    {
        if (pre1[R[i]] - pre1[L[i] - 1] > pre0[R[i]] - pre0[L[i] - 1])
            return true;
    }
    return false;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        cin >> L[i] >> R[i];
    cin >> q;
    for (int i = 1; i <= q; ++i)
        cin >> qry[i];
    int l = 1, r = q;
    bool flag = false;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(mid))
        {
            r = mid - 1;
            flag = true;
        }
        else
            l = mid + 1;
    }
    if (flag)
        cout << l << endl;
    else
        cout << -1 << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

F1. Omsk Metro (simple version)

给一棵有根树,每次给定点 v,询问从根节点v 路径上的某个连续子段的和能否等于k

题解:\(dp\)——最大/最小子段和

  • 容易发现从根节点到\(v\)的路径上子段和的取值范围为\([最小子段和,最大字段和]\)
  • 所以我们可以\(dp\)即可
  • 状态转移时有3种选择:
  • 选择接在前面的子段上
  • 不接在前面的字段上,变成一个新的子段
  • 选择成为空子段
  • 查询时验证\(k\)是否在范围内即可
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;

int n;

void solve()
{
    cin >> n;
    int idx = 1;
    vector<int> fmin(n + 10, INF), fmax(n + 10, -INF);
    vector<int> mi(n + 10, INF), mx(n + 10, -INF);
    fmin[1] = 0;
    fmax[1] = 1;
    mi[1] = min({mi[1], fmin[1], 0LL});
    mx[1] = max({mx[1], fmax[1], 0LL});
    for (int i = 1; i <= n; ++i)
    {
        char op;
        int u, v, k, x;
        cin >> op;
        if (op == '+')
        {
            cin >> u >> x;
            idx++;
            fmin[idx] = min({fmin[u] + x, x, 0LL});
            fmax[idx] = max({fmax[u] + x, x, 0LL});
            mi[idx] = min(mi[u], fmin[idx]);
            mx[idx] = max(mx[u], fmax[idx]);
        }
        else
        {
            cin >> u >> v >> k;
            if (mi[v] <= k && mx[v] >= k)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
    }
}
signed main(void)
{
    Zeoy;
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

标签:10,881,const,idx,int,Codeforces,cin,fmax,Div
From: https://www.cnblogs.com/Zeoy-kkk/p/17500242.html

相关文章

  • Codeforces 1603D. Artistic Partition
    题目链接:D-ArtisticPartition题目大意:要求将\([1,n]\)分成\(k\)段,使得每段对应的\(c(l,r)\)之和最小,其中\(c(l,r)=\sum_{i=l}^r\sum_{j=i}^r[\gcd(i,j)\gel]\)。首先注意到当\(r<2l\)时,\(c(l,r)=r-l+1\)。所以当\(2^k-1\gen\)时答案即为\(n\)。考虑\(\texttt......
  • Codeforces Round 766 (Div. 2) 比赛报告
    0比赛经过比赛还没开始的时候就感觉状态不太好。果然。总归到底都是一个心态问题。A题经过看A题,结果半天看不懂,一开始没有注意到一定要在黑格子上操作。扔到DeepL上翻译了一下,再手玩一下样例就做出来了,速度有点慢。CF怎么这么喜欢出分讨题啊。看题目不能太急,要一个一......
  • Codeforces Round 881 (Div. 3)--F2
    F2.OmskMetro(hardversion)#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#defineendl"\n"#defineintlonglongconstintN=2e5+5;constintINF=0x3f3f3f3f;//假设一个区间的最大字段和为max最小字段和为min//那么[min,max]区间的......
  • 鼠标悬浮div或者列表li时,展示出button按钮
    <template><divclass="item"><span><inputtype="checkbox":checked="obj.done"@click="handleCheck(obj.id)"></span><span>{{......
  • Codeforces 1835F - Good Graph
    goodproblem,badround。判断YES还是NO很trivial,就直接跑最大匹配看看是不是\(n\)即可。如果是NO,那么考虑Hall定理的证明过程构造即可。具体方法就是找到左部任意一非匹配点,在残量网络上BFS可以到达的点,那所有可以到达的左部点形成的集合就是符合要求的反例。因为你......
  • Codeforces 1835E - Old Mobile
    首先先观察到一个非常浅显的性质:就是一个位置在序列中不是第一次出现,那么到这个位置的时候打出这个字符需要恰好一次按键,这是因为我们肯定在打出第一次出现这个字符的位置的时候已经知道哪个键对应这个字符了,到那个位置的时候直接敲一下就ok了。也就是我们只用关心这个序列中出......
  • Codeforces Round 878 (Div. 3) D. Wooden Toy Festival
    题目翻译:给定一个序列,你可以把序列分为任意的三组不要求顺序,对于每一组序列给出一个数字作为标准,求出序列中和该数字的差绝对值的最大值,现在要求你选顶三个数字使得三个序列的差最大值的最大值最小解题思路:二分,要想方差最小,就让每一组的极差都最小,即最大值减最小值最小#include......
  • 练习记录-cf-Codeforces Round 881 (Div. 3)A-F1
    E是补的太蠢了没想到期末考完的复健A.SashaandArrayColoring题意:可以给不同数字涂上很多颜色,每个颜色的贡献是同一个颜色内的数字最大值和最小值的差思路:排序一遍,取头和尾的差#include<bits/stdc++.h>#defineclosestd::ios::sync_with_stdio(false),cin.tie(0)......
  • CodeForces 合集
    1838E.CountSupersequenceshttps://codeforces.com/contest/1838/problem/E题意给定\(n,m,k\),一个长度为\(n\)的序列\(a=(a_1,a_2,\dots,a_n)\),满足\(1\leqa_i\leqk\),求有多少个序列\(b=(b_1,b_2,\dots,b_m)\),满足\(a\)是\(b\)的一个子序列,并且\(......
  • Kullback-Leibler-divergence 和 Jensen–Shannon divergence 的计算示例
    #!/usr/bin/envpython3#-*-coding:utf-8-*-"""CreatedonFriJun2616:05:572020@author:vkchlt0297"""frommatplotlibimportpyplotfrommathimportlog2importnumpyasnp#Defineeventevents=['red'......