gdufe22年程序设计赛题解

IT文化节程序设计赛初赛 Problem A. 可莉上学啦

思路：模拟，没有特殊的技巧。不过很坑的点就是判断是否是三角形，最后输出的是YE5，N0(N后面居然要输出的是0)，WTF！！

#include
#include
#include
using namespace std;
const int N=5;
int len[N];

int main()
{
   
    cin>>len[0]>>len[1]>>len[2];
    sort(len,len+3);
    int a=len[0],b=len[1],c=len[2];
    if(((a+b>c)&&(c-a<b))&&(c-b<a)){
        cout<<"YE5"<<endl;
        if(a==b&&a==c)cout<<"Equilateral triangle!"<<endl;
        else if(a==b||b==c){
            if(a*a+b*b==c*c)cout<<"Isosceles right triangle!"<<endl;
            else cout<<"Isosceles triangle!"<<endl;
        }
        
        else if(a*a+b*b==c*c){
            cout<<"Right triangle!"<<endl;
        }
        else {
            cout<<"Triangle!"<<endl;
        }
    }
    else cout<<"No"<<endl;
    
    return 0;
}

Problem B. 赌上骑士的荣誉

思路：知识是背景囚徒困境的一道题目，有关数学背景可以看的3blue3brown的有关囚徒困境的视频。题目贼长，很绕。

最后的ac的思路是，判断K的n次方能否被n整除。数据范围给的很大，0<=n,k<=10^18。那么此时我们如果用c++自带的pow函数然后直接去求余应该会寄，开模拟赛测试了一下，果然寄。赛后出题人给出的标程，求

代码

#include
using namespace std;
typedef long long ll;
int main() {
    int q=1;
    while(q--){
        ll n,k;
        cin>>n>>k;
        for(int i=1;i<=64;i++)//i小于等于64，因为long long只有64位
        {
            n/=__gcd(n,k);
            if(__gcd(n,k)==1) break;
        }
        if(n==1) cout<<"I am the king of the world!\n";
        else cout<<"Human fall flat!\n";
    }
}

Problem c 阿老师授课

思路：因为求两块面积相等那么，分别求面积，在用二分逼近求那个点。值得注意的是，求面积时要将所有表示边的表达式绝对值化。
代码

#include

using namespace std;
double x,y,a,b;
double p02(double p)//两点式做直线方程，求出我们需要的mid直线的y坐标
{
   double xx0=x,yy0=y+b,xx2=x+a,yy2=y;
   double res=(yy2-yy0)*1.0/(xx2-xx0)*(p-xx0)+yy0;
    return res-y;
}
int main()
{
    
    cin>>x>>y>>a>>b;
    
   
    double s1=100,s2=0;
    double l=x,r=x+a;
    double mid=(l+r)/2;
   
    while(abs(s1-s2)>=1e-8)
    {  
        mid=(l+r)/2;
        s1=(abs(b)+abs(p02(mid)))*abs(mid-x)/2;
        s2=abs(p02(mid))*abs(x+a-mid)/2;
        if(s1-s2<0)l=mid;//如果左边面积小，那么左边界就变成mid
        else r=mid;//反之右边界为mid
        //如此一来不断逼近那个正确的指
    }
    
    
    cout<<mid<<endl;
    return 0;
}

Problem D.白鹭霜华华

思路：期望问题，一开始我以为可以用几何概形的思路能过的，后来发现
我连样例都过不了，寄！！ ac思路，直接看下面的出题背景。

出题背景：
代码：

#include 
#include
using namespace std;

int main()
{
   double x;
   cin>>x;
   x=1/x;
   //exp(x)相当于e^x，需要添加头文件math
   cout<<exp(x)<<endl;
}

Problem E

思路：模拟题，需要找出给出的正方块图像的特点来数正方体，很折磨
想了很久也没有做出来，出题人给出的解题思路

代码：

#include 
using namespace std;
int r, c;
char mp[555][555];
int main()
{
    cin >> r >> c;
    for (int i = 1; i <= r; i++){
        getchar();
        for (int j = 1; j <= c; j++)
            cin >> noskipws >> mp[i][j];//noskipws是输入控制符
    }
    
    int p = strstr(mp[r] + 1, ".") - mp[r];
    int m = p - 2 >> 2, n = c - p + 1 >> 1;
    int ans = m * n * (r - n);
    for (int i = 2; i <= r; ++i)
    {
        int now = 1;
        char *tmp;
        while (tmp = strstr(mp[i] + now, "/   /"))
            ans -= i, now = tmp - mp[i] + 4;
    }
    cout << ans / 3 << '\n';
    return 0;
}

