开始水一波博客
题目链接: https://www.jisuanke.com/contest/1403
A. Choosing Ice Cream
传送门 https://nanti.jisuanke.com/t/28201
题意就是 n 个冰淇淋, 骰子有 k 个面, 问你是否能在公平的概率下转几次骰子能确定买哪个冰淇淋.
举个例子, 假设我只有一个冰淇淋, 我不用转骰子直接就会买这个, 所以转骰子的次数是 0, 如果我有 4 个冰淇淋, 2 个骰子面, 我可以先把冰淇淋 abcd 分成两部分, ab 一组, cd 一组, 这是等概率的, 我先转一次骰子确定是选 ab 组还是 cd 组, 然后再转一次就可以确定买哪个了. 如果我有 6 个冰淇淋, 12 个面, 我可以每一种冰淇淋贴 2 个面, 转一次就可以确定了. 个人理解是这种意思.
这个题读题猜题意猜了好久 (捂脸 ==), 题意猜对之后还是没过, 最后发现是 gcd 是变化的, 所以每循环一次就要重新算一遍 gcd,1 的情况特判一下就可以了.
代码:
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- #include<iomanip>
- #include<stdio.h>
- #include<math.h>
- #include<cstdlib>
- #include<set>
- #include<map>
- #include<ctime>
- #include<stack>
- #include<queue>
- #include<vector>
- #include<set>
- #define ll long long int
- #define INF 0x7fffffff
- #define LIT 0x3f3f3f3f
- #define mod 1000000007
- #define me(a,b) memset(a,b,sizeof(a))
- #define PI acos(-1.0)
- #define ios ios::sync_with_stdio(0),cin.tie(0);
- using namespace std;
- const int maxn=1e5+5;
- int main(){
- int t,n,k;
- scanf("%d",&t);
- while(t--){
- scanf("%d%d",&n,&k);
- if(n==1){
- printf("0\n");
- continue;
- }
- int c=__gcd(n,k);
- if(c==1){
- printf("unbounded\n");
- continue;
- }
- int ans=0;
- while(c!=1){
- n/=c;
- c=__gcd(n,k);
- ans++;
- }
- if(n==1)
- printf("%d\n",ans);
- else
- printf("unbounded\n");
- }
- }
- View Code
- B. Failing Components
传送门 https://nanti.jisuanke.com/t/28202
题意就是单向图, 从起点开始找最短路, 然后统计一下个数就可以. 方向是从 b 到 a, 权值为 s.
直接最短路跑迪杰斯特拉, 一开始用数组版的没过, 换了一个队列版的过了.
代码:
- //B
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #include<cstdlib>
- #include<queue>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- const int maxn=1e5+10;
- const double eps=1e-7;
- const int N=1e5+10;
- const int INF=0x3f3f3f3f;
- int head[N*2], nex[N*2], to[N*2], val[N*2], dis[N], vis[N], tot;
- struct cmp{
- bool operator()(int a,int b) {
- return dis[a]>dis[b];
- }
- };
- priority_queue<int, vector<int>, cmp> Q;
- void init() {
- tot = 0;
- while(!Q.empty()) Q.pop();
- memset(head, -1, sizeof(head));
- memset(dis, INF, sizeof(dis));
- memset(vis, 0, sizeof(vis));
- }
- void addedge(int u, int v, int w) {
- to[tot] = v;
- nex[tot] = head[u];
- val[tot] = w;
- head[u] = tot++;
- }
- void Dijkstra(int S) {
- Q.push(S);
- dis[S] = 0;
- while(!Q.empty()) {
- int u = Q.top();
- Q.pop();
- for(int i=head[u]; i!=-1; i=nex[i]) {
- int v = to[i];
- if(!vis[v] && dis[u]+val[i] <dis[v]) {
- dis[v] = dis[u]+val[i];
- Q.push(v);
- }
- }
- }
- }
- int main(){
- int t;
- scanf("%d",&t);
- while(t--){
- init();
- int n,p,k;
- scanf("%d%d%d",&n,&p,&k);
- int h,l,val;
- for(int i=0;i<p;i++){
- scanf("%d%d%d",&h,&l,&val);
- addedge(l,h,val);
- }
- Dijkstra(k);
- int num=0;
- int maxx=-1;
- for(int i=1;i<=n;i++)
- {
- if(dis[i]!=INF)
- {num++;maxx=max(maxx,dis[i]);}
- }
- cout<<num<<" "<<maxx;
- cout<<endl;
- }
- return 0;
- }
- View Code
- F. Runway Planning
传送门 https://nanti.jisuanke.com/t/28206
题意简直就是有毒, 中间 bb 一堆都是没用的, 主要的意思就是度数大于 180 度的就先减去 180 度, 然后除以 10, 四舍五入的值就是答案. 如果最后结果是 0 就输出 18 就可以, 其他没了, 看懂题意就是水题.
代码:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- #include<cstdlib>
- using namespace std;
- typedef long long ll;
- const int maxn=1e5+10;
- int main(){
- int t;
- scanf("%d",&t);
- while(t--){
- int n,ans;
- scanf("%d",&n);
- if(n>=180)n-=180;
- int cnt=n%10;
- if(cnt>=5)ans=n/10+1;
- else ans=n/10;
- if(ans==0){
- if(cnt>=5)ans=1;
- else ans=18;
- }
- printf("%02d\n",ans);
- }
- }
- View Code
其他题并不想补题, 因为不想看题目猜题意, 去看别的东西了.
吐槽一下, 这场比赛全是阅读理解题, 我看不懂题意, 以后要训练一下读题能力, 英语等级考试水平和能不能读懂题一毛钱关系都没有.
Debug 能力也要训练一下, 因为自己 Debug 能力实在是差到变形.
受不了, 为什么我队友还不理我, 简直要哭死了 (我错了, 我错了, 小声 bb...)
来源: http://www.bubuko.com/infodetail-2676751.html