07月24, 2018

7.23 杭电多校1题解及补题

比赛过程

这场比较失败。 开场卡A,想到了一个直观的解法。不告诉队友结果gg,后来仔细分析一下,才过的。

D认为是个贪心,没贪出来,全场卡了nlogn算法,不知道什么鬼

时区题是个傻逼题,很快过了

B题认为贪心,但是没找到比较好的贪心策略,可以说,只贪对了一半

Xander全场梦游

题解

A

题意

求f[i] = max{a b c| i % a == 0 && i % b ==0 && i % c==0 && a + b + c == i}

解法

不难发现 1 = 1 / 2 + 1 /4 + 1 /4; 1 = 1 / 3 + 1 / 3 + 1 / 3; 1 = 1 / 3 + 1 / 2 + 1 / 6;

判断能否被3 4 整除即可

代码

#include <cstdio>

int main() {
  int T;
  scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) {
    int n;
    scanf("%d", &n);
    if (n % 3 == 0) printf("%lld\n", 1ll * n * n * n / 27);
    else if (n % 4 == 0) printf("%lld\n", 1ll * n * n * n / 32);
    else puts("-1");
  }
  return 0;
}

B

题意

求n个字符串任意排列后可以得到的最大的括号匹配个数

解法

每个字符串处理后可以得到形如))))((((的字符串,那么使得右括号少的尽量往左

代码

#include <bits/stdc++.h>
#define REP(i, x, n) for (int i = (x); i < (n); ++i)
#define PER(i, x, n) for (int i = (n) -1; i >= x; --i)
#define endl "\n"
#define DE puts("----------")
#define CASE(i, ans) cout << "Case #" << (i) << ": " << (ans) << "\n"
#define lowbit(x) ((x) & (-(x)))
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define PI acos(-1.0)
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll n, m, k;
const long long mod = 1000000007;
struct node {
    string s;
    int l;
    int r;
};
node *s;
node anss;
int ans = 0;
bool cmp(node y, node x) {
    if (x.l >= x.r && y.l < y.r) return false;
    if (x.l < x.r && y.l >= y.r) return true;
    if (x.l >= x.r && y.l >= y.r) return x.r > y.r;
    return x.l < y.l;
}
stack<char> q;
void fuck(node &x) {
    int t = (int) x.s.size();
    while (!q.empty()) q.pop();
    string p = "";
    REP(i, 0, t) {
        if (x.s[i] == ')') {
            if (!q.empty() && q.top() == '(') {
                q.pop();
                ans++;
            } else {
                q.push(')');
            }
        } else {
            q.push('(');
        }
    }
    x.r = (int) q.size();
    x.l = 0;
    while (!q.empty() && q.top() == '(') {
        q.pop();
        x.l++;
        x.r--;
    }
    REP(i, 0, x.r) {
        p += ')';
    }
    REP(i, 0, x.l) {
        p += '(';
    }
    x.s = p;
}
int main() {
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    // cout << unsigned(-1);
    while (t--) {
        cin >> n;
        ans = 0;
        s = new node[n + 1];
        REP(i, 0, n) {
            cin >> s[i].s;
        }
        REP(i, 0, n) {
            fuck(s[i]);
        }
        stable_sort(s, s + n, cmp);
        while (!q.empty()) q.pop();
        REP(i, 0, n) {
            int sz = s[i].s.size();
            REP(j, 0, sz) {
                if (s[i].s[j] == ')') {
                    if (!q.empty() && q.top() == '(') {
                        q.pop();
                        ans++;
                    } else {
                        q.push(')');
                    }
                } else {
                    q.push('(');
                }
            }
        }
        cout << ans * 2 << endl;
    }
    return 0;
}

C

题意

给定3N个点,任意三点不共线,请将其构造为N个不相交的三角形

解法

假设有一个扫描线,我们从x轴开始向后扫即可

代码

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define REP(i, x, n) for (int i = (x); i < (n); ++i)
#define PER(i, x, n) for (int i = (n) -1; i >= x; --i)
#define endl "\n"
#define DE puts("----------")
#define CASE(i, ans) cout << "Case #" << (i) << ": " << (ans) << "\n"
#define lowbit(x) ((x) & (-(x)))
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define PI acos(-1.0)
#define MOD 1000000007
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
__gnu_pbds::cc_hash_table<string, int> hash1;
__gnu_pbds::gp_hash_table<string, int> hash2;
__gnu_pbds::priority_queue<int> pq;
__gnu_pbds::tree<int, null_type, less<int>, rb_tree_tag> rbtree;
ll n, m, k;
const long long mod = 1000000007;
// int a[10000];
struct node {
    int a, b, i;
} s[4000];
bool cmp(node x, node y) {
    return x.a < y.a;
}
int main() {
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        REP(i, 0, 3 * n) {
            cin >> s[i].a >> s[i].b;
            s[i].i = i + 1;
        }
        sort(s, s + 3 * n, cmp);
        for (int i = 0; i < 3 * n; i += 3) {
            cout << s[i].i << " " << s[i + 1].i << " " << s[i + 2].i << endl;
        }
    }

    return 0;
}

D

题意

要求构造n个数的序列 满足[li,ri] 中的数不相同 而且字典序最小

解法

按照l 去掉重复和被包含的r,排序后,按顺序枚举

用set或者priority_queue维护可以使用的最小值即可

代码

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#define REP(i, x, n) for (int i = (x); i < (n); ++i)
#define PER(i, x, n) for (int i = (n) -1; i >= x; --i)
#define endl "\n"
#define DE puts("----------")
#define CASE(i, ans) cout << "Case #" << (i) << ": " << (ans) << "\n"
#define lowbit(x) ((x) & (-(x)))
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define PI acos(-1.0)
#define MOD 1000000007
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef bitset<1005> Bitset;
inline char gc() {
    static char buf[1 << 20], *h = buf, *t = buf;
    return (h == t && (t = (h = buf) + fread(buf, 1, 1 << 20, stdin), h == t) ? -1 : *h++);
}
template <typename T> inline bool read(T &x) {
    static int f;
    static char c;
    for (c = gc(), f = 1; !isdigit(c); c = gc()) {
        if (c == -1)
            return false;
        else if (c == 45)
            f = -1;
    }
    for (x = c - 48; isdigit(c = gc()); x = x * 10 + c - 48)
        ;
    return x *= f, true;
}
template <typename A, typename B> inline bool read(A &x, B &y) {
    return read(x) && read(y);
}
template <typename A, typename B, typename C> inline bool read(A &x, B &y, C &z) {
    return read(x) && read(y) && read(z);
}

int r[100020];
int a[100020];
set<int> qq;
int q[100020];
int n, m, t, li, ri;
int main() {
    read(t);
    while (t--) {
        read(n);
        read(m);
        qq.clear();
        memset(r, 0, sizeof r);
        memset(a, 0, sizeof a);
        memset(q, 0, sizeof q);
        int poss = 0;
        REP(i, 0, m) {
            read(li);
            read(ri);
            if (!r[li]) {
                q[poss] = li;
                poss++;
            }
            if (ri > r[li]) {
                r[li] = ri;
            }
        }
        int pos = 0;
        int sz = poss;
        int maxr = 0;
        REP(i, 1, n + 1) {
            if (!r[i]) {
                qq.insert(a[i]);
                continue;
            }
            if (a[r[i]]) {
                qq.insert(a[i]);
                continue;
            }
            if (a[i] == 0) {
                int pos = 1;
                REP(j, i, r[i] + 1) {
                    a[j] = pos;
                    pos++;
                    maxr = max(maxr, j);
                }
                li = i;
                qq.clear();
            } else {
                int j;
                for (j = maxr + 1; j < r[i] + 1; ++j) {
                    if (!qq.empty()) {
                        a[j] = *qq.begin();
                        qq.erase(a[j]);
                    } else
                        break;
                }
                int maxx = j - i + 1;  //可用数不够了,从最大值开始继续填数
                REP(k, j, r[i] + 1) {
                    a[k] = maxx++;
                }
                maxr = r[i];
                li = i;
            }
            qq.insert(a[i]);
        }
        REP(i, 1, n) {
            printf("%d ", a[i] == 0 ? 1 : a[i]);
        }
        printf("%d\n", a[n] == 0 ? 1 : a[n]);
    }
    return 0;
}

H

题意

定义RMQ相似为对于任意(l,r),A序列,B序列RMQ所在位置都相同,现在给定A,B序列为元素随机(0,1)区间实数,求A,B RMQ相似时B元素和的期望

解法

单个元素期望0.5 和期望n/2

不难发现,如果B要跟A RMQ相似,那么AB的笛卡尔树同构,建立A的笛卡尔树后,求出形成每个分支的概率,与总期望累乘即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define stack Stack
#define pii pair<int, int>
#define SZ(x) ((int) (x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int, int> PII;
const ll mod = 1000000007;
ll powmod(ll a, ll b) {
    ll res = 1;
    a %= mod;
    assert(b >= 0);
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

const int N = 1010000;
int stack[N], top, l[N], r[N], vis[N], n, x, _;
PII a[N];
ll inv[N], ret;
struct node {
    pii val, key;
    int l, r, f;
} d[N];
int dfs(int u) {
    int s = 1;
    // if (u == 0) s--;
    if (d[u].l) s += dfs(d[u].l);
    if (d[u].r) s += dfs(d[u].r);
    ret = ret * inv[s] % mod;
    return s;
}
void build(int n) {
    for(int i = 1; i <= n; ++i){
        d[i].val = a[i];
        d[i].l = 0;
        d[i].r = 0;
        d[i].f = 0;
    }
    int top = 1;
    stack[top] = 1;
    for (int i = 2; i <= n; i++) {
        while (top > 0 && d[i].val < d[stack[top]].val) //小根堆则改成小于
            top--;
        if (top > 0) // 右链中的节点
        {
            d[i].f = stack[top];
            d[i].l = d[stack[top]].r;
            d[d[stack[top]].r].f = i;
            d[stack[top]].r = i;
            stack[++top] = i;
        } else // 根节点
        {
            d[stack[1]].f = i;
            d[i].l = stack[1];
            stack[++top] = i;
        }
    }
    dfs(stack[1]);
}
int main() {
    inv[1] = 1;
    rep(i, 2, 1000001) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    for (scanf("%d", &_); _; _--) {
        scanf("%d", &n);
        rep(i, 1, n + 1) {
            scanf("%d", &x);
            a[i] = mp(-x, i);
        }
        ret = inv[2] * n % mod;
        build(n);
        printf("%lld\n", ret);
    }
}

K

题意

给你一个时区,转化为北京时间

解法

模拟,瞎搞

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    int h, m;
    char str[20];
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%s", &h, &m, str);
        // int T8 = h * 60 + m;
        int len = strlen(str);
        int pos = -1, pos2 = -1;
        bool flag = 1;
        for (int i = 0; i < len; ++i) {
            if (str[i] == '+') {
                flag = 1;
                pos = i;
            }
            if (str[i] == '-') {
                flag = 0;
                pos = i;
            }
            if (str[i] == '.') {
                pos2 = i;
            }
        }
        int x, y;
        if (pos2 != -1) {
            y = str[pos2 + 1] - '0';
            if (pos2 - pos == 2) {
                x = str[pos2 - 1] - '0';
            } else {
                x = (str[pos2 - 1] - '0') + 10 * (str[pos + 1] - '0');
            }
        } else {
            pos2 = len;
            y = 0;
            if (len - 2 == pos) {
                x = str[pos2 - 1] - '0';

            } else {
                x = (str[pos2 - 1] - '0') + 10 * (str[pos2 - 2] - '0');
            }
        }
        // cout << "x==" << x << endl;
        // cout << "y==" << y << endl;

        h -= 8;
        if (flag) {
            h += x;
            m += y * 6;

        } else {
            h -= x;
            m -= y * 6;
        }
        while (m < 0) {
            m += 60;
            h--;
        }
        while (m >= 60) {
            h++;
            m -= 60;
        }
        while (h < 0) {
            h += 24;
        }
        while (h >= 24) {
            h -= 24;
        }
        if (h < 10) {
            printf("0");
        }
        printf("%d:", h);
        if (m < 10) {
            printf("0");
        }
        printf("%d\n", m);

        // printf("%02d:%02d\n", h, m);
    }
}

本文链接:https://www.haolovej.com/post/hdumulti1.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。