当前位置：首页 > news >正文

ABC354学习笔记

news 来源：原创 2024/9/29 23:32:39

在这里插入图片描述
高桥有一棵植物，这个植物在第 $0$ 天时高度为 $0\,\mathrm{cm}$ ，此后的第 $i$ 天，他的植物会增高 $2^i\,\mathrm{cm}$ 。
高桥身高为 $H\,\mathrm{cm}$ 。
高桥想知道在第几天，他的植物的高度会超过他的身高。

思路：因为数据最多到 $2^{30}$ ，所以可以直接模拟判断。

#include <bits/stdc++.h>
#define int long long
using namespace std;void solve()
{int sum = 0,num = 1,h;cin >> h;for (int i = 1;;i++){sum += num;if (sum > h){cout << i;return ;}num*=2;}
}signed main()
{solve();return 0;
}

在这里插入图片描述
有 $N$ 个人在玩游戏，第 $i$ 个人名字为 $S_i$ ，评级为 $C_i$ 。
设 $T$ 的值为 $\displaystyle\sum_{i=0}^N C_i$ ，再按照名字的字典序一次分配给他们编号 $0,1,\dots,N-1$ ，编号为 $T\bmod N$ 的人获胜。

思路：先用结构体排序，再计算编号，输出名字。

#include <bits/stdc++.h>
#define int long long
using namespace std;struct node
{string s;int a;
}a[200];bool cmp(node a,node b)
{return a.s < b.s;
}void solve()
{int n,sum = 0;cin >>n;for (int i = 1;i <= n;i++){cin >> a[i].s >> a[i].a;sum += a[i].a;}sum %= n;sort(a+1,a+n+1,cmp);cout << a[sum+1].s;
}signed main()
{solve();return 0;
}

在这里插入图片描述
给定 $n$ 张卡牌，第 $i$ 张卡牌有强度 $a_i$ 和花费 $c_i$ 。
对于卡牌 $i, j$ ，如果 $a_i > a_j$ 且 $c_i < c_j$ ，卡牌 $j$ 将会被丢弃。
我们一直重复以上操作，问最后剩下的牌是哪些。

思路：因为只要一个数与另一个数满足条件，这张牌就会被丢掉。所以我们先按照花费排序，然后用最大的强度和一张牌比，看看是否会被丢掉。

#include <bits/stdc++.h>
//#define int long long
using namespace std;int n;
struct node
{int a,c;int id;
}a[200010];
bool cmp(node a,node b) {return a.c < b.c;}vector <int> ans;void solve()
{cin >> n;for (int i = 1;i <= n;i++)cin >> a[i].a >> a[i].c,a[i].id = i;sort(a+1,a+n+1,cmp);int mx = 0;for (int i = 1;i <= n;i++)if (a[i].a > mx){mx = a[i].a;ans.push_back(a[i].id);}sort(ans.begin(),ans.end());cout << ans.size() << '\n';for (int i = 0;i < ans.size();i++)cout << ans[i] << ' ';
}signed main()
{solve();return 0;
}