Chen

WIT2018程序设计竞赛题解
武汉工程大学计算机学院2018程序设计竞赛题解A、画个圈圈诅咒你​ 这道题就是一个“简单”的数学题,先把图祭...
扫描右侧二维码阅读全文
12
2018/11

WIT2018程序设计竞赛题解

武汉工程大学计算机学院2018程序设计竞赛题解


A、画个圈圈诅咒你

​ 这道题就是一个“简单”的数学题,先把图祭出来。
970f64a6301fa75ae2eb22.png
首先,我们先来看下这个圆,整道题看来这题貌似根圆没有关系,但是会不会有什么暗示?答案是肯定不存在的。

​ 显而易见,题目给出的公式即是塞瓦定理,通过正弦定理转换一下得出塞瓦定理的角元形式:

​ 塞瓦定理适用于任意三角形,证明自行百度。

$$ \frac{sin\angle BAO}{sin\angle OAC}\cdot \frac{sin\angle ACO}{sin\angle OCB}\cdot \frac{sin\angle CBO}{sin\angle OBA}=1 $$

​ 化下简

$$ \frac{sin\angle BAO}{sin(\frac{\pi}{3} -\angle BAO)} = \frac{sin(\frac{\pi}{3} -\angle ACO)}{sin\angle ACO}\cdot \frac{sin(\frac{\pi}{3} -\angle CBO)}{sin\angle CBO} \\ $$

​ 为了简化计算,我们将三个角重命名$\boldsymbol{a} 、 \boldsymbol{b} 、\boldsymbol{c}$

$$ \frac{sin\boldsymbol{a}}{sin(\frac{\pi}{3} -\boldsymbol{a})} = \frac{sin(\frac{\pi}{3} -\boldsymbol{b})}{\boldsymbol{b}}\cdot \frac{sin(\frac{\pi}{3} -\boldsymbol{c})}{sin\boldsymbol{c}} \\ $$

​ 等式右边的值是已知的,为方便计算,令等式右边值等于$tmp$。注意输入为角度,运算时转换为弧度计算,假设输入$\angle BAO$度数为$60^\circ$ 则相应转换公式为$sin\angle BAO = sin(\frac{60}{180} \cdot \pi)$。防止精度丢失可令 $\pi=acos(-1)$ 。

​ 再次化简(化简过程略,太简单了)

$$ \boldsymbol{T}=sin\boldsymbol{a}=\sqrt{\frac{\frac{3}{4} \cdot tmp^{2}}{tmp^{2}+tmp+1.0}} $$

​ 然后反三角函数答案就出来了

$$ \angle BAO =\boldsymbol{a} = asin\boldsymbol{T} $$

代码:

#include<stdio.h>
#include<math.h>
#define PI acos(-1)
int main() {
    int t;
    double a, b, tmp, x,  ans;
    scanf("%d", &t);
    while(t--) {
        scanf("%lf%lf", &a, &b);
        tmp = sin(PI / 3.0 - a / 180.0 * PI) / sin(a / 180.0 * PI) * sin(PI / 3.0 - b / 180.0 * PI) / sin(b / 180.0 * PI);
        x = sqrt(3.0 / 4.0 * tmp * tmp / (tmp * tmp + tmp + 1.0));
        ans = asin(x) / PI * 180.0;
        printf("%.2f\n", ans);
    }
    return 0;
}

B、咸鱼落泪

​ 本题是一个排序问题,由于数据范围很小,可以用各种姿势过。大家有时间可以去学习下各种排序,本题题解采用一个最简单易懂的排序方法--冒泡排序。

代码:

