2016CCPC东北地区大学生程序设计竞赛 - 重现赛

发表于 | 更新于 | 阅读次数：
本文字数： 27k | 阅读时长 ≈ 25 分钟

A 题目连接：HDU 5922 Minimum’s Revenge

水题，每次连接上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
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;


int main() {
    int n,t,cas=1;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        ll res=n;
        printf("Case #%d: %lld\n",cas++,(res+2)*(res-1)/2);
    }
    return 0;
}

B 题目链接：HDU 5923 Prediction

题意：一棵树，每个点代表一条边，每次选择几个点，需要把他的祖先也选上，然后把图里面相应的边连接上，问连接后的图有多少个联通块。

题解：可持续化并查集，每个顶点开一个并查集，维护从根节点到当前节点已经连接的图，再把自己这条边连上。

查询，把所有点的并查集合并一下就可以，然后输出合并后并查集块的个数。

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
 #include<bits/stdc++.h>
using namespace std;
const int maxn=5e2+2;
const int maxm=1e4+5;
bool u[maxm];
int par[maxm][maxn];
struct node {
    int x,y;
    int fa;
} tree[maxm];
int n,m;
int find(int y,int x) {
    return par[y][x]==x?x:par[y][x]=find(y,par[y][x]);
}

void dfs(int x) {
    int fa=tree[x].fa;
    u[x]=1;
    if(u[fa]==0) {
        dfs(fa);
    } else {
        if(x==1) {
//            cout<<"1asd"<<endl;
            for(int i=0; i<=n; i++)par[1][i]=i;
            par[1][tree[x].x]=tree[x].y;
        } else {
            for(int i=0; i<=n; i++)par[x][i]=par[fa][i];
            int X=find(x,tree[x].x),Y=find(x,tree[x].y);
            if(X!=Y) {
                par[x][X]=par[x][Y];
            }
        }
    }
}
int main() {
    int t,cas=1;
    scanf("%d",&t);
    while(t--) {

        scanf("%d%d",&n,&m);
        for(int i=1; i<=m; i++) {
            if(i==1)tree[i].fa=1;
            else {
                int x;
                scanf("%d",&x);
                tree[i].fa=x;
            }
        }
        for(int i=1; i<=m; i++) {
            u[i]=0;
            scanf("%d%d",&tree[i].x,&tree[i].y);
        }
        for(int i=1; i<=m; i++) {
            if(!u[i]) {
                dfs(i);
            }
        }
        int q;
        scanf("%d",&q);
        printf("Case #%d:\n",cas++);
        while(q--) {
            int k,s;
            scanf("%d",&k);
            int res=0;
            for(int i=0; i<=n; i++)par[0][i]=i;
            while(k--) {
                scanf("%d",&s);
//                for(int i=1; i<=n; i++)printf("%d ",par[s][i]);
                for(int i=1; i<=n; i++) {
                    int t1=find(0,i),t2=find(s,i);
                    if(t1!=t2) {
                        int t3=find(0,t2);
                        if(t3!=t1) {
                            res++;
                            par[0][t1]=par[0][t3];
                        }
                    }
                }
            }
            printf("%d\n",n-res);
        }
    }
    return 0;
}

C 题目连接：HUD 5924 Mr. Frog’s Problem

A/B+ B/A 只有在两个数最接近的时候最小，所以如果A<=C<D<=B,C /D+D/C必定小于于等 A/B+B/A所以只有和A B相同的时候才会满足条件。

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
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;

ll a,b,t,n;
int main() {
    int cas=1;
    cin>>t;
    while(t--) {
        cin>>a>>b;
        printf("Case #%d:\n",cas++);
        if(a==b) {
            puts("1");
            cout<<a<<" "<<b<<endl;
        } else {
            puts("2");
            cout<<a<<" "<<b<<endl;
            cout<<b<<" "<<a<<endl;
        }
    }
    return 0;
}

D 题目连接:HDU 5925 Coconuts

题意：给你一个R*C的矩阵中间有几个n个点，问分成了几个联通块，联通块的大小是多少。

题解：R，C范围是1e9肯定是要离散，离散之后变成了一个不到 2000*2000的矩阵，求联通块数量直接DFS一遍就可以了。

问题来了了，离散之后怎么求每个块的大小呢。

