0%

Camp Day7

发表于 阅读次数：

Camp第七天部分题解

K. 修炼

有一款双人小游戏，两个玩家分别控制两个人物，这两个人物的能力可以用v1,v2来表示，初始两人的能力都为0。

游戏进行的单位是天，每一天这两个人都会分别提升a1,a2的能力值，此外，每天可以获得一个能力点，可以让a1+=1或者a2+=1。

等到两人修炼足够长的时间，就可以去打boss通关了。

小沃沃通过查攻略，发现最后两人的能力值组合只要满足v1≥b1且v2≥b2，就可以过关。

由于通关方式有很多种，可能有很多组b1,b2的组合，只要满足其中任意一组就可以通关。

现在小沃沃想知道最短几天能够通关。

输入格式

第一行2个数，表示a1,a2 (0≤a1,a2<100000)。

接下来一行输入一个数 n (1≤n≤1000)。

下面n行，每行2个数，表示一组可以通关的b1,b2 (0<b1,b2<10^9)。

输出格式

一个数表示最短通关天数。

输入样例

1
2
3
0 0
1
1 2
1
2
3
4
1 1
2
5 7
6 6

输出样例

1
2
1
3

题解：在第i加给某个人+1，最终带来的贡献是n-i+1点能力值，相当于提供n个能力值，分别为1,2，…，n，来分配给两个数，看是否满足至少一组组合。因为1，..，n可以组成1~（n+1)*n/2之间任意的数，故给你一组b1,b2,可以O(1)计算当前的a1,a2是否满足。故可采用二分最短天数，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
33
34
35
	#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a1, a2;
int n;
ll b1[1111], b2[1111];
bool check(int mid){
    ll k = 1LL*(mid+1)*mid/2;
    ll _a1 = a1*mid;
    ll _a2 = a2*mid;
    for(int i=1;i<=n;i++){
        ll d1 = b1[i] - _a1;
        ll d2 = b2[i] - _a2;
        if(d1<=0 && d2 <= 0) return 1;
        if(d1<= 0) if(k>=d2) return 1;
        if(d2<= 0) if(k>=d1) return 1;
        if(d1 + d2 <= k)     return 1;
    }
    return 0;
}
int main(){

    scanf("%lld %lld", &a1, &a2);
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%lld %lld", &b1[i], &b2[i]);
    }
    ll l = 1, r = 2e9;
    while(l <= r){
        ll mid = 1LL*(l+r)>>1;
        if(check(mid)) r = mid - 1;
        else l = mid + 1;
    }
    printf("%lld\n", l);
}

L.圆

一个n个点的有向图，初始每个顶点都有一个颜色，黑或白。

每一轮，每个顶点的颜色会改变，规则如下：如果在上一轮，有奇数个黑色顶点连向他，那么这个顶点会变成黑的；如果在上一轮，有偶数个黑色顶点连向他，那么这个顶点会变成白的。

初始状态为第0轮。

小渣渣想要知道对于某一个点，从第0轮开始，最少过了几轮，使得它在这几轮结束的时候，顶点是黑色的次数大于等于k次（第0轮结束也算）？

输入格式

输入第一行三个数n,m,q (1≤n≤20,1≤m≤n∗n−n,1≤q≤100000)，表示顶点数，边数和询问次数。

接下来一行n个数（0或1），表示这个点初始的颜色，0表示白，1表示黑。

接下来m行，每行两个数x,y，表示有一条x到y的边，不存在重边和自环。

接下来q行，每行两个数x,k (k≤10^10)，表示一次询问，x号点，在每轮结束时顶点是黑色的次数大于等于k次，所需的轮次最少是多少。

输出格式

输出包含q行，每行一个数，表示每个询问的答案。如果不存在，输出−1。

输入样例

1
2
3
4
5
6
7
3 2 3
1 0 0
1 2
2 1
1 2
2 2
3 1

输出样例

1
2
3
2
3
-1

题解：因为n只有20，故所有状态只有2^20，所以这些转换存在循环节，这样的状态转换图就会是蝌蚪状，先是一条链，链尾后是一个环，分两段前缀和处理，具体最少次数采用二分即可。

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;
int vis[1<<21];
int sum[21][1050000];
int num[22];
#define ll long long
vector<pair<int,int> >e;
ll check(int a[], int n, ll k, int x = 0){
    int l=0, r=n;
    while(l<=r){
        int mid = l+r>>1;
        if(a[mid] - x>= k) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}
int main(){
    int n, m, q;
    memset(vis, -1, sizeof vis);
    scanf("%d %d %d", &n, &m, &q);
    int now = 0;
    for(int i=1;i<=n;i++) {
        int x; scanf("%d", &x);
        now += x*(1<<i);
        sum[i][0] = x;
    }
    for(int i=1;i<=m;++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        e.push_back({x,y});
    }
    int nt  =-1;
    int cnt = 1;
    while(vis[now]==-1){
        vis[now] = cnt-1;
        for(int i=1;i<=n;i++) {
            num[i]=0;
            sum[i][cnt] = sum[i][cnt-1];
        }
        for(int i=0;i<e.size();++i){
            int x = e[i].first;
            int y = e[i].second;
            if(now&(1<<x)) num[y]++;
        }
        now = 0;
        for(int  i=1;i<=n;i++) if(num[i]&1) now += (1<<i), sum[i][cnt]++;
        if(vis[now]!=-1) nt = vis[now],cnt-=2;
        cnt++;
    }

    while(q--){
        int x; ll k;
        scanf("%d %lld", &x, &k);
        ll ans = 0;
        if(!k){
            puts("0");
            continue;
        }
        if(n==1){
            if(sum[1][0] < k) ans = -1;
            else ans = 0;
        }

        else if(nt==-1){
            if(sum[cnt-1][x] < k) ans = -1;
            else ans += check(sum[x],cnt-1,k);
        }
        else if(nt){ // 初始状态循环节起点
            ll tmp = sum[x][nt-1]; 
            if(k <= tmp) ans += check(sum[x], nt-1,k);
            else {
                k -= tmp;
                ans += nt-1;
                if(sum[x][cnt] - sum[x][nt-1] == 0) ans = -1;
                else {
                    tmp = sum[x][cnt] - sum[x][nt-1];
                    ans += 1LL*(k-1)/tmp*(cnt-nt+1);
                    k = k-(k-1)/tmp*tmp;
                    if(k)ans += check(&sum[x][nt-1],cnt-nt+1,k,sum[x][nt-1]);
                }
            }
        }
        else {  //
            if(sum[x][cnt] == 0) ans = -1;
            else {
                ll tmp = sum[x][cnt];
                ans += 1LL*(k-1)/tmp*(cnt-nt+1);
                k = k-(k-1)/tmp*tmp;
                if(k)ans += check(&sum[x][nt-1],(cnt-nt+1),k)-1;
            }
        }
        printf("%lld\n", ans);
    }

}
/*
3 2 3
1 0 0
1 2
2 1


*/