欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

2018HDU 多校一

程序员文章站 2022-06-09 17:48:05
...

A. Maximum Multiple

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6298

题意：给出一个整数N，找到3个整数N = X + Y + Z，且N是X,Y,Z的倍数，使得X*Y*Z最大，无解输出-1.

题解：2018HDU 多校一, 因此按照N是否能被三或者四整除即可。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while(T --) {
        int n;
        cin >> n;
        if(n % 3 == 0) {
            int t = n / 3;
            cout << t * 1LL * t * t << '\n';
        } else if(n % 4 == 0) {
            int t1 = n / 2;
            int t2 = n / 4;
            cout << t1 * 1LL * t2 * t2 << '\n';
        } else {
            cout << "-1\n";
        }
    }
    return 0;
}

B. Balanced Sequence

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6299

题意

给你n个包含’(‘与’)’的字符串，可以将这些字符串任意排序，求所有排序中，子序列是正规括号序列的最大长度。

题解

首先我们对所有的字符串找到通过stack找到所有的串内正规括号子序列，之后剩下的串只有三种可能: 
1. 只包含’(’ 
2. 先是一串’)’然后再是一串’(’ 
3. 只包含’)’ 
然后，按照第一类，第二类，第三类的顺序放置串。对于第二类内的排序，首先按照’(‘个数贡献正负排序,’)’个数小于’(‘个数则贡献为正，贡献是正的则排前面。然后正贡献的串，我们按照’)’个数从小到大排。负贡献的串，我们按照’(‘个数从大到小排。对于排序完的串，我们从前往后模拟记录一下即可。

#include <bits/stdc++.h>

using namespace std;
const int maxn = 100007;
struct node {
    string s;
    int lc, rc;
    node () {}
    node (string ss, int l, int r) : s(ss), lc(l), rc(r) {}
} a[maxn], b[maxn], c[maxn];
char sta[5000009];
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while(T --) {
        int n, res = 0;
        int tot1 = 0, tot2 = 0, tot3 = 0, sz = 0;
        cin >> n;
        for(int i = 1; i <= n; ++i) {
            string s;
            cin >> s;
            sz = 0;
            for(char c : s) {
                if(!sz) sta[++sz] = c;
                else {
                    if(c == '(') {
                        sta[++sz] = c;
                    } else {
                        if(sta[sz] == '(') res += 2, --sz;
                        else sta[++sz] = c;
                    }
                }
            }
            if(sz) {
                int lc = 0, rc = 0;
                s.clear();
                for(int j = 1; j <= sz; ++j) {
                    if(sta[j] == '(') lc ++;
                    else rc ++;
                    s = s + sta[j];
                }
                if(lc == rc) {
                    b[++tot2] = {s, lc, rc};
                } else if(lc > rc) {
                    a[++tot1] = {s, lc, rc};
                } else {
                    c[++tot3] = {s, lc, rc};
                }
            }
        }
        sort(a + 1, a + 1 + tot1, [&](node & t1, node & t2) {
            return t1.rc < t2.rc;
        });
        sort(c + 1, c + 1 + tot3, [&](node & t1, node & t2) {
            return t1.lc > t2.lc;
        });
        sz = 0;
        auto solve = [&] (node * a, int tot) {
            for(int i = 1; i <= tot; ++i) {
                for(char c : a[i].s) {
                    if(!sz) sta[++sz] = c;
                    else {
                        if(c == '(') {
                            sta[++sz] = c;
                        } else {
                            if(sta[sz] == '(') res += 2, --sz;
                            else sta[++sz] = c;
                        }
                    }
                }
            }
        };
        solve(a,tot1);
        solve(b,tot2);
        solve(c,tot3);
        cout << res << '\n';
    }
    return 0;
}

C. Triangle Partition

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6300

题意:

给出3*N个点，让你输出N个三角形使得他们互不相交， 题目输出保证不会有三点共线。

题解：

因为不会有三点共线的情况，所以按照X坐标排序，顺次输出即可。

#include <bits/stdc++.h>

using namespace std;
#define fi first
#define se second

int main()
{
    int T;
    cin >> T;
    while(T --) {
        int n;
        cin >> n;
        vector< pair<pair<int,int>,int> > p (n * 3);
        for(int i = 0; i < n * 3; ++i) {
            cin >> p[i].fi.fi >> p[i].fi.se;
            p[i].se = i + 1;
        }
        sort(p.begin(), p.end());
        for(int i = 0; i < n * 3; i += 3) {
            cout << p[i].se << ' ' << p[i+1].se << ' ' << p[i+2].se << '\n';
        }
    }

    return 0;
}

 

