首页 > 其他分享 >AtCoder Beginner Contest 283

AtCoder Beginner Contest 283

时间：2022-12-25 00:55:44浏览次数：71  
标签：AtCoder Beginner min int cin long ans using 283

A - Power (abc283 a)

题目大意

给定\(A,B\)，输出 \(A^B\)

解题思路

数不大，暴力即可。

数大了可用快速幂。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int a,b;
    cin >> a >> b;
    int ans = 1;
    while(b--){
        ans *= a;
    }
    cout << ans << '\n';

    return 0;
}

B - First Query Problem (abc283 b)

题目大意

给定一个数组\(A\)和 \(Q\)个操作，分两种

  • 1 k x，令 \(A_k = x\)
  • 2 k，输出 \(A_k\)

解题思路

暴力模拟即可。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &i : a)
        cin >> i;
    int q;
    cin >> q;
    while(q--){
        int op;
        cin >> op;
        if (op == 1){
            int k, x;
            cin >> k >> x;
            a[k - 1] = x;
        }else{
            int k;
            cin >> k;
            cout << a[k - 1] << '\n';
        }
    }

    return 0;
}

C - Cash Register (abc283 c)

题目大意

要在屏幕上输入一个数字\(S\)，有以下 \(11\)种操作，其中 \(10\)种就是输入数字 \(0,1,2,3,4,5,6,7,8,9\)，跟正常输手机号码一样，还有一种操作是连输入两个 \(0\)（即\(00\)，但算一次操作） 。问最小的输入次数。

解题思路

连续的\(0\)的区间必定是若干次 \(00\)和一次 \(0\)（如果需要的话）。因此答案就是每个连续 \(0\)区间\(0\)的个数除以 \(2\)的上取整和其他数的个数。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    int ans = 0;
    int cnt = 0;
    for(auto &i : s){
        if (i == '0'){
            ++ cnt;
        }else{
            ans ++;
            ans += (cnt + 1) / 2;
            cnt = 0;
        }
    }
    ans += (cnt + 1) / 2;
    cout << ans << '\n';

    return 0;
}

D - Scope (abc283 d)

题目大意

给定一个合法的括号序列，其中夹杂着若干个小写字母。依次扫描这个序列的每个字符。

  • 如果是小写字母，则放到对应的盒子里（即 a放到盒子a）里。若对应盒子已经有东西，则扫描失败。
  • 如果是 (，则什么都不做。
  • 如果是)，则找到与其匹配的(，将这期间的放入盒子的字母都扔掉。

问扫描是否成功。

解题思路

因为字母只有\(26\)个，因此当遇到一个 )时，我们不必扫描原序列，而只用看这\(26\)个盒子是否有要扔掉的即可。

记录每个盒子放入时的下标，即可知道要不要扔掉。

括号匹配，用栈即可求得与)匹配的(的下标。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    auto check = [&](){
        int n = s.size();
        vector<int> pos(26, -1);
        stack<int> left;
        for(int i = 0; i < n; ++ i){
            if (s[i] == '('){
                left.push(i);
            }else if (s[i] == ')'){
                assert(!left.empty());
                int l = left.top();
                left.pop();
                for(int i = 0; i < 26; ++ i)
                    if (pos[i] >= l)
                        pos[i] = -1;
            }else{
                if (pos[s[i] - 'a'] != -1)
                    return false;
                pos[s[i] - 'a'] = i;
            }
        }
        return true;
    };
    if (check())
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';

    return 0;
}

E - Don't Isolate Elements (abc283 e)

题目大意

给定一个\(01\)矩阵。可以进行一种操作，该操作为翻转某行的 \(01\)值。

问操作次数的最小值，使得不存在一个位置，其上下左右的值都与其不同。

解题思路

因为一个位置合不合法涉及到上下左右四个方向，我们从上往下\(dp\)时，因为当前行的下的位置还未做决策，因此不能判断当前行是否合法，得留到后面来判断。

除此之外，我们称一个位置为危险位置，当仅当上左右的值与其不同。转移时要判断是否合法，即要判断每一列是不是危险位置，需要知道当前行和上一行的翻转状态才能知道。

