第九届福建省大学生程序设计竞赛-重现赛（感谢承办泉州师范学院）

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

A - Uint47 calculator FZU - 2294

水题，用unsigned long long,自带自动溢出，然后就可以随便写了。

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
 #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));

ull mod=1;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
string s;
map<string,ull> mp;
int main() {
    char op[100];
    string  tx,ty;
    ull x,y;
    for(int i=1;i<48;i++){
        mod*=2;
    }
    while(~scanf("%s",op)) {
        if(op[0]=='d'&&op[1]=='e') {  //def
            cin>>s>>x;
            mp[s]=x;
            cout<<s<<" = "<<x<<'\n';
        } else if(op[0]=='s') {    //sub
            cin>>tx>>ty;
            x=mp[tx];
            y=mp[ty];
            mp[tx]=x=(x-y+mod)%mod;
            cout<<tx<<" = "<<x<<'\n';
        } else if(op[0]=='a') {
            cin>>tx>>ty;
            x=mp[tx];
            y=mp[ty];
           mp[tx]=x=(x+y)%mod;
            cout<<tx<<" = "<<x<<'\n';
        } else if(op[0]=='m'&&op[1]=='u') {
            cin>>tx>>ty;
            x=mp[tx];
            y=mp[ty];
            mp[tx]=x=(x*y)%mod;
            cout<<tx<<" = "<<x<<'\n';
        } else if(op[0]=='d') {
            cin>>tx>>ty;
            x=mp[tx];
            y=mp[ty];
            mp[tx]=x=(x/y)%mod;
            cout<<tx<<" = "<<x<<'\n';
        } else {
            cin>>tx>>ty;
            x=mp[tx];
            y=mp[ty];
            mp[tx]=x=x%y;
            cout<<tx<<" = "<<x<<'\n';
        }
    }
    return 0;
}

B - Human life FZU - 2295

最大权闭合子图，k只有5暴力枚举所有状态。然后就是一个裸题了。

答案 是最大正权值-去最大流。如果有人想了解为啥，自行百度吧。。

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
199
200
201
202
 #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=1e3+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int v[maxn];
int pre[maxn][maxn];
int u[maxn];
int n,m,K;
int a[2][5];
int ku[maxn];
vector<int> tv[maxn];
struct edge {
    int to,cap,rev;
};
vector <edge> G[maxn];
int level[maxn];
int iter[maxn];

void init(int _n) {
    for(int i=0; i<=_n; i++) {
        G[i].clear();
        tv[i].clear();
    }
    mem(pre,0);
    mem(u,0);
}
void init(){
    for(int i=0;i<=n+m+1;i++)G[i].clear();
}

void bfs(int s) {
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()) {
        int v= que.front();
        que.pop();
        for(int i=0; i<G[v].size(); i++) {
            edge & e=G[v][i];
            if(e.cap>0&&level[e.to]<0) {
                level[e.to]=level[v] + 1;
                que.push(e.to);
            }
        }
    }
}

void add(int from,int to,int cap) {
    edge eg;
    eg.to=to;
    eg.cap=cap;
    eg.rev=G[to].size();
    G[from].push_back(eg);
    eg.to=from;
    eg.cap=0;
    eg.rev=G[from].size()-1;
    G[to].push_back(eg);
}

