[原创]第七届福建省赛 【(5+2)/10】

2017-07-18 21:46:10 Tabris_ 阅读数：560

博客爬取于2020-06-14 22:39:36
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/75331107

做的怀疑人生啊 最终5题，其中F和J思路都是对的 但是就是不AC啊

看来之前高估了自几的代码能力，以为代码能力已经差不多了，，没想到原来代码能力都这么菜。

2262 Best Friend Forever

————————————————————————————————————————————

2263 Bond

————————————————————————————————————————————

2264 Card Game (First Edition)

————————————————————————————————————————————

每回合两个人轮流在一个序列中任意取一个数，谁的数大谁的1分 ，相等 不得分，问你所有可能下先手得分的期望

能确定得分的期望 就是任意顺序下总得分除以总的所有可能的轮数

所有可能的轮数 就是(2n)!(2n)! 因为取数是有顺序的 所以就是全排列

然后计算先手的总分

考虑拿先手拿到aia_i时对结果的贡献.

那就是∑j=1n[ai>aj]×(2n−2)!×C(n,1)\sum_{j=1}^n[a_i>a_j] \times(2n-2)! \times C(n,1)

后手取的 是(aj)(a_j) 固定这两个数 然后一共有nn轮,这是其中的一轮,所以乘一个C(n,1)C(n,1)
而其他的2n−22n-2个数 就又是全排列的

然后约分下式子就是∑i=1n∑j=1n[ai>aj]n∗4−2\dfrac{\sum_{i=1}^n\sum_{j=1}^n[a_i>a_j]}{n*4-2}

计算∑j=1n[ai>aj]\sum_{j=1}^n[a_i>a_j]的时候只要先对a排个序 然后二分就好了

