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 阿老师授课

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

#includeusing 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;//如果左边面积小，那么左边界就变成midelse 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，需要添加头文件mathcout<<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)搞完初赛题解

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！