Atcoder 269

标签：std Atcoder int tt cin long ++ 269

T1:计算（a + b） * (c - d) 输出字符串

点击查看代码

#include<bits/stdc++.h>
 
using i64 = long long;
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int tt = 1; //std::cin >> tt;
 
    while(tt--){
        int a, b, c, d; 
        std::cin >> a >> b >>c >> d;
        std::cout << (a + b) * (c - d) << '\n';
        std::cout << "Takahashi" << '\n';
    }
 
    return 0;
}

T2:给定只含". #"字符矩阵，其中存在一个子矩阵完全由"#"组成，求该子矩阵的上下行数和左右列数
显然上行数必定是所有"#"row的最小值，其它类似

点击查看代码

#include<bits/stdc++.h>
 
using i64 = long long;
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int tt = 1; //std::cin >> tt;
 
    while(tt--){
        std::vector<std::string> s(10);
        for(int i = 0; i < 10; ++i){
            std::cin >> s[i];
        }
 
        int a = 9, b = 0, c = (int)s[0].size() - 1, d = 0;
        for(int i = 0; i < 10; ++i){
            int l, r;
            for(int j = 0; j < (int)s[j].size(); ++j){
                if(s[i][j] == '#'){
                    a = std::min(a, i);
                    b = std::max(b, i);
                    c = std::min(c, j);
                    d = std::max(d, j);
                }
            }
        }
        std::cout << a + 1 << ' ' << b + 1 << '\n' << c + 1 << ' ' << d + 1 << '\n';
    }
 
    return 0;
}

T3：求某个数的二进制意义下的子集

点击查看代码

#include<bits/stdc++.h>
 
using i64 = long long;
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    i64 n; std::cin >> n;
 
    std::vector<i64> a;
 
    for(i64 i = n; i; i = (i - 1) & n){
        a.push_back(i);
    }
    a.push_back(0);
 
    std::reverse(a.begin(), a.end());
 
    for(auto x : a){
        std::cout << x << '\n';
    }
 
    return 0;
}

T4：给定坐标位于蜂窝坐标内，求连通块数目
dfs求连通块即可

点击查看代码

#include<bits/stdc++.h>
 
using i64 = long long;

std::vector<int> xx = {-1, -1, 0, 0, 1, 1}, yy = {-1, 0, -1, 1, 0, 1};
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int tt = 1; //std::cin >> tt;
 
    while(tt--){
        int n; std::cin >> n;
 
        std::vector<int> x(n), y(n);
        for(int i = 0; i < n; ++i){
            std::cin >> x[i] >> y[i];
        }
 
        std::vector<int> vis(n); int res = 0;
 
        std::map<std::pair<int, int>, int> q;
        for(int i = 0; i < n; ++i){
            q[{x[i], y[i]}] = i;
        }
        std::function<void(int, int)> dfs = [&] (int xz, int yz){
            for(int k = 0; k < 6; ++k){
                int xxx = xz + xx[k], yyy = yz + yy[k];
                if(!q.count({xxx, yyy})){
                    continue;
                }else{
                    int p = q[{xxx, yyy}];
                    if(vis[p]){
                        continue;
                    }else{
                        vis[p] = 1;
                        dfs(xxx, yyy);
                    }
                }
            }
        };
 
        for(int i = 0; i < n; ++i){
            if(!vis[i]){
                vis[i] = 1;
                dfs(x[i], y[i]);
                ++res;
            }
        }
        std::cout << res << '\n';
    }
    return 0;
}

T5：给定n * n矩阵，其中放置了n - 1个棋子，两两不可互相攻击，求某个位置使得所有点两两互不攻击，可以证明该位置必定唯一存在
根据互不攻击的特性，分别二分出该位置的row和col即可

点击查看代码

#include<bits/stdc++.h>
 
using i64 = long long;
 
 
std::vector<int> xx = {-1, -1, 0, 0, 1, 1}, yy = {-1, 0, -1, 1, 0, 1};
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int tt = 1; //std::cin >> tt;
 
    while(tt--){
        int n; std::cin >> n;
 
        int xx, yy;
        int a = 1, b = n, c = 1, d = n, x, y;
          while(a != b){
              int mid = (a + b) >> 1;
              std::cout << "? " << a << " " << mid << " " << c << " " << d << std::endl;
              std::cin >> x;
              int s1 = mid - a + 1 - x;
              if(s1 == 1){
                  b = mid;
              }else{
                  a = mid + 1;
              }
          }
          xx = a;
          a = 1, b = n;
          while(c != d){
              int mid = (c + d) >> 1;
              std::cout << "? " << a << " " << b << " " << c << " " << mid << std::endl;
              std::cin >> x;
              int s1 = mid - c + 1 - x;
              if(s1 == 1){
                  d = mid;
              }else{
                  c = mid + 1;
              }
          }
          yy = c;
          std::cout << "! " << xx << ' ' << yy << '\n';
    }

    return 0;
}

T6：给定A，B，C，D, M，求：

\[\sum_{i = A}^{B}\sum_{j = C}^{D}(i - 1) * M + j \,\, [(i + j) \& 1 == 0] \]

暴力肯定超时,考虑优化，考虑贡献来源分为i和j，且二者可以完全分离（分奇偶两种情况）
先考虑j的贡献：
1.若i为奇数，j只能取偶数
2.若i为偶数，j只能取奇数
此时j的贡献均可由等差数列求和公式快速求出
考虑i的贡献：
M提出，则也可经等差数列求和公式快速求出
然后注意求和后乘上个数后求和即可
tip:对于求贡献的题，尝试将其来源的不同分为完全独立的几部分，然后对于这些独立的部分进行优化求和，最后所有部分求和来达到优化的目的

