A 怪盗-1412

problem

进行排列,求最多有多少个子序列

solution

显然让所有的4和2分别相邻答案会更大。然后就是将1分成两份,分别放在4两边。如果前面的个,那么答案就是,这是一个二次函数,当时取得最大值。

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

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

solution

对于第i个点统计出他的度数,当我们要求这个点的答案时,就枚举一个与有连边的将答案加上。减一是因为要减去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的序列,求的值。

solution

的枚举提到前面来,

这就非常了,统计一个的前缀和,然后枚举,答案就是

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

颗宝石装入个箱子中,每个箱子中都必须有宝石,第个宝石不能装入第个箱子中,问有多少种方案。

solution

长得类似于错排问题。所以我们可以先在外面套一个容斥。设表示至少有个箱子不合法其他的箱子先不放的方案数。
那么答案就是。乘是因为剩下的个箱子可以随便排列。

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

发现数据范围允许我们的求。考虑。先预处理出一个表示有个宝石不能放到第个箱子中。用表示前个箱子有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

给出一个长度为的字符串。然后有次查询,每次询问区间内回文串的个数。

solution

学到许多~

如果我们现在在查询这个区间,对于一个所造成的贡献就是。其中表示以i这个点中心的回文串长度。

这就比较难处理了。我们把一次询问拆成两半()进行查询。以查询为例,我们就是要求所有满足的点。因为每个回文串只有一个中心点,所以并不会被重复查询。

然后我们考虑求。其实对于一个满足条件的回文串,我们只要将这个区间+1,然后查询的时候查询的区间和就行了。因为要控制中心点的位置,所以离线下来,将询问按照右端点从小到大排序。然后一边进行区间加,一边查询就行了。

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;
}