Problem F.帝君算数

思路：就是将n,m范围内的k的倍数分别计数，然后相乘就可以得到结果了。

代码

#include
using namespace std;
typedef long long LL;
int main()
{
    LL n,m,k,c=0,p=0,t=0;
    cin >> n >> m >> k;
    for(LL i = k; i <= n; i+=k)
    {
        p++;
    }
    for(LL i = k; i <= m; i+=k)
    {
        t++;
    }
    cout << p*t << endl;
    return 0;
}

Problem G.华山论剑

思路: 构造题，因为杨辉三角的每一层之和都为2^（n-1），因此我们将每一个数都可以视为1个30位的二进制数(因为数据范围位1<= n <= 2^9 ),如此我们就可以，如果当前位有1，那么我们就加上这一行，如果没有就跳过，因为题目需要一条路径，导致我们不论是否需要，必须经过一行，所以我们提前减去30，来设置提前量，再在后面加上去。

代码：

#include 
using namespace std;
typedef pair<int,int>PII;
int main(void){
    int n;
    cin >> n;

    if(n <= 30){  //当n小于30时，直接一条路过去，不断加一
        cout << n << '\n';
        for(int i = 0; i <= n - 1; i++){
            cout << i << " " << i << '\n';
        }

    } else{
        //px代表行，py代表列
        int cnt = 0, r = n - 30, px = 0, py = 0, g = 30, bit = 0;
        vector<PII> ans;
        ans.push_back({px, py});//存入(0,0)这个点，即最开始的点

        if(r & 1)//如果r是偶数，即二进制最低位不为1，判断为false，否则判断为true
        {
            r--;
        }
         else{
            g--;
        }

        while(r){
            if(r & (1 << (bit + 1))){//判断当前位是否为1

        //因为题目规定的方式，我们必须从头读到尾，再从尾读到头的形式读入每一行
                if(py)
                {
                    px++; py++;
                    while(py){ ans.push_back({px, py}); py--; }
                    ans.push_back({px, py});
                } else{
                    px++;
                    while(py <= bit){ ans.push_back({px, py}); py++; }
                    ans.push_back({px, py});
                }
                r -= (1 << (bit + 1));
            }
            //如若为0，就读入这一行的最左边或最右边1，跳到下面一行去
           else{
                g--;
                //如果计算的是右边的1，那么需要不断y不断向右边多走一格
                px++; if(py) py++;
                ans.push_back({px, py});
            }
            bit++;
        }
        //计算剩下的
        for(int i = 1; i <= g; i++){
            px++; if(py) py++;
            ans.push_back({px, py});
        }
        //算出有多少个数组
        cout << ans.size() << '\n';
        //遍历数组给出答案
        for(auto x : ans){
            cout << x.first << " " << x.second << '\n';
        }
    }
    return 0;
}

Problem H.刻晴的小说

思路：
因为数据大小是 10^5 ，只能循环一次，如果想要按照它的规则去用构造图的方式去写并查集或者搜索，就会tle，比赛a了很久没有出来，但是我有队友。

代码：

#include 
 
using i64 = long long;
 
void solve() {
    int n;
    std::cin >> n;
     
    std::vector<int> a(n), b(n);//声明了一个n大小的，且初始值为0的vector 
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        b[i] = a[i];
        if (i > 0) {
            a[i] = std::max(a[i], a[i - 1]);//找出每一段最大那个
        }
    }
    
    for (int i = n - 2; i >= 0; i--) {
        b[i] = std::min(b[i], b[i + 1]);//找出每一段最小那个
    }
    
    int ans = 1;
    for (int i = 0; i < n - 1; i++) {
        ans += (a[i] < b[i + 1]);//如果出现一个前面最大比后面最小的还有小的话，就会加1
    }
    
    std::cout << ans << "\n";
}
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t = 1;（）
    
    while (t--) {
        solve();
    }
    
    return 0;
}

初赛赛后评论：

题面原味很浓，而且群里那个林忽悠一直在说这里简单简单，我只能说你麻麻的，这还能算简单？我以为puts(hello world); ，你给我N0。也可能是我太蒟蒻了吧，大哭，等复赛后继续补复赛题目。

---

至于为什么只有解，没有题目的原因，图难截，上传又太麻烦了，并且这个题解是个人向题解

---

(5.11)夜以深，先鸽为敬。明日再补
(5.12)搞完初赛题解