Educational Codeforces Round 46 (Rated for Div. 2)

A - Codehorses T-shirts

思路：有相同抵消，没有相同的对答案+1

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int, int>

using namespace std;

const int N = 1e5 + ;

const int M = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

string a[], b[];

int n;

map<string, int> mp;

int main(){

    scanf("%d", &n);

    for(int i = ; i <= n; i++) cin >> a[i], mp[a[i]]++;

    int ans = ;

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

        cin >> b[i];

        if(mp[b[i]]) {

            mp[b[i]]--;

        } else {

            ans++;

        }

    }

    printf("%d\n", ans);

    return ;

}

/*

*/

B - Light It Up

思路：求一下前缀，如果要加一个开关肯定是加在原来是关的前面一个或者后面一个，枚举一下就好啦。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int, int>

using namespace std;

const int N = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

int n, M, sum[N], fsum[N], a[N];

int main(){

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

    for(int i = ; i <= n; i++) scanf("%d", &a[i]);

    a[++n] = M;

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

        sum[i] = sum[i - ];

        if(i & ) sum[i] += a[i] - a[i - ];

        fsum[i] = a[i] - sum[i];

    }

    int ans = sum[n];

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

        if(i & ) {

            if(a[i] > a[i - ] + ) {

                int ret = a[i] - a[i - ] - ;

                ret += fsum[n] - fsum[i];

                ret += sum[i - ];

                ans = max(ans, ret);

            }

            if(a[i] < a[i + ] - ) {

                int ret = sum[i];

                ret += fsum[n] - fsum[i + ];

                ret += a[i + ] - a[i] - ;

                ans = max(ans, ret);

            }

        }

    }

    printf("%d\n", ans);

    return ;

}

/*

*/

C - Covered Points Count

思路：离散化差分标记搞一搞

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int, int>

using namespace std;

const int N = 1e6 +  + 2e5;

const int M = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

LL n, tot, in[N], out[N], ans[N];

LL hs[N], l[N], r[N];

int main(){

    scanf("%lld", &n);

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

        scanf("%lld%lld", &l[i], &r[i]);

        hs[++tot] = l[i];

        hs[++tot] = r[i];

        hs[++tot] = l[i] + ;

        hs[++tot] = l[i] - ;

        hs[++tot] = r[i] + ;

        hs[++tot] = r[i] - ;

    }

    sort(hs + , hs +  + tot);

    tot = unique(hs + , hs +  + tot) - hs - ;

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

        int pos1 = lower_bound(hs + , hs +  + tot, l[i]) - hs;

        int pos2 = lower_bound(hs + , hs +  + tot, r[i]) - hs;

        in[pos1]++;

        out[pos2]++;

    }

    LL cnt = ;

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

        cnt += in[i];

        ans[cnt]++;

        cnt -= out[i];

        LL num = hs[i + ] - hs[i] - ;

        ans[cnt] += num;

    }

    cnt += in[tot];

    ans[cnt]++;

    for(int i = ; i <= n; i++) printf("%lld ", ans[i]);

    return ;

}

/*

*/

D - Yet Another Problem On a Subsequence

题目大意：给你n个数字 (n <= 1000)， 问你有多少个子序列是good  sequence

good sequence的定义是能变成若干个good arrays

good array 的定义是这个数组的第一个元素的值等于这个数组的length - 1。

思路: A了三题之后日常开始挂机。。。 还是太菜啦！！！！

比赛的时候感觉是个dp，但是不知到如何定义状态。。。

后来发现原来我看错了题，原来是把good sequence划分成若干个good arrays

我们定义dp[ i ]，表示从第 i 个开始，并且 i 作为一个array第一个元素的的合法答案的方案数。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int, int>

using namespace std;

const int N = 1e3 + ;

const int M = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

int a[N], dp[N], C[N][N], n;

void init() {

    for(int i = (C[][] = ); i < N; i++)

        for(int j = (C[i][] = ); j < N; j++)

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

}

int main() {

    init();

    scanf("%d", &n);

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

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

    }

    dp[n + ] = ;

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

        if(a[i] > ) {

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

                dp[i] = (dp[i] + 1LL * dp[j] * C[j - i - ][a[i]]) % mod;

            }

        }

    }

    int ans = ;

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

        ans = (ans + dp[i]) % mod;

    }

    printf("%d\n", ans);

    return ;

}

/*

*/