2020-05-24 14:43 已编辑山东大学 Java

关注

【题解】牛客练习赛64

A 怪盗-1412

problem

用 $n$ 个 $1$ ， $m$ 个 $2$ ， $k$ 个 $4$ 进行排列，求最多有多少个子序列 $1412$ 。

solution

显然让所有的4和2分别相邻答案会更大。然后就是将1分成两份，分别放在4两边。如果前面的 $1$ 有 $t$ 个，那么答案就是 $t\times m\times (n-t)\times k$ ，这是一个二次函数，当 $t=\frac{n}{2}$ 时取得最大值。

code

/*
* @Author: wxyww
* @Date:   2020-05-22 18:59:57
* @Last Modified time: 2020-05-22 19:03:29
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;

ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}

int main() {
    int T = read();
    while(T--) {
        ll n = read(),m = read(),K = read();
        ll t = n / 2;
        cout<<t * (n - t) * m * K<<endl;
    }

    return 0;
}

B Dis2

problem

给出一个 $n$ 个点树，对于每个点求与它距离为2的点的数目。

solution

对于第i个点统计出他的度数 $d_i$ ,当我们要求 $u$ 这个点的答案时，就枚举一个与 $u$ 有连边的 $v$ 将答案加上 $d_v-1$ 。减一是因为要减去u这个点。

code

/*
* @Author: wxyww
* @Date:   2020-05-22 19:04:43
* @Last Modified time: 2020-05-22 19:06:04
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N =200010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
vector<int>e[N];
int du[N];
int main() {
    int n = read();
    for(int i = 1;i < n;++i) {
        int u = read(),v = read();
        du[u]++;du[v]++;
        e[u].push_back(v);e[v].push_back(u);
    }
    for(int i = 1;i <= n;++i) {
        ll ans = 0;
        for(vector<int>::iterator it = e[i].begin();it != e[i].end();++it) {
            ans += du[*it] - 1;
        }
        printf("%lld\n",ans);
    }

    return 0;
}

C 序列卷积之和

problem

给出一个长度为n的序列 $a$ ，求 $\sum\limits_{l=1}^n\sum\limits_{r=l}^n\sum\limits_{i=l}^r\sum\limits_{j=i}^r a_ia_j$ 的值。

solution

将 $i$ 和 $j$ 的枚举提到前面来， $\sum\limits_{i=1}^n\sum\limits_{j=i}^n\sum\limits_{l=1}^i\sum\limits_{r=j}^n a_ia_j=\sum\limits_{i=1}^n ia_i\sum\limits_{j=i}^n ja_j$

这就非常 $easy$ 了，统计一个 $ia_i$ 的前缀和 $s_i$ ，然后枚举 $j$ ,答案就是 $\sum\limits_{i=1}^n ia_is_i$

code

/*
* @Author: wxyww
* @Date:   2020-05-22 19:09:59
* @Last Modified time: 2020-05-22 19:21:52
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 200010,mod = 1e9+7;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
ll a[N];
int main() {
    int n = read();
    ll sum = 0,ans = 0;
    ll inv = (mod + 1) / 2;
    for(int i = 1;i <= n;++i) {
        a[i] = read();
        ll t1 = 1ll * i * a[i] % mod;
        ll t2 = 1ll * (n - i + 1) * a[i] % mod;

        sum += t1;
        sum %= mod;

        ans += sum * t2 % mod;
        ans %= mod;
    }

    cout<<(ans + mod) % mod;

    return 0;
}

D 宝石装箱

problem

将 $n$ 颗宝石装入 $n$ 个箱子中，每个箱子中都必须有宝石，第 $i$ 个宝石不能装入第 $a_i$ 个箱子中，问有多少种方案。

solution

长得类似于错排问题。所以我们可以先在外面套一个容斥。设 $f_i$ 表示至少有 $i$ 个箱子不合法其他的箱子先不放的方案数。
那么答案就是 $\sum\limits_{i=0}^n (-1)^i f_i (n-i)!$ 。乘 $(n-i)!$ 是因为剩下的 $(n-i)$ 个箱子可以随便排列。

然后我们只要求出来 $f_i$ 就行了。

发现数据范围允许我们 $O(n^2)$ 的求 $f_i$ 。考虑 $dp$ 。先预处理出一个 $b_i$ 表示有 $b_i$ 个宝石不能放到第 $i$ 个箱子中。用 $f_{ij}$ 表示前 $i$ 个箱子有j个不合法，其他的先不放的方案数。转移就是 $f_{ij}=f_{(i-1)(j-1)}\times b_i+f_{(i-1)j}$

code

/*
* @Author: wxyww
* @Date:   2020-05-22 19:23:49
* @Last Modified time: 2020-05-22 19:29:28
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 8010,mod = 998244353;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
ll qm(ll x,ll y) {
    ll ret = 1;
    for(;y;y >>= 1,x = x * x % mod)
        if(y & 1) ret = ret * x % mod;
    return ret;
}
ll f[2][N],jc[N],ans;
int b[N];

int main() {
    int n = read();
    jc[0] = 1;
    for(int i = 1;i <= n;++i) {
        b[read()]++;
        jc[i] = jc[i - 1] * i % mod;
    }

    f[0][0] = 1;

    for(int i = 1;i <= n;++i) {
        int t = i & 1;
        for(int j = 0;j <= n;++j) {
            f[t][j] = f[t ^ 1][j];
            if(j) f[t][j] += 1ll * f[t ^ 1][j - 1] * b[i] % mod,f[t][j] >= mod ? f[t][j] -= mod : 0;
        }
    }

    for(int i = 0;i <= n;++i) {
        ll k = 1;
        if(i & 1) k = -1;
        ans += k * jc[n - i] * f[n & 1][i] % mod;
        ans %= mod;
    } 
    cout<<(ans + mod) % mod<<endl;


    return 0;
}

E 如果我让你查回文你还爱我吗

problem

给出一个长度为 $n$ 的字符串 $s$ 。然后有 $Q$ 次查询，每次询问区间 $[l,r]$ 内回文串的个数。

solution

学到许多~

如果我们现在在查询 $[l,r]$ 这个区间，对于一个 $l\leq i\leq r$ 所造成的贡献就是 $min\{i-l+1,r-i+1,\lceil \frac{p_i}{2}\rceil \}$ 。其中 $p_i$ 表示以i这个点中心的回文串长度。

这就比较难处理了。我们把一次询问拆成两半( $[l,mid],[mid+1,r]$ )进行查询。以查询 $[l,mid]$ 为例，我们就是要求所有满足 $l\leq i \leq mid$ 的点 $min(i-l+1,\lceil\frac{p_i}{2}\rceil)$ 。因为每个回文串只有一个中心点，所以并不会被重复查询。

然后我们考虑求 $min(i-l+1,\lceil \frac{p_i}{2}\rceil)$ 。其实对于一个满足条件的回文串，我们只要将 $[i-\lceil \frac{p_i}{2}\rceil]$ 这个区间+1，然后查询的时候查询 $[l,mid]$ 的区间和就行了。因为要控制中心点的位置，所以离线下来，将询问按照右端点从小到大排序。然后一边进行区间加，一边查询就行了。

PS：细节超多~

code

/*
* @Author: wxyww
* @Date:   2020-04-21 20:46:23
* @Last Modified time: 2020-05-22 21:24:27
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 500010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
int now,fail[N],ans[N],len[N],lst,lstans;
char s[N];
int get(int p) {
    while(s[now - len[p] - 1] != s[now]) p = fail[p];
    return p;
}
int trie[N][26],tot = 1,dy2[N];
void ins() {
    int p = get(lst);
    if(!trie[p][s[now] - 'a']) {
        len[++tot] = len[p] + 2;
        dy2[tot] = now;
        int tmp = get(fail[p]);
        fail[tot] = trie[tmp][s[now] - 'a'];        

        add(dy2[fail[tot]],tot);

        trie[p][s[now] - 'a'] = tot;
    }
    else {
        dy2[++tot] = now;
        fail[now] = trie[p][s[now] - 'a'];
        add(dy2[fail[tot]],tot);
    }

    lst = trie[p][s[now] - 'a'];
}

int dfn[N],cnt;
struct node {
    int v,nxt;
}e[N << 1];
int siz[N],head[N],ejs;
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
void dfs(int u,int fa) {
    dfn[u] = ++cnt;
    siz[u] = 1;
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;if(v == fa) continue;
        dfs(v,u);
        siz[u] += siz[v];
    }
}


int main() {
    int n = read(),m = read();

    scanf("%s",s + 1);
    len[1] = -1;
    fail[0] = 1;fail[1] = 0;
    for(int i = 1;i <= n;++i) {
        now = i;
        ins();
    }

    add(0,1);

    dfs(0,0);



    return 0;
}