whu-contest-2019（online）

比赛网址：http://whu2019.contest.codeforces.com/group/YyBKO8xFiH/contest/102167

赛后总结：

T：今天参加了武汉大学校赛网络赛，在cf上做的。界面还是挺熟悉的。开始三个人分头看题，我从最后往前面看，最后一题是kuangbin的主席树模板题，觉得打板子时间有点长，先看有没有别的简单题。然后就看到了E，E题就是一道简单模拟题。map存一下，模拟即可，然后就A了。然后是金姐看了B题，开始打了，也A了。这次我们第一题A花了16分钟，第二题是在第一题后6分钟A的，时间有在进步吧。别的题因为一下子想不出来，我就开始搞F题了。然后板子上的是求第m小的，所以改了很久（丢人。。。），金姐后来帮我一起改，金姐发挥了她的智慧，我们终于搞样例出来了。。呜呜。然后TLE了，因为链式前向星head赋值的问题，for改了就过了。做出来的时候已经只剩下一个小时了，我们开始研究D题。金姐和彭彭和我说觉得是规律算式题，我们整了很久，都没整出来。有点像组合数学，但是没搞出来。今天就结束了。

　　最后比赛结束看到群里很多大佬在讲解题目。发现有很多未触及的知识盲区。想着自己如果主席树模板搞快点就可以和队友一起想更久了。dbq。

P：看的第一题是C题，后来才知道是线段树上二分。然后看了B题，谭总敲完E，金姐就去打B了，我跟谭总说了一遍B题题意。谭总跟我说了一下F题，我大概感觉确实是主席树（然而菜的我wqbh）。然后看了D题，因为发现榜上A的人相对较多，题目意思容易理解，跟金姐讲了一遍，一致觉得是规律题（确实算吧，但不知道卡特兰，规律完全找不出）所以我们想的还是有一点偏差，嗯。。杠D题杠到结束--。确实，知识盲区太大，自己太菜。

　J：这次只打了一道签到题，太菜了。进了D题找规律的坑就爬不出来了，呜呜呜呜。下次要是一个小时还做不出来，就要放弃！知识盲区还是太多。。。。

最后本队做出来B、E、F，罚时比较少。没做出来的先不提供题解（官方已给出）。

题解：

简单模拟

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#include<string>

#include<vector>

#include<ctime>

#include<stack>

using namespace std;

const int maxn = ;

#define MAX_DISTANCE 0x3f3f3f3f

#define mm(a,b) memset(a,b,sizeof(a))

#define ll long long

#define SIGN(A) ((A > 0) ? 1 : -1)

#define NO_DISTANCE 1000000

const int INF = 0x3f3f3f3f;

#define LL long long int

#define mod 1000000007

int gcd(int a, int b) { return a ==  ? b : gcd(b % a, a); }

ll x, y;

int n;

int main()

{

    int t;

    ll a;

    scanf("%d", &t);

    for (int k = ; k <= t; k++)

    {

        scanf("%d", &n);

        x = y = ;

        for (int i = ; i < n; ++i)

        {

            scanf("%lld", &a);

            if (i %  == )

                x += a;

            else if (i %  == )

                y += a;

            else if (i %  == )

                x -= a;

            else

                y -= a;

        }

        ll ans = x * x + y * y;

        printf("Case #%d:%lld\n", k, ans);

    }

}

一个蒲公英从(0,0)出发，向(x+1,y)或(x,y+1)出发，要求x<y。给你N个询问，最后达到(n,m)的方法有多少种。

用费马小定理求逆元，然后直接套公式。
ans = C(n+m-1,m) - C(n+m-1,m-1)

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

using namespace std;

const int maxn = 5e5+;

#define MAX_DISTANCE 0x3f3f3f3f

#define mm(a,b) memset(a,b,sizeof(a))

#define ll long long

#define SIGN(A) ((A > 0) ? 1 : -1)

#define NO_DISTANCE 1000000

const int INF = 0x3f3f3f3f;

#define LL long long int

#define mod 1000000007

int gcd(int a, int b) { return a ==  ? b : gcd(b % a, a); }

int mi[maxn];

inline int quick(int a, int b) {

    int res = a, ans = ;

    for (int i = ; i < ; i++) {

        if ( << i & b) ans = (long long)ans * res % mod;

        res = (long long)res * res % mod;

    }

    return ans;

}

