首页 > 其他 > 详细

Educational Codeforces Round 76 (Rated for Div. 2)

时间：2019-11-14 20:10:04      阅读：75      评论：0      收藏：0      [点我收藏+]

传送门

A. Two Rival Students

签到。


Code

/*
 * Author:  heyuhhh
 * Created Time:  2019/11/13 22:37:26
 */
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '\n'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
 
int n, x, a, b;
 
void run(){
    cin >> n >> x >> a >> b;
    if(a > b) swap(a, b);
    int tmp = min(a - 1, x);
    x -= tmp;
    a -= tmp;
    tmp = min(n - b, x);
    x -= tmp;
    b += tmp;
    cout << b - a << '\n';
} 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int t; cin >> t;
    while(t--) run();
    return 0;
}

B. Magic Stick

分情况讨论一下即可。
神志不清讨论地很乱


Code

/*
 * Author:  heyuhhh
 * Created Time:  2019/11/13 22:42:05
 */
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '\n'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
 
int a, b;
 
void run(){
    cin >> a >> b;
    if(a == 1) {
        if(b == 1) return pt("YES");
        else return pt("NO");
    }
    if(a >= b) return pt("YES");
    if(a > 3) return pt("YES");
    if(b <= 3) return pt("YES");
    pt("NO");
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int t; cin >> t;
    while(t--) run();
    return 0;
}

C. Dominated Subarray

题意：
给出\(n\)个数，找到长度最短的区间，满足区间长度大于\(1\)且存在一个数其出现次数严格大于其它数。

思路：
显然最终的答案区间两端点为同一个数，考虑一个这样的区间，如果其不合法，说明存在一个答案更优的区间。
并且若那个数出现次数超过\(2\)次，我们选择一个更小的区间使得这个数只出现\(2\)次，此时有两种情况：一个是合法，那显然答案更优；另一个是不合法，说明答案也可以更优。
就这样归纳一下，发现答案就是两个相同数的最小间隔。
然而我神智不清，写了个线段树


Code

/*
 * Author:  heyuhhh
 * Created Time:  2019/11/13 22:49:57
 */
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '\n'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;
 
int n;
int a[N];
int pre[N], last[N];
int maxv[N << 2];
 
void upd(int o, int l, int r, int p, int v) {
    if(p == 5) dbg(l, r);
    if(l == r) {
        maxv[l] = v;
        return;   
    }
    int mid = (l + r) >> 1;
    if(p <= mid) upd(o << 1, l, mid, p, v);
    else upd(o << 1|1, mid + 1, r, p, v);
    maxv[o] = max(maxv[o << 1], maxv[o << 1|1]);
}
 
int query(int o, int l, int r, int L, int R) {
    if(L > R) return 0;
    if(L <= l && r <= R) {
        return maxv[o];
    }   
    int mid = (l + r) >> 1, res = 0;
    if(L <= mid) res = query(o << 1, l, mid, L, R);
    if(R > mid) res = max(res, query(o << 1|1, mid + 1, r, L, R));
    return res;
}
 
void build(int o, int l, int r) {
    maxv[o] = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1|1, mid + 1, r);   
}
 
void run(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], last[a[i]] = 0;
    if(n == 1) return pt(-1);
    build(1, 1, n);
    for(int i = 1; i <= n; i++) {
        pre[i] = last[a[i]];
        last[a[i]] = i;
        upd(1, 1, n, i, pre[i]);
        dbg(i, pre[i]);
    }
    dbg(query(1, 1, n, 5, 5), pre[5]);
    int ans = INF;
    for(int i = 1; i <= n; i++) {
        if(pre[i]) {
            int L = pre[i] + 1, R = i - 1;
            dbg(i, L, R);
            if(query(1, 1, n, L, R) < L) ans = min(ans, R - L + 3);
        }   
    }
    if(ans == INF) ans = -1;
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int T; cin >> T;
    while(T--) run();
    return 0;
}

D. Yet Another Monster Killing Problem

题意：
现在有\(n\)只怪，每只怪有力量\(a_i\)。
同时有\(n\)个英雄，每个英雄有\(p_i,s_i\)分别代表力量和耐力。
每一天只能选派一个英雄去打怪兽，每个英雄最多打\(s_i\)只怪，一个英雄能打败一只怪，当且仅当其力量不低于怪兽的力量。
一个英雄可以被选派多次。
问最少需要多少天能打败所有的怪兽。