点击查看代码

#include<bits/stdc++.h>

using i64 = long long;

constexpr int P = 998244353;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m; std::cin >> n >> m;

    int tt = 1; std::cin >> tt;

    while(tt--){
        int a, b, c, d; std::cin >> a >> b >> c >> d;

        int p1 = ((a + c) & 1) ? c + 1 : c, p2 = (p1 == c) ? c + 1 : c;
        int p3 = a - 1, p4 = a;

        int num1 = (((d - c + 1) & 1) == 1 && ((a + d) & 1) == 0) ? (d - c + 1) / 2 + 1: (d - c + 1) / 2, num2 = d - c + 1 - num1;
        int num3 = (b - a + 1) & 1 ? (b - a + 1) / 2 + 1 : (b - a + 1) / 2, num4 = b - a + 1 - num3;

        // std::cout << p1 << ' ' << p2 << ' ' << p3 << ' ' << p4 << '\n';
        // std::cout << num1 << ' ' << num2 << ' ' << num3 << ' ' << num4 << '\n';

        i64 sum1 = (i64)((p1 + num1 - 1) % P + P) % P * num1 % P, sum2 = (i64)((p2 + num2 - 1) % P + P) % P * num2 % P;
        i64 sum3 = (i64)((p3 + num3 - 1) % P + P) % P * num3 % P, sum4 = (i64)((p4 + num4 - 1) % P + P) % P * num4 % P;

        // std::cout << sum1 << ' ' << sum2 << ' ' << sum3 << ' ' << sum4 << '\n';

        i64 res {0};

        res = (res + (i64)(sum1 * num3) % P) % P;
        res = (res + (i64)(sum2 * num4) % P) % P;

        res = (res + (i64)sum3 * num1 % P * m % P) % P;
        res = (res + (i64)sum4 * num2 % P * m % P) % P;

        std::cout << res << '\n';
    }
}

T7：给定n张卡片，正面值为Ai，背面值为Bi，满足\(\sum_{i = 1}^{n}\)(Ai + Bi) = M
问最少的翻片数（正面变反面）使得翻片后正面值之和为i(i <= M)
一开始的数值之和为S，预处理出翻篇S的变化值，于是转换成为了一个0/1背包问题，但是会超时（O(NM)），考虑优化：
tip：dp的优化就哪几个方面，多深入理解吧，哎
预处理后，变化值为\(C_i\),对变化值相同的进行计数，记为\(F_i\)
优化性质：|F| <= 2\(\sqrt{M}\)

\[\sum_{i = 1}^{n}|C_i| <= M（*） \]

反证：|F| > 2\(\sqrt{M}\)

\[ |-\sqrt{M}| + |(-\sqrt{M} + 1)| + ... + |(\sqrt{M} - 1)| + |{\sqrt{M}}| > M \]

与（*）矛盾，故必有|F| <= 2 * \(\sqrt{M}\)
此时转化为了多重背包，时间复杂度为O(M\(\sum_{i = 1}^{|F|}Fi\)),已经可以通过此题
对于多重背包，我们还可以进行二进制优化，时间复杂度优化至为O(M\(\sum_{i = 1}^{|F|}\,log_{2}{F_i}\))

点击查看代码

#include<bits/stdc++.h>
 
using i64 = long long;
constexpr int P = 998244353;
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int tt = 1; //std::cin >> tt;
 
    while(tt--){
        int n, m; std::cin >> n >> m;
 
        std::vector<int> c(n); int sum = 0;
        for(int i = 0; i < n; ++i){
            int a, b; std::cin >> a >> b;
            c[i] = b - a; sum += a;
        }
 
        std::vector<int> x;
        std::map<int, int> q;
        for(int i = 0; i < n; ++i){
            if(!q.count(c[i])){
                q[c[i]] = 1;
                x.push_back(c[i]);
            }else{
                q[c[i]]++;
            }
        }
        
        std::vector<int> w, v;
        for(int i = 0; i < (int)x.size(); ++i){
            int num = q[x[i]];
            int r = 1;
            while(r <= num){
                w.push_back(x[i] * r);
                v.push_back(r);
                num -= r;
                r <<= 1;
            }
            if(num){
                w.push_back(x[i] * num);
                v.push_back(num);
            }
        }
 
        std::vector<int> dp(m + 1, n + 1); dp[sum] = 0;
        for(int i = 0; i < (int)w.size(); ++i){
            std::vector<int> dpx(dp);
            for(int j = 0; j <= m; ++j){
                if(0 <= j + w[i] && j + w[i] <= m){
                    dpx[j + w[i]] = std::min(dpx[j + w[i]], dp[j] + v[i]);
                }
            }
            dp = dpx;
        }
 
        for(auto xx : dp){
            std::cout << (xx <= n ? xx : -1) << '\n';
        }
    }
 
    return 0;
}

T8:树上背包肯定超时，转移过程用NTT优化，依旧超时。
tip:似乎树上背包可以有一种优化(改造树的形状使其按照某种解法也可以获取答案)，这题似乎可以借鉴一下(改造树后，按照类似方法NTT)

标签：std,Atcoder,int,tt,cin,long,++,269
From： https://www.cnblogs.com/iqer/p/16711990.html

相关文章

赞助商

阅读排行