#include<stdio.h>
int main() {
    int a[105] = {0}; //一般比题目数据范围要求大一点
    int i, j, t, n;
    //数据输入
    scanf("%d", &n);
    for(i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    //冒泡排序
    for(i = 0; i < n - 1; i++) { //n个数的数列总共扫描n-1次
        for(j = 0; j < n - i - 1; j++) { //每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束
            if(a[j] > a[j + 1]) { //后一位数比前一位数小的话,就交换两个数的位置(升序)
                t = a[j + 1];
                a[j + 1] = a[j];
                a[j] = t;
            }
        }
    }
    //输出排列
    for(i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

C、World

​ 这题也没什么好说的,就是考察一下 if 判断和输入输出格式控制,先计算出总价钱,然后再判断是否有优惠,如果有优惠减去优惠金额即可。

代码:

#include<stdio.h>
int main() {
    double n, sum = 0;
    scanf("%lf", &n);
    sum = n * 6;
    if(n >= 15)
        sum -= n * 0.1;
    printf("%.2f", sum);
    return 0;
}

D、Hello

​ 这题你没看错,是送分题,如果你挨着挨着把题目读完了,你会发现已经有人过了这道题。题目要求输出一行 Hello, WITACM!注意写代码直接复制粘贴。

代码:

#include<stdio.h>
int main() {
    printf("Hello, WITACM!\n");
    return 0;
}

E、白色相簿

题意:

  • 判断是否存在3人以上的多元关系

解题思路:

  • 因为不能存在3人以上的关系,即每人最多只能和除自己以外的1个人存在关系

所以记录一下每个人和几个人存在关系,只要存在有人关系数>=2即不稳定

  • 先将题目给出的所有关系排序,删除重复出现的关系,和自身与自身之间的关系。将剩下的关系进行计数,每存在一对关系,两个人的计数+1
  • 最后对所有人进行遍历,看是否存在大于等于2的人,如果存在,说明这个人至少与2个不同的人之间存在关系,输出Error;否则输出Nice
  • 例如:A和B存在关系,A和B计数+1;A和C存在关系,A和C计数+1。最后A计数为2,存在两个不同关系,即不稳定,输出Error

代码:

#include<bits/stdc++.h>
using namespace std;
 
struct abc
{
    int x,y,f;
}s[10005];
 
int a[10005];
 
bool cmp(abc a,abc b)
{
    return (a.x<b.x || (a.x==b.x && a.y<b.y));
}
 
int main()
{
    int i,j,m,n,t,x,y,xx,yy;
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
        cin>>x>>y;
        xx=min(x,y);
        yy=max(x,y);
        s[i].x=xx;
        s[i].y=yy;
        s[i].f=1;
    }
    sort(s+1,s+m+1,cmp);
    for (i=1;i<m;i++)
    {
        if (s[i].x==s[i+1].x && s[i].y==s[i+1].y)
            s[i+1].f=0;
    }
    memset(a,0,sizeof(a));
    for (i=1;i<=m;i++)
        if (s[i].f && s[i].x!=s[i].y)
        {
            a[s[i].x]++;
            a[s[i].y]++;
        }
    bool ans=true;
    for (i=1;i<=n;i++)
        if (a[i]>=2)
        {
            ans=false;
            break;
        }
    if (ans)
        cout<<"Nice"<<endl;
    else
        cout<<"Error"<<endl;
    return 0;
}

F、英雄联盟

题意:

  • 题目描述较长,按照描述规则进行八强抽签模拟,注意理解同组规避原则

解题思路:

  • 按照规则直接模拟即可,先放位置1,从小组第一中选1个;然后位置2,从小组第二中选一个;位置3从剩下3个小组第一中选1个;位置4从剩下3个小组第二中选1个;位置5从剩下2个小组第一中选1个……以此类推
  • 选取时优先按照字典序顺序选取(从小到大), 最终结果共有96种。

    代码:

#include<bits/stdc++.h>
using namespace std;

string s1[4]={"AFS","FNC","KT","RNG"};
string s2[4]={"C9","EDG","G2","IG"};
string s[1000];
map<string,int> a;

int main()
{
    a["AFS"]=1; a["G2"]=1;
    a["RNG"]=2; a["C9"]=2;
    a["KT"]=3;  a["EDG"]=3;
    a["FNC"]=4; a["IG"]=4;
    int i,i1,i2,i3,i4,j1,j2,j3,j4,x=0;
    string t1,t2,t3,t4,t5,t6,t7,t8,tt;
    for (i1=0;i1<4;i1++)
    {
        t1=s1[i1];
        for (j1=0;j1<4;j1++)
        {
            t2=s2[j1];
            for (i2=0;i2<4;i2++)
                if (i2!=i1)
                {
                    t3=s1[i2];
                    for (j2=0;j2<4;j2++)
                        if (j2!=j1)
                        {
                            t4=s2[j2];
                            for (i3=0;i3<4;i3++)
                                if (i3!=i1 && i3!=i2)
                                {
                                    t5=s1[i3];
                                    for (j3=0;j3<4;j3++)
                                        if(j3!=j1 && j3!=j2)
                                        {
                                            t6=s2[j3];
                                            for (i4=0;i4<4;i4++)
                                                if ((i4!=i3) && (i4!=i2) && (i4!=i1))
                                                {
                                                    t7=s1[i4];
                                                    for (j4=0;j4<4;j4++)
                                                        if (j4!=j3 && j4!=j2 && j4!=j1)
                                                        {
                                                            t8=s2[j4];
                                                            if ( (a[t1]!=a[t2] && a[t1]!=a[t3] && a[t1]!=a[t4] && a[t2]!=a[t3] && a[t2]!=a[t4] && a[t3]!=a[t4]) && (a[t5]!=a[t6] && a[t5]!=a[t7] && a[t5]!=a[t8] && a[t6]!=a[t7] && a[t6]!=a[t8] && a[t7]!=a[t8]) )
                                                            {
                                                                tt=t1+" "+t2+" "+t3+" "+t4+" "+t5+" "+t6+" "+t7+" "+t8;
                                                                x++;
                                                                s[x]=tt;
                                                            }
                                                        }
                                                }
                                        }
                                }
                        }
                }
        }
    }
    cout<<x<<endl;
    for (i=1;i<=x;i++)
        cout<<s[i]<<endl;
    return 0;
}

G、禁言大冒险

题意:

  • 禁言规则如题目描述

解题思路:

此题需要分情况讨论,首先是两种大情况:

一、 打断复读的和复读最后一人是同一人,禁言最后一个人

二、 打断复读的和复读最后一人不同,禁言倒数第二个人

对于这两种大情况,每种又细分为4种小情况:

​ 1 、群主(yellow)在,应该禁言的人为群主时,此时向后顺延一个(不管下一个是管理员还是普通群员都直接禁言);

​ 2、 群主不在,应该禁言的为管理员(green)时,此时向后顺延一直找到下一个普通群员

​ 3、 群主在,应该禁言的为管理员或普通群员时,直接禁言

​ 4、 群主不在,应该禁言的为普通群员时,直接禁言

读入数据时先记录群主是否参与复读,然后再分具体情况输出禁言对象

代码:

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int i,j,m,n,t,s;
    string s1[105],s2[105];
    string x,y;
    cin>>n;
    t=0;
    for (i=1;i<=n;i++)
    {
        cin>>s1[i]>>s2[i];
        if (s2[i][0]=='y')
            t=1;
    }
    cin>>x>>y;
    if (x==s1[n])
    {
        if (y[0]=='y')
            cout<<s1[n-1]<<endl;
        else if (y[2]=='e' && t!=1)
        {
            for (i=n-1;i>=1;i--)
            {
                if (s2[i][2]=='a')
                {
                    cout<<s1[i]<<endl;
                    break;
                }
            }
        }
        else
            cout<<x<<endl;
    }
    else
    {
        if (s2[n-1][0]=='y')
            cout<<s1[n-2]<<endl;
        else if (s2[n-1][2]=='e' && t!=1)
        {
            for (i=n-2;i>=1;i--)
            {
                if (s2[i][2]=='a')
                {
                    cout<<s1[i]<<endl;
                    break;
                }
            }
        }
        else
            cout<<s1[n-1]<<endl;
    }
    return 0;
}

H、刺客信条

题意:

  • 从S点出发,到E点,中间经过每个点需要花费时间,经过A、B、C三点时花费时间为100,求最短用时

解题思路:

  • 该题为一道典型的搜索题,搜索从起点到终点的最短路径。
  • 可以在读入处理时直接将A、B、C处理为100,然后进行广度优先搜索
  • 在搜索过程中每走到终点一次,将总用时记录下来,如果小于之前总用时,则更新。凡是大于当前最小总用时的其他道路可以直接放弃(因为继续走下去不可能总用时小于当前用时了)
  • 直到将所有路走完一遍,或剩下的路全都超过当前总用时,搜索终止,输出最终结果。

    代码:

#include<bits/stdc++.h>
using namespace std;

int ans,t,n,m;
int sx,sy,ex,ey;
int a[105][105]={0};
int b[105][105]={0};
int f[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

struct abc
{
    int x,y,t;
};

void BFS(int x,int y)
{
    queue<abc> q;
    abc start;
    start.x=x,start.y=y,start.t=0;
    q.push(start);
    while (!q.empty())
    {
        abc front=q.front();
        q.pop();
        if (front.x<1 || front.x>n || front.y<1 || front.y>m)
            continue;
        else if (front.x==ex && front.y==ey)
        {
            if (ans>front.t)
                ans=front.t;
            continue;
        }
        else if (front.t>ans)
        {
            b[front.x][front.y]=1;
            continue;
        }
        else
        {
            b[front.x][front.y]=1;
            int x1,y1;
            for (int i=0;i<4;i++)
            {
                x1=front.x+f[i][0];
                y1=front.y+f[i][1];
                if (!b[x1][y1])
                {
                    abc v;
                    v.x=x1;
                    v.y=y1;
                    v.t=front.t+a[x1][y1];
                    q.push(v);
                }
            }
        }
    }
}

int main()
{
    int i,j;
    char c;
    cin>>n>>m;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
        {
            cin>>c;
            if (c=='S')
                sx=i,sy=j;
            else if (c=='E')
                ex=i,ey=j;
            else if (c=='A' || c=='B' || c=='C')
                a[i][j]=100;
            else
                a[i][j]=c-'0';
            getchar();
        }
    ans=10000,t=0;
    BFS(sx,sy);
    cout<<ans<<endl;
    return 0;
}

I、太吾绘卷

题意:

  • 按照题目描述计算伤害,注意是回合制游戏

解题思路:

  • 先求出内力总量和U,然后根据公式计算出S与T,再计算出每回合造成的伤害W1和受到的伤害W2
  • 判断一下能否破防,不能则直接输出No
  • 如果可以破防,你打死敌人需要的回合数 = 敌人血量V2/你的伤害W1,敌人打死你的回合数 = 你的血量V1/敌人伤害W2,判断一下你能否在被打死之前打死敌人

注意最后输出结果时,如果你用了n回合打死敌人,那么你只受到了敌人n-1回合的伤害

代码:

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int i,j,m,n,u1=0,u2=0;
    double s1,s2,t1,t2,w1,w2,v1,v2;
    cin>>n;
    for (i=1;i<=n;i++)
    {
        cin>>m;
        u1+=(10-m)*10;
    }
    cin>>u2>>v1>>v2;
    s1=u1*1.0/500;
    t1=u1*1.0/1000;
    s2=u2*1.0/500;
    t2=u2*1.0/1000;
    if (1+s1<=t2 && 1+s2<=t1)
    {
        cout<<"No"<<endl;
        return 0;
    }
    else if (1+s1<=t2 && 1+s2>t1)
    {
        cout<<"No"<<endl;
        return 0;
    }
    else if (1+s2<=t1 && 1+s1>t2)
    {
        printf("%.2lf\n",v1);
        return 0;
    }
    else
    {
        w1=u1*(1+s1-t2);
        w2=u2*(1+s2-t1);
        m=ceil(v2/w1);
        v1=v1-(m-1)*w2;
        if (v1>0)
            printf("%.2lf\n",v1);
        else
            cout<<"No"<<endl;
    }
    return 0;
}

J、玩UNO还是玩斗地主

题意:

  • 给出两人出石头、剪刀、布的概率,计算两人获胜的概率

解题思路:

  • 小A获胜概率 = 小A石头小B剪刀 + 小A剪刀小B布 + 小A布小B石头
  • 即 ans1 = p1*q2 + p2*q3 + p3*q1
  • 小B获胜概率 = 小B石头小A剪刀 + 小B剪刀小A布 + 小B布小A石头
  • 即 ans2 = q1*p2 + q2*p3 + q3*p1
  • $ans_1>ans_2$时小A获胜概率更大,$ans_1<ans_2$时小B获胜概率更大,$ans_1==ans_2$时概率相等

代码:

#include<bits/stdc++.h>
using namespace std;

int main()
{
    double p1,p2,p3,q1,q2,q3;
    double ans1,ans2,ans3;
    while(~scanf("%lf%% %lf%% %lf%%",&p1,&p2,&p3))
    {
        p1/=100; p2/=100; p3/=100;
        scanf("%lf%% %lf%% %lf%%",&q1,&q2,&q3);
        q1/=100; q2/=100; q3/=100;
        ans1=p1*q2+p2*q3+p3*q1;
        ans2=p1*q1+p2*q2+p3*q3;
        ans3=p2*q1+p3*q2+p1*q3;
        if (ans1>ans3)
            cout<<"A"<<endl;
        else if (ans1<ans3)
            cout<<"B"<<endl;
        else
            cout<<"equal"<<endl;
    }
    return 0;
}
Last modification:March 2nd, 2019 at 09:23 am
If you think my article is useful to you, please feel free to appreciate

Comment here is closed