首先你是根据行和列分别离散，计算主要是把离散掉的重新算回来。

如下图加入黄色是你被覆盖的格子，你会把横着离散黑色的格子为一个格子，红色的竖着离散成一个格子。因此，你只要把这些离散的格子从新加回来就行了，另外还要加上中间那一块被离散掉的。

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=205;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int n;
map<int,int> mpx,mpy;
int x[maxn],y[maxn];
int lx[maxn],ly[maxn];
ll vx[maxn*10],vy[maxn*10];
int mp[maxn*10][maxn*10],mx,my;

int dx[]= {-1,0,1,0},dy[]= {0,-1,0,1};
ll ans[maxn*10];
void dfs(int tx,int ty,int pos) {
    if(mp[tx][ty]!=0)return ;
    mp[tx][ty]=pos;
    ++ans[pos];
    for(int i=0; i<4; i++) {
        int ttx=tx+dx[i],tty=ty+dy[i];
        if(ttx>0&&ttx<=mx&&tty>0&&tty<=my) {
            dfs(ttx,tty,pos);
        }
    }
}

int main() {
    int cas=1,t;
//    freopen("in.txt","r",stdin);
    scanf("%d", &t);
    while(t--) {
        mpx.clear();
        mpy.clear();
        mem(ans,0);
        int r,c;
        scanf("%d%d",&r,&c);
        scanf("%d",&n);
        for(int i=0; i<n; i++) {
            scanf("%d%d",&x[i],&y[i]);
            lx[i]=x[i];
            ly[i]=y[i];
        }
        lx[n]=r;
        sort(lx,lx+n+1);
        int d=0;
        vx[d]=0;
        for(int i=0; i<=n; i++) {
            if(lx[i]==vx[d])continue;
            else if(lx[i]==vx[d]+1) {
                vx[d+1]=vx[d]+1;
                mpx[lx[i]]=d+1;
                d+=1;
            } else if(lx[i]-d==2) {
                vx[d+1]=vx[d]+1;
                vx[d+2]=vx[d]+2;
                mpx[lx[i]]=d+2;
                d+=2;
            } else {
                vx[d+1]=vx[d]+1;
                vx[d+2]=lx[i];
                mpx[lx[i]]=d+2;
                d+=2;
            }
        }
        ly[n]=c;
        sort(ly,ly+n+1);
        mx=d;
        d=0;
        vy[d]=0;
        for(int i=0; i<=n; i++) {
            if(ly[i]==vy[d])continue;
            else if(ly[i]==vy[d]+1) {
                vy[d+1]=vy[d]+1;
                mpy[ly[i]]=d+1;
                d+=1;
            } else if(ly[i]-d>=2) {
                vy[d+1]=vy[d]+1;
                vy[d+2]=ly[i];
                mpy[ly[i]]=d+2;
                d+=2;
            }
        }
        my=d;
        mem(mp,0);
        for(int i=0; i<n; i++) {
            mp[mpx[x[i]]][mpy[y[i]]]=-1;
        }
        int num=1;
        for(int i=1; i<=mx; i++) {
            for(int j=1; j<=my; j++) {
                if(mp[i][j]==0) {
                    dfs(i,j,num++);
                }
            }
        }
        for(int j=1; j<=my; j++) {            //把离散竖着的加起来
            for(int i=1; i<=mx; i++) {
                if(mp[i][j]!=-1) {
                    ans[mp[i][j]]+=vx[i]-vx[i-1]-1;
                } else if(mp[i-1][j]!=-1) {
                    ans[mp[i-1][j]]+=vx[i]-vx[i-1]-1;
                }
            }
        }
        for(int i=1; i<=mx; i++) {            //把横着离散掉的加起来
            for(int j=1; j<=my; j++) {
                if(mp[i][j]!=-1) {
                    ans[mp[i][j]]+=vy[j]-vy[j-1]-1;
                } else if(mp[i][j-1]!=-1) {
                    ans[mp[i][j-1]]+=vy[j]-vy[j-1]-1;
                }
            }
        }
        for(int i=1; i<=mx; i++) {            //把中间那块离散掉的加起来
            for(int j=1; j<=my; j++) {
                if(mp[i][j]!=-1) {
                    ans[mp[i][j]]+=(vy[j]-vy[j-1]-1)*(vx[i]-vx[i-1]-1);
                } else if(mp[i-1][j-1]!=-1) {
                    ans[mp[i-1][j-1]]+=(vy[j]-vy[j-1]-1)*(vx[i]-vx[i-1]-1);
                }
            }
        }
        printf("Case #%d:\n%d\n",cas++,num-1);
        sort(ans+1,ans+num);
        for(int i=1; i<num; i++) {
            printf("%lld",ans[i]);
            if(i+1==num)printf("\n");
            else printf(" ");
        }
    }
    return 0;
}
下面是2组数据，正确答案能手算出来
/*
2
100 100
20
1 50
1 51
1 55
1 60
2 50
2 54
2 56
2 60
3 50
3 51
3 55
3 60
4 51
4 52
4 53
4 54
4 56
4 57
4 58
4 59


100 100
8
1 2
2 1
100 99
99 100
99 1
100 2
1 99
2 100
*/

