Educational Codeforces Round 46

A. Codehorses T-shirts
题目大意：给出n个上一年的衣服码数和n个今年的衣服码数，问最少修改多少次字母把上一年的衣服码数变成今年的衣服码数
题解：开一个两个索引的map，一个索引是长度，另一个索引是最后一个字母，模拟一下就好了

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define CLR(a) memset(a, 0, sizeof(a))
#define DBG(x) cout<<(#x)<<"="<<x<<endl
#define FOR(i, a, b)  for(int i=(a); i<(b); i++)
#define REP(i, a, b)  for(int i=(a); i<=(b); i++)
#define DOWN(i, a, b) for(int i=(a); i>=(b); i--)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000009;
const int N = 1e3 + 10;

int n;
string s;
map<int, map<char, int>> M, M2;
int len;
int ans;

int main() {
    cin>>n;
    REP(i, 1, n) {
        cin>>s;
        len=s.length();
        if (len==1) M[len][s[0]]++;
        else M[len][s.back()]++;
    }
    REP(i, 1, n) {
        cin>>s;
        len=s.length();
        if (len==1) M2[len][s[0]]++;
        else M2[len][s.back()]++;
    }
    if (M[1]['M']>M2[1]['M']) ans+=(M[1]['M']-M2[1]['M']);
    if (M[1]['S']>M2[1]['S']) ans+=(M[1]['S']-M2[1]['S']);
    if (M[1]['L']>M2[1]['L']) ans+=(M[1]['L']-M2[1]['L']);
    ans+=abs(M[2]['S']-M2[2]['S']);
    ans+=abs(M[3]['S']-M2[3]['S']);
    ans+=abs(M[4]['S']-M2[4]['S']);
    cout<<ans<<endl;
    //cout<<1.*clock()/CLOCKS_PER_SEC<<"ms"<<"\n";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

B.Light It Up
题目大意：给出n个时间点，每个时间点灯都会改变开关状态，问插入一个时间点后，亮灯时间最长为多长
题解：先把0，M也插入进去，可以证明，插入点必为序号为偶数的点+1或-1，先预处理出一开始的亮灯时间，每次枚举插入时间点后翻转区间就好了

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define CLR(a) memset(a, 0, sizeof(a))
#define DBG(x) cout<<(#x)<<"="<<x<<endl
#define FOR(i, a, b)  for(int i=(a); i<(b); i++)
#define REP(i, a, b)  for(int i=(a); i<=(b); i++)
#define DOWN(i, a, b) for(int i=(a); i>=(b); i--)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000009;
const int N = 1e5 + 10;

int n, M;
int a[N];
set<int> S;
int sum[N];
int t, ans;
int len;
int L, R;

int main() {
    cin>>n>>M;
    a[1]=0;
    a[n+2]=M;
    REP(i, 2, n+1) cin>>a[i];
    n=n+2;
    S.insert(0);
    S.insert(M);
    REP(i, 1, n) {
        S.insert(a[i]);
        if (i%2==1) sum[i]=sum[i-1];
        else sum[i]=sum[i-2]+a[i]-a[i-1];
    }
    ans=sum[n];
    REP(i, 1, n) {
        t=a[i]-1;
        if (t<0||t>M) continue;
        if (S.count(t)) continue;
        if (i%2==1) continue;
        L=sum[i]-1;
        R=sum[n]-sum[i]+1;
        len=M-t;
        ans=max(ans, L+len-R);
    }
    REP(i, 1, n) {
        t=a[i]+1;
        if (t<0||t>M) continue;
        if (S.count(t)) continue;
        if (i%2==1) continue;
        L=sum[i];
        R=sum[n]-sum[i];
        len=M-t;
        ans=max(ans, L+len-R);
    }
    cout<<ans<<endl;
    //cout<<1.*clock()/CLOCKS_PER_SEC<<"ms"<<"\n";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

C. Covered Points Count
题目大意：给出n个线段，问覆盖i次的点有多少个
题解：扫描线经典题目

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define CLR(a) memset(a, 0, sizeof(a))
#define DBG(x) cout<<(#x)<<"="<<x<<endl
#define FOR(i, a, b)  for(int i=(a); i<(b); i++)
#define REP(i, a, b)  for(int i=(a); i<=(b); i++)
#define DOWN(i, a, b) for(int i=(a); i>=(b); i--)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000009;
const int N = 4e6 + 10;

int n;
ll l, r;
int cnt;
int k;
ll len;
ll ans[N];

struct node {
    ll x;
    int p;
    bool operator <(const node& rhs) const {
        return x<rhs.x;
    }
}a[N];

int main() {
    cin>>n;
    REP(i, 1, n) {
        cin>>l>>r;
        a[cnt].p=1;
        a[cnt++].x=l;
        a[cnt].p=-1;
        a[cnt++].x=r+1;

    }
    sort(a, a+cnt);
    FOR(i, 0, cnt) {
        if (i>0) {
            len=a[i].x-1-a[i-1].x+1;
            ans[k]+=len;
        }
        k+=a[i].p;
    }
    REP(i, 1, n) {
        cout<<ans[i];
        if (i==n) cout<<endl;
        else cout<<' ';
    }
    //cout<<1.*clock()/CLOCKS_PER_SEC<<"ms"<<"\n";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

D. Yet Another Problem On a Subsequence
题目大意：一个数组为好数组当且仅当这个数组有k个元素且首元素为k-1，一个序列为好序列当且仅当这个序列可以分为几个好数组
题解：定义dp[i]为以a[i]开头的好序列个数，容易发现dp[i]的递推关系

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define CLR(a) memset(a, 0, sizeof(a))
#define DBG(x) cout<<(#x)<<"="<<x<<endl
#define FOR(i, a, b)  for(int i=(a); i<(b); i++)
#define REP(i, a, b)  for(int i=(a); i<=(b); i++)
#define DOWN(i, a, b) for(int i=(a); i>=(b); i--)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 1e4 + 10;

ll f[N], inv[N], a[N], dp[N];
int n;
ll ans;

ll C(ll n, ll m) {
    if (n<m) return 0;
    return f[n]*inv[n-m]%mod*inv[m]%mod;
}

ll Pow(ll a, ll b) {
    ll ret=1;
    while(b) {
        if (b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}

void init() {
    f[0]=1;
    REP(i, 1, 2000) {
        f[i]=f[i-1]*i%mod;
    } 
    REP(i, 0, 2000) {
        inv[i]=Pow(f[i], mod-2);
    }
}

int main() {
    init();
    cin>>n;
    REP(i, 1, n) cin>>a[i];
    DOWN(i, n, 1) {
        if (a[i]<=0) continue;
        dp[i]=C(n-i, a[i]);
        REP(j, i+1, n) {
            if (a[j]<=0) continue;
            dp[i]=(dp[i]+(dp[j]*C(j-i-1, a[i]))%mod)%mod;
        }
    }
    REP(i, 1, n) ans=(ans+dp[i])%mod;
    cout<<ans<<endl;
    //cout<<1.*clock()/CLOCKS_PER_SEC<<"ms"<<"\n";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

教练，我想打ACM