题解报告（CDUT暑期集训——第一场）

- 日理万妓 2023-08-17 16:22 121阅读 0赞

# **题解报告（CDUT暑期集训——第一场）** #

--------------------

## **A - Maximum Multiple** ##

### [HDU - 6298][] ###

*  **思路：先按照题意打表 发现规律 就出来了（最开始没开long long贡献了3发 然后又忘了换行又贡献了一发**
 *  AC代码

--------------------

#include<bits/stdc++.h> typedef long long ll; typedef unsigned long long ull; using namespace std; ll Pow(ll a, ll b, ll c){ ll ans = 1; a %= c; while (b){ if (b & 1) ans = (ans * a) % c; a = (a * a) % c; b >>= 1; } return (ans % c); } bool cmp(const int &a, const int &b){ return a < b; } ll gcd(ll x, ll y){ return x % y == 0 ? y : gcd(y, x % y); } ll lcm(ll x, ll y){ return x / gcd(x, y) * y; } const int MAXN = 2000 + 5; const int mod = 1e9 + 7; ll comb[MAXN][MAXN]; void init(){ for (int i = 0; i < MAXN; i ++ ){ comb[i][0] = comb[i][i] = 1; for (int j = 1; j < i; j ++ ){ comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1]; comb[i][j] %= mod; } } } ll mult_mod(ll a, ll b, ll c){ a %= c; b %= c; ll res = 0; while (b){ if (b & 1){ res += a; res %= c; } a <<= 1; a %= c; b >>= 1; } return res; } int main(){ ll t; scanf("%lld", &t); ll n; while (t--){ scanf("%lld", &n); if (n % 12 == 1 || n % 12 == 2 || n % 12 == 5 || n % 12 == 7 || n % 12 == 10 || n % 12 == 11) printf("-1\n"); else{ if (n % 3) printf("%lld", (n / 4) * (n / 4) * (n / 4) * 2); else printf("%lld", (n / 3) * (n / 3) * (n / 3)); } } return 0; }

## **B - Balanced Sequence** ##

### [HDU - 6299][] ###

*  **思路：贪心 先把每个串里面的括号匹配之后去掉 再对它们排序 匹配剩下的括号就行了（开始莫名其妙MLE了九发 找不到原因 然后再交TLE RE 后面发现cmp写错了 改了之后就过了**
 *  AC代码

--------------------

#include<stdio.h>
    #include<iostream>
    #include<math.h>
    #include<algorithm>
    #include<string>
    #include<string.h>
    typedef long long ll;
    typedef unsigned long long ull;
    using namespace std;
    
    const int N = 100010;
    
    int n, t, ans, cnt_l;
    char c[N];
    
    struct st{
        int l;
        int r;
    }s[N];
    
    bool cmp(st a, st b){
        if (a.l > a.r && b.l <= b.r) return true;
        else if (a.l <= a.r && b.l > b.r) return false;
        else if (a.l > a.r && b.l > b.r) return a.r < b.r;
        else return a.l > b.l;
    }
    
    int main(){
        scanf("%d", &t);
        while (t --){
            ans = 0;
            cnt_l = 0;
            scanf("%d", &n);
            for (int i = 1; i <= n; i ++ ){
                s[i].l = 0;
                s[i].r = 0;
                scanf("%s", c);
                for (int j = 0; j < strlen(c); j ++ ){
                    if (c[j] == '(') s[i].l ++;
                    if (c[j] == ')') s[i].l == 0 ? s[i].r ++ : (s[i].l -= 1, ans += 2);
                }
            }
            sort(s + 1, s + n + 1, cmp);
            for (int i = 1; i <= n; i ++ ){
                if (s[i].r > cnt_l) s[i].r = cnt_l;
                ans += 2 * s[i].r;
                cnt_l += s[i].l - s[i].r;
            }
            printf("%d\n", ans);
        }
        return 0;
    }

## **C - Triangle Partition** ##

### [HDU - 6300][] ###

*  **思路：贪心 写个struct对x排个序就出来了（**
 *  AC代码

--------------------

