UPC训练赛二十/20240217

A:无穷力量

题目描述

2022年重庆突发山火让世界看到了中国一个又一个的感人事迹：战士们第一时间奔赴火场，志愿者们自发组成团队，为救火提供一切的可能的服务，人们自发输送物资，有的志愿者甚至几天几夜没有睡觉。每个人献出一点力，造就了集体的无穷力量。山火被灭后，记者想统计共有多少人志愿者参加了灭火行动，他在山脚共找到了N个不同的志愿者进行调查。这N个被调查的志愿者回答如下：
第1位志愿者回答：和我一起行动的，除了我之外，还有A[1]个人。
第2位志愿者回答：和我一起行动的，除了我之外，还有A[2]个人。
第3位志愿者回答：和我一起行动的，除了我之外，还有A[3]个人。
。。。。。。
第N位志愿者回答：和我一起行动的，除了我之外，还有A[N]个人。
假设这N位志愿者都没有记错，那么至少有多少志愿者参与了灭火？

输入

分两行输入。
第一行，一个整数N。
第二行，N个整数，空格分开，第i个整数表示A[i]。

输出

一个整数，表示至少有多少个志愿者。

样例输入 Copy

【样例1】
4
1 2 1 2
【样例2】
9
2 2 44 2 2 2 444 2 2

样例输出 Copy

【样例1】
5
【样例2】
499

提示

对于100%的数据，3<N<=50，0<=A[i]<=1000000。

#include <bits/stdc++.h>
using namespace std; 
map<int, int>mp;
int main()
{int n; cin >> n;for (int i = 1; i <= n; i++){int num;scanf("%d", &num); mp[++num]++;}int sum = 0;for (auto it : mp){sum += it.first;while (mp[it.first] > it.first){mp[it.first] -= it.first;sum += it.first;}}if (sum >= n) printf("%d\n", sum); else printf("%d\n", n); return 0;
}

B:幸运位置

题目描述

刀越磨越快，脑子越用灵。不管什么事情，小宏总是喜欢多思考。今天他和小伙伴们玩一个游戏：n个人围成一圈，从第1个位置开始报数，每隔m个人报一次数，每次报数的人要表演节目，这样很有可能有人不用表演节目。例如有6个人，每隔3报数，报数的位置则是：1、5、3、1、5、3……，这样位置2、4、6的人就不用表演节目。小宏想考考你：在玩游戏前，根据n和m，迅速找出这些不用表演节目的位置。

输入

共一行，两个整数：n和m。1<=n<=10000,  1<=m<=1000。

输出

共一行，不用表演节目的位置，如果所有位置都要表演节目，则输出”NO”。

样例输入 Copy

【样例1】
6 3
【样例2】
5 3

样例输出 Copy

【样例1】
2 4 6
【样例2】
NO

/*一个大佬的方法*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define N 1000009
int arr[N];
int main()
{int n, m, i = 1, ans = 0;scanf("%d%d", &n, &m);while (arr[i] == 0){arr[i] = 1;i += (m + 1);if (i != n) i %= n;}for (int i = 1; i <= n; i++){if (arr[i] == 1) ans++;else printf("%d ", i);}if (ans == n) puts("NO");return 0;
}/*我的方法*/
#include <bits/stdc++.h>
using namespace std;
set<int>arr;
int main()
{int n, m;scanf("%d%d", &n, &m);int idx = 1, cntof1 = 0, cnt = 0;while (cntof1 < 2){cnt++;if (idx % n == 0) arr.insert(n);else arr.insert(idx % n);if (idx % n == 1) cntof1++;idx += m + 1;}if (arr.size() == n) printf("NO\n");elsefor (int i = 1; i <= n; i++){if (arr.find(i) == arr.end()) printf("%d ", i);}return 0;
}

G:智力测试题

题目描述

牛牛同学智商为-1e9，但是他既不谦虚又不低调，很喜欢炫耀他的智商。
现在，牛牛就来测智商了，题目是这样。
已知一个n乘以n的矩阵，有一个小球一开始在(1,1)处，小球每秒都会向右走一格，如果到达最右边，小球就会掉落在下一行的第一格。
如果到达(n, n)则返回(1,1)。现在给定n和时间t，请你输出小球最后所在的行和列。

输入

一行两个正整数，n和t。

输出

两个整数代表小球最终的行和列。

样例输入 Copy

【样例 1 输入】 
3 5 
【样例 2 输入】 
4 2 
【样例 3 输入】
2 7

样例输出 Copy

【样例 1 输出】 
2 3 
【样例 2 输出】 
1 3 
【样例 3 输出】
2 2

提示

【数据范围】
对于 50% 数据保证：t ≤ n2 − 1 对于

80% 数据保证：t ≤ n2 对于

100% 数据保证：1 ≤ n ≤ 10，0 ≤ t ≤ 500
题目数据比较毒瘤，请考虑所有情况。
 

#include <stdio.h>
int main()
{int n, t;scanf("%d%d", &n, &t);if (!((t / n + 1) % n)) printf("%d ", n);else printf("%d ", (t / n + 1) % n);printf("%d\n", 1 + t % n);return 0;
}

 H:采集灵石

题目描述

牛牛打开了一个有趣的游戏。在游戏中，灵石是一种非常重要的资源。每位玩家每天有且仅有一次采集的机会。