E:题目链接 HDU 5926 Mr. Frog’s Game

水题不解释了。

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
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;

int ar[35][35];
int n,m;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int main() {
    int cas=1,t;
    scanf("%d", &t);
    while(t--) {

        scanf("%d%d", &n, &m);
        for(int i=0;i<n;++i){
            for(int j = 0; j < m; ++j){
                scanf("%d", &ar[i][j]);
            }
        }
        int flag = 0;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                for(int k=0;k<4;++k){
                    int px = i + dir[k][0],py = j + dir[k][1];
                    if(px<0||py<0||px>=n||py>=m)continue;
                    if(ar[px][py]==ar[i][j]){
                        flag=1;break;
                    }
                }
                if(flag)break;
            }
            if(flag)break;
        }
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                if(ar[i][0]==ar[j][0]||ar[i][m-1]==ar[j][m-1]){
                    flag=1;break;
                }
            }
            if(flag)break;
        }
        for(int i=0;i<m;++i){
            for(int j=i+1;j<m;++j){
                if(ar[0][i]==ar[0][j]||ar[n-1][i]==ar[n-1][j]){
                    flag=1;break;
                }
            }
            if(flag)break;
        }
        printf("Case #%d: ",cas++);
        if(flag)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

F 题目链接：HDU 5927 Auxiliary Set

题意：随便选几个点作为不重要的点，其他的全是重要的点，然后把不重要的点中如果是两个不同节点的最近公共祖先就把他变为重要的点，问，选了几个不重要的点，最后重要的点总共有多少个。

题解：数据看的挺吓人的 1e3 组 1e5的数据那命去写啊，实际上没多少。。。。。直接按不重要的点深度排个序，如果是另外两个重要的点的LCA就变成重要的点。

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=1e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int n,m;
struct edge {
    int to,next;
} eg[maxn*2];
int head[maxn],tot;
void init() {
    mem(head,-1);
    tot=0;
}
void add(int u,int v) {
    eg[tot].to=v;
    eg[tot].next=head[u];
    head[u]=tot++;
}