即设\(dp[i][j]\)表示前 \(i\)行，最后两行的翻转状态为 \(j\)，且前\(i-1\)行都合法的最小操作次数。转移则枚举前两行和当前行的翻转状态即可。

注意从最后一行得答案时还要判断最后一行的合法性。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int inf = 1e9 + 7;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int h, w;
    cin >> h >> w;
    vector<vector<int>> a(h, vector<int>(w, 0));
    for(auto &i : a)
        for(auto &j : i)
            cin >> j;
    vector<vector<int>> dp(h, vector<int>(4, inf));
    dp[0][0] = 0;
    dp[0][1] = 1;
    dp[0][2] = 0;
    dp[0][3] = 1;
    auto danger = [&](int x, int y, int s){
        int s1 = ((s >> 1) & 1);
        int s2 = (s & 1);
        int cnt = 0;
        if (x == 0 || (a[x - 1][y] ^ s1) != (a[x][y] ^ s2))
            ++ cnt;
        if (y == 0 || (a[x][y - 1] ^ s2) != (a[x][y] ^ s2))
            ++ cnt;
        if (y == w - 1 || (a[x][y + 1] ^ s2) != (a[x][y] ^ s2))
            ++ cnt;
        return cnt == 3;
    };

    auto valid = [&](int x, int s, int ls, int sign){
        int s1 = (ls & 1);
        int s2 = (s & 1);
        for(int i = 0; i < w; ++ i){
            if (danger(x - 1, i, ls) && (sign || (a[x - 1][i] ^ s1) != (a[x][i] ^ s2)))
                return false;
        }
        return true;
    };
    for(int i = 1; i < h; ++ i){
        for(int j = 0; j < 2; ++ j)
            for(int k = 0; k < 4; ++ k)
                if (valid(i, j, k, 0)){
                    int sign = ((k & 1) << 1);
                    int nxstat = (j | sign);
                    dp[i][nxstat] = min(dp[i][nxstat], dp[i - 1][k] + (j == 1));
                }
    }
    int ans = inf;
    for(int i = 0; i < 4; ++ i)
        if (valid(h, 0, i, 1))
            ans = min(ans, dp[h - 1][i]);
    if (ans == inf)
        ans = -1;
    cout << ans << '\n';

    return 0;
}

F - Permutation Distance (abc283 f)

题目大意

给定一个排列\(p\)，求 \(d\)数组，其中 \(d_i = \min\limits_{j \neq i} ( |p_i - p_j| + |i - j| )\)

解题思路

将绝对值去掉，得

\[\begin{aligned} d_i = \min \{& \min_{j < i, p_j < p_i} (p_i + i - (p_j + j) ), \\ & \min_{j < i, p_j > p_i} (- p_i + i - (- p_j + j) ) \\ & \min_{j > i, p_j < p_i} (p_i - i - (p_j - j) ) \\ & \min_{j > i, p_j > p_i} (- p_i - i - (- p_j - j) ) \} \\ = \min \{& p_i + i + \min_{j < i, p_j < p_i} (- (p_j + j) ), \\ -&p_i + i + \min_{j < i, p_j > p_i} (- (- p_j + j) ) \\ & p_i - i + \min_{j > i, p_j < p_i} (- (p_j - j) ) \\ -&p_i - i + \min_{j > i, p_j > p_i} (- (- p_j - j) ) \} \end{aligned} \]

里面四项每一个都是一个二维偏序问题（满足两个不等关系的条件下求最值）。分别解之取最小值即可。

二维偏序的解法，即通过循环满足一个不等式关系（即满足一维），再用一个数据结构维护另一个不等式关系（维护另一维）求最值。

以第一个偏序问题为例，即枚举下标\(i\)，把小于 \(j\)的加入到数据结构中（满足了 \(j < i\)），然后在满足小于\(p_i\)中找到最小的 \(p_j + j\)。即对\(p_i\)建立一棵线段树， 其位置（为\(p_i\)，不是 \(i\)）维护的值是\(p_i + i\)。然后查询\([1,p_i - 1]\)的最小值。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int inf = 1e9 + 7;
const int N = 2e5 + 8;