int dfs(int v,int t,int f) {
    if(v == t)return f;
    for(int &i = iter[v]; i < G[v].size(); i++) {
        edge &e=G[v][i];
        if(e.cap>0 && level[v]<level[e.to]) {
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0) {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int maxflow(int s,int t) {
    int flow=0;
    for(;;) {
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f = dfs(s,t,INF))>0) {
            flow +=f;
        }
    }
}


void dfs(int r) {
    u[r]=1;
    for(int i=1; i<=n; i++) {
        if(pre[r][i]) {
            if(u[i]==0) {
                dfs(i);
            }
            for(int j=1; j<=n; j++) {
                pre[r][j]|=pre[i][j];
            }
        }
    }
}

int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d%d",&n,&m,&K);
        init(n+m+1);
        for(int i=1; i<=n; i++) {
            scanf("%d",&v[i]);
            int k;
            scanf("%d",&k);
            if(k==0)u[i]=1;
            for(int j=0; j<k; j++) {
                int x;
                scanf("%d",&x);
                pre[i][x]=1;
            }
        }
        for(int i=1; i<=n; i++) {
            if(u[i]==0) {
                dfs(i);
            }
        }
        for(int i=n+1; i<=n+m; i++) {
            scanf("%d",&v[i]);
            int k;
            bool tu[maxn]= {0};
            scanf("%d",&k);
            for(int j=0; j<k; j++) {
                int x;
                scanf("%d",&x);
                if(tu[x])continue;
                tu[x]=1;
                for(int l=1; l<=n; l++) {
                    tu[l]|=pre[x][l];
                }
            }
            for(int j=1; j<=n; j++) {
                if(tu[j]) {
                    tv[i].push_back(j);
                }
            }
        }
        for(int i=0; i<K; i++) {
            scanf("%d%d",&a[0][i],&a[1][i]);
        }
        int mx=0;
        for(int i=0; i<1<<K; i++) {
            mem(ku,0);
            init();
            for(int j=0; j<K; j++) {
                ku[a[(i>>j)&1][j]+n]=1;
//                debug(a[(i>>j)&1][j]+n);
            }
            int sum=0;
            for(int i=n+1; i<=n+m; i++) {
                if(ku[i]==1)continue;
//                debug(i);
                add(0,i,v[i]);
                for(int j=0; j<tv[i].size(); j++) {
                    add(i,tv[i][j],inf);
                }
                sum+=v[i];
            }
            for(int i=1; i<=n; i++)add(i,n+m+1,v[i]);
            mx=max(sum-maxflow(0,n+m+1),mx);
        }
        printf("%d\n",mx);
    }
    return 0;
}

D - Number theory FZU - 2297

一开始还以为是大数，java 了一发，大数了一发，全都TLE，正解就是一个线段树。

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
 #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=1e3+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;

int c[maxn][maxn];
int q[maxn][maxn];
int b2[maxn];

long long pow(long long x,long long n,long long mod=1e9+7) {
    long long res=1;
    while(n>0) {
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res%mod;
}

int main() {
    c[1][1]=1;
    c[1][0]=1;
    for(int i=1; i<1e3+1; i++) {
        c[i+1][0]=1;
//        printf("%d ",c[i+1][0]);
        for(int j=1; j<=i+1; j++) {
            c[i+1][j]=(c[i][j-1]+c[i][j])%mod;
//            printf("%d ",c[i+1][j]);
        }
    }
    for(int i=1; i<1e3+1; i++) {
        for(int j=0; j<=i; j++) {
            q[i][j+1]=(q[i][j]+c[i][j])%mod;
        }
    }
    b2[0]=1;
    for(int i=1; i<1e3+1; i++) {
        b2[i]=(b2[i-1]*2)%mod;
    }
    int t;
    scanf("%d",&t);
    while(t--) {
        int n,m;
        scanf("%d%d",&n,&m);
        if(m>n) {
            puts("0");
        } else {
            cout<<(q[n][n+1]-q[n][m]+mod)%mod*pow(b2[n],mod-2,mod)%mod<<endl;
        }
    }
    return 0;
}

E - Traffic jamFZU - 2298

最短路，处理下到某个点的情况，如果是红灯，时间变为到绿灯开始。

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
 #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 cost[maxn];
int n,m;
struct edge {
    int to,c,next;
} eg[maxn*2];
int head[maxn],tot,vis[maxn];
void init() {
    mem(head,-1);
    tot=0;
}
void add(int u,int v,int c) {
    eg[tot].to=v;
    eg[tot].c=c;
    eg[tot].next=head[u];
    head[u]=tot++;
}

int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++) {
            scanf("%d",&a[i]);
        }
        init();
        for(int i=0; i<m; i++) {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        int st,en;
        scanf("%d%d",&st,&en);
        queue<int> q;
        q.push(st);
        mem(cost,inf);
        mem(vis,0);
        cost[st]=0;
        while(q.size()) {
            int v=q.front();
            q.pop();
            vis[v]=0;
            for(int i=head[v]; i!=-1; i=eg[i].next) {
                int d=cost[v]+eg[i].c,to=eg[i].to;
                if(to!=en&&(d/a[to])&1)d=(d/a[to]+1)*a[to];
                if(d<cost[to]) {
                    cost[to]=d;
                    if(vis[to]==0) {
                        vis[to]=1;
                        q.push(to);
                    }
                }
            }
        }
        printf("%d\n",cost[en]);
    }
    return 0;
}