int dep[maxn],pre[maxn];
int u[maxn];
int res[maxn];
int num[maxn];
int dfs(int r,int p,int d) {
    dep[r]=d;
    pre[r]=p;
    int ans=0;
    for(int i=head[r]; i!=-1; i=eg[i].next) {
        if(eg[i].to!=p) {
            ans+=dfs(eg[i].to,r,d+1);
        }
    }
    num[r]=ans;
    return ans;
}
void read(int &sum) {
    scanf("%d",&sum);
    return ;
    sum=0;
    int flag=0;
    char ch=getchar();
    while(!(ch>='0'&&ch<='9')) {
        if (ch == '-') {
            flag = 1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=getchar();
    if(flag)sum*=-1;
}

bool cmp(int &a,int &b) {
    return dep[a]>dep[b];
}
int main() {
    int t,cas=1;
    scanf("%d",&t);
    while(t--) {

        read(n);
        read(m);
        init();
        for(int i=0; i<n-1; i++) {
            int a,b;
            read(a);
            read(b);
            add(a,b);
            add(b,a);
        }
        dfs(1,-1,1);
        printf("Case #%d:\n",cas++);
        while(m--) {
            int k,d,ans=0;
            read(k);
            ans=n-k;
            for(int i=0; i<k; i++) {
                read(res[i]);
                u[res[i]]=-1;
            }
            sort(res,res+k,cmp);
            for(int i=0; i<k; i++) {
                d=0;
                for(int j=head[res[i]]; j!=-1; j=eg[j].next) {
                    int to=eg[j].to;
                    if(to==pre[res[i]]) {
                        continue;
                    } else {
                        if(u[to]<0) {
                            continue;
                        }
                        if(u[res[i]]==-1) {
                            u[res[i]]=1;
                        } else u[res[i]]++;
                        if(u[res[i]]==2) {
                            ans++;
                            break;
                        }
                    }
                }
            }
            for(int i=0; i<k; i++)u[res[i]]=0;
            printf("%d\n",ans);
        }
    }
    return 0;
}

H 题目连接：HDU 5929 Basic Data Structure

简单模拟一下就可以了，记录下一最后一个零的位置，因为到零除了是第一个位置之外全都必定是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
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
104
105
106
107
108
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;

int a[maxn];
int l,r;
int t,cas=1;
int Q;
char s[100];
deque<int> q;
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&Q);
        int x;
        bool b=1;
        l=r=2e5+5;
        printf("Case #%d:\n",cas++);
        q.clear();
        while(Q--) {
            scanf("%s",s);
            if(b) {
                if(s[0]=='P'&&s[1]=='U') {
                    scanf("%d",&x);
                    a[++r]=x;

                    if(x==0)q.push_back(r);

                } else if(s[0]=='Q') {
                    if(r==l)printf("Invalid.\n");
                    else if(r-l==1)printf("%d\n",a[r]);
                    else {
                        if(q.size()==0) {
                            printf("%d\n",(r-l)&1);
                        } else {
                            int k=q.front();
                            if(r==k)printf("%d\n",(k-l+1)&1);
                            else printf("%d\n",(k-l)&1);
                        }

                    }

                } else if(s[0]=='R') {
                    b=0;

                } else {
                    if(a[r]==0)q.pop_back();
                    --r;

                }
            } else {
                if(s[0]=='P'&&s[1]=='U') {
                    scanf("%d",&x);
                    a[l--]=x;
                    if(x==0)q.push_front(l+1);

                } else if(s[0]=='Q') {
                    if(r==l)printf("Invalid.\n");
                    else if(r-l==1)printf("%d\n",a[r]);
                    else {
                        if(q.size()==0)printf("%d\n",(r-l)&1);
                        else {
                            int k=q.back();
                            if(k==l+1)printf("%d\n",(r-k)&1);
                            else printf("%d\n",(r-k+1)&1);
                        }
                    }
                } else if(s[0]=='R') {
                    b=1;
                } else {
                    if(a[l+1]==0)q.pop_front();
                    ++l;
                }
            }
        }
    }
    return 0;
}

I -题目链接：HDU - 5930 GCD

这题是真的难理解.这题要是不用线段树大家都会写吧，首先暴力从前面的每个位置到当前位置的GCD ，然后记录每个GCD的个数，更新一个点就是删除一个点，然后再加一个点，就是暴力从前面所有位置到后面所有位置的GCD，减去这个值。把值更新再一次算从前面所有位置到后面所有位置的GCD，然后加上去。

竟然会这个这个，这题就是用线段树维护一下GCD的值，，，就像二分一样，因为会有很长一段的GCD值是一样的，每次不用一个个去找，直接找到前面GCD改变的位置，然后减去上一次GCD改变的位置。也是一种暴力。。。修改其实也是一样的就是把前面GCD和后面GCD求一个GCD，然后前后GCD 的数量相乘

比如 1 1 1 2 4 4 4 前面3个数的GCD是3 个 1 和后面3个数 是 2 那么GCD为 gcd(1,2) 数量就是 3 * 3;

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;

int g[maxn<<4],c[maxn];
int f[maxn<<4],a[maxn],aa[maxn],b[maxn],bb[maxn];
int A,B,n,m;

long long gcd(long long a,long long b) {
    return b==0?a:gcd(b,a%b);
}



void build(int l,int r,int k) {
    if(r-l==1) {
        g[k]=c[r];
    } else {
        build(lson);
        build(rson);
        g[k]=gcd(g[chl],g[chr]);
    }
}

