codeforces签到题之div4
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
🌼坏女孩抖音热门版 - Laziness惰/西洛卡 - 单曲 - 网易云音乐
标签模拟暴力排序贪心双指针几何字符串
目录
前言
昨晚参加了洛谷入门赛和codeforces的div4今晚参加AcWing周赛
洛谷遇到了不会的思维题codeforces遇到了写半天只过了样例的题AcWing遇到了需要dp和状态转移的题都是当场没做出来的
接下来我会把昨晚cf前5题题解写出来复盘以便提高会的题目的熟练程度同时解决未AC题目的BUG
一codeforces检查
标签模拟字符串
逐个比对输入的字母看是否在codeforces这几个字母里遍历
#include<iostream>
using namespace std;
bool check(char a)
{
string s = "codeforces";
for(int i = 0; i < 10; ++i) {
if(a == s[i]) return true;
}
return false;
}
int main()
{
string s;
int n;
cin>>n;
for(int i = 0; i < n; ++i) {
cin>>s[i];
if(check(s[i])) cout<<"YES";
else cout<<"NO";
if(i != n - 1) cout<<endl;
}
return 0;
}
二接下来的方向
标签模拟几何
两个变量初始为0分别代表横纵坐标在加减过程中加个判断即可
#include<iostream>
using namespace std;
int main()
{
int n, m, a, b;
cin>>n;
for(int i = 0; i < n; ++i) {
cin>>m;
string s;
cin>>s;
a = 0, b = 0;
for(int j = 0; j < m; ++j) {
if(s[j] == 'U') a++;//横坐标
else if(s[j] == 'D') a--;
else if(s[j] == 'L') b--;//纵坐标
else if(s[j] == 'R') b++;
if(a == 1 && b == 1) {
cout<<"YES";
break;
}
if(j == m - 1) {
cout<<"NO";
break;
}
}
if(i != n - 1) cout<<endl;
}
return 0;
}
三前置和追加
标签模拟双指针
用了s.substr()来截取头文件#include<cstring>同时flag来标记头尾是否还符合删除条件
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
while(n) {
int m;
string s;
cin>>m;
cin>>s;
int flag = 1;
while(flag) {
flag = 0;
if(s[0] == '0' && s[m - 1] == '1') {
s = s.substr(1, m - 2);
m -= 2;
flag = 1;
}
if(s[0] == '1' && s[m - 1] == '0') {
s = s.substr(1, m - 2);
m -= 2;
flag = 1;
}
}
cout<<s.size();
if(n != 1) cout<<endl;
n--;
}
return 0;
}
四明显的分裂
标签暴力贪心字符串
知识储备
思路是将字符串分成两部分分别用set中元素不重复的特点得到左右两边不重复的字母数同时由于字符数长度最大可达2*10^5建议用vector保存不用数组
#include<iostream>
#include<set> //set<char>a;
#include<vector> //vector<int>b(m) ;
using namespace std;
int main()
{
int n;
cin>>n;
while(n) {
int m;
cin>>m;
string s;
cin>>s;
set<char>a;
vector<int>b(m); //长度跟字符串一样
for(int i = m - 1; i >= 0; --i) {
a.insert(s[i]); //正序插入
b[i] = a.size(); //尾在前
}
a.clear(); //清空a集合
int ans = 0; //记得初始化
for(int i = 0; i < m - 1; ++i) {
a.insert(s[i]); //头在前
ans = max(int(a.size()) + b[i + 1], ans); //int转化
}
cout<<ans;
if(n != 1) cout<<endl;
n--;
}
return 0;
}
五负数和正数
标签贪心排序
真的codeforces中很多题都和奇偶数的规律有关比如本题
只要负数的个数是偶数都可以通过有限次的操作全部变成正数
当负数的个数是奇数也可以通过有限次的操作通过负数位置的移动最终剩1个负数
比如
1 -3 4 -16 2 -8 2
1 -3 4 -16 -2 8 2
1 -3 4 16 2 8 2
-1 3 4 16 2 8 2发现这个规律后代码就变得很简单了
否则就像我一开始写了半小时也只过了样例。。。
#include<iostream>
#include<cmath> //abs()
using namespace std;
int main()
{
int t;
cin>>t;
while(t) {
int n;
cin>>n;
long long sum = 0, Min = 1e9, flag = 0; //10的9次方
while(n) {
long long a;
cin>>a;
sum += abs(a); //绝对值
if(a < 0) flag++; //统计负数个数
Min = min(Min, abs(a));
n--;
}
if(flag % 2) sum -= 2 * Min; //减去多加的和本身
printf("%lld", sum);
if(t != 1) printf("\n");
t--;
}
return 0;
}
总结
codeforces很多思维题也就是规律题有种回到初高中数学的感觉所以不应该固步自封我们要算法规律两手抓能找到规律就用规律多点见识大佬们的代码找不到就老老实实上并查集二叉树dfsSTL等等
真的不要一整天用自己的思路死磕代码多点看看codeforces里别人的代码以后你做题都会快很多思路广很多
这就是为什么你要在CSDNAcWing洛谷codeforces四个网站上打比赛的原因多点看看别人的AC代码把思维打开