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 = 1000;
#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 == 0 ? b : gcd(b % a, a); }
ll x, y;
int n;
int main()
{
    int t;
    ll a;
    scanf("%d", &t);
    for (int k = 1; k <= t; k++)
    {
        scanf("%d", &n);
        x = y = 0;
        for (int i = 0; i < n; ++i)
        {
            scanf("%lld", &a);
            if (i % 4 == 0)
                x += a;
            else if (i % 4 == 1)
                y += a;
            else if (i % 4 == 2)
                x -= a;
            else
                y -= a;
        }
        ll ans = x * x + y * y;
        printf("Case #%d:%lld\n", k, ans);
    }
}

View Code

一个蒲公英从(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+50;
#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 == 0 ? b : gcd(b % a, a); }

int mi[maxn];
inline int quick(int a, int b) {
    int res = a, ans = 1;
    for (int i = 0; i < 31; i++) {
        if (1 << 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 - 2) % mod;
    return ans;
}
int main() {
    int n, m;
    mi[0] = 1;
    for (int i = 1; i <= 200000; i++) mi[i] = (long long)mi[i - 1] * i % mod;
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &m, &n);
        printf("%d\n", (C(n + m - 1, m) - C(n + m - 1, m - 1) + mod) % mod);
    }
    return 0;
}

View Code

简单模拟

#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 = 1000;
#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 == 0 ? b : gcd(b % a, a); }
map<char, char>letter;
void init()
{
    letter['a'] = '2';
    letter['b'] = '2';
    letter['c'] = '2';

    letter['d'] = '3';
    letter['e'] = '3';
    letter['f'] = '3';

    letter['g'] = '4';
    letter['h'] = '4';
    letter['i'] = '4';

    letter['j'] = '5';
    letter['k'] = '5';
    letter['l'] = '5';

    letter['m'] = '6';
    letter['n'] = '6';
    letter['o'] = '6';

    letter['p'] = '7';
    letter['q'] = '7';
    letter['r'] = '7';
    letter['s'] = '7';

    letter['t'] = '8';
    letter['u'] = '8';
    letter['v'] = '8';

    letter['w'] = '9';
    letter['x'] = '9';
    letter['y'] = '9';
    letter['z'] = '9';
}
int main()
{
    init();
    int T;
    cin >> T;
    int ccase = 1;
    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 = 0; i < s.length(); i++)
            {
                ans += letter[s[i]];
            }
            if (ans == num)
                cout << "Maybe.." << endl;
            else 
                cout << "How could that be possible?" << endl;
        }
    }
    return 0;
}

View Code

树上区间第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 = 1000;
#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 == 0 ? b : gcd(b % a, a); }


//主席树部分 *****************8
const int MAXN = 200010;
const int M = MAXN * 40;
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 = 1; i <= n; i++)
        t[i] = a[i];
    sort(t + 1, t + 1 + n);
    m = unique(t + 1, t + n + 1) - t - 1;
}
int build(int l, int r)
{
    int root = TOT++;
    c[root] = 0;
    if (l != r)
    {
        int mid = (l + r) >> 1;
        lson[root] = build(l, mid);
        rson[root] = build(mid + 1, r);
    }
    return root;
}
int hhash(int x)
{
    return lower_bound(t + 1, t + 1 + m, x) - t;
}
int update(int root, int pos, int val)
{
    int newroot = TOT++, tmp = newroot;
    c[newroot] = c[root] + val;
    int l = 1, r = m;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        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 + 1;
        }
        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 = 1, r = m;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        int tmp = c[lson[left_root]] + c[lson[right_root]] - 2 * 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 + 1;
        }
    }
    return l;
}

//LCA部分
int rmq[2 * MAXN];//rmq数组，就是欧拉序列对应的深度序列
struct ST
{
    int mm[2 * MAXN];
    int dp[2 * MAXN][20];//最小值对应的下标
    void init(int n)
    {
        mm[0] = -1;
        for (int i = 1; i <= n; i++)
        {
            mm[i] = ((i&(i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
            dp[i][0] = i;
        }
        for (int j = 1; j <= mm[n]; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                dp[i][j] = rmq[dp[i][j - 1]] < rmq[dp[i + (1 << (j - 1))][j - 1]] ? dp[i][j - 1] : dp[i + (1 << (j - 1))][j - 1];
    }
    int query(int a, int b)//查询[a,b]之间最小值的下标
    {
        if (a > b)swap(a, b);
        int k = mm[b - a + 1];
        return rmq[dp[a][k]] <= rmq[dp[b - (1 << k) + 1][k]] ? dp[a][k] : dp[b - (1 << k) + 1][k];
    }
};
//边的结构体定义
struct Edge
{
    int to, next;
};
Edge edge[MAXN * 2];
int tot, head[MAXN];

int F[MAXN * 2];//欧拉序列，就是dfs遍历的顺序，长度为2*n-1,下标从1开始
int P[MAXN];//P[i]表示点i在F中第一次出现的位置
int cnt;

ST st;
void init()
{
    tot = 0;
    for (int i = 0; i <= n; i++)
        head[i] = -1;
}
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 != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == pre)continue;
        dfs(v, u, dep + 1);
        F[++cnt] = u;
        rmq[cnt] = dep;
    }
}
void LCA_init(int root, int node_num)//查询LCA前的初始化
{
    cnt = 0;
    dfs(root, root, 0);
    st.init(2 * node_num - 1);
}
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, 1);
    for (int i = head[u]; i != -1; 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 = 1; i <= n; i++)
            scanf("%d", &a[i]);
        Init_hhash();
        init();
        TOT = 0;
        int u, v;
        for (int i = 1; i < n; i++)
        {
            scanf("%d%d", &u, &v);
            addedge(u, v);
            addedge(v, u);
        }
        LCA_init(1, n);
        T[n + 1] = build(1, m);
        dfs_build(1, n + 1);
        int k;
        while (q--)
        {
            scanf("%d %d %d", &u, &v, &k);
            int K = rmq[P[u]] + rmq[P[v]] - 2 * rmq[P[query_lca(u, v)]] + 1;
            if (k > K)
                printf("-1\n");
            else
            {
                K = K - k + 1;
                printf("%d\n", t[query(T[u], T[v], query_lca(u, v), K)]);
            }
        }
    }
    return 0;
}

View Code