int findleft(int l,int r,int k,int u,int v) {
    if(r<=u) {
        if(gcd(g[k],v)==v)return 0;
        if(l+1==r)return r;
        int x=findleft(rson,u,v);
        if(x)return x;
        else return findleft(lson,u,v);
    }
    if(u>mid) {
        int x=findleft(rson,u,v);
        if(x)return x;
    }
    return findleft(lson,u,v);
}

void getleft(int x) {
    A=0;
    for(int i=c[x],j=x,k; j!=0; j=k) {
        k=findleft(0,n,0,j,i);
        a[A]=j-k;
        aa[A++]=i;
        if(k==0)return ;
        i=gcd(c[k],i);
    }
    return ;
}
int findright(int l,int r,int k,int u,int v) {          //这个是用线段树往左找GCD
    if(l+1>=u) {
        if(gcd(g[k],v)==v)return n+1;
        if(l+1==r)return r;
        int x = findright(lson,u,v);
        if(x<=n)return x;
        else return findright(rson,u,v);
    }
    if(u<=mid) {
        int x=findright(lson,u,v);
        if(x<=n)return x;
    }
    return findright(rson,u,v);
}

void getright(int x) {
    B=0;
    for(int i= c[x],j=x,k; j<=n; j=k) {  //这个是暴力X所有左边的GCD
        k=findright(0,n,0,j,i);
        b[B]=k-j;
        bb[B++]=i;
        i=gcd(c[k],i);
    }
    return ;
}
void change(int l,int r,int k,int u,int v) {
    if (l+1==r) {
        g[k] = v;
        return;
    }
    if (u<=mid) change(lson,u,v);
    else change(rson,u,v);
    g[k]=gcd(g[chl],g[chr]);
}

int main() {
    int t,cas=1;
    scanf("%d",&t);
    while(t--) {
        printf("Case #%d:\n",cas++);
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; ++i)scanf("%d",&c[i]);
        build(0,n,0);           //初始化线段树
        memset(f,0,sizeof(f));
        int ans=0;
        for(int i=1; i<=n; i++) {
            getleft(i);                 //初始化只要找所有i左边的GCD或者右边也可以，但是只能找一边不然会重复。
            for(int j=0; j<A; j++) {
                if(!f[aa[j]])ans++;
                f[aa[j]]+=a[j];
            }
        }
        while(m--) {
            int x,y;
            scanf("%d%d",&x,&y);
            getleft(x);             //找到所有左边的GCD
            getright(x);            //找到所有右边的GCD
            for(int j=0; j<A; j++) {//暴力所有左右两边GCD所有可能
                for(int k=0; k<B; k++) {
                    int t=gcd(aa[j],bb[k]); //左右两边的GCD的GCD
                    f[t]-=1LL *a[j]*b[k];       // 暴力删除
                    if(!f[t])ans--;
                }
            }
            c[x]=y;
            change(0,n,0,x,y);
            getleft(x);
            getright(x);
            for(int j=0; j<A; j++) {
                for(int k=0; k<B; k++) {
                    int t=gcd(aa[j],bb[k]);//暴力添加
                    if(!f[t])ans++;
                    f[t]+=1LL*a[j]*b[k];
                }
            }
            printf("%d\n",ans); // 得出结论
        }
    }
    return 0;
}

J 题目链接：HDU5931 - Mission Possible

暴力所有速度，推一下公式，发现要么是用初始血量去掉不加血，要么是加血等于掉血数量的时候是最优解。

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
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
ll D,A,GA,GB,GC;
int main() {
    int t,cas=1;
    scanf("%d",&t);
    while(t--) {
        scanf("%lld%lld%lld%lld%lld",&D,&A,&GA,&GB,&GC);
        ll v,r,h;
        ll ans=1e18,temp;
        for(v=1; v<=D; v++) {
            double t=1.0*D/v;
            temp=v*GB+A*GC+A*GA;
            ans=min(ans,temp);
            double tem2=t*A;
            temp=v*GB+floor(t*A-eps+1)*GA;
//            debug(temp-v*GB);
            ans=min(ans,temp);
        }
        printf("Case #%d: %lld\n",cas++,ans);
    }
    return 0;
}