2
13
2017
0

CF Round #373

这一场非常奇怪。

A.

 

A - Vitya in the Countryside
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
#include <stdio.h>
inline int F() { register int aa , bb , ch;
    while(ch = getchar() , (ch<'0'||ch>'9') && ch != '-'); ch == '-' ? aa=bb=0 : (aa=ch-'0',bb=1);
    while(ch = getchar() , ch>='0'&&ch<='9') aa = aa*10 + ch-'0'; return bb ? aa : -aa;
}
int n , a[100010];
int main() {
    n = F();
    if(n == 1) {
        int qwq = F();
        if(qwq == 15) puts("DOWN");
        else if(qwq == 0) puts("UP");
        else puts("-1");
        return 0;
    }
    for(int i=1; i<=n; ++i) {
        a[i] = F();
    }
    if(a[n] < a[n-1]) {
        if(a[n] == 0) puts("UP");
        else puts("DOWN");
    }
    else {
        if(a[n] == 15) puts("DOWN");
        else puts("UP");
    }
}

B.

 

B - Anatoly and Cockroaches
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
#include <stdio.h>
#include <iostream>
using std::max; using std::min;
inline int F() { register int aa , bb , ch;
    while(ch = getchar() , (ch<'0'||ch>'9') && ch != '-'); ch == '-' ? aa=bb=0 : (aa=ch-'0',bb=1);
    while(ch = getchar() , ch>='0'&&ch<='9') aa = aa*10 + ch-'0'; return bb ? aa : -aa;
}
const int Maxn = 100010;
int n , a[Maxn] , ans1 , ans2 , ans; char s[Maxn];
int main() {
    n = F();
    scanf("%s",s+1);
    for(int i=1; i<=n; ++i) {
        if(s[i] == 'b') a[i] = 1;
        else a[i] = 0;
    }
    for(int i=1 , p = 0; i<=n; ++i , p ^= 1) {
        if(a[i] != p) {
            if(p) ++ans1;
            else ++ans2;
        }
    }
    ans = max(ans1,ans2);
    ans1 = ans2 = 0;
    for(int i=1; i<=n; ++i) {
        if(s[i] == 'b') a[i] = 1;
        else a[i] = 0;
    }
    for(int i=1 , p = 1; i<=n; ++i , p ^= 1) {
        if(a[i] != p) {
            if(p) ++ans1;
            else ++ans2;
        }
    }
    ans = min(ans , max(ans1,ans2));
    printf("%d\n",ans);
}

C.

 

C - Sasha and Array
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <iostream>
using std::min; using std::max;
const int mod = 1000000007;
inline int F() { register int aa , bb , ch;
    while(ch = getchar() , (ch<'0'||ch>'9') && ch != '-'); ch == '-' ? aa=bb=0 : (aa=ch-'0',bb=1);
    while(ch = getchar() , ch>='0'&&ch<='9') aa = aa*10 + ch-'0'; return bb ? aa : -aa;
}
const int Maxt = 819210;
struct node { int a[2][2]; } lzy , lazy[Maxt] , tree[Maxt] , Std , f1 , Nul;
node operator + (node a , node b) {
    a.a[0][0] = (a.a[0][0] + b.a[0][0]) % mod;
    a.a[1][0] = (a.a[1][0] + b.a[1][0]) % mod;
    a.a[0][1] = (a.a[0][1] + b.a[0][1]) % mod;
    a.a[1][1] = (a.a[1][1] + b.a[1][1]) % mod;
    return a;
}
node operator * (node a , node b) {
    node c;
    for(int i=0; i<2; ++i)
        for(int j=0; j<2; ++j) {
            c.a[i][j] = 0;
            for(int k=0; k<2; ++k)
                c.a[i][j] = (c.a[i][j] + (long long)a.a[i][k]*b.a[k][j]) % mod;
        }return c;
}
node pow(node tmp , int i) {
    node ans = Std;
    for(; i; i>>=1 , tmp = tmp*tmp) if(i&1) ans = ans*tmp;
    return ans;
}
const int Maxn = 100010;
int n , m , ll[Maxt] , rr[Maxt] , a[Maxn];
 
void update(int x) {
    if(ll[x] == rr[x]) tree[x] = lazy[x];
    else tree[x] = (tree[x<<1] + tree[x<<1|1]) * lazy[x];
}
void Build(int x , int l  , int r) {
    ll[x] = l; rr[x] = r; lazy[x] = Std;
    if(l == r) {
        lazy[x] = pow(f1,a[l]);
    }
    else {
        int mid = (l + r) >> 1;
        Build(x<<1 , l , mid);
        Build(x<<1|1 , mid+1 , r);
    }
    update(x);
}
 
void modify(int x , int l , int r) {
    l = max(ll[x] , l); r = min(rr[x] , r);
    if(l > r) return;
    if(ll[x] == l && rr[x] == r) lazy[x] = lazy[x] * lzy;
    else {
        modify(x<<1 , l , r);
        modify(x<<1|1 , l , r);
    }
    update(x);
}
 
node query(int x , int l , int r) {
    l = max(ll[x] , l); r = min(rr[x] , r);
    if(l > r) return Nul;
    if(l == ll[x] && r == rr[x]) return tree[x];
    return (query(x<<1 , l , r) + query(x<<1|1 , l , r)) * lazy[x];
}
 
int main() {
    f1.a[0][0] = f1.a[1][0] = f1.a[0][1] = 1; f1.a[1][1] = 0;
    Std.a[0][0] = Std.a[1][1] = 1; Std.a[0][1] = Std.a[1][0] = 0;
    Nul.a[0][0] = Nul.a[0][1] = Nul.a[1][0] = Nul.a[1][1] = 0;
    n = F() , m = F();
    for(int i=1; i<=n; ++i)
        a[i] = F();
    Build(1,1,n);
    while(m--) {
        int flag = F() , l = F() , r = F();
        if(flag == 1) {
            int v = F();
            lzy = pow(f1,v);
            modify(1,l,r);
        }
        else printf("%d\n",query(1,l,r).a[0][1]);
    }
}
Category: Codeforces | Tags: | Read Count: 395

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com