[原创]第七届福建省赛 【(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)!$ 因为取数是有顺序的 所以就是全排列
然后计算先手的总分
考虑拿先手拿到$a_i$时对结果的贡献.
那就是 $\sum_{j=1}^n[a_i>a_j] \times(2n-2)! \times C(n,1)$
后手取的 是$(a_j)$ 固定这两个数 然后一共有$n$轮,这是其中的一轮,所以乘一个$C(n,1)$
然后约分下式子就是$\dfrac{\sum_{i=1}^n\sum_{j=1}^n[a_i>a_j]}{n*4-2}$
计算$\sum_{j=1}^n[a_i>a_j]$的时候只要先对a排个序 然后二分就好了
总复杂度是$O(n\log n)$
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) ————————————————————————————————————————————
只不过 先手只能那自己的那个序列里面的数 后手同理
公式为
做法和上题一样,只不过计算分子的时候是对b进行二分
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这么做过去了,但是我菜啊 调了很久 还是不行,最终放弃..)
正解是后缀数组
首先能想到对两个序列 进行类似归并的过程，取最大的。
应该用后缀数组来处理，
附带一点数据,
//#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\ 要算两次$
然后考虑如何判定三角形全等,
由初中学过的 ,三边相等就行了, 但是题目要求 可以旋转,但是不能翻转
所以们要对两个图形判定一下,只要$O(3*3)$固定一个旋转另一个判定就好了, 有一次满足就行,
然后n只有10 ,所以$C(10,3)=120 ,所以暴力枚举两个三角形在判定是否一样$
所以总复杂度是$O(C(10,3)^2*9)$
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 中松弛的过程
那么这个过程中，如果边$map[i][j]$ 被松弛了 那么这条边就可以被删掉了,
注意些细节不要计算重复就好了
给队友说完这个思路，然后作为我队唯一图论选手的XXX居然没有认同，，最后认同了写了代码 还wa。。。 我也很绝望啊
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; }