D. Distinct Values

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6301

题意：

构造一个长度为N的数组， 给出M个限制, 每个限制给出[L,R]区间，需要保证[L,R]区间内的数不能有重复，满足M个限制，且字典序最小的数组。

题解：

对于每个位置i维护一下他往前最远不能冲突的位置pre[i]，定义一个指针cur,表示现在指针到的位置,维护下即可。

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 7;
int pre[maxn];
int ret[maxn];
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while(T --) {
        int n, m;
        cin >> n >> m;
        for(int i = 1; i <= n; ++i) pre[i] = i;
        for(int i = 0; i < m; ++i) {
            int l, r;
            cin >> l >> r;
            pre[r] = min(pre[r], l);
        }
        for(int i = n - 1; i >= 1; --i) pre[i] = min(pre[i], pre[i+1]);
        int cur = 1;
        priority_queue<int, vector<int>, greater<int> > pq;
        for(int i = 1; i <= n; ++i) pq.push(i);
        for(int i = 1; i <= n; ++i) {
            while(cur < pre[i]) {
                pq.push(ret[cur++]);
            }
            ret[i] = pq.top();
            pq.pop();
        }
        for(int i = 1; i <= n; ++i) {
            if(i == 1) cout << ret[i];
            else cout << ' ' << ret[i];
        }
        cout << '\n';
    }
    return 0;
}

G. Chiaki Sequence Revisited

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6304

题意：

2018HDU 多校一

题解：

解：2018HDU 多校一

 2018HDU 多校一

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int a[1024];
int cnt[1024];
const int MOD = 1e9 + 7;

const ll inv2 = (MOD + 1) / 2;

void dabiao()
{
    a[1] = a[2] = 1;
    for(int i = 3; i < 1000; ++i) {
        a[i] = a[i - a[i-1]] + a[i-1-a[i-2]];
    }
    for(int i = 2; i < 1000; ++i) cnt[a[i]] ++;
    for(int i = 2; i < 500; i += 2) {
        cout << cnt[i / 2] << ' ' << cnt[i] << '\n';
    }
}

ll calc(ll n)
{
    if(n <= 1) return n;
    else return n + calc(n / 2);
}
ll solve(ll n)
{
    ll up, st = 1, ed = n;
    while(st <= ed) {
        ll mid = (st + ed) / 2;
        if(calc(mid) > n) ed = mid - 1;
        else st = mid + 1;
    }
    ll rest = n - calc(ed);
    ll res = 0;
    ll c = 1;
    for(ll i = 1; ;i <<= 1, ++c) {
        if(i > ed) break;
        ll fir = i % MOD;
        ll det = i * 2 % MOD;
        ll cnt = ((ed - i) / (2 * i)) % MOD;
        ll last = (fir + cnt * det) % MOD;
        res = (res + c * ((fir + last) * (cnt + 1) % MOD * inv2 % MOD) % MOD )  % MOD;
    }
    res = (res + (ed + 1) * rest) % MOD;
    ++res;
    if(res >= MOD) --res;
    else if(res < 0) res += MOD;
    return res;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
//    for(int i = 1; i <= 1000;i ++) cout << calc(i) << endl;
    cin >> T;
    while(T --) {
        ll n;
        cin >> n;
        -- n;
        cout << solve(n) << '\n';
    }
    return 0;
}

 K. Time Zone

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6308

题意：

给出一个标准时间UTF+8， 给出一个当前时间和时区，计算当前标准时间。

题解：

全部转换成分钟计算，注意浮点数处理。

#include <bits/stdc++.h>

using namespace std;
int main()
{
    int T;
    scanf("%d", &T);
    while(T --) {
        int h, m;
        double d;
        scanf("%d %d UTC%lf", &h, &m, &d);
        h = h * 60 + m;
        int c = 0;
        if(d > 0) {
            c = (int)(d * 10 + 0.1);
        } else {
            c = (int)(d * 10 - 0.1);
        }
        c = c * 6 - 80 * 6;
        h += c;
        h %= (24 * 60);
        if(h < 0) h += 24 * 60;
        printf("%02d:%02d\n", h / 60, h % 60);
    }
    return 0;
}

 

上一篇： Photoshop 一张超简洁的光影壁纸

下一篇： cookie.js 加载顺序问题怎么才有效_jquery

推荐阅读