int C(int n, int m) {

    int tmp = (long long)mi[n - m] * mi[m] % mod;

    int ans = (long long)mi[n] * quick(tmp, mod - ) % mod;

    return ans;

}

int main() {

    int n, m;

    mi[] = ;

    for (int i = ; i <= ; i++) mi[i] = (long long)mi[i - ] * i % mod;

    int t;

    scanf("%d", &t);

    while (t--) {

        scanf("%d%d", &m, &n);

        printf("%d\n", (C(n + m - , m) - C(n + m - , m - ) + mod) % mod);

    }

    return ;

}

简单模拟

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#include<string>

#include<vector>

#include<ctime>

#include<stack>

using namespace std;

const int maxn = ;

#define MAX_DISTANCE 0x3f3f3f3f

#define mm(a,b) memset(a,b,sizeof(a))

#define ll long long

#define SIGN(A) ((A > 0) ? 1 : -1)

#define NO_DISTANCE 1000000

const int INF = 0x3f3f3f3f;

#define LL long long int

#define mod 1000000007

int gcd(int a, int b) { return a ==  ? b : gcd(b % a, a); }

map<char, char>letter;

void init()

{

    letter['a'] = '';

    letter['b'] = '';

    letter['c'] = '';

    letter['d'] = '';

    letter['e'] = '';

    letter['f'] = '';

    letter['g'] = '';

    letter['h'] = '';

    letter['i'] = '';

    letter['j'] = '';

    letter['k'] = '';

    letter['l'] = '';

    letter['m'] = '';

    letter['n'] = '';

    letter['o'] = '';

    letter['p'] = '';

    letter['q'] = '';

    letter['r'] = '';

    letter['s'] = '';

    letter['t'] = '';

    letter['u'] = '';

    letter['v'] = '';

    letter['w'] = '';

    letter['x'] = '';

    letter['y'] = '';

    letter['z'] = '';

}

int main()

{

    init();

    int T;

    cin >> T;

    int ccase = ;

    while (T--)

    {

        string num;

        cin >> num;

        int m;

        cin >> m;

        printf("Case #%d:\n", ccase);

        ccase++;

        while (m--)

        {

            string s;

            cin >> s;

            string ans="";

            for (int i = ; i < s.length(); i++)

            {

                ans += letter[s[i]];

            }

            if (ans == num)

                cout << "Maybe.." << endl;

            else

                cout << "How could that be possible?" << endl;

        }

    }

    return ;

}

树上区间第k大。裸的板题，判断数据是否合法即计算路径上的点是否有k个即可。

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

using namespace std;

const int maxn = ;

#define MAX_DISTANCE 0x3f3f3f3f

#define mm(a,b) memset(a,b,sizeof(a))

#define ll long long

#define SIGN(A) ((A > 0) ? 1 : -1)

#define NO_DISTANCE 1000000

const int INF = 0x3f3f3f3f;

#define LL long long int

#define mod 1000000007

int gcd(int a, int b) { return a ==  ? b : gcd(b % a, a); }

//主席树部分 *****************8

const int MAXN = ;

const int M = MAXN * ;

int n, q, m, TOT;

int a[MAXN], t[MAXN];

int T[M], lson[M], rson[M], c[M];

void Init_hhash()

{

    for (int i = ; i <= n; i++)

        t[i] = a[i];

    sort(t + , t +  + n);

    m = unique(t + , t + n + ) - t - ;

}

int build(int l, int r)

{

    int root = TOT++;

    c[root] = ;

    if (l != r)

    {

        int mid = (l + r) >> ;

        lson[root] = build(l, mid);

        rson[root] = build(mid + , r);

    }

    return root;

}

int hhash(int x)

{

    return lower_bound(t + , t +  + m, x) - t;

}

int update(int root, int pos, int val)

{

    int newroot = TOT++, tmp = newroot;

    c[newroot] = c[root] + val;

    int l = , r = m;

    while (l < r)

    {

        int mid = (l + r) >> ;

        if (pos <= mid)

        {

            lson[newroot] = TOT++; rson[newroot] = rson[root];

            newroot = lson[newroot]; root = lson[root];

            r = mid;

        }

        else

        {

            rson[newroot] = TOT++; lson[newroot] = lson[root];

            newroot = rson[newroot]; root = rson[root];

            l = mid + ;

        }

        c[newroot] = c[root] + val;

    }

    return tmp;

}

