首页 > 其他分享 >Codeforces Round 966 (Div. 3)

Codeforces Round 966 (Div. 3)

时间：2024-08-29 10:37:52浏览次数：14  
标签：966 int Codeforces long read while Div dis define

A. Primary Task

if-else语句练习，判断前两个字符是否为"10"，并判断之后的字符是否大于1

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; char c = getchar();
    while (c < '0' || c > '9') f = c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 1e4 + 5;
char s[N];

int main()
{
    int T = read();
    while(T--)
    {
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        if(s[1] == '1' && s[2] == '0' && ((len > 3 && s[3] >= '1') || (len == 3 && s[3] >= '2'))) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

B. Seating in a Bus

模拟

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; char c = getchar();
    while (c < '0' || c > '9') f = c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;
int a[N], vis[N];

int main()
{
    int T = read();
    while(T--)
    {
        int n = read();
        for(int i = 1; i <= n; ++i) a[i] = read();
        for(int i = 1; i <= n; ++i) vis[i] = 0;
        vis[a[1]] = 1;
        int flag = 1;
        for(int i = 2; i <= n; ++i)
        {
            int ner = 0;
            if(a[i] > 1) ner |= vis[a[i] - 1];
            if(a[i] < n) ner |= vis[a[i] + 1];
            if(ner == 0){ flag = 0; break; }
            vis[a[i]] = 1;
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

C. Numeric String Template

还是模拟，每个数字第一次出现映射到一个字符上，之后再出现直接判断，字符第一次出现同理

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; char c = getchar();
    while (c < '0' || c > '9') f = c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;
int a[N], b[N];
int id1[N], id2[N];
char s[N];
void solve()
{
    int n = read();
    for(int i = 1; i <= n; ++i) a[i] = b[i] = read();
    sort(b + 1, b + n + 1);
    int x = unique(b + 1, b + n + 1) - (b + 1);
    for(int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + x + 1, a[i]) - b;
    int m = read();
    while(m--)
    {
        scanf("%s", s + 1);
        int flag = 1, len = strlen(s + 1);
        if(len != n){ printf("NO\n"); continue; }
        for(int i = 1; i <= n; ++i) id1[i] = -1;
        for(int i = 1; i <= n; ++i)
        {
            if(id1[a[i]] == -1) id1[a[i]] = s[i] - 'a';
            else if(id1[a[i]] != s[i] - 'a') flag = 0;
            if(!flag) break;
        }
        for(int i = 0; i <= 25; ++i) id2[i] = -1;
        for(int i = 1; i <= len; ++i)
        {
            if(id2[s[i] - 'a'] == -1) id2[s[i] - 'a'] = a[i];
            else if(id2[s[i] - 'a'] != a[i]) flag = 0;
            if(!flag) break;
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

D. Right Left Wrong

注意到 \(LLRR\) 取 \((1, 3)(2, 4)\) 和 \((1, 4)(2, 3)\) 是等价的，于是直接取所有区间只有包含没有相交的情况，即用双指针从两端向中间扫即可

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; char c = getchar();
    while (c < '0' || c > '9') f = c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;
int a[N];
char s[N];
ll sum[N];

void solve()
{
    int n = read();
    for(int i = 1; i <= n; ++i) a[i] = read(), sum[i] = sum[i - 1] + a[i];
    scanf("%s", s + 1);
    int l = 1, r = n;
    ll ans = 0;
    while(l < r)
    {
        while(l <= n && s[l] != 'L') ++l;
        while(r >= 1 && s[r] != 'R') --r;
        if(l < r) ans += sum[r] - sum[l - 1];
        ++l, --r;
    }
    printf("%lld\n", ans);
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

E. Photoshoot for Gorillas

简单计算一下一个格子被多少个边长为 \(K\) 的子方阵包含，那么这个格子里的数就会贡献这么多次，贪心的让大数放到次数多的格子里

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; char c = getchar();
    while (c < '0' || c > '9') f = c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;
int a[N];
int cnt[N];

bool cmp(int a, int b){ return a > b; }

void solve()
{
    int n = read(), m = read(), K = read(), W = read(), tot = 0;
    for(int i = 1; i <= W; ++i) a[i] = read();
    sort(a + 1, a + W + 1, cmp);
    for(int x = 1; x <= n; ++x)
        for(int y = 1; y <= m; ++y)
        {
            int lx = max(1, x - K + 1), rx = min(n - K + 1, x);
            int ly = max(1, y - K + 1), ry = min(m - K + 1, y);
            cnt[++tot] = 1ll * (rx - lx + 1) * (ry - ly + 1);
        }
    sort(cnt + 1, cnt + tot + 1, cmp);
    ll ans = 0;
    for(int i = 1; i <= W; ++i) ans += 1ll * a[i] * cnt[i];
    printf("%lld\n", ans);
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

F. Color Rows and Columns

首先想到的是贪心，即一个 \(a \times b\) 的矩形，填满一行或一列需要 \(\min\{a, b\}\) 步

这样贪心的取，发现当 \(1 \times 1\) 时一次性填了一行和一列，答案 + 2

贪心不完全对，转而考虑背包 \(DP\)

需要注意的是：想要答案 + a + b ，需要 \(a \times b\) 步，想要答案 + a + b - 1 ，也需要 \(a \times b\) 步

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; char c = getchar();
    while (c < '0' || c > '9') f = c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int inf = 0x3f3f3f;
int dp[2][105], a[1005], b[1005];
vector< pair<int, int> > x[1005];

void init(int id)
{
    x[id].clear();
    int A = a[id], B = b[id], sum = 0, K = 0;
    while(A && B)
    {
        sum += A, --B, ++K;
        if(A > B) swap(A, B);
        if(A == 0) x[id].emplace_back(pair<int, int>(K, sum)), ++K;
        x[id].emplace_back(pair<int, int>(K, sum));
    }
}

void solve()
{
    int n = read(), K = read();
    for(int i = 1; i <= n; ++i)
    {
        a[i] = read(), b[i] = read();
        if(a[i] > b[i]) swap(a[i], b[i]);
        init(i);
    }
    for(int i = 1; i <= K; ++i) dp[0][i] = inf;
    int ans = inf;
    for(int i = 1, op = 1; i <= n; ++i, op ^= 1)
    {
        for(int j = 0; j <= K; ++j) dp[op][j] = dp[op ^ 1][j];
        for(auto [w, val] : x[i])
        {
            for(int j = w; j <= K; ++j)
                dp[op][j] = min(dp[op][j], dp[op ^ 1][j - w] + val);
        }
        ans = min(ans, dp[op][K]);
    }
    if(ans == inf) printf("-1\n");
    else printf("%d\n", ans);
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

G. Call During the Journey

最短路魔改，松弛操作时分三种情况：

  1. 直接走路过去，不受任何限制

  2. 坐车过去，需要保证下车时间 \(\le t1\) 或者上车时间 \(\ge t2\)

  3. 等到 \(t2\) 再上车

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; char c = getchar();
    while (c < '0' || c > '9') f = c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const ll inf = 0x7fffffffffff;
const int N = 1e5 + 5;  
int n, m;
int t0, t1, t2;

struct node
{
    int v, l1, l2;
    node(){ v = l1 = l2 = 0; }
    node(int x, int y, int z){ v = x, l1 = y, l2 = z; }
};

vector<node> e[N];

ll dis[N];
bool vis[N];
priority_queue< pair<int, int> > q;

bool check(int t)
{
    // printf("t = %d\n", t);
    for(int i = 1; i <= n; ++i) dis[i] = inf, vis[i] = 0;
    dis[1] = t;
    q.push(pair<int, int>(-dis[1], 1));
    while(!q.empty())
    {
        int u = q.top().second ;
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        // printf("u = %d, dis = %lld\n", u, dis[u]);
        for(auto [v, l1, l2] : e[u])
        {
            int flag = 0;
            if(dis[v] > dis[u] + l2)
            {
                dis[v] = dis[u] + l2;
                flag = 1;
            }
            if(dis[v] > dis[u] + l1 && ((dis[u] + l1 <= t1) || (dis[u] >= t2)))
            {
                dis[v] = dis[u] + l1;
                flag = 1;
            }
            if(dis[u] <= t2 && dis[v] > t2 + l1)
            {
                dis[v] = t2 + l1;
                flag = 1;
            }
            if(flag) q.push(pair<int, int>(-dis[v], v));
        }
    }
    if(dis[n] <= t0) return true;
    else return false;
}

void solve()
{
    n = read(), m = read();
    t0 = read(), t1 = read(), t2 = read();
    for(int i = 1; i <= n; ++i) e[i].clear();
    for(int i = 1; i <= m; ++i)
    {
        int u = read(), v = read(), l1 = read(), l2 = read();
        e[u].emplace_back(node(v, l1, l2));
        e[v].emplace_back(node(u, l1, l2));
    }
    int l = -1, r = t0;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    printf("%d\n", l);
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

H. Ksyusha and the Loaded Set

转化题意为，最初所有数都为 \(1\) ，集合中包含的数为 \(0\) ，三种操作：

  1. 加入集合一个数，等价于将此位置设为 \(0\)

  2. 删去集合一个数，等价于将此位置设为 \(1\)

  3. 询问集合中1的连续段长度 \(\ge k\) 的最小左端点

权值线段树搞就完了

终于知道多测的意义了，专门卡 \(O(值域)\) 的算法

注意到每次测试时都重建一颗一模一样的树，时间消耗主要在这里，不优

又注意到每个测试中的操作数是 \(O(n)\) 的，考虑撤销操作

只在一开始建树，之后每次用时撤销前面的测试的操作

总结

  • 权值线段树遇上多测，考虑撤销操作
点击查看代码 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; char c = getchar();
    while (c < '0' || c > '9') f = c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;
int n, m, a[N];

struct node
{
    int mx, lsum, rsum, len;
    node(){ mx = lsum = rsum = len = 0; }
    node friend operator + (node a, node b)
    {
        node c;
        c.mx = max(a.mx , b.mx );
        c.mx = max(c.mx , a.rsum + b.lsum );
        c.len = a.len + b.len ;
        c.lsum = a.lsum + ((a.lsum == a.len ) ? b.lsum : 0);
        c.rsum = b.rsum + ((b.rsum == b.len ) ? a.rsum : 0);
        return c;
    }
};

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

node A[8388605 + 10];

void build(int k, int l, int r)
{
    if(l == r)
    {
        A[k].mx = A[k].lsum = A[k].rsum = A[k].len = 1;
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls(k), l, mid), build(rs(k), mid + 1, r);
    A[k] = A[ls(k)] + A[rs(k)];
}

void update(int k, int l, int r, int pos, int val)
{
    if(l == r)
    {
        A[k].mx = A[k].lsum = A[k].rsum = val;
        return ;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(ls(k), l, mid, pos, val);
    else update(rs(k), mid + 1, r, pos, val);
    A[k] = A[ls(k)] + A[rs(k)];
}

int query(int k, int l, int r, int len)
{
    if(l == r) return l;
    int mid = (l + r) >> 1;
    if(A[ls(k)].mx >= len) return query(ls(k), l, mid, len);
    if(A[ls(k)].rsum + A[rs(k)].lsum >= len) return mid - A[ls(k)].rsum + 1;
    return query(rs(k), mid + 1, r, len);
}

pair<int, int> sta[N << 1];
int top;

void solve()
{
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    m = read();
    top = 0;
    for(int i = 1; i <= n; ++i) update(1, 1, 4e6, a[i], 0), sta[++top] = pair<int, int>(a[i], 0);
    while(m--)
    {
        char c;
        int x;
        scanf(" %c %d", &c, &x);
        if(c == '-') update(1, 1, 4e6, x, 1), sta[++top] = pair<int, int>(x, 1);
        if(c == '+') update(1, 1, 4e6, x, 0), sta[++top] = pair<int, int>(x, 0);
        if(c == '?') printf("%d ", query(1, 1, 4e6, x));
    }
    while(top)
    {
        update(1, 1, 4e6, sta[top].first , sta[top].second ^ 1);
        --top;   
    }
    printf("\n");
}

int main()
{
    int T = read();
    build(1, 1, 4e6);
    while(T--) solve();
    return 0;
}

标签：966,int,Codeforces,long,read,while,Div,dis,define
From： https://www.cnblogs.com/wenqizhi/p/18386129

相关文章

  • EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2) VP记录
    EPICInstituteofTechnologyRoundSummer2024(Div.1+Div.2)VP记录A一眼\((n-1)m+1\)。B最后的数列是固定的，每个数与最后数列的数相减后，对差值求和再加上最大值即可。C唐诗C题，获得\(3\)发罚时。只有一个数右边的数归零了，它才会归零。右往左扫，如果右边......
  • Hitachi Vantara Programming Contest 2024（AtCoder Beginner Contest 368）F - Dividing
    https://atcoder.jp/contests/abc368/tasks/abc368_f#include<bits/stdc++.h>#definexfirst#defineysecondusingnamespacestd;typedeflonglongll;typedefpair<ll,char>pii;constintN=2e5+10,inf=1e9;lln,m,k;intb[N],sg[N],a[N];vector......
  • Educational Codeforces Round 169 (Rated for Div. 2)
    A.ClosestPoint两个数时只要不相邻就有解，超过两个数无解点击查看代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsignedlonglong#definepiipair<int,int>intread(){intx=0,f=0;charc=getchar();whi......
  • Codeforces Round 968 (Div. 2)
    题目链接：CodeforcesRound968(Div.2)-Codeforces总结：C题想到了，但是写成shi了，出得有点慢。A.TurtleandGoodStringtag：签到Solution：直接判断第一个字符是否与最后一个字符相等即可。voidsolve(){cin>>n;strings;cin>>s;if(s[0]==s[n-1]......
  • Codeforces Round 968 (Div. 2)
    题目链接：CodeforcesRound968(Div.2)-Codeforces总结：C题想到了，但是写成shi了，出得有点慢。A.TurtleandGoodStringtag：签到Solution：直接判断第一个字符是否与最后一个字符相等即可。voidsolve(){cin>>n;strings;cin>>s;if(s[0]==s[......
  • Pinely Round 4 (Div. 1 + Div. 2) VP记录
    PinelyRound4(Div.1+Div.2)VP记录场上打了ABCDF，被E二粉兔创飞了。这场的构造题有：BDEGI，乐死了。A把数列黑白染色，第一个格为黑色，那么每次删除会删除一个黑格子和一个白格子。而黑格子始终比白格子多一个，因此最后选到的是黑格子。答案极为黑格子的最大值，也易证一......
  • Codeforces Round 967 (Div. 2)
    题目链接：CodeforcesRound967(Div.2)-Codeforces总结：B题没测试就交wa一发，C题一直没想到怎么回溯，哎。A.MakeAllEqualtag：签到Solution：找到相同元素的最大值，将其它所有元素删去。voidsolve(){cin>>n;vector<int>a(n);map<int,int>mp;intans......
  • Codeforces Round 962 (Div. 3)
    A.Legs若只判断题，根据模4意义下分类即可。B.Scale模拟题，缩小同值矩阵即可。C.Sort对每个字母求前缀数量和，答案就是两端点的差。constintN=2e5+5;intT,n,q;chara[N],b[N];intc[N][26],d[N][26];signedmain(void){ for(read(T);T;T--){ read(......
  • Codeforces Round 968 (Div. 2)
    A.TurtleandGoodStrings题意：确定是否存在一种方案使得\(s=t_1+t_2+\cdots+t_m\)，满足\(m>1\)且任意\(i<j\)，\(t_i\)的第一个字母不等于\(t_j\)的最后一个字母。\(s_1\)和\(s_n\)一定不属于一个子串，因此\(s_1\nes_n\)是条件非法的必要条件。那么反......
  • Codeforces Round 968 (Div. 2)
    A.TurtleandGoodStrings思路：题意大致为把一个字符串分成若干段，要求每两段，前一段的首字符不能等于后的一段的尾字符，给你一个字符串，能不能构造出合法方案。观察到，分的段数越小，越有助于我们判断。所以，不妨分成两段，问题转化为判断首尾字符是否相等。代码：#include<bits/stdc++.......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99