Codeforces 1000 组合数可行线段倒dp 边双联通缩点求树直径

A

/*Huyyt*/

#include<bits/stdc++.h>

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

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = 1e9 + , gakki =  +  +  +  + 1e9;

const int MAXN = 2e5 + , MAXM = 2e5 + , N = 2e5 + ;

const int MAXQ = ;

/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;

inline void addedge(int u, int v)

{

        to[++tot] = v;

        nxt[tot] = Head[u];

        Head[u] = tot;

}*/

inline void read(int &v)

{

        v = ;

        char c = ;

        int p = ;

        while (c < '' || c > '')

        {

                if (c == '-')

                {

                        p = -;

                }

                c = getchar();

        }

        while (c >= '' && c <= '')

        {

                v = (v << ) + (v << ) + c - '';

                c = getchar();

        }

        v *= p;

}

int num[];

int anser[];

map<string, int> mp;

int main()

{

        mp["S"] = , mp["M"] = , mp["L"] = ;

        mp["XL"] = , mp["XXL"] = , mp["XXXL"] = ;

        mp["XS"] = , mp["XXS"] = , mp["XXXS"] = ;

        int n;

        int ans = ;

        read(n);

        string now;

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

        {

                cin >> now;

                num[mp[now]]++;

        }

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

        {

                cin >> now;

                anser[mp[now]]++;

        }

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

        {

                ans += abs(num[i] - anser[i]);

        }

        cout << ans /  << endl;

        return ;

}

B

分奇偶即可

/*Huyyt*/

#include<bits/stdc++.h>

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

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = 1e9 + , gakki =  +  +  +  + 1e9;

const int MAXN = 2e5 + , MAXM = 2e5 + , N = 2e5 + ;

const int MAXQ = ;

/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;

inline void addedge(int u, int v)

{

        to[++tot] = v;

        nxt[tot] = Head[u];

        Head[u] = tot;

}*/

inline void read(int &v)

{

        v = ;

        char c = ;

        int p = ;

        while (c < '' || c > '')

        {

                if (c == '-')

                {

                        p = -;

                }

                c = getchar();

        }

        while (c >= '' && c <= '')

        {

                v = (v << ) + (v << ) + c - '';

                c = getchar();

        }

        v *= p;

}

int num[];

int anser = ;

int number[];

int main()

{

        ios_base::sync_with_stdio();

        cin.tie();

        int n, m;

        cin >> n >> m;

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

        {

                cin >> num[i];

        }

        n++;

        num[n] = m;

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

        {

                number[i] = number[i - ];

                if (i & )

                {

                        int add = num[i] - num[i - ];

                        number[i] += add;

                }

        }

        anser = number[n];

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

        {

                if (num[i] -  > num[i - ] || num[i] +  < num[i + ])

                {

                        if (i & )

                        {

                                int now = number[i] + m - num[i] + number[i] - number[n] - ;

                                anser = max(anser, now);

                        }

                }

        }

        cout << anser << endl;

        return ;

}

C

离散化前缀和

/*Huyyt*/

#include<bits/stdc++.h>

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

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = 1e9 + , gakki =  +  +  +  + 1e9;

const int MAXN = 2e5 + , MAXM = 2e5 + , N = 2e5 + ;

const int MAXQ = ;

/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;

inline void addedge(int u, int v)

{

        to[++tot] = v;

        nxt[tot] = Head[u];

        Head[u] = tot;

}*/

inline void read(int &v)

{

        v = ;

        char c = ;

        int p = ;

        while (c < '' || c > '')

        {

                if (c == '-')

                {

                        p = -;

                }

                c = getchar();

        }

        while (c >= '' && c <= '')

        {

                v = (v << ) + (v << ) + c - '';

                c = getchar();

        }

        v *= p;

}

ll number[];

ll ans[];

ll l[], r[];

ll anser[];

map<ll, ll> mp;

map<ll, ll> mpb;

int main()

{

        ios_base::sync_with_stdio();

        cin.tie();

        int n;

        cin >> n;

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

        {

                cin >> l[i] >> r[i];

                number[ * i - ] = l[i];

                number[ * i - ] = r[i];

                number[ * i] = r[i] + ;

        }

        sort(number + , number +  * n + );

        int pop = unique(number + , number +  * n + ) - number - ;

        //        for (int i = 1; i <= pop; i++)

        //        {

        //                cout << number[i] << " ";

        //        }

        //        cout << endl;

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

        {

                mp[number[i]] = i;

                mpb[i] = number[i];

        }

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

        {

                ans[mp[l[i]]]++;

                ans[mp[r[i]] + ]--;

        }

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

        {

                ans[i] += ans[i - ];

        }

        ll cur = ans[];

        for (int i = ; i <= pop - ; i++)

        {

                cur = ans[i];

                anser[cur] += mpb[i + ] - mpb[i];

        }

        cur = ans[pop];

        anser[cur]++;

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

        {

                cout << anser[i] << " ";

        }

        cout << endl;

        return ;

}

