(巅峰赛?) 排位赛#14题解 (T1-T5)
2024-11-11 13:54:37
发布于：广东
122阅读
0回复
0点赞
T1
按照题意模拟即可，不要看提示说明.
#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
pair <char, char> c[3] = {{'1', 'l'}, {'0', 'O'}, {'5', 'S'}};//混淆字符串的内容
int main(){
int n;
string s1, s2;
cin >> n >> s1 >> s2;
int ct = 0;
for(int i = 0; i < n; i++){
bool flag = 0;
for(int j = 0; j < 3; j++){
if(s1[i] == c[j].first && s2[i] == c[j].second) flag = 1;
if(s1[i] == c[j].second && s2[i] == c[j].first) flag = 1;
}
if(!flag && s1[i] != s2[i]){//如果不是混淆字符对且不相等就不对
cout << "No";
return 0;
}
}
cout << "Yes";
return 0;
}
T2
代码写得很史 由于不知道怎么求循环节，就只能暴力了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
int main(){
int n, m, len = 0;
cin >> n >> m;
while(n > m){
int tmp = m;
while(tmp < n) tmp *= 10;
tmp /= 10;
n %= tmp;
}
n = n % m * 10;
string s;
for(int i = 1; i <= 5000; i++){//循环
s += n / m + '0';
n = n % m * 10;
}
for(int i = 1;; i++){
for(int j = 0; j < 5000 - i - i; j += i){
for(int k = j; k < j + i; k++){
if(s[k] != s[k + i]) goto _label;//跳转 继续
}
}
for(int j = 0; j < i; j++){
cout << s[j];
}
return 0;
_label:;
}
return 0;
}
T3
这道题难点主要是读题 读懂题贪心就行了
要注意桶和染料的区别，以及只能将将桶 中的染料和桶 中的染料进行倒换（即只能挑相邻的桶）
#include <iostream>
#include <cstdio>
using namespace std;
int a[100005], b[100005];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
int ct = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j < n; j++){
if(a[j] > a[j + 1]){
int mx = 0x3f3f3f3f;
for(int k = 1; k <= n; k++){
if(k != j && k != j + 1 && min(a[j], a[j + 1]) + a[k] <= n) mx = min(mx, b[a[k]]);//每次挑满足条件最小的
}
swap(a[j], a[j + 1]), ct += mx;//交换！
}
}
}
cout << ct;
return 0;
}
T4
由于手指数量较小，所以我们可以分别枚举 根手指能不能AP
check函数可以参考这篇题解，用小根堆模拟.
如果手指数量大的话（比如说二十万手观音）可以二分答案解决，时间复杂度可以从 降至 .（ 指手指数量）
#include <iostream>
#include <cstdio>
#include <queue>
#define pq priority_queue <int, vector <int>, greater <int>>
using namespace std;
int a[100005];
int n;
bool check(pq q){
for(int i = 1; i <= n; i++){
int head = q.top();//q.top()表示这根手指CD好了的时间
q.pop();
if(head > a[i] + 30) return 0;//接不上
if(head < a[i] - 30) q.push(a[i] + 70);//最多只能提前30ms击打
else q.push(head + 100);
}
return 1;
}
int solve(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
pq q;
for(int i = 1; i <= 4; i++){
q.push(0);
if(check(q)) return i;
}
return -1;
}
int main(){
int t;
cin >> t;
while(t--) cout << solve() << endl;
return 0;
}
T5
仔细观察，发现前两个样例已经说明了一切.
压缩一下（如 压缩成 ），发现施完法后也就这两种情况：
（包含 ， 等情况）
（包含 ， 等情况）
每种情况 种状态，一共 种状态……吗？
聪明的你发现这两种情况前两种状态是相同的，那么就可以节省两个状态！
现在拿剩下 个DP就行了
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[200005], b[200005], c[200005];
int dp[200005][8];
signed main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++) cin >> c[i];
for(int i = 1; i <= n; i++){
dp[i][0] = dp[i - 1][0] + a[i];//0
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]) + b[i];//01
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1]) + a[i];//010
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2]) + b[i];//0101
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3]) + a[i];//01010
dp[i][5] = max(dp[i - 1][5], max(dp[i - 1][0], dp[i - 1][1])) + c[i];//012（2可以由0，1得到）
dp[i][6] = max(dp[i - 1][6], dp[i - 1][5]) + b[i];//0121
dp[i][7] = max(dp[i - 1][7], max(dp[i - 1][6], dp[i - 1][5])) + a[i];//01210（0可以由1，2得到）
}
int mx = 0;
for(int i = 0; i <= 7; i++){
mx = max(mx, dp[n][i]);//求最大值
}
cout << mx;
return 0;
}
有帮助，赞一个