首页 > 代码库 > 东南大学第十三届程序设计竞赛初赛题解
东南大学第十三届程序设计竞赛初赛题解
问题 A: 天梯评分系统
题目描述
在一个下雨的日子,沈学姐和四个好基友约定无事一同打dota(dota是一个5对5的MOBA类游戏)因为想证明谁最NB,他们就全部注册新号去爬天梯了。天梯有一套完整的评分系统,它可以根据每位选手每局的数据进行评分,因为dota的英雄既有辅助又有ganker还有后期,所以不同的英雄的评分标准不一样。可惜那天天梯服务器维护,无法进行评分。于是,他们记录下每一局的数据,找你来帮忙,希望你能够帮他们仿照天梯编一个评分系统,以便于他们比较谁是真正的神牛。
已知对于每个账号每个英雄的初始积分都是1200分,并且该账号的天梯积分是所有使用过的英雄的积分的加权平均数(按次数加权,最终用整除)。每局一个英雄的数据包括主数据(杀敌/死亡/助攻)和附数据(破塔/正补/反补),你会得到所出现的英雄的主数据评分标准。此外还会根据附数据评出 MVP,英魂,富豪,破军,偏将,补王的称号,每个称号都有一个得分。而每局英雄的最终得分是由胜负、初始积分、主数据得分和附数据得分决定的。
主数据得分:每个英雄都有对应的 x,y,z 三个评分参数。主数据得分是:杀敌数*x+死亡数*y+助攻数*z
胜负得分:胜利不影响正常的分,失败方额外扣去 200 分;
附数据得分:MVP:胜利方主数据得分最高者获得 MVP,额外得到 20 分;英魂:失败方主数据得分最高者获得英魂,免去失败扣分;
以下称号仅胜利方获得:
富豪:每个正补得到 40 金钱,每个杀敌得到 250 金钱,每次死亡失去 100 金钱,每次破塔得到 450 金钱,每局游戏获得金钱最多者获得富豪,额外得到10 分;
破军:破塔最多者获得破军,额外得到 10分;
偏将:助攻最多者获得偏将,额外得到 10 分;
补王:反补最多者获得补王,额外得到 10 分;
最终得分=初始积分+主数据得分+附数据的分+胜负得分;输入
第一行为一个整数T,代表有T组数据。
对于每组数据:
第一行一个整数 n (n<=15),代表所要用到的 n 个英雄主数据评分标准;
第 2到n+1行,第i行三个整数 x,y,z(0<x,z<=10,-10<=y<0,x+z=10),代表编号为i-1的英雄的评分参数。
第 n+2 行一个整数 m (m<=5),代表玩的局数,
n+3 行到第 n+m*6+3 行每 6 行为一组,共m组代表m局游戏,每组第一到第五行代表每局游戏第一个人到第五人的数据,每一行7个正整数,h代表此局该人使用的英雄编号,a,b,c,d,e,f(a,b,c<=20,d<=11,e,f<=100),代表杀敌/死亡/助攻/破塔/正补/反补,第六行一个数,0代表失败,1代表胜利。输出
对于第i组数据先输出一行“Case #i:”(不含引号)
接下来输出五行,每行一个数,第i行为第i个人的最终天梯积分。
样例输入
1
5
8 -8 2
2 -3 8
9 -5 1
5 -5 5
4 -6 6
1
1 9 1 5 4 90 20
2 1 4 9 0 14 10
3 11 4 2 2 58 44
4 6 2 4 1 33 31
5 7 4 6 1 22 24
1
样例输出
Case #1:
1294
1272
1311
1240
1240
题解
模拟题。题目大意是说5个人开黑打dota,打了m盘,问每个人最终的天梯积分。
注意每个人的天梯积分是所有使用过的英雄的积分的加权平均数(按次数加权,最终用整除)。
设数组g[i][j]表示第i个人使用第j个英雄的英雄积分,cnt[i][j]表示第i个人使用第j个英雄的次数。
最终第i个人的积分为∑(g[i][j]*cnt[i][j])/∑cnt[i][j]。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 using namespace std; 5 6 const int INF = 1e8; 7 8 int g[6][16]; 9 int h[6],cnt[6][16]; 10 int hero_x[15 + 5], hero_y[15 + 5], hero_z[15 + 5]; 11 12 int main() 13 { 14 int t; 15 cin >> t; 16 for (int i = 1; i <= t; i++) 17 { 18 int n; 19 cin >> n; 20 for (int j = 1; j <= 5; j++) 21 for (int k = 1; k <= n; ++k) 22 { 23 g[j][k] = 1200; 24 cnt[j][k] = 0; 25 } 26 for (int j = 1; j <= n; j++) 27 { 28 scanf("%d %d %d", &hero_x[j], &hero_y[j],&hero_z[j]); 29 } 30 int m; 31 cin >> m; 32 for (int k = 1; k <= m; ++k) 33 { 34 int max_main_g = -INF, max_main_w=-1; 35 int max_gold_g = -INF, max_gold_w = -1; 36 int max_pojun_g = -INF, max_pojun_w = -1; 37 int max_pianjiang_g = -INF, max_pianjiang_w = -1; 38 int max_buwang_g = -INF, max_buwang_w = -1; 39 for (int j = 1; j <= 5; j++) 40 { 41 int a, b, c, d, e, f; 42 scanf("%d %d %d %d %d %d %d", &h[j], &a, &b, &c, &d, &e, &f); 43 cnt[j][h[j]]++; 44 int main_g = a*hero_x[h[j]] + b*hero_y[h[j]] + c*hero_z[h[j]]; 45 g[j][h[j]] += main_g; 46 if (main_g > max_main_g) max_main_g = main_g, max_main_w = j; 47 48 int gold = 40 * e + 250 * a - 100 * b + 450 * d; 49 if (gold > max_gold_g) max_gold_g = gold, max_gold_w = j; 50 51 if (d > max_pojun_g) max_pojun_g = d, max_pojun_w = j; 52 53 if (c > max_pianjiang_g) max_pianjiang_g = c, max_pianjiang_w=j; 54 55 if (f > max_buwang_g) max_buwang_g = f, max_buwang_w = j; 56 } 57 int isWin; 58 cin >> isWin; 59 if (isWin == 1) 60 { 61 g[max_gold_w][h[max_gold_w]] += 10; 62 g[max_pojun_w][h[max_pojun_w]] += 10; 63 g[max_pianjiang_w][h[max_pianjiang_w]] += 10; 64 g[max_main_w][h[max_main_w]] += 20; 65 g[max_buwang_w][h[max_buwang_w]] += 10; 66 } 67 else 68 { 69 for (int j = 1; j <= 5; j++) 70 g[j][h[j]] -= 200; 71 g[max_main_w][h[max_main_w]] += 200; 72 } 73 } 74 printf("Case #%d:\n", i); 75 for (int j = 1; j <= 5; j++) 76 { 77 int sum = 0, sum_cnt = 0; 78 for (int k = 1; k <= n; ++k) 79 { 80 sum += cnt[j][k] * g[j][k]; 81 sum_cnt += cnt[j][k]; 82 } 83 cout << sum / sum_cnt << endl; 84 } 85 } 86 return 0; 87 }
问题 B: 三体问题
题目描述
沈学姐是一个科幻小说爱好者,最近她读了《三体》,喜欢数学的学姐对三体问题产生了兴趣。当然,学姐并不想去算某颗行星的轨道。
她把整个三体星系简化为一个平面,三颗恒星的球心投影成平面上的三点,每颗恒星都有一个半径为r的圆形引力场(r由恒星自身属性决定)。学姐想知道,三颗恒星的引力场总面积是多少。
输入
第一行为一个整数T,表示数据组数。
每组数据有三行输入:
每行有三个数x,y,r(保留两位小数),分别为该恒星中心坐标(x,y)和引力场半径r。
(|x|<=5,|y|<=5,0<=r<=5)
输出
对于第i组数据,输出一行,形如“Case #i: ans”(不含引号)
其中,ans表示引力场总面积,保留整数部分(因为学姐不想太难)。
样例输入
2 0.00 0.00 1.00 0.00 2.00 1.00 2.00 0.00 1.00 0.00 0.00 5.00 1.00 1.00 2.22 2.00 0.00 1.00
样例输出
Case #1: 9 Case #2: 79
题解
本题约束输出整数,意味着可以小步长step枚举点,判断点是否在圆内,若在则累加面积step*step。
此问题的一般形式:圆的面积并问题,使用辛卜生求积公式,代码转自->这里
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 8 #define ld double 9 #define eps 1e-13 10 11 int n,top,st,ed; 12 ld xl[1001],xr[1001]; 13 ld ans; 14 bool del[1001]; 15 16 struct data{ld x,y,r;}t[1001],sk[1001]; 17 struct line{ld l,r;}p[1001]; 18 19 ld dis(data a,data b) 20 {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} 21 22 bool cmp1(data a,data b){return a.r<b.r;} 23 24 bool cmp2(data a,data b){return a.x-a.r<b.x-b.r;} 25 26 bool cmp3(line a,line b){return a.l<b.l;} 27 28 void ini() 29 { 30 memset(del,0,sizeof(del)); 31 n=3; 32 for(int i=1;i<=n;i++) 33 {scanf("%lf%lf%lf",&t[i].x,&t[i].y,&t[i].r);} 34 sort(t+1,t+n+1,cmp1); 35 for(int i=1;i<=n;i++) 36 for(int j=i+1;j<=n;j++) 37 if(dis(t[i],t[j])<=t[j].r-t[i].r) 38 {del[i]=1;break;} 39 for(int i=1;i<=n;i++)if(!del[i])sk[++top]=t[i];n=top; 40 sort(sk+1,sk+n+1,cmp2); 41 } 42 43 ld getf(ld x) 44 { 45 int sz=0,i,j;ld r,len=0,dis; 46 for(i=st;i<=ed;i++) 47 { 48 if(x<=xl[i]||x>=xr[i])continue; 49 dis=sqrt(sk[i].r-(x-sk[i].x)*(x-sk[i].x)); 50 p[++sz].l=sk[i].y-dis;p[sz].r=sk[i].y+dis; 51 } 52 sort(p+1,p+sz+1,cmp3); 53 for(i=1;i<=sz;i++) 54 { 55 r=p[i].r; 56 for(j=i+1;j<=sz;j++) 57 { 58 if(p[j].l>r)break; 59 if(r<p[j].r)r=p[j].r; 60 } 61 len+=r-p[i].l;i=j-1; 62 } 63 return len; 64 } 65 66 ld cal(ld l,ld fl,ld fmid,ld fr) 67 {return (fl+fmid*4+fr)*l/6;} 68 69 ld simpson(ld l,ld mid,ld r,ld fl,ld fmid,ld fr,ld s) 70 { 71 ld m1=(l+mid)/2,m2=(r+mid)/2; 72 ld f1=getf(m1),f2=getf(m2); 73 ld g1=cal(mid-l,fl,f1,fmid),g2=cal(r-mid,fmid,f2,fr); 74 if(fabs(g1+g2-s)<eps)return g1+g2; 75 return simpson(l,m1,mid,fl,f1,fmid,g1)+simpson(mid,m2,r,fmid,f2,fr,g2); 76 } 77 78 void work() 79 { 80 int i,j;ld l,r,mid,fl,fr,fmid; 81 for(i=1;i<=n;i++){xl[i]=sk[i].x-sk[i].r;xr[i]=sk[i].x+sk[i].r;sk[i].r*=sk[i].r;} 82 for(i=1;i<=n;i++) 83 { 84 l=xl[i];r=xr[i]; 85 for(j=i+1;j<=n;j++) 86 { 87 if(xl[j]>r)break; 88 if(xr[j]>r)r=xr[j]; 89 } 90 st=i;ed=j-1;i=j-1; 91 mid=(l+r)/2; 92 fl=getf(l);fr=getf(r);fmid=getf(mid); 93 ans+=simpson(l,mid,r,fl,fmid,fr,cal(r-l,fl,fmid,fr)); 94 } 95 } 96 97 int main() 98 { 99 int T; 100 cin>>T; 101 for(int i=1;i<=T;++i) 102 { 103 ini(); 104 work(); 105 printf("Case #%d: %.0f\n",i,ans); 106 ans=top=st=ed=0; 107 } 108 return 0; 109 }
问题 C: 男票管理系统
签到题,略。
1 #include<iostream> 2 #include<vector> 3 4 using namespace std; 5 6 int bf[2000]; 7 int s = 0; 8 9 void init() 10 { 11 for (int i = 0; i < 2000; ++i) 12 { 13 bf[i] = 0; 14 } 15 } 16 17 long long calc() 18 { 19 long long ans = 0; 20 for (int i = 0; i < s; ++i) 21 { 22 for (int j = i + 1; j < s; ++j) 23 { 24 if (bf[j] > bf[i]) 25 { 26 ++ans; 27 } 28 } 29 } 30 return ans; 31 } 32 33 int main() 34 { 35 int num = 0; 36 cin >> num; 37 vector<long long> ans; 38 for (int i = 0; i < num; ++i) 39 { 40 init(); 41 cin >> s; 42 for (int j = 0; j < s; ++j) 43 { 44 cin >> bf[j]; 45 } 46 47 ans.push_back(calc()); 48 } 49 int i = 1; 50 for (auto t = ans.begin(); t != ans.end(); ++t) 51 { 52 cout << "Case #" << i++ << ": " << *t << endl; 53 } 54 return 0; 55 }
问题 D: 男票的名字
二分+hash
问题 E: 学姐招亲
暂无思路。
问题 F: 学姐护卫队
树状数组
问题 G: 礼物分配
暂无思路。
问题 H: 学姐的树
基于期望的DP
问题 I: 谁是卧底
并查集裸题,略。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 using namespace std; 5 6 int f[2010]; 7 8 int find(int x) 9 { 10 int r = x; 11 while (f[r] != r) 12 r = f[r]; 13 14 int i = x, j; 15 while (i != r) 16 { 17 j = f[i]; 18 f[i] = r; 19 i = j; 20 } 21 return r; 22 } 23 24 25 void join(int x, int y) 26 27 { 28 int fx = find(x), fy = find(y); 29 if (fx != fy) 30 f[fx] = fy; 31 } 32 33 int main() 34 { 35 int t; 36 cin >> t; 37 for (int i = 1; i <= t; ++i) 38 { 39 int n, m; 40 scanf("%d %d", &n, &m); 41 for (int j = 1; j <= n; ++j) 42 f[j] = j; 43 f[2001] = 2001; 44 f[2002] = 2002; 45 f[2003] = 2003; 46 for (int j = 1; j <= m; j++) 47 { 48 int k, x, y; 49 scanf("%d %d %d", &k, &x, &y); 50 if (k == 1) 51 { 52 join(x, y); 53 } 54 else 55 { 56 join(x, 2000 + y); 57 } 58 } 59 int flag = 0; 60 for (int j = 1; j <= n; ++j) 61 { 62 int fa = find(f[j]); 63 if (!(fa == find(2001) || fa == find(2002) || fa == find(2003))) 64 { 65 flag = 1; 66 break; 67 } 68 } 69 if (flag == 0) 70 { 71 printf("Case #%d: YES\n", i); 72 } 73 else 74 { 75 printf("Case #%d: NO\n", i); 76 } 77 } 78 return 0; 79 }
问题 J: 去吧贝塔
分类讨论题
问题 K: 反立方数
题目描述
立方数是形如x3的数,如1,8,27...
定义反立方数为:所有非1因子中不含有立方数的数。
学姐想知道在区间[L,R]中,所有反立方数的平方和。
由于答案可能很大,输出结果对19260817的取模即可。
输入
第一行一个整数T,表示有T组数据。
接下来T行:
每行为两个整数L,R。(1<=L<=R<=10^18)
输出
对每组数据输出一行,形如”Case #i: ans”(不含引号)
ans为区间[L,R]中所有反立方数的平方和
样例输入
2 1 5 1 10
样例输出
Case #1: 55 Case #2: 321
题解
容斥原理。
预处理10^6以内的质数,作为立方数的原数。
暴力搜索10^6以内质数的组合,注意保证没有重复的数字,比如2*2不合法,因为2*2的倍数包含在2的倍数里;以及重复的组合,比如2*3*5和3*2*5是重复的。
设sum=(1^3)^2+(2^3)^2+...+(n^3)^2
设cnt为立方数的平方和。对于枚举到的素数组合,若组合数的个数为奇数,则cnt加上该组合数所有倍数的平方和,用平方和公式计算;若为偶数,则减去。
根据容斥原理,n以内的反立方数的平方和ans=sum-cnt。
答案为ans(r)-ans(l-1)。
需要注意MOD的使用,很容易遗漏MOD导致爆long long。
另外程序中会用到(A/B)%MOD,根据费马小定理,(A/B)%MOD=A*B^(MOD-2)。
东南大学第十三届程序设计竞赛初赛题解