Codeforces Round #305 (Div. 1)

A:

化出式子后其实就是求扩展欧几里德的最小正整数解,

先求出一个ax+by=gcd(a,b)的解x0 y0

由扩展欧几里德可知

|x0| <= b/gcd(a, b)   , |y0| <= a / gcd(a,b)

解的一般形式为

x = x0 + b / gcd(a, b);

y = y0 - a / gcd(a, b);

假如存在一个x y都大于零的解。那么肯定可以在 O(max(a,b))级别的范围内枚举出来,

因为|b/gcd(a,b)| >= 1 ,  |a / gcd(a, b)|>=1 , x0 y0又是同级别的,一个加1,一个减1,暴力即可得出解

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
#include <bits/stdc++.h>
const int N = 1000010;
int m, mp[N];
struct Gao
{
        int h, a, x, y, p, q;
        void in() {
                scanf("%d%d%d%d", &h,&a,&x,&y);
        }
        int cal(long long A, long long B) {
                memset(mp, -1, sizeof(mp));
                for(int i=1;;i++) {
                        A=(A*x+y)%m;
                        if(A==B)  {
                                return i;
                        }
                        if(mp[A]!=-1) {
                                return -1;
                        }
                        mp[A]=i;
                }
        }
 
        void solve() {
                p = cal(h,a);
                q = cal(a,a);
        }
 
}a, b;
 
 
 
int gcd(int x,int y)
{
        return !y ? x : gcd(y, x % y);
}
long long solve()
{
        if(a.p==-1¦¦b.p==-1) {
                return -1;
        }
        if(a.p==b.p) {
                return a.p;
        }
        if(a.p < b.p) {
                std::swap(a,b);
        }
        if(b.q != -1 && (a.p - b.p) % b.q == 0) {
                return a.p;
        }
 
 
 
        if(a.q==-1¦¦b.q==-1) return -1;
        int g = gcd(a.q, b.q);
        if((a.p-b.p) % g != 0) {
                return -1;
        }
        if(a.q < b.q) {
                std::swap(a,b);
        }
        for(int i=1;i<=m;i++) {
                long long tmp=(long long) i * a.q + a.p;
                if(tmp >= b.p && (tmp - b.p) % b.q == 0) {
                        return tmp;
                }
        }
        return -1;
 
}
int main()
{
        scanf("%d", &m);
        a.in();b.in();
        a.solve();b.solve();
        printf("%I64d\n",solve());
}

 

B:

这种题往往倒过来想,即考虑每个数成为某段区间最小值的作用范围。会有奇效。

我们先求出l[i] r[i],表示最左以及最右的两个位置,满足对于 l[i] <= x <= r[i] , a[x] >= a[i].

所以a[i]“统治”的区间长度就是r[i]-l[i]+1,那么,a[i]也可以统治区间长度小于 r[i]-l[i]+1的区间,意思就是a[i]可以更新

ret[1]->ret[r[i]-l[i]+1],所以只需要记录一个ret[r[i]-l[i]+1] = max(ret[r[i]- l[i] + 1], a[i]),然后最后倒着更新一边ret数组即可。

关于l r数组的求法可以这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
        for(int i = 1; i <= n; i++) {
                scanf("%d", &a[i]);
                l[i] = r[i] = i;
        }
        for(int i = 1; i <= n; i++) {
                while(l[i] - 1 >= 1 && a[l[i] - 1] >= a[i]) {
                        l[i] = l[l[i] - 1];
                }
        }
        for(int i = n; i >= 1; i--) {
                while(r[i] + 1 <= n && a[r[i] + 1] >= a[i]) {
                        r[i] = r[r[i] + 1];
                }
        }

 

这个复杂度平摊下来是O(n)的。

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
#include <bits/stdc++.h>
const int N= 200010;
int c[N],a[N],l[N],r[N],ret[N];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        l[i] = r[i] = i;
    }
    for(int i = 1; i <= n; i++) {
        while(l[i] - 1 >= 1 && a[l[i] - 1] >= a[i]) {
            l[i] = l[l[i] - 1];
        }
    }
    for(int i = n; i >= 1; i--) {
        while(r[i] + 1 <= n && a[r[i] + 1] >= a[i]) {
            r[i] = r[r[i] + 1];
        }
    }
    for(int i = 1; i <= n; i++) {
        ret[r[i]-l[i]+1] = std::max(a[i], ret[r[i]-l[i]+1]);
    }
    for(int i = n; i >= 1; i--) {
        ret [i] = std::max(ret[i], ret[i + 1]);
    }
    for(int i = 1; i <= n; i++) {
        printf("%d ", ret[i]);
    }
    return 0;
}

 

C:

考虑最基本的思路,放一个数或者拿出一个数,我们都需要求这个数跟集合内的多少个数不互质。

我们先将每个数化简成单一素数相乘的形式,比如2 * 2 * 3 * 3 * 5这个数就变成2 × 3 × 5,这样的话每个数就最多有5个质数相乘,总的因子数是2^5 = 32个,现在,假设我们插入一个数x,假设x = 2 * 3 * 5,那实际上就是求集合中

2的倍数的个数 + 3的倍数的个数 + 5的倍数的个数 - 2×3的倍数的个数 - 3×5的倍数的个数 - 2×5的倍数的个数 + 2×3×5的倍数的个数。由于在插入一个数的时候我们会将这个数的所有的因子fac都加入,即count[fac]++(相当于fac的倍数多了一个数),所以我们直接通过count数组就可以知道某个数的倍数有多少个了。

就是基本的容斥原理的思路。

D:

假如每行每列都是偶数个点,这个问题就相当于每个点的度数都是偶数的欧拉回路问题,每行每列都是一个点,显然是有解的。随便从某行或者某列开始染色,然后行列交替着染色即可。

由于题目保证有解,所以碰到奇数的行或者列,就一直交替染色下去直到都变成偶数为止。

E:

后缀数组建立起来之后本质就是求一段区间内小于等于r大于等于l的数有多少个,离线+树状数组搞之。

E题用后缀树的思想有更简单的写法。http://codeforces.com/contest/547/submission/11340158

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注