挑战赛#9 T1-T5题解
2024-09-09 11:10:17
发布于：广东
89阅读
0回复
0点赞
这次题目确实挺幽默
由于T6不算奖励，我就没有写（绝对不是我不会），以下是T1-T5的题解：
T1
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
cout << "KEY1,Yu1lice!";
return 0;
}
T2
我们很容易地发现， 越大， 中出现质数的频率就越低.所以必然存在一个质数，在它之后的所有数都不满足条件.
那么怎么求这个数呢？
我们又发现， 中出现质数的频率约等于 .
若 ，则 .所以这个质数就大概为 .
我们将 之后的一个质数 代入试试，发现 之内的质数有 个，确实不满足条件.
所以这个分界线就是 了！
那么我们只需要将 以内的数逐个判断，发现只有 满足条件.
所以，我们只需要判断输入的数是否为 中之一就行了！
#include <iostream>
#include <cstdio>
#define int long long
signed main(){
int t;
cin >> t;
while(t--){
long long n;
cin >> n;
puts(n == 3 || n == 5 || n == 7 ? "YES" : "NO");
}
return 0;
}
T3
本题消灭了所有没参加过今年蓝桥杯或使用Python的人
水题，了解题意就行.
注意对负数取模结果仍为负数，所以应先加上模数再取模.
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
signed main(){
string s;
cin >> s;
int n;
cin >> n;
int len = s.length();
n %= len;
for(int i = 0; s[i] != '\0'; i++){
cout << s[(i - n + len) % (len)];//转换成正数
}
return 0;
}
T4
数据强度太高了，看不懂啊（
这题绝对不能骗分，否则你只能拿到94分，50个测试点只能通过47个（
骗分思路：我们发现两个操作不会改变序列的总和，所以我们判断两个序列的和是否相等就行了
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
int a[200005], b[200005];
bool solve(){
memset(a, 0, sizeof(b));
memset(b, 0, sizeof(a));
int n, m, k, ct1 = 0, ct2 = 0;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
ct1 += a[i];
}
cin >> k;
for(int i = 1; i <= k; i++){
cin >> b[i];
ct2 += b[i];
}
if(ct1 != ct2) return 0;
return 1;
}
int main(){
int t;
cin >> t;
while(t--){
cout << (solve() ? "Yes\n" : "No\n");
}
return 0;
}
可以发现样例是5个Yes，但是成功骗得94分笑死我了（Macw说比赛后会加强数据，帮我看看加强的怎么样）
ok现在来说说正经解法
我们可以将两个序列都按照操作一拆分到极限，再来对比是否相等.
比如
6 3
18 18 54 2 18 54 7 18
4
162 2 7 18
两个序列拆分后完全相同，说明是可以的
但是以刚刚的例子，我们注意到原来的 个元素拆分后变成 个元素，要是放极端数据就会有 个 ，根本存不下.
那么我们可以只存连续的一段数的个数
例如原来的
3 3 3 3 3 3 3 3 3 5 5 2 3 3 3
压缩后变成
3 9 5 2 2 1 3 3
精简了很多
//不可以，总司令！
#include <iostream>
#include <cstdio>
#include <memory.h>
#define int long long
using namespace std;
struct node{
int val = 0, ct = 0;
}a[50005], b[50005];
bool solve(){
memset(a, 0, sizeof(b));
memset(b, 0, sizeof(a));
int n, m, k, x, y, ct1 = 0, ct2 = 0;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> x;
y = 1;
while(x % m == 0){
x /= m, y *= m;
}
if(a[ct1].val != x){
a[++ct1].val = x;
a[ct1].ct = y;
}else{
a[ct1].ct += y;
}
}
cin >> k;
for(int i = 1; i <= k; i++){
cin >> x;
y = 1;
while(x % m == 0){
x /= m, y *= m;
}
if(b[ct2].val != x){
b[++ct2].val = x;
b[ct2].ct = y;
}else{
b[ct2].ct += y;
}
}
if(ct1 != ct2) return 0;
for(int i = 1; i <= ct1; i++){
if(a[i].val != b[i].val || a[i].ct != b[i].ct) return 0;
}
return 1;
}
signed main(){
int t;
cin >> t;
while(t--){
cout << (solve() ? "Yes\n" : "No\n");
}
return 0;
}
T5
相对简单一些，直接模拟
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
int l, r, val;
bool operator < (const node &b) const{
return l < b.l;
}
}a[105];
bool vis[105];
int n, ct, cur;
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i].l >> a[i].r >> a[i].val;
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++){
for(int j = 1; j < i; j++){
if(a[i].l > a[j].r && !vis[j]){
cur += a[j].val, vis[j] = 1;//退还打包箱
}
}
if(cur > a[i].val) cur -= a[i].val;
else ct += a[i].val - cur, cur = 0;//用还的打包箱，节约
}
cout << ct;
return 0;
}
当然还可以使用堆优化 ，我就不讲了
有帮助，赞一个