思路：

  • 考虑\(dp:dp[i]\)表示打败前\(i\)只怪兽最少需要多少天，显然\(dp[i]=min\{dp[j]+1\}\)
  • \(j\)满足存在一个英雄，能从\(j+1\)打到\(i\)，显然这个\(j\)的位置具有单调性。
  • 发现\(dp\)值也是单调不降的，那么我们就可以找一个最远的\(j\)进行转移，二分即可。
  • 二分的话，可以对英雄的耐力维护一个后缀最大值，即\(maxv[s]\)表示耐力\(\geq s\)的英雄中，最大的力量为多少；同时维护怪兽力量的区间最大值，这里\(rmq\)维护即可。两个判断一下就行。

神志不清写了一年


Code

/*
 * Author:  heyuhhh
 * Created Time:  2019/11/13 23:47:28
 */
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '\n'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;
 
int n, m;
int a[N];
struct node{
    int s, p;   
    bool operator < (const node &A) const {
        return s < A.s;   
    }
}b[N];
int f[N][22];
int lg[N];
void init() {
    lg[2] = 1;
    for(int i = 3; i < N; i++) lg[i] = lg[i >> 1] + 1;   
}
int ask(int l, int r) {
    int k = lg[r - l + 1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);   
}
int dp[N], maxv[N];
bool chk(int l, int r) {
    int mx = ask(l, r);
    int i = lower_bound(b + 1, b + m + 1, node{r - l + 1, 0}) - b;
    return maxv[b[i].s] >= mx;
}
int get(int x) {
    int l = 1, r = x + 1, mid;
    while(l < r) {
        mid = (l + r) >> 1;
        if(chk(mid, x)) r = mid;
        else l = mid + 1;
    }   
    return r;
}
void run(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], f[i][0] = a[i];
    for(int i = 1; i <= 20; i++) {
        for(int j = 1; j + (1 << (i - 1)) <= n; j++) {
            f[j][i] = max(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
        }
    }
    cin >> m;
    for(int i = 1; i <= m; i++) cin >> b[i].p >> b[i].s;
    sort(b + 1, b + m + 1);
    b[m + 1].s = 0;
    for(int i = m; i >= 1; i--) {
        maxv[b[i].s] = max(maxv[b[i + 1].s], b[i].p);   
    }
    if(maxv[b[1].s] < ask(1, n)) return pt(-1);
    dp[0] = 0;
    for(int i = 1; i <= n; i++) {
        int p = get(i) - 1;
        dp[i] = dp[p] + 1;
    }
    cout << dp[n] << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    init();
    int T; cin >> T;
    while(T--) run();
    return 0;
}

E. The Contest

题意：
给出三个集合，每个集合里面装了一些数，这些数的并集为\(1\)~\(n\)的排列。
现在可以移动任意一个数从一个集合到另外一个集合。
问最少的移动次数使得\(1\)集合中为一个前缀\(1,\cdots,k\)，然后\(2\)集合中\(k+1,\cdots,p\)，\(3\)集合中\(p+1,\cdots,n\)。（可以有集合为空集）。

思路：

  • 考虑枚举\(1\)集合中装的前缀的长度，然后将其余的所有数我们先移到\(3\)集合中，并且给这些数打上标记，表示删除这些数不消耗额外的次数。
  • 之后我们要操作一些数，使得\(3\)集合中的数为一个后缀。
  • 显然我们对\(3\)集合的操作是删掉前面的一些数，然后填补后面的空格。假设\(3\)集合中的数为\(p\)~\(n\)，那么我们用\(pre[i]\)表示\(3\)集合中原来有的数的前缀，\(suf[i]\)表示后缀空格的数量。那么显然我们枚举\(i,i\geq p\)，求出\(min\{pre[i]-pre[p-1]+suf[i+1]\}\)即可。
  • 显然\(p\)随着枚举\(1\)集合前缀个数时在不断增大，那么直接维护后缀\(pre[i]+suf[i+1]\)的最小值即可。