int query(int left_root, int right_root, int LCA, int k)

{

    int lca_root = T[LCA];

    int pos = hhash(a[LCA]);

    int l = , r = m;

    while (l < r)

    {

        int mid = (l + r) >> ;

        int tmp = c[lson[left_root]] + c[lson[right_root]] -  * c[lson[lca_root]] + (pos >= l && pos <= mid);

        if (tmp >= k)

        {

            left_root = lson[left_root];

            right_root = lson[right_root];

            lca_root = lson[lca_root];

            r = mid;

        }

        else

        {

            k -= tmp;

            left_root = rson[left_root];

            right_root = rson[right_root];

            lca_root = rson[lca_root];

            l = mid + ;

        }

    }

    return l;

}

//LCA部分

int rmq[ * MAXN];//rmq数组，就是欧拉序列对应的深度序列

struct ST

{

    int mm[ * MAXN];

    int dp[ * MAXN][];//最小值对应的下标

    void init(int n)

    {

        mm[] = -;

        for (int i = ; i <= n; i++)

        {

            mm[i] = ((i&(i - )) == ) ? mm[i - ] +  : mm[i - ];

            dp[i][] = i;

        }

        for (int j = ; j <= mm[n]; j++)

            for (int i = ; i + ( << j) -  <= n; i++)

                dp[i][j] = rmq[dp[i][j - ]] < rmq[dp[i + ( << (j - ))][j - ]] ? dp[i][j - ] : dp[i + ( << (j - ))][j - ];

    }

    int query(int a, int b)//查询[a,b]之间最小值的下标

    {

        if (a > b)swap(a, b);

        int k = mm[b - a + ];

        return rmq[dp[a][k]] <= rmq[dp[b - ( << k) + ][k]] ? dp[a][k] : dp[b - ( << k) + ][k];

    }

};

//边的结构体定义

struct Edge

{

    int to, next;

};

Edge edge[MAXN * ];

int tot, head[MAXN];

int F[MAXN * ];//欧拉序列，就是dfs遍历的顺序，长度为2*n-1,下标从1开始

int P[MAXN];//P[i]表示点i在F中第一次出现的位置

int cnt;

ST st;

void init()

{

    tot = ;

    for (int i = ; i <= n; i++)

        head[i] = -;

}

void addedge(int u, int v)//加边，无向边需要加两次

{

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot++;

}

void dfs(int u, int pre, int dep)

{

    F[++cnt] = u;

    rmq[cnt] = dep;

    P[u] = cnt;

    for (int i = head[u]; i != -; i = edge[i].next)

    {

        int v = edge[i].to;

        if (v == pre)continue;

        dfs(v, u, dep + );

        F[++cnt] = u;

        rmq[cnt] = dep;

    }

}

void LCA_init(int root, int node_num)//查询LCA前的初始化

{

    cnt = ;

    dfs(root, root, );

    st.init( * node_num - );

}

int query_lca(int u, int v)//查询u,v的lca编号

{

    return F[st.query(P[u], P[v])];

}

void dfs_build(int u, int pre)

{

    int pos = hhash(a[u]);

    T[u] = update(T[pre], pos, );

    for (int i = head[u]; i != -; i = edge[i].next)

    {

        int v = edge[i].to;

        if (v == pre)continue;

        dfs_build(v, u);

    }

}

int main()

{

    int ccase;

    cin >> ccase;

    while (ccase--)

    {

        scanf("%d %d", &n, &q);

        for (int i = ; i <= n; i++)

            scanf("%d", &a[i]);

        Init_hhash();

        init();

        TOT = ;

        int u, v;

        for (int i = ; i < n; i++)

        {

            scanf("%d%d", &u, &v);

            addedge(u, v);

            addedge(v, u);

        }

        LCA_init(, n);

        T[n + ] = build(, m);

        dfs_build(, n + );

        int k;

        while (q--)

        {

            scanf("%d %d %d", &u, &v, &k);

            int K = rmq[P[u]] + rmq[P[v]] -  * rmq[P[query_lca(u, v)]] + ;

            if (k > K)

                printf("-1\n");

            else

            {

                K = K - k + ;

                printf("%d\n", t[query(T[u], T[v], query_lca(u, v), K)]);

            }

        }

    }

    return ;

}

巴特西

whu-contest-2019（online）

最新文章

热门文章