灵石会在许多浮岛上刷新，每个浮岛上灵石刷新数量可能不同。这些浮岛之间通过传送法阵相连，激活每个岛屿上的传送法阵花费的灵石数量也不同。玩家可以耗费mi 块灵石从任意一个其他浮岛或初始平台前往第i个浮岛。采集完毕后玩家

可以从任何浮岛直接退出地图。

现在，牛牛手中有着K块灵石，他想知道自己今天采集结束后最多能拥有多少块灵石。牛牛只能在周末玩一小时游戏，他希望你能编写一个程序帮他及时算出来。 

输入

第一行两个正整数N, K分别表示浮岛的数量和牛牛手中初始的灵石数量。
接下来N行，每行两个正整数ki, mi，第i行的正整数ki表示第i个浮岛上今日刷新的灵石数量,mi表示传送到第i个浮岛所需的灵石数量。

输出

一个正整数，表示牛牛今天采集后最多能拥有的灵石数量。

样例输入 Copy

【样例 1 输入】
3 5
4 3
4 3
4 3
【样例 2 输入】
2 1
5 2
8 2
【样例 3 输入】
2 6
2 3
4 3

样例输出 Copy

【样例 1 输出】
8
【样例 2 输出】
1
【样例 3 输出】
7

提示

【数据范围】
对于 30% 的数据，满足 ki > mi
对于 100% 的数据，满足0 < N, K ≤ 105, 0 < ki, mi ≤ 109
保证答案在int范围内。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
priority_queue< pair<int,int>,vector<pair <int,int> >, greater< pair<int,int> > > q;
const int N = 1e5 + 10;
int k[N], m[N];
int main()
{int n,K;cin >> n >> K;while(n--){int x,y;scanf("%d%d",&x,&y);if(x > y) q.push(make_pair(y,x));}while(q.size()!=0){auto t = q.top();int y = t.first;int x = t.second;if(K >= y){K += x - y;q.pop();}else{break;}}cout << K << endl;return 0;
}

I：跳跃的排列

题目描述

小 B 很喜欢排列，这次他有一个长为n的排列 a1, a2, ⋯ , an。由于他音游玩多了，所以他想让排列也跳跃起来。他定义一次排列的跳跃为：

令 bi 表示最大的j (i ≤ j ≤ n)满足 aj ≥ ai，则bi= aj。最后对于所有i = 1 ∼ n，将 ai赋值为bi。  

他想重复上述操作若干次。若操作k次和操作k + 1次序列保持不变，那么跳跃停止，跳跃次数为k。他想知道排列会跳跃多少次，请你来帮他计算一下。   

输入

第一行， 输入一个数n。第二行输入n个数，第i个数表示ai。

输出

输出排列的跳跃次数。

样例输入 Copy

【样例 1 输入】
4
4 1 3 2
【样例 2 输入】
10
1 9 2 6 8 7 4 3 5 10
【样例 3 输入】
8
8 7 6 5 4 3 2 1

样例输出 Copy

【样例 1 输出】
1
【样例 2 输出】
1
【样例 3 输出】
0

提示

【样例 1 说明】 经过1轮操作后，序列变成4 2 3 2，经过2轮操作后，序列仍然是4 2 3 2，因此排 列跳跃了1次。
【样例 2 说明】 经过1轮操作后，所有数都变成了10，经过2轮操作后，序列仍然全都是10，因此 排列跳跃了1次。
【样例 3 说明】 经过1轮操作后，序列仍然是8 7 6 5 4 3 2 1，因此排列没有进行跳跃。

【数据范围】
对于奇数编号的数据，满足给定的排列形如n, n − 1, ⋯ ,1或1,2, ⋯ , n。

对于30%的数据，1 ≤ n ≤ 1000；
对于70%的数据，1 ≤ n ≤ 105；
对于100%的数据，1 ≤ n ≤ 106。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N];
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++) scanf("%d", &a[i]);b[1] = a[1];for (int i = 2; i <= n; i++){if (b[i - 1] >= a[i]) b[i] = a[i];else b[i] = b[i - 1];}// b数列实时存储当前a数列中的最小值if (a[n] <= b[n]) puts("0"); // j要取最大值，看最右端。也就是，// 当a里面的数连最小值都不如的时候，就没法再替换了，故输出0else puts("1");// 反之return 0;
}

 K:最接近

小明同学最近正在研究一些幂次的特性，比如 3^2 = 9 和 4^3 = 64。小花是小明的好朋友，她总是和小明一起学习，由于小花刚刚学习幂次，很多计算还不太熟练。她很好奇，对于任意给出的正整数 N，不超过 N 的最大的 2 的幂次方的数是多少？例如：如果 N 等于 10，那么不超过 10 的最大的 2 的幂次方的整数就是 8，如果 N 是 100，那么不超过 100 的最大的 2 的幂次方的整数就是 64。小花希望你能帮助她解决这个问题。如果你能解决这个问题，就能和小花成为好朋友，小花希望朋友越多越好。

输入只有一行一个正整数 N。

输出只有一行一个正整数，表示不超过 N 的最大的 2 的幂次方的正整数。

样例1 input 10 output 8

样例2 input 100 output 64

1<=N<=1e18;

#include <bits/stdc++.h>
using namespace std;
int main()
{long long n;cin >> n;long long L = 1,  R = 63;while (L <=  R){long long mid = (L + R) >> 1;long long ans = pow(2, mid);if (ans > n) R = mid;else if (ans < n){if (pow(2, mid + 1) > n){cout << ans;break;}L = mid + 1;}else{cout << ans;break;}}return 0;
}