[原创]第七届福建省赛 【(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分 ,相等 不得分,问你所有可能下先手得分的期望
能确定得分的期望 就是任意顺序下总得分除以总的所有可能的轮数
所有可能的轮数 就是( 2 n ) ! (2n)! ( 2 n )! 因为取数是有顺序的 所以就是全排列
然后计算先手的总分
考虑拿先手拿到a i a_i a i 时对结果的贡献.
那就是∑ j = 1 n [ a i > a j ] × ( 2 n − 2 ) ! × C ( n , 1 ) \sum_{j=1}^n[a_i>a_j] \times(2n-2)! \times C(n,1) ∑ j = 1 n [ a i > a j ] × ( 2 n − 2 )! × C ( n , 1 )
后手取的 是( a j ) (a_j) ( a j ) 固定这两个数 然后一共有n n n 轮,这是其中的一轮,所以乘一个C ( n , 1 ) C(n,1) C ( n , 1 ) 而其他的2 n − 2 2n-2 2 n − 2 个数 就又是全排列的
然后约分下式子就是∑ i = 1 n ∑ j = 1 n [ a i > a j ] n ∗ 4 − 2 \dfrac{\sum_{i=1}^n\sum_{j=1}^n[a_i>a_j]}{n*4-2} n ∗ 4 − 2 ∑ i = 1 n ∑ j = 1 n [ a i > a j ]
计算∑ j = 1 n [ a i > a j ] \sum_{j=1}^n[a_i>a_j] ∑ j = 1 n [ a i > a j ] 的时候只要先对a排个序 然后二分就好了
总复杂度是O ( n log n ) O(n\log 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 = 1 n ∑ j = 1 n [ a i > b j ] × C ( n , 1 ) × ( n − 1 ) ! × ( n − 1 ) ! n ! × n ! = ∑ i = 1 n ∑ j = 1 n [ a i > b j ] 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} n ! × n ! ∑ i = 1 n ∑ j = 1 n [ a i > b j ] × C ( n , 1 ) × ( n − 1 )! × ( n − 1 )! = n ∑ i = 1 n ∑ j = 1 n [ a i > b j ]
做法和上题一样,只不过计算分子的时候是对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) ———————————————————————————————————————————— 队友写的 我不知道这个题 。。。 等会儿 补、、
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\ 要算两次 a 全等 b 和 b 全等 a 要算两次
然后考虑如何判定三角形全等,
由初中学过的 ,三边相等就行了, 但是题目要求 可以旋转,但是不能翻转
所以们要对两个图形判定一下,只要O ( 3 ∗ 3 ) O(3*3) O ( 3 ∗ 3 ) 固定一个旋转另一个判定就好了, 有一次满足就行, 但是要注意 描述这两个三角形的时候要采取同样的顺序,要顺时针都是顺时针,否则都逆时针,
然后n只有10 ,所以C ( 10 , 3 ) = 120 , 所以暴力枚举两个三角形在判定是否一样 C(10,3)=120 ,所以暴力枚举两个三角形在判定是否一样 C ( 10 , 3 ) = 120 , 所以暴力枚举两个三角形在判定是否一样
所以总复杂度是O ( C ( 10 , 3 ) 2 ∗ 9 ) 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 中松弛的过程
i f ( f l o y d [ i ] [ j ] > = f l o y d [ i ] [ k ] + f l o y d [ k ] [ j ] ) f l o y d [ i ] [ j ] = f l o y d [ i ] [ k ] + f l o y d [ k ] [ j ] ; if(floyd[i][j] >=floyd[i][k]+floyd[k][j])\\ floyd[i][j] = floyd[i][k]+floyd[k][j]; i f ( f l oy d [ i ] [ j ] >= f l oy d [ i ] [ k ] + f l oy d [ k ] [ j ]) f l oy d [ i ] [ j ] = f l oy d [ i ] [ k ] + f l oy d [ k ] [ j ] ;
那么这个过程中,如果边m a p [ i ] [ j ] map[i][j] ma p [ 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; }