hdu第一场多校

2018-07-23

1001.Maximum Multiple

找规律结论题,只有能整除3或4的才能拆.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 2e5 + 5;

int main()
{
    int T; scanf("%d", &T);
    while (T--)
    {
        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 printf("-1\n");
    }
     return 0;
}

1002.Balanced Sequence

贪心神题,我们都知道是先预处理自己能匹配的,然后安照莫一种顺序排序,但是试了一万种也不行… 这题没意思,没什么好讲的

/* ***********************************************
Author        :JiangYu
Created Time  :2018年07月23日 星期一 13时41分02秒
File Name     :2.cpp
************************************************ */
using namespace std;
#include <bits/stdc++.h>
const int N = 1e5 + 1024;
char str[N];
struct node{
    int a, b;
}no[N];
bool cmp(const node &o, const node &p) {
    if(o.a >= o.b && p.a < p.b)
        return 0;
    if(o.a < o.b && p.a >= p.b)
        return 1;
    if(o.a >= o.b && p.a >= p.b)
        return o.b > p.b;
    return o.a < p.a;
}
int main()
{
    //std::ios::sync_with_stdio(false);
    //freopen("out.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        int ans = 0;

        for(int i = 1; i <= n; ++i) {
            no[i].a = no[i].b = 0;
            scanf("%s", str);
            int len = strlen(str);
            for(int j = 0; j < len; j++)
		    {
                if(str[j] == '(')
                    no[i].b++;
                else
                {
                    //cout << str[j] << endl;
                    if(no[i].b > 0)
                        no[i].b--, ans += 2;
                    else
                        no[i].a++;
                }
            }
        }
        //cout << ans << endl;
        sort(no+1, no+1+n, cmp);
        int cnt = 0;
        for(int i = 1; i <= n; ++i) {
            //cout << no[i].b<< " " << no[i].a<<endl;
            //cout << cnt << endl;
            if(no[i].a > cnt) no[i].a = cnt;
            ans += no[i].a*2;
            cnt -= no[i].a;
            cnt += no[i].b;
        }

        printf("%d\n", ans);
    }
    return 0;

}

1003.Triangle Partition

因为保证了不存在三点共线,按x,y排序就好了.签到题.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 1e3 + 5;

struct Node{
    int x, y, id;
    bool operator<(const Node& o) const
    {
        if (x == o.x) return y < o.y;
        return x < o.x;
    }
}e[3 * N];

int main()
{
    int t; scanf("%d", &t);
    while (t--)
    {
        int n; scanf("%d", &n);
        n *= 3;
        for (int i = 0; i < n; i++)
        {
            scanf("%d%d", &e[i].x, &e[i].y);
            e[i].id = i + 1;
        }
        sort(e, e + n);
        for (int i = 0; i < n; i += 3)
            printf("%d %d %d\n", e[i].id, e[i + 1].id, e[i + 2].id);
    }

     return 0;
}

1004.Distinct Values

先把区间排序,然后从左往右,能盖小的就盖小的,用一个set来存能放的值.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 2e5 + 5;

struct Node{
    int l, r;
    bool operator<(const Node& o) const
    {
        if (l == o.l) return r > o.r;
        return l < o.l;
    }
}e[N];

int a[N];

int main()
{
    int T; scanf("%d", &T);
    while (T--)
    {
        int n, m; scanf("%d%d", &n, &m);
        for (int i = 0; i < m; i++)
            scanf("%d%d", &e[i].l, &e[i].r);
        sort(e, e + m);
        set<int> S;
        for (int i = 1; i <= n; i++) S.insert(i);
        int L = 1, R = 0;
        for (int i = 0; i < m; i++)
        {
            while (R < e[i].l - 1) a[++R] = 1;
            while (L < e[i].l) S.insert(a[L++]);
            while (R < e[i].r)
            {
                a[++R] = *S.begin();
                S.erase(S.begin());
            }
        }
        while (R < n) a[++R] = 1;
        for (int i = 1; i <= n; i++)
            printf("%d%c", a[i], " \n"[i == n]);
    }
     return 0;
}