class segment{
    #define lson (root << 1)
    #define rson (root << 1 | 1)
    public:

    int minn[N << 2];

    void build(int root, int l, int r){
        if (l == r){
            minn[root] = inf;
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        minn[root] = min(minn[lson], minn[rson]);
    }

    void update(int root, int l, int r, int pos, int val){
        if (l == r){
            minn[root] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(lson, l, mid, pos, val);
        else 
            update(rson, mid + 1, r, pos, val);
        minn[root] = min(minn[lson], minn[rson]);
    }

    int query(int root, int l, int r, int ll, int rr){
        if (ll > rr)
            return inf;
        if (ll <= l && r <= rr){
            return minn[root];
        }
        int mid = (l + r) >> 1;
        int ans = inf;
        if (ll <= mid)
            ans = min(ans, query(lson, l, mid, ll, rr));
        if (rr > mid)
            ans = min(ans, query(rson, mid + 1, r, ll, rr));
        return ans;
    }
}sg1, sg2, sg3, sg4;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; ++ i)
        cin >> a[i];
    vector<int> ans(n + 1, inf);
    sg1.build(1, 1, n);
    sg2.build(1, 1, n);
    for(int i = 1; i <= n; ++ i){
        ans[i] = min(ans[i], a[i] + i + sg1.query(1, 1, n, 1, a[i] - 1));
        ans[i] = min(ans[i], i - a[i] + sg2.query(1, 1, n, a[i] + 1, n));
        sg1.update(1, 1, n, a[i], -(a[i] + i));
        sg2.update(1, 1, n, a[i], -(-a[i] + i));
    }
    sg3.build(1, 1, n);
    sg4.build(1, 1, n);
    for(int i = n; i >= 1; -- i){
        ans[i] = min(ans[i], a[i] - i + sg3.query(1, 1, n, 1, a[i] - 1));
        ans[i] = min(ans[i], -i - a[i] + sg4.query(1, 1, n, a[i] + 1, n));
        sg3.update(1, 1, n, a[i], -(a[i] - i));
        sg4.update(1, 1, n, a[i], -(-a[i] - i));
    }
    for(int i = 1; i <= n; ++ i)
        cout << ans[i] << " \n"[i == n];

    return 0;
}

貌似还可以看成点\((i, p_i)\)，然后问曼哈顿距离的最小值。对原图求一遍曼哈顿距离最小生成树，与之相连的边距离取个最小值。

G - Partial Xor Enumeration (abc283 g)

题目大意

给定一个\(n\)个数的数组\(A\)，任选数进行异或，可得异或集合 \(S\)，问该集合里第 \(l\)到第 \(r\)小的数分别是多少。

解题思路

其实就是异或线性基求第\(k\)大的裸题。

即对\(n\)个数求得一组线性基，假设该线性基有\(k\)个，这意味着这\(n\)个数在二进制下张成了一个\(k\)维空间。

然后对这\(k\)个线性基正交化后（类似于二维空间的两个基\((1,0),(0,1)\)，或三位空间的两个基 \((1,0,0),(0,1,0),(0,0,1)\)，即正交基组成的矩阵是个对角阵），这个时候各维互不干扰，可以选择也可以不选择。

那么第 \(k\)小（从\(0\)开始）的值就是其二进制下为\(1\)的位数（即维度）的那些线性基的异或值。

即\(k=b_4b_3b_2b_1b_0\)，那么其值就是 \(b_4ji_4 \oplus b_3ji_3 \oplus b_2ji_2 \oplus b_1ji_1 \oplus b_0ji_0\)

