首页 > 其他 > 详细

Codeforces Round #594 (Div. 2)

时间：2019-10-22 10:26:39      阅读：121      评论：0      收藏：0      [点我收藏+]

目录

Contest Info

Practice Link

Solved A B C D1 D2 E F
4/7 O O O O - -
  • O 在比赛中通过
  • ? 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Solutions

A. Integer Points

题意：
\(A\)给出\(n\)条直线，形式为\(y = x + p_i\), \(B\)给出\(m\)条直线，形式为\(y = -x + q_i\)。
问有多少个二元组\((i, j)\)，使得\(i\)表示\(A\)的直线，\(j\)表示\(B\)的直线，并且这两条直线有整数交点。

思路：
考虑两条直线的交点\(x + p_i = -x + q_i\)，那么\(x = \frac{q_i - p_i}{2}\)。
那么\(p_i, q_i\)的奇偶性要相同才可以。

代码：


view code

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define fi first
#define se second
#define endl "\n" 
using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long; 
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } 
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }  
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0) 
void err() { cout << "\033[39;0m" << endl; } 
template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A> 
void err(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; err(args...); }
inline void pt() { cout << endl; } 
template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << ' '; pt(args...); }
template <template<typename...> class T, typename t, typename... A> 
void pt(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; pt(args...); }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
//head
constexpr int N = 1e5 + 10;
int n, m, cnt[2][2]; 
void run() {
    memset(cnt, 0, sizeof cnt);
    n = rd();
    for (int i = 1; i <= n; ++i) {
        ++cnt[0][rd() % 2];
    }
    m = rd();
    for (int i = 1; i <= m; ++i) {
        ++cnt[1][rd() % 2];
    }
    pt(1ll * cnt[0][0] * cnt[1][0] + 1ll * cnt[0][1] * cnt[1][1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T; cin >> _T;
    while (_T--) run();
    return 0;
}

B. Grow The Tree

题意：
给出一些线段，要求从\((0, 0)\)出发放置这些线段，类似于这样：
技术分享图片
并且交替放置，就是一根横着，一根竖着这样放。
问从\((0, 0)\)到终点的距离的平方最大是多少。

思路：
考虑横着的距离为\(a\)，竖着的距离为\(b\)，那么距离的平方为\(a^2 + b^2\)，并且有\(a + b\)是定长。
并且我们发现当\(b\)等于\(0\)时最长，但是因为有限制，所以将最小的\(n / 2\)根竖着放，其余的横着放

代码：


view code

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define fi first
#define se second
#define endl "\n" 
using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long; 
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } 
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }  
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0) 
void err() { cout << "\033[39;0m" << endl; } 
template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A> 
void err(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; err(args...); }
inline void pt() { cout << endl; } 
template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << ' '; pt(args...); }
template <template<typename...> class T, typename t, typename... A> 
void pt(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; pt(args...); }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
//head
constexpr int N = 1e5 + 10;
int n, a[N]; 
void run() {
    for (int i = 1; i <= n; ++i) a[i] = rd();
    sort(a + 1, a + 1 + n);
    ll A = 0, B = 0;
    int mid = n / 2;
    for (int i = 1; i <= mid; ++i) {
        A += a[i];
    }
    for (int i = mid + 1; i <= n; ++i) {
        B += a[i];
    }
    pt(A * A + B * B);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout << fixed << setprecision(20);
    while (cin >> n) run();
    return 0;
}

C. Ivan the Fool and the Probability Theory

题意：
在一个\(n \cdot m\)的\(01\)矩形上，每个位置可以放\(0\)或者\(1\)，现在询问有多少种方案使得每个数和它相邻的最多四个数中最多只有一个和它相同。

思路：

  • 如果第一行中有两个连续相同的，那么下面的行放什么是唯一确定的
  • 如果第一行中是交替放的，那么可以将这个视为整体，然后看成一行的情况。

并且如果只有一行的情况我们直接\(dp\)出来，\(f[i][j][k]\)表示前\(i\)个位置，前一个位置放\(j\)，当前位置放\(k\)的方案数。

代码：


view code

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define fi first
#define se second
#define endl "\n" 
using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long; 
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } 
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }  
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0) 
void err() { cout << "\033[39;0m" << endl; } 
template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A> 
void err(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; err(args...); }
inline void pt() { cout << endl; } 
template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << ' '; pt(args...); }
template <template<typename...> class T, typename t, typename... A> 
void pt(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; pt(args...); }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
//head
constexpr int N = 1e5 + 10;
int n, m, f[N][2][2];  
void run() {
    if (n == 1 && m == 1) return pt(2);
    if (n > m) swap(n, m);
    memset(f, 0, sizeof f);
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            f[2][i][j] = 1;
    for (int i = 3; i <= m; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                for (int o = 0; o < 2; ++o) {
                    if (!(j == k && j == o)) {
                        chadd(f[i][k][j], f[i - 1][o][k]);
                    }
                }
            }
        }
    }
    ll res = 0;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
        //  dbg(i, j, f[m][i][j]);
            chadd(res, f[m][i][j]);
            chadd(res, f[n][i][j]);
        }
    }
    chadd(res, -2); 
    if (n == 1) chadd(res, 2);
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout << fixed << setprecision(20);
    while (cin >> n >> m) run();
    return 0;
}

D1. The World Is Just a Programming Task (Easy Version)

题意：
有一个括号序列，现在可以交换两个位置的括号，问哪种交换方案使得存在很多的循环移位方案使得它是一个合法的括号序列。

思路：
枚举交换方案，并且根据一个括号序列是合法的当前仅当\(f[i] \leq 0\)，\(f[i]\)表示前\(i\)个括号中右括号个数减去左括号个数

代码：


view code

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define fi first
#define se second
#define endl "\n" 
using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long; 
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } 
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }  
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0) 
void err() { cout << "\033[39;0m" << endl; } 
template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A> 
void err(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; err(args...); }
inline void pt() { cout << endl; } 
template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << ' '; pt(args...); }
template <template<typename...> class T, typename t, typename... A> 
void pt(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; pt(args...); }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
//head
constexpr int N = 1e3 + 10, INF = 0x3f3f3f3f;
int n, a[N], f[N], g[N], h[N]; char s[N]; 
int calc() {
    f[0] = g[0] = h[n + 1] = 0;
    for (int i = 1; i <= n; ++i) f[i] = f[i - 1] + a[i];
    for (int i = 1; i <= n; ++i) g[i] = max(g[i - 1], f[i]);
    for (int i = n; i >= 1; --i) h[i] = max(h[i + 1], f[i]);
    if (f[n] != 0) return 0; 
    int res = 0; 
    for (int i = n; i >= 1; --i) {
        if (h[i] - f[i - 1] <= 0 && g[i - 1] + (f[n] - f[i - 1]) <= 0)
            ++res;  
    }
    return res;
}
void run() {
    cin >> (s + 1);
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '(') a[i] = -1;
        else a[i] = 1;
    }
    int num = calc(), x = 1, y = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            swap(a[i], a[j]);
            int now = calc();
            if (now > num) {
                num = now;
                x = i, y = j;
            }
            swap(a[i], a[j]);
        }
    }
    pt(num);
    pt(x, y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout << fixed << setprecision(20);
    while (cin >> n) run();
    return 0;
}

Codeforces Round #594 (Div. 2)

原文：https://www.cnblogs.com/Dup4/p/11717787.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！