D

倒着DP

/*Huyyt*/

#include<bits/stdc++.h>

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

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = , gakki =  +  +  +  + 1e9;

const int MAXN = 2e5 + , MAXM = 2e5 + , N = 2e5 + ;

const int MAXQ = ;

/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;

inline void addedge(int u, int v)

{

        to[++tot] = v;

        nxt[tot] = Head[u];

        Head[u] = tot;

}*/

inline void read(int &v)

{

        v = ;

        char c = ;

        int p = ;

        while (c < '' || c > '')

        {

                if (c == '-')

                {

                        p = -;

                }

                c = getchar();

        }

        while (c >= '' && c <= '')

        {

                v = (v << ) + (v << ) + c - '';

                c = getchar();

        }

        v *= p;

}

ll zuhe[][];

int n;

ll num[];

ll ans[];

ll anser = ;

void init()

{

        zuhe[][] = ;

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

        {

                zuhe[i][] = ;

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

                {

                        zuhe[i][j] = (zuhe[i - ][j] + zuhe[i - ][j - ]) % mod;

                }

        }

}

int main()

{

        ios_base::sync_with_stdio();

        cin.tie();

        cin >> n;

        ans[n + ] = ;

        init();

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

        {

                cin >> num[i];

        }

        for (int i = n; i >= ; i--)

        {

                if (num[i] <= )

                {

                        continue;

                }

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

                {

                        ans[i] += zuhe[j - i - ][num[i]] * ans[j];

                        ans[i] %= mod;

                }

        }

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

        {

                anser += 1LL * ans[i];

                anser %= mod;

        }

        cout << anser << endl;

        return ;

}

E

边双联通分量缩点后是一颗树 再求树的直径即可

/*Huyyt*/

#include <bits/stdc++.h>

#include <vector>

#include <cstdio>

#include <cstring>

#include <string>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <stack>

#include <vector>

#include <set>

#include <map>

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

using namespace std;

const int N =  + ;

const int M =  + ;

struct EDGE

{

    int v, next;

} edge[M * ];

int first[N], low[N], dfn[N], belong[N], degree[N], sta[M], instack[M];

vector<int> gra[];

int g, cnt, top, scc;

int min(int a, int b)

{

    return a < b ? a : b;

}

void AddEdge(int u, int v)

{

    edge[g].v = v;

    edge[g].next = first[u];

    first[u] = g++;

}

void Tarjan(int u, int fa)

{

    int i, v;

    low[u] = dfn[u] = ++cnt;

    sta[++top] = u;

    instack[u] = ;

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

    {

        v = edge[i].v;

        if (i == (fa ^ ))

        {

            continue;

        }

        if (!dfn[v])

        {

            Tarjan(v, i);

            low[u] = min(low[u], low[v]);

        }

        else if (instack[v])

        {

            low[u] = min(low[u], dfn[v]);

        }

    }

    if (dfn[u] == low[u])

    {

        scc++;

        while ()

        {

            v = sta[top--];

            instack[v] = ;

            belong[v] = scc;

            if (v == u)

            {

                break;

            }

        }

    }

}

map<pair<int, int>, int> mp;

int ssssstart, eeeeeeend;

int distence[];

int visit[];

void getdis(int x)

{

    visit[x] = ;

    int len = gra[x].size();

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

    {

        int to = gra[x][i];

        if (visit[to])

        {

            continue;

        }

        distence[to] = distence[x] + ;

        getdis(to);

    }

}

int main()

{

    ios_base::sync_with_stdio();

    cin.tie();

    memset(first, -, sizeof(first));

    int n, m;

    int u, v;

    cin >> n >> m;

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

    {

        cin >> u >> v;

        AddEdge(u, v);

        AddEdge(v, u);

    }

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

    {

        if (!dfn[i])

        {

            Tarjan(i, -);

        }

    }

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

    {

        for (int j = first[i]; j != -; j = edge[j].next)

        {

            v = edge[j].v;

            if (belong[i] != belong[v])

            {

                if (!mp[make_pair(belong[i], belong[v])])

                {

                    gra[belong[i]].push_back(belong[v]);

                    gra[belong[v]].push_back(belong[i]);

                    mp[make_pair(belong[i], belong[v])] = mp[make_pair(belong[v], belong[i])] = ;

                }

            }

        }

    }

    getdis();

    int maxnn = -;

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

    {

        if (distence[i] > maxnn)

        {

            ssssstart = i;

            maxnn = distence[i];

        }

    }

    mem(visit, ), mem(distence, );

    getdis(ssssstart);

    maxnn = -;

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

    {

        if (distence[i] > maxnn)

        {

            eeeeeeend = i;

            maxnn = distence[i];

        }

    }

    cout << distence[eeeeeeend] << endl;

    return ;

}