其正确性感觉很显然吧，这些线性基本身有大小关系，而且选择与否不会影响到其他维度的值，然后线性基本身只有选和不选两种，感觉就跟二进制数一样，第\(0\)小就是什么都不选（\(0\)），第 \(1\)小就是选最小的（\(1\)），第 \(2\)小就是选择 \(ji_1\)（\(10\)），第三小就是选择 \(ji_1\)和 \(ji_0\)（\(11\)）.

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    LL l, r;
    cin >> n >> l >> r;
    vector<LL> ji(64, 0);
    for(int i = 0; i < n; ++ i){
        LL a;
        cin >> a;
        for(int j = 60; j >= 0; -- j){
            if (((a >> j) & 1) && ji[j] == 0){
                ji[j] = a;
                break;
            }
            else if (((a >> j) & 1)){
                a ^= ji[j];
            }
        }
    }
    for(int i = 60; i >= 0; -- i)
        for(int j = i + 1; j <= 60; ++ j)
            if ((ji[j] >> i) & 1)
                ji[j] ^= ji[i];
    vector<LL> jj;
    for(int i = 0; i <= 60; ++ i)
        if (ji[i])
            jj.push_back(ji[i]);
    -- l;
    -- r;
    for(LL i = l; i <= r; ++ i){
        LL ans = 0;
        int pos = 0;
        LL tmp = i;
        while(tmp){
            if (tmp & 1)
                ans ^= (jj[pos]);
            ++ pos;
            tmp >>= 1;
        }
        cout << ans << " \n"[i == r];
    }

    return 0;
}

Ex - Popcount Sum (abc283 h)

题目大意

给定\(n,m,r\)，问 \([1,n]\)中满足 \(i \mod m = r\)的所有 \(i\)的二进制下 \(1\)的个数的和。

多组数据。

解题思路

<++>

神奇的代码

标签：AtCoder,Beginner,min,int,cin,long,ans,using,283
From： https://www.cnblogs.com/Lanly/p/17003594.html

相关文章

  • abc--283--E
    关键跟炮兵阵地那道题目很像，先确定上面哪一行的状态，然后在确定下面这一行的状态，采用dp就可以枚举所有的状态代码#include<bits/stdc++.h>usingnamespacestd;const......
  • abc 283 E Don't Isolate Elements
    abc283EDon'tIsolateElements题意:给出一个\(h*w\)的01矩阵，对于每一行，可以进行翻转操作。如果\(a_{i,j}\)的上下左右没有一个和它数值一样的话，这个点就被称......
  • atcoder
    AGC001D题目大意：有一个长度为\(m\)的序列\(a\)，它的和为\(n\)，需要将\(a\)重排，并构造一个任意长度但和为\(n\)的序列\(b\)，使得对任意长度为\(n\)的字符串，如果......
  • 283. 移动零
    给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。示例1:输入:nums=[0,......
  • [翻译]写给初学者的源代码安装指南Beginner's Guide to Installing from Source
    写给初学者的源代码安装指南引入本文档面向希望直接从原始作者处安装软件的开源操作系统用户，而不是仅依赖其操作系统提供的软件（和版本）。它是为那些不熟悉以源代码形式下......
  • AtCoder Beginner Contest 282
    https://atcoder.jp/contests/abc282A-GeneralizedABC原题链接题意给出一个数\(k\)，输出A~Z中的前\(k\)个字母。分析从\(0\)到\(k\)枚举，将A加上\(i\)输......
  • AtCoder Beginner Contest 282
    《MakeBipartite2》思维，二分图  这个简单图可以有两种情况：1.全部点都通过边连起来，即连通分量只有一个，其自己2.还有有些点没有全部连起来，即有多个连通分......
  • 【LeeCode】283. 移动零
    【题目描述】给定一个数组 ​​nums​​​，编写一个函数将所有 ​​0​​ 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进......
  • (AtCoder Beginner Contest 282) D - Make Bipartite 2(二分图)
    题目大意：给定一个n个点m条边的图，请你在其中加一条边使得整个图G是二分图，问有多少种可能。（已有的边不能加）解题思路：首先我们要知道，二分图内是没有长度为奇数的回路的所......
  • atcoder ABC 282(A-C)
    A输入k，要从A打印到第k个大写字母。只要看懂题目就行。#include<iostream>usingnamespacestd;intmain(){ intk; scanf("%d",&k); for(inti=0;i<k;i++){ prin......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99