巅峰赛#15 T1-T5 题解
2024-12-16 15:08:04
发布于：广东
149阅读
0回复
0点赞
先报个人难度：红 红 橙 黄 绿（预判的还挺准）
T1
逐个枚举，找到第一个比 大的就输出.
#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
int main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
if(i != 1 && a[i] > a[1]){//比它高
cout << i;
return 0;//不找了
}
}
cout << -1;//没找到
return 0;
}
T2
模拟，吃掉一盘菜就把所需的对应元素逐个减少，如果最后都小于 就说明已经足够了.
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[100005];
signed main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
int n, m;
cin >> m >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int x;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++) cin >> x, a[j] -= x;//减去营养
}
for(int i = 1; i <= n; i++){
if(a[i] > 0){
cout << "No";//还有元素没摄取完毕
return 0;
}
}
cout << "Yes";
return 0;
}
T3
如果 为 那么 就为 ，否则 为 ，
如果和还有剩余就全加在 中一个为 的元素上.
注意判断特殊情况， 时是得不出来的
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[100005];
void solve(){
int n;
cin >> n;
int ct = 0;
for(int i = 1; i <= n; i++){
cin >> a[i], ct += a[i];
}
if(n == 1){//特判
cout << ":-(\n";
return;
}
for(int i = 1; i <= n; i++){
ct -= (a[i] == 1 ? 2 : 1);//贪心
}
cout << (ct < 0 ? ":-(\n" : "^_^\n");
}
signed main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
T4
思路1
加一个偏移量使 的最大值最小，判断此时最大值是否小于 .
但是这个偏移量不好找，取最大值、最小值都行不通，按 一个一个试的话时间复杂度是 的，会超时.
所以这个办法行不通
思路2
欢乐赛#34T3 给了我一点启发
我们注意到，把所有 取模后排序，则 构成了一个环，如图所示.
而这个环的长度为 .
事实上题目就是让我求这个环砍掉一条边后形成的链的最短长度.
所以我们只需要判断是否满足 即可.
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int a[200005];
signed main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
int n, m, k;
cin >> n >> m >> k;
int mx = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i] %= (m + k);
}
sort(a + 1, a + n + 1);//排序
for(int i = 1; i < n; i++){
mx = max(mx, a[i + 1] - a[i]);
}
mx = max(mx, a[1] + m + k - a[n]);//求出最小的链长
cout << (m + k - mx < m ? "Yes" : "No");
return 0;
}
T5
这题应该改名为后缀和问题（
注意到 ，明显就是给暴力分块做的
对于这类问题，一次查询运算次数只需要不超过 次就行，这里我取 的近似值 .
当 时，运算次数必定小于 ，直接暴力枚举.
所以我们只需要思考 的情况就行.
340pts
按内存极限预处理 的情况，剩下的暴力.
为当 时的答案.
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[300005], dabiao[25][300005];
signed main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i < 24; i++){
for(int j = n; j; j--){
dabiao[i][j] = dabiao[i][j + i] + a[j];//处理后缀和
}
}
int m;
cin >> m;
while(m--){
int l, len;
cin >> l >> len;
if(len < 24) cout << dabiao[len][l] << '\n';//直接输出
else{
int ct = 0;
for(int i = l; i <= n; i += len) ct += a[i];
cout << ct << '\n';
}
}
return 0;
}
500pts
仔细思考，如果我们隔一个预处理一个，如
1 2 3 4 5 6 7
变成
1 3 5 7
2,4,6查询时再计算，那这样运算次数只多了一次，但是内存却省了一半！
按照这个办法，把 的步长改为 ，运行次数仍然不超过 .
#include <iostream>
#include <cstdio>
#include <vector>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#define int long long
#define N 600
//块长：600
using namespace std;
int a[600005];
vector <vector <int>> dp[605], dp2[605];//dp2指向的真实的数，为方便预处理增加了一维
signed main(){
cin.tie(nullptr) -> sync_with_stdio(0);
cout.tie(nullptr) -> sync_with_stdio(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= 600; i++){
dp[i].resize(i, vector <int>(n / i / N + 5));
dp2[i].resize(i, vector <int>(n / i / N + 5));
for(int j = 0; j < i; j++){
int tmp = n / N / i * N * i + j;
dp2[i][j][n / N / i + 1] = tmp + i * N;
for(int k = n / N / i; k >= 0; k--, tmp -= i * N){
dp[i][j][k] = dp[i][j][k + 1];
for(int l = 0; l < N * i; l += i){
dp[i][j][k] += a[tmp + l];//计算后缀和
}
dp2[i][j][k] = tmp;
}
}
}
int m;
cin >> m;
while(m--){
int idx, len;
cin >> idx >> len;
if(len * len > n){
int ans = 0;
for(int i = idx; i <= n; i += len){//暴力
ans += a[i];
}
cout << ans << '\n';
continue;
}
int ans = dp[len][idx % len][idx / len / N + 1];
for(int i = idx; i < dp2[len][idx % len][idx / len / N + 1]; i += len){//处理前面没加到的数
ans += a[i];
}
cout << ans << '\n';
}
return 0;
}
有帮助，赞一个