G - IoU FZU - 2300

签到题

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
 #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));

ull mod=1;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
string s;
map<string,ull> mp;
int T;
struct node {
    ll x,y,w,h;
}a[3];

int main() {
    scanf("%d", &T);
    while (T --) {
        scanf("%lld %lld %lld %lld", &a[0].x,&a[0].y,&a[0].w,&a[0].h);
        scanf("%lld %lld %lld %lld", &a[1].x,&a[1].y,&a[1].w,&a[1].h);
        ll wi = (min(a[0].x+a[0].w, a[1].x+a[1].w)-max(a[0].x, a[1].x));
        ll hi = (min(a[0].y+a[0].h, a[1].y+a[1].h)-max(a[0].y, a[1].y));
        ll un;
        if(wi > 0 && hi > 0) un = wi*hi;
        else un = 0;
        //debug(un);
        ll sum = a[0].w*a[0].h+a[1].w*a[1].h-un;
        //debug(sum);
        printf("%.2f\n", 1.0*un/sum);
    }
    return 0;
}

/*
6
1 1 1 1
1 1 2 2

1 1 2 1
1 1 1 2

1 1 2 2
2 0 1 1

0 3 3 3
2 2 2 1

0 3 3 3
2 4 5 5

1 1 1 1
-100 -100 1 1
*/

H - Chosen by god FZU - 2301

题意：n点伤害随机分配，求分配到敌人身上大于等于m，的期望，就是求C(M,N)+…+C(M,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
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
 #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=1e3+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;

int c[maxn][maxn];
int q[maxn][maxn];
int b2[maxn];

long long pow(long long x,long long n,long long mod=1e9+7) {
    long long res=1;
    while(n>0) {
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res%mod;
}

int main() {
    c[1][1]=1;
    c[1][0]=1;
    for(int i=1; i<1e3+1; i++) {
        c[i+1][0]=1;
//        printf("%d ",c[i+1][0]);
        for(int j=1; j<=i+1; j++) {
            c[i+1][j]=(c[i][j-1]+c[i][j])%mod;
//            printf("%d ",c[i+1][j]);
        }
    }
    for(int i=1; i<1e3+1; i++) {
        for(int j=0; j<=i; j++) {
            q[i][j+1]=(q[i][j]+c[i][j])%mod;
        }
    }
    b2[0]=1;
    for(int i=1; i<1e3+1; i++) {
        b2[i]=(b2[i-1]*2)%mod;
    }
    int t;
    scanf("%d",&t);
    while(t--) {
        int n,m;
        scanf("%d%d",&n,&m);
        if(m>n) {
            puts("0");
        } else {
            cout<<(q[n][n+1]-q[n][m]+mod)%mod*pow(b2[n],mod-2,mod)%mod<<endl;
        }
    }
    return 0;
}

J - Mind control FZU - 2303

题意：n个人，m个蛋糕，你把蛋糕给一个人，他后面的人也会被选上，例如选1 ，2 3 4 5 ….等都会被选上，选 3 4 5 …都会被选上，求选上人数的期望。

题解：给蛋糕的总肯能是C（M,N），选的人最高为1 的选择种数是，C（M-1,N-1），选一个蛋糕给1，然后其他蛋糕给他后面的人，以此类推，最高为2 选择种数是 ,C(M-1,N-2)，最高为3 可能是 C（m-1,N-3）;

然后权值乘以概率就是期望 ，NC(M-1,N-1)+(N-1)C(M-1,N-2)+….+M*C(M-1,M-1)/C(M,N)；

看到权值是 N,N-1肯定要化进组合数 ，大答案m/m, 就可以化成MC(M,N)+M(M,N-1)+…..+MC(M,M)/C(M,N)；

在化简 MC(M+1,N+1)/C(M,N)最后化为M(N+1)/(M+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
 #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;

long long pow(long long x,long long n,long long mod=1e9+7) {
    long long res=1;
    while(n>0) {
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res%mod;
}

void read(ll &sum) {
    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;
}

int main() {
    ll t;
    read(t);
    while(t--) {
        ll n,m;
        read(n);
        read(m);
        cout<<m*(n+1)%mod*pow(m+1,mod-2,mod)%mod<<"\n";
    }
    return 0;
}