CCPC2018-湖南全国邀请赛
2021/10/22 23:09:37
本文主要是介绍CCPC2018-湖南全国邀请赛,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A - Easy $h$-index
思路:
这题题目说的太晦涩难懂了,英语不好直接炸掉,简单来说就是找到一个引用次数,使得至少引用这些次数的文章的数量要大于这个引用数,因为是至少,所以比如说至少引用3次,那么引用四次五次也是属于至少引用了三次的,所以由于要求的是最大的引用次数,所以我们把a从后往前加起来,直到大于当前引用次数时即为答案
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <vector> #include <map> #include <unordered_set> #include <unordered_map> #define x first #define y second #define IOS ios::sync_with_stdio(false);cin.tie(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 200010, M = 200010, MOD = 1000000007, INF = 0x3f3f3f3f; int a[N]; int main() { IOS; int n; while(cin >> n) { for (int i = 0; i <= n; i ++ ) cin >> a[i]; LL sum = 0, res = 0; for (int i = n; i >= 0; i -- ) { sum += a[i]; if(sum >= i) { res = i; break; } } cout << res << endl; } return 0; }
B - Higher $h$-index
思路:
要使文章数最大,可知每篇文章工作一小时满足情况,由于题目说之前的文章会对现在的文章的引用加一,即多的这一个引用也算到之前的那篇文章里,所以第i篇文章当前的引用为a,多出来的引用为他之后的文章的数量,即(n - i),所以第i篇文章的总引用数为a + n - i,同上一题要>=i,所以i <= (n + a) / 2
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <vector> #include <map> #include <unordered_set> #include <unordered_map> #define x first #define y second #define IOS ios::sync_with_stdio(false);cin.tie(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 200010, M = 200010, MOD = 1000000007, INF = 0x3f3f3f3f; int a[N]; int main() { IOS; int n, a; while(cin >> n >> a) { cout << (n + a) / 2 << endl; } return 0; }
F - Sorting
思路:
给出若干个三元组(a,b,c),按照(a+b)/(a+b+c)排序。首先不能直接排序,会卡精度。移项除变乘sort就行,但需要再化简一下,否则会爆long long。
对于分数有这么一个性质:
所以原来的按照(a[i-1]+b[i-1])*(a[i]+b[i]+c[i])<(a[i]+b[i])*(a[i-1]+b[i-1]+c[i-1])可以变为(a[i-1]+b[i-1])*c[i]<(a[i]+b[i])*c[i-1]
最后注意输出格式
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <vector> #include <map> #include <unordered_set> #include <unordered_map> #define x first #define y second #define IOS ios::sync_with_stdio(false);cin.tie(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 1010, M = 200010, MOD = 1000000007, INF = 0x3f3f3f3f; struct Tuple{ int id; LL a, b, c; bool operator< (const Tuple& t) const { LL n1 = (a + b) * t.c, n2 = (t.a + t.b) * c; if(n1 == n2) return id < t.id; else return n1 < n2; } } arr[N]; int main() { IOS; int n; while(cin >> n) { for (int i = 1; i <= n; i ++ ) { cin >> arr[i].a >> arr[i].b >> arr[i].c; arr[i].id = i; } sort(arr + 1, arr + 1 + n); for (int i = 1; i <= n; i ++ ) { cout << arr[i].id; if(i != n) cout << ' '; } cout << endl; } return 0; }
这篇关于CCPC2018-湖南全国邀请赛的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-07fastcgi 是什么-icode9专业技术文章分享
- 2024-10-07fastcgi 的详细使用教程介绍-icode9专业技术文章分享
- 2024-10-07git如何更新单个文件到本地-icode9专业技术文章分享
- 2024-10-07如何使用ASM(Abstract Syntax Tree Manipulation)技术来修改第三方AAR依赖中的函数-icode9专业技术文章分享
- 2024-10-07Activity 跳转时间耗时很长怎么优化解决-icode9专业技术文章分享
- 2024-10-07Androud Toast 有哪些常用的第三方组件-icode9专业技术文章分享
- 2024-10-07在viewmodel中怎么使用 mmkv?-icode9专业技术文章分享
- 2024-10-07MMKV.defaultMMKV() 是单例模式吗?-icode9专业技术文章分享
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享