#include<bits/stdc++.h> typedef long long ll; typedef unsigned long long ull; using namespace std; ll Pow(ll a, ll b, ll c){ ll ans = 1; a %= c; while (b){ if (b & 1) ans = (ans * a) % c; a = (a * a) % c; b >>= 1; } return (ans % c); } //bool cmp(const int &a, const int &b){ // return a < b; //} ll gcd(ll x, ll y){ return x % y == 0 ? y : gcd(y, x % y); } ll lcm(ll x, ll y){ return x / gcd(x, y) * y; } const int MAXN = 2000 + 5; const int mod = 1e9 + 7; ll comb[MAXN][MAXN]; void init(){ for (int i = 0; i < MAXN; i ++ ){ comb[i][0] = comb[i][i] = 1; for (int j = 1; j < i; j ++ ){ comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1]; comb[i][j] %= mod; } } } ll mult_mod(ll a, ll b, ll c){ a %= c; b %= c; ll res = 0; while (b){ if (b & 1){ res += a; res %= c; } a <<= 1; a %= c; b >>= 1; } return res; } const int N = 1010; struct point{ int x, y; int index; }p[N]; bool cmp(point a, point b){ if (a.x == b.x) return a.y < b.y; return a.x < b.x; } int main(){ int t; scanf("%d", &t); int n; while (t--){ scanf("%d", &n); for (int i = 1; i <= 3 * n; i ++ ){ scanf("%d%d", &p[i].x, &p[i].y); p[i].index = i; } sort(p + 1, p + 3 * n + 1, cmp); for (int i = 1; i <= n; i ++ ) printf("%d %d %d\n", p[(i - 1) * 3 + 1].index, p[(i - 1) * 3 + 2].index, p[(i - 1) * 3 + 3].index); } return 0; }

## **D - Distinct Values** ##

### [HDU - 6301][] ###

*  **思路：贪心 先排序 后用set维护就行了（学到了一个新东西 迭代器赋值前要加\* 要不然会报错** 
 *  AC代码

--------------------

#include<stdio.h> #include<iostream> #include<math.h> #include<algorithm> #include<string.h> #include<queue> #include<set> typedef long long ll; typedef unsigned long long ull; using namespace std; ll Pow_mod(ll a, ll b, ll c){ ll ans = 1; a %= c; while (b){ if (b & 1) ans = (ans * a) % c; a = (a * a) % c; b >>= 1; } return (ans % c); } const int N = 1000010; int t, n, m, L, R; set<int> st; int ans[N]; struct node{ int l, r; }interval[N]; int cmp(node a, node b){ return a.l == b.l ? a.r < b.r : a.l < b.l; } int main(){ scanf("%d", &t); while (t -- ){ st.clear(); scanf("%d%d", &n, &m); for (int i = 1; i <= m; i ++ ) scanf("%d%d", &interval[i].l, &interval[i].r); sort(interval + 1, interval + m + 1, cmp); L = interval[1].l; R = interval[1].r; for (int i = 1; i <= n; i ++ ){ st.insert(i); ans[i] = 1; } for (int i = L; i <= R; i ++ ){ ans[i] = *st.begin(); st.erase(st.begin()); } for (int i = 2; i <= m; i ++ ){ while (L < interval[i].l){ st.insert(ans[L]); L ++; } while (R < interval[i].r){ if (R < interval[i].l - 1) R ++; else{ R ++; ans[R] = *st.begin(); st.erase(st.begin()); } } } for (int i = 1; i < n; i ++ ) printf("%d ", ans[i]); printf("%d\n", ans[n]); } }

## **G - Chiaki Sequence Revisited** ##

### [HDU - 6304][] ###

*  **思路：先打表 找规律 令f(i)为i出现的次数 再打表 去掉a1 = 1出现的一次 可以得到f(2 \* i) = f(i) + 1 f(2 \* i + 1) = 1 当时到了这里就卡死了 卡了两个半小时 然后想着把f(i) = n, n = 1, 2, 3, ...打印出来看下 结果一打印就发现了f(i)相同的构成了一个首项为2^(n-1) 公差为2^n的等差数列 就直接根据公式就解出来了 结束前没能写出来 结束之后几分钟写好交了三发才过 第一发用自己写的乘法取膜函数tle了 第二发有一处忘了取膜贡献了一发wa 第三发才终于过了**
 *  AC代码

--------------------