时间复杂度\(O(n)\)。也可以\(dp\)来做，\(dp[i][j]\)表示第\(i\)个数在第\(j\)个集合的最小操作次数。因为分布连续，直接分情况考虑即可。
然而神志不清，想了好久都没想清楚


Code

/*
 * Author:  heyuhhh
 * Created Time:  2019/11/14 9:29:05
 */
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
//#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '\n'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;
 
int k1, k2, k3, n;
int a[N], b[N], c[N];
int suf[N], pre[N], sum[N], Min[N];
int f[N];
 
void run(){
    n = k1 + k2 + k3;
    memset(f, 0, sizeof(f));
    for(int i = 1; i <= k1; i++) cin >> a[i];
    for(int i = 1; i <= k2; i++) cin >> b[i];
    for(int i = 1; i <= k3; i++) cin >> c[i];
    int tot = 0;
    int i = 1, j = 1;
    for(int i = 1; i <= k1; i++) f[a[i]] = 2;
    for(int i = 1; i <= k3; i++) f[c[i]] = 1;
    for(int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + (f[i] == 1);
    }
    for(int i = n; i >= 1; i--) {
        suf[i] = suf[i + 1] + (f[i] == 0);
    }
    for(int i = n; i >= 0; i--) {
        if(i == n) Min[i] = pre[i];
        else Min[i] = min(Min[i + 1], pre[i] + suf[i + 1]);
    }
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (f[i] == 2);
    int ans = INF;
    for(int i = 0; i <= n; i++) {
        dbg(i, pre[i], suf[i], Min[i] - pre[i]);
        ans = min(ans, i - 2 * sum[i] + sum[n] - pre[i] + Min[i]);
    }
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    while(cin >> k1 >> k2 >> k3) run();
    return 0;
}

F. Make Them Similar

题意：
给出\(n,n\leq 100\)个数，现在定义两个数相似为其二进制\(1\)的个数相同。
现在问能否找到一个数\(x\)，使得这\(n\)个数都异或上\(x\)，并且最终都相似。
\(a_i\leq 2^{30}-1\)。

思路：

  • 显然我们要从二进制的每一位来考虑，但是直接来考虑又显然不行。
  • 注意到二进制位不超过\(30\)，那么可以考虑\(meet\ in\ middle\)的方法：即折半处理，预处理出一边，然后枚举这一边。
  • 预处理一边后随便用个\(map\)或哈希一下存储即可。

感觉这个比前几个稍微还简单点？
可能是因为我之前神志不清hhh


Code

/*
 * Author:  heyuhhh
 * Created Time:  2019/11/14 15:21:26
 */
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '\n'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 100 + 5;
 
int n;
int a[N];
 
unordered_map<string, int> mp;
string trans(int x) {
    string res = "";
    if(x > 9) {
        res += ((x / 10) + '0');
        res += ((x % 10) + '0');
    } else res += (x + '0');
    return res;
}
void run(){
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < 1 << 15; i++) {
        for(int k = 0; k <= 30; k++) {
            int ok = 1;
            for(int j = 1; j <= n; j++) {
                int x = (a[j] >> 15) ^ i;        
                if(__builtin_popcount(x) > k) ok = 0;
            }
            if(ok) {
                string tmp = "";
                for(int j = 1; j <= n; j++) {
                    int x = (a[j] >> 15) ^ i;
                    tmp += trans(k - __builtin_popcount(x));
                }
                if(mp.find(tmp) == mp.end())
                    mp[tmp] = i;
            }
        }
    }
    for(int i = 0; i < 1 << 15; i++) {
        string tmp = "";
        for(int j = 1; j <= n; j++) {
            int x = ((a[j] >> 15) << 15) ^ a[j];
            x ^= i;
            tmp += trans(__builtin_popcount(x));
        }
        if(mp.find(tmp) != mp.end()) {
            int ans = (mp[tmp] << 15) + i;
            cout << ans << '\n';
            return;   
        }
    }
    cout << -1 << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    while(cin >> n) run();
    return 0;
}

Educational Codeforces Round 76 (Rated for Div. 2)

原文：https://www.cnblogs.com/heyuhhh/p/11861110.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 版权所有
打开技术之扣，分享程序人生！