总复杂度是O(nlog⁡n)O(n\log 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
LL a[N];

int main(){
    int _=read(),kcase=0;
    while(_--){
        int n=read()*2;
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

        sort(a+1,a+n+1);

        LL ans = 0;
        for(int i=1;i<=n;i++){
            int l=1,r=n,mid,tmp=0;
            while(l<=r){//puts("---");
                mid = r+l >> 1;
                if(a[mid]<a[i]) tmp = mid,l = mid+1;
                else  r = mid-1;
            }
            ans+=tmp;
        }
//        printf("%lld/%lld\n",ans,(LL)(2*n-2));
        double aaa = ans*1.0/(2.0*n-2.0);
        printf("Case %d: %.2f\n",++kcase,aaa);

    }
    return 0;
}

2265 Card Game (Second Edition)

————————————————————————————————————————————
和上一题一样

只不过 先手只能那自己的那个序列里面的数 后手同理

公式为

∑i=1n∑j=1n[ai>bj]×C(n,1)×(n−1)!×(n−1)!n!×n!=∑i=1n∑j=1n[ai>bj]n\dfrac{\sum_{i=1}^n\sum_{j=1}^n[a_i>b_j]\times C(n,1)\times (n-1)!\times (n-1)!}{n!\times n!} \\=\dfrac{\sum_{i=1}^n\sum_{j=1}^n[a_i>b_j]}{n}

做法和上题一样,只不过计算分子的时候是对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
LL a[N],b[N];

int main(){
    int _=read(),kcase=0;
    while(_--){
        int n=read();
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
        sort(b+1,b+n+1);

        LL ans = 0;
        for(int i=1;i<=n;i++){
            int l=1,r=n,mid,tmp=0;
            while(l<=r){//puts("---");
                mid = r+l >> 1;
                if(b[mid]<a[i]) tmp = mid,l = mid+1;
                else  r = mid-1;
            }
            ans+=tmp;
        }
        double aaa = ans*1.0/(1.0*n);
        printf("Case %d: %.2f\n",++kcase,aaa);

    }
    return 0;
}

2266 Card Game (Third Edition)

————————————————————————————————————————————
队友写的 我不知道这个题 。。。 等会儿 补、、

1

2267 The Bigger the Better

————————————————————————————————————————————
给你两个序列， 然你合并成一个字符串，保证新字符串中每个元素在原字符串中的顺序不该变， 使得这个新的字符串的字典序最大。

想了几个小时的贪心,(虽然有dalao这么做过去了,但是我菜啊 调了很久 还是不行,最终放弃…)

正解是后缀数组

首先能想到对两个序列 进行类似归并的过程，取最大的。
但是如果当前一段的数都相同的时候就会判断出错误。

应该用后缀数组来处理，
将这个两个数组前后拼接成一个
用后缀数组来处理出Rank[]
然后遇到a[la]和b[lb]相同是不知道选哪个的情况
就将Rank[la]和Rank[lb]进行比较,哪个大就选哪个, 因为要大的数,所以选择优先级小的

附带一点数据,

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
//#include <bits/stdc++.h>
# include <iostream>
# include <string.h>
# include <algorithm>
# include <stdio.h>
typedef long long int LL;
using namespace std;

const int N   = 2e5+7;
const int MOD = 1e9+7;

/********************************************/

int n,m;

const int MAXN=400010;
//以下为倍增算法求后缀数组
int wa[MAXN],wb[MAXN],wv[MAXN],Ws[MAXN];
int cmp(int *r,int a,int b,int l) {
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
/**< 传入参数：str,sa,len+1,ASCII_MAX+1 */
void da(const int r[],int sa[],int n,int m) {
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0; i<m; i++) Ws[i]=0;
    for(i=0; i<n; i++) Ws[x[i]=r[i]]++;//以字符的ascii码为下标
    for(i=1; i<m; i++) Ws[i]+=Ws[i-1];
    for(i=n-1; i>=0; i--) sa[--Ws[x[i]]]=i;
    /*cout<<"SA"<<endl;;
    for(int i=0;i<n+1;i++)cout<<sa[i]<<' ';*/
    for(j=1,p=1; p<n; j*=2,m=p) {
        for(p=0,i=n-j; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0; i<n; i++) wv[i]=x[y[i]];
        for(i=0; i<m; i++) Ws[i]=0;
        for(i=0; i<n; i++) Ws[wv[i]]++;
        for(i=1; i<m; i++) Ws[i]+=Ws[i-1];
        for(i=n-1; i>=0; i--) sa[--Ws[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return;
}
int sa[MAXN],Rank[MAXN],height[MAXN];
//求height数组
/**< str,sa,len */
void calheight(const char *r,int *sa,int n) {
    int i,j,k=0;
    for(i=1; i<=n; i++) Rank[sa[i]]=i;
    for(i=0; i<n; height[Rank[i++]]=k)
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
    // Unified
    for(int i=n; i>=1; --i) ++sa[i],Rank[i]=Rank[i-1];
}

int a[N*2];

int main() {
    int _ ,kcase = 0;
    scanf("%d",&_);
    while(_--) {
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++) scanf("%d",&a[i]);
        a[n]=0;
        for(int i=0; i<m; i++) scanf("%d",&a[i+n+1]);

        da(a,sa,n+m+1,101);
        for(int i=0;i<n+m+1;i++) Rank[sa[i]]=i;

        int la=0,lb=n+1;
        printf("Case %d: ",++kcase);
        while(la<n&&lb<n+m+1){
            if(a[la]>a[lb])            printf("%d",a[la++]);
            else if(a[la]<a[lb])       printf("%d",a[lb++]);
            else if(Rank[la]>Rank[lb]) printf("%d",a[la++]);
            else                       printf("%d",a[lb++]);
        }
        while(la<n) printf("%d",a[la++]);
        while(lb<n+m+1) printf("%d",a[lb++]);
        puts("");
    }
    return 0;
}
/**
44
4 4
1 1 9 5
1 1 9 8

4 4
1 1 9 8
1 1 9 5

8 7
5 5 9 8 5 5 9 8
5 5 9 5 5 9 5

7 8
5 5 9 5 5 9 5
5 5 9 8 5 5 9 8

8 7
5 5 9 8 5 5 9 5
5 5 9 5 5 9 8

7 8
5 5 9 5 5 9 8
5 5 9 8 5 5 9 5

2 3
3 2
3 4 7

3 2
3 4 7
3 2

3 4
3 3 2
3 3 4 7

4 3
3 3 4 7
3 3 2

6 6
3 3 4 4 7 9
3 3 4 4 7 9

3 3
1 2 2
2 1 2

1 1
1
1

5 10
5 6 7 8 9
1 5 6 7 8 5 6 7 9 9

4 3
1 3 2 4
4 1 3

3 3
4 4 3
4 2 3

3 3
4 2 3
4 4 3

3 3
4 4 6
4 2 6

3 3
4 2 6
4 4 6

7 7
7 1 9 1 7 1 9
7 1 9 1 8 7 1

7 7
7 1 1 9 7 1 9
7 1 9 1 1 8 7

----------------------

Case 1: 11981195
Case 2: 11981195
Case 3: 559855985595595
Case 4: 559855985595595
Case 5: 559855955985595
Case 6: 559855955985595
Case 7: 34732
Case 8: 34732
Case 9: 3347332
Case 10: 3347332
Case 11: 334479334479
Case 12: 212212
Case 13: 11
Case 14: 567891567856799
Case 15: 4132413
Case 16: 444323
Case 17: 444323
Case 18: 446426
Case 19: 446426
Case 20: 77191918717191
Case 21: 77191197191187
*/

2268 Cutting Game

————————————————————————————————————————————

2269 Picking Game

————————————————————————————————————————————

2270 Two Triangles

————————————————————————————————————————————
给你几个点,问你有多少对全等三角形,
两个三角形 不能取相同点 ,
判定相等的时候可以旋转图形,但是不能翻转

注意,a全等b 和 b全等a 要算两次a全等b\ 和\ b全等a\ 要算两次

然后考虑如何判定三角形全等,

由初中学过的 ,三边相等就行了, 但是题目要求 可以旋转,但是不能翻转

所以们要对两个图形判定一下,只要O(3∗3)O(3*3)固定一个旋转另一个判定就好了, 有一次满足就行,
但是要注意 描述这两个三角形的时候要采取同样的顺序,要顺时针都是顺时针,否则都逆时针,

然后n只有10 ,所以C(10,3)=120,所以暴力枚举两个三角形在判定是否一样C(10,3)=120 ,所以暴力枚举两个三角形在判定是否一样

所以总复杂度是O(C(10,3)2∗9)O(C(10,3)^2*9)

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
int n,ans;
struct point{
    int x,y;
}p[100];

int dis(int p1,int p2){
    return (p[p1].x-p[p2].x)*(p[p1].x-p[p2].x)+(p[p1].y-p[p2].y)*(p[p1].y-p[p2].y);
}

int mul(int p1,int p2,int p0){
    return ((p[p1].x-p[p0].x)*(p[p2].y-p[p0].y)-(p[p2].x-p[p0].x)*(p[p1].y-p[p0].y));
}

int judge(int s1p1,int s1p2,int s1p3,int s2p1,int s2p2,int s2p3){
    if(mul(s1p2,s1p3,s1p1)<0) swap(s1p2,s1p3);
    if(mul(s2p2,s2p3,s2p1)<0) swap(s2p2,s2p3);

    int s1l1 = dis(s1p1,s1p2);
    int s1l2 = dis(s1p2,s1p3);
    int s1l3 = dis(s1p1,s1p3);

    int s2l1 = dis(s2p1,s2p2);
    int s2l2 = dis(s2p2,s2p3);
    int s2l3 = dis(s2p1,s2p3);

    if(s1l1 == s2l1 &&s1l2 == s2l2 &&s1l3 == s2l3 )  return 1;
    if(s1l1 == s2l2 &&s1l2 == s2l3 &&s1l3 == s2l1 )  return 1;
    if(s1l1 == s2l3 &&s1l2 == s2l1 &&s1l3 == s2l2 )  return 1;

    return 0;
}
double l[4];
void solve(int p1,int p2,int p3){

    l[1] = sqrt(1.0*dis(p1,p2));
    l[2] = sqrt(1.0*dis(p2,p3));
    l[3] = sqrt(1.0*dis(p1,p3));
    sort(l+1,l+4);
    if(l[1]+l[2]<=l[3]+eps&&l[1]+l[2]>=l[3]-eps) return;

    for(int i=1;i<=n-2;++i){
        if(i==p1||i==p2||i==p3) continue;
        for(int j=i+1;j<=n-1;++j){
            if(j==p1||j==p2||j==p3) continue;
            for(int k=j+1;k<=n;++k){
                if(k==p1||k==p2||k==p3) continue;
                if(judge(p1,p2,p3,i,j,k)) ans++;
            }
        }
    }
}

int main(){
    int _ = read(),kcase=0;
    while(_--){
        n=read(); ans = 0;
        for(int i=1;i<=n;++i) scanf("%d%d",&p[i].x,&p[i].y);

        for(int i=1;i<=n-2;++i)
            for(int j=i+1;j<=n-1;++j)
                for(int k=j+1;k<=n;++k)
                    solve(i,j,k);

        printf("Case %d: %d\n",++kcase,ans);
    }
    return 0;
}

2271 X

————————————————————————————————————————————

给你一个无向图,问你最多去掉多少条边,使得剩下的图中 任意两点间最短路长度不变

首先题目手没有自环，于是 需要去重边，边取最短的。

看到n为 100 就想到是floyd

然后 考虑 floyd 中松弛的过程

if(floyd[i][j]>=floyd[i][k]+floyd[k][j])floyd[i][j]=floyd[i][k]+floyd[k][j];if(floyd[i][j] >=floyd[i][k]+floyd[k][j])\\ floyd[i][j] = floyd[i][k]+floyd[k][j];

那么这个过程中，如果边map[i][j]map[i][j] 被松弛了 那么这条边就可以被删掉了,

注意些细节不要计算重复就好了

给队友说完这个思路，然后作为我队唯一图论选手的XXX居然没有认同，，最后认同了写了代码 还wa。。。 我也很绝望啊

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
int n,m,ans;

int mp[111][111];
int fd[111][111];
int vs[111][111];

int main(){
    int _ = read(),kcase = 0;
    while(_--){
        n=read(),m=read(); ans = 0 ;

        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
            fd[i][j]=mp[i][j]=N;vs[i][j]=0;
        }

        for(int i=1,x,y,w;i<=m;i++){
            x=read(),y=read(),w=read();
            if(mp[x][y]!=N){
                ans++;
                if(w<mp[x][y]){
                    mp[x][y]=mp[y][x]=w;
                    fd[x][y]=fd[y][x]=w;
                }
                continue;
            }
            mp[x][y]=mp[y][x]=w;
            fd[x][y]=fd[y][x]=w;
        }

        for(int i=1;i<=n;i++) fd[i][i]=mp[i][i]=0;

        for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
            if(fd[i][j]>=fd[i][k]+fd[k][j]){
                fd[i][j]=fd[i][k]+fd[k][j];
                if(i!=j&&i!=k&&k!=j&&mp[i][j]!=N&&!vs[i][j]){
                    ans++;vs[i][j]=vs[j][i]=1;
                }
            }
        }
        printf("Case %d: %d\n",++kcase,ans);
    }
    return 0;
}