1007.Chiaki Sequence Revisited

又是一个找规律题,队友写的,这题我基本上没干啥.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 1e3 + 5;

ll f[70], g[70];

int main()
{
    g[0] = f[0] = 1;
    for (int i = 1; i < 63; i++)
    {
        f[i] = 2 * f[i - 1] + 1;
        g[i] = (2 * g[i - 1] % MOD + (1ll << i) % MOD + (1ll << i - 1) % MOD * (f[i - 1] % MOD) % MOD) % MOD;
//        cout << i << " " << g[i] << endl;
    }
    int t; scanf("%d", &t);
    while (t--)
    {
        ll n; scanf("%lld", &n);
        ll ans = 1;
        --n;
        for (int i = 62; i >= 0; i--)
        {
            while (n >= f[i])
            {
                ans = (ans + g[i]) % MOD;
                ans = ((1ll << i) % MOD * ((n -= f[i]) % MOD) % MOD + ans) % MOD;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

1008.RMQ Similar Sequence

这个题很棒啊.首先你要知道什么是笛卡尔树 然后你就会发现$A,B RMQ Similar$就是$A, B$ 笛卡尔树相同. 其次,B的元素是在$0~1$的实数之间均匀分布,则其权值的期望为$ \frac{2}{n}$ 然后笛卡尔树的总数则为$ \frac{n!}{\prod_{i} size_{i}}$ ($n!$ 实际含义为 $ A_{n}^{n} $, $ \frac{n!}{\prod_{i} size_{i}}$ 含义为依次出去每个最大点的儿子数,画图便于理解)

/* ***********************************************
Author        :JiangYu
Created Time  :2018年07月24日 星期二 10时26分21秒
File Name     :8.cpp
************************************************ */

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 1024;
int mod = 1e9 + 7;
int a[N];
int stk[N], top, l[N], r[N], p[N];
ll inv[N], ret;

int dfs(int u) {
    int s = 1;
    if(l[u]) s += dfs(l[u]);
    if(r[u]) s += dfs(r[u]);
    ret = ret * inv[s] % mod;
    return s;
}
void build(int n) {
    int top = 0;
    for(int i = 1; i <= n; ++i) {
        l[i] = 0, r[i] = 0, p[i] = 0;
    }
    for(int i = 1; i <= n; ++i) {
        int k = top;
        while(k > 0 && a[stk[k-1]] < a[i]) --k;
        if(k) r[stk[k-1]] = i;
        if(k < top) l[i] = stk[k];
        stk[k++] = i;
        top = k;
    }
    for(int i = 1;  i <= n; ++i) {
        p[l[i]] = p[r[i]] = 1;
    }
    int rt = 0;
    for(int i = 1; i <= n; ++i) {
        if(p[i] == 0) rt = i;
    }
    dfs(rt);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    inv[1] = 1;
    int n;
    for(int i = 2; i <= 1000000; ++i)
        inv[i] = inv[mod %i] * (mod - mod/i) % mod;
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
        }
        ret = inv[2] * n % mod;
        build(n);
        printf("%d\n", ret);
    }
    
    return 0;
}

1009.Lyndon Substring

论文题,没意思,不补

1011.Time Zone

时区转换,遇到的唯一坑点就是$+0.2$有精度误差,耽误了蛮久.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 2e5 + 5;

int main()
{
    int T; scanf("%d", &T);
    while (T--)
    {
        int h, m; double f;
        scanf("%d%d UTC%lf", &h, &m, &f);
        int t = h * 60 + m - 480;
        t += round(f * 60);
        t %= 24 * 60;
        while (t < 0) t += 24 * 60;
        printf("%02d:%02d\n", t / 60, t % 60);
    }
     return 0;
}

所有文章