#include<bits/stdc++.h> typedef long long ll; typedef unsigned long long ull; using namespace std; ll Pow_mod(ll a, ll b, ll c){ ll ans = 1; a %= c; while (b){ if (b & 1) ans = (ans * a) % c; a = (a * a) % c; b >>= 1; } return (ans % c); } ll Pow(ll a, ll b){ ll ans = 1; while (b){ if (b & 1) ans *= a; a *= a; b >>= 1; } return ans; } bool cmp(const int &a, const int &b){ return a < b; } ll gcd(ll x, ll y){ return x % y == 0 ? y : gcd(y, x % y); } ll lcm(ll x, ll y){ return x / gcd(x, y) * y; } const int MAXN = 2000 + 5; const int mod = 1e9 + 7; ll comb[MAXN][MAXN]; void init(){ for (int i = 0; i < MAXN; i ++ ){ comb[i][0] = comb[i][i] = 1; for (int j = 1; j < i; j ++ ){ comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1]; comb[i][j] %= mod; } } } ll mult_mod(ll a, ll b, ll c){ a %= c; b %= c; ll res = 0; while (b){ if (b & 1){ res += a; res %= c; } a <<= 1; a %= c; b >>= 1; } return res; } const int N = 63; ll s[N], t[N]; ll calc(ll n){ ll tmp = 0; if (n == 1) return 1; n -= 1; for (int i = N - 1; i >= 0; i -- ){ while (s[i] <= n){ n -= s[i]; tmp += t[i]; } } return tmp; } ll get_pos(ll n){ ll pos = 0; if (n == 1) return 1; n -= 1; for (int i = N - 1; i >= 0; i -- ){ while (t[i] <= n){ n -= t[i]; pos += s[i]; } } return pos + 1; } int main(){ s[0] = 1; t[0] = 1; for (int i = 1; i < N; i++){ s[i] = s[i - 1] * 2 + 1; t[i] = t[i - 1] * 2; } int T; scanf("%d", &T); ll n; while (T--){ scanf("%lld", &n); ll tmp = calc(n); ll cnt = n - get_pos(tmp); ll sum = 0; for (int i = 1; t[i - 1] <= tmp; i ++ ){ ll b1 = t[i - 1]; ll d = t[i]; ll n_ = (tmp - b1) / d; if ((tmp - b1) % d) n_ += 1; ll bn = b1 + (n_ - 1) * d; ll sum_b = (b1 % mod + bn % mod) * (n_ % mod) * 500000004 % mod; sum += i * sum_b % mod; sum %= mod; if (!((tmp - b1) % d)) sum += (cnt % mod) * (tmp % mod) % mod; sum %= mod; } printf("%lld\n", sum + 1); } return 0; }

## **K - Time Zone** ##

### [HDU - 6308][] ###

*  **思路：数学题 把时区差换算成时间差（分钟） 然后换算过去就行了 最开始写了个贼蠢的模拟 写的很长 还wa了 后面才想起来没写%02d才wa的**
 *  AC代码

--------------------

#include<bits/stdc++.h> typedef long long ll; typedef unsigned long long ull; using namespace std; ll Pow(ll a, ll b, ll c){ ll ans = 1; a %= c; while (b){ if (b & 1) ans = (ans * a) % c; a = (a * a) % c; b >>= 1; } return (ans % c); } bool cmp(const int &a, const int &b){ return a < b; } ll gcd(ll x, ll y){ return x % y == 0 ? y : gcd(y, x % y); } ll lcm(ll x, ll y){ return x / gcd(x, y) * y; } const int MAXN = 2000 + 5; const int mod = 1e9 + 7; ll comb[MAXN][MAXN]; void init(){ for (int i = 0; i < MAXN; i ++ ){ comb[i][0] = comb[i][i] = 1; for (int j = 1; j < i; j ++ ){ comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1]; comb[i][j] %= mod; } } } ll mult_mod(ll a, ll b, ll c){ a %= c; b %= c; ll res = 0; while (b){ if (b & 1){ res += a; res %= c; } a <<= 1; a %= c; b >>= 1; } return res; } int main(){ int t; scanf("%d", &t); int a, b; while (t--){ char flag; double utc; scanf("%d %d UTC%c%lf", &a, &b, &flag, &utc); int tmp = (int)(utc * 10 + 0.1); if (flag == '-') tmp = -tmp; int sum = a * 60 + b + (tmp * 6 - 8 * 60); sum %= (24 * 60); if (sum < 0) sum += (24 * 60); printf("%02d:%02d\n", sum / 60, sum % 60); } return 0; }

转载于:https://www.cnblogs.com/Misuchii/p/11211178.html

[HDU - 6298]: http://acm.hdu.edu.cn/showproblem.php?pid=6298
[HDU - 6299]: http://acm.hdu.edu.cn/showproblem.php?pid=6299
[HDU - 6300]: http://acm.hdu.edu.cn/showproblem.php?pid=6300
[HDU - 6301]: http://acm.hdu.edu.cn/showproblem.php?pid=6301
[HDU - 6304]: http://acm.hdu.edu.cn/showproblem.php?pid=6304
[HDU - 6308]: http://acm.hdu.edu.cn/showproblem.php?pid=6308