前天晚10:35的Codeforces Round #767 (Div. 2) A~D
昨天D没补完,遇到点小问题,刚刚整理了一遍思路AC了,现在来写题解.
(弱鸡场上只写出了AB, C差点就交上去了,赛后补了D). 希望再打几把能稳ABC.加油吧
题目描述
A. Download More RAM
大致题意:给出 n个条件 和 初始代价,代价能累积, 如果当前代价大于条件代价, 就能获得在初始代价基础上加贡献值. 求max
样例
Example
inputCopy
4
3 10
20 30 10
9 100 10
5 1
1 1 5 1 1
1 1 1 1 1
5 1
2 2 2 2 2
100 100 100 100 100
5 8
128 64 32 16 8
128 64 32 16 8
(暴力枚举) 简单模拟就是啦
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<unordered_map>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=110;
int n,k;
PII a[N];
void _solve()
{
cin>>n>>k;
memset(a,0,sizeof a);
for(int i=1;i<=n;i++){
cin>>a[i].first;
}
for(int i=1;i<=n;i++){
cin>>a[i].second;
}
sort(a+1,a+1+n);
if(k<a[1].first) {
cout<<k<<endl;
return ;
}
for(int i=1;i<=n;i++){
if(k>=a[i].first) k+=a[i].second;
}
cout<<k<<endl;
return ;
}
int main()
{
int _test;
for(cin>>_test;_test;_test--){
_solve();
}
return 0;
}
B. GCD Arrays
大致题意: 给定一个区间[l,r] 表示 l,l+1,l+2,..r;给出k个操作, 每个操作是在区间中选两个数(并删除)的乘积加入区间,求区间的总gcd是否大于1;
分类讨论:
奇数乘偶数->偶数 奇数乘奇数 -> 奇数
1: 如果k==r-l的话 而且l&&r都!=1 则一定能满足条件 否则不能
2:如果端点l,r都是偶数 则k>=(r-l)/2 就能满足条件 否则不能
3:else 条件2 k>(r-l)/2就能满足条件 否则不能
时间复杂度
样例
Example
inputCopy
9
1 1 0
3 5 1
13 13 0
4 4 0
3 7 4
4 10 3
2 4 0
1 7 3
1 5 3
outputCopy
NO
NO
YES
YES
YES
YES
NO
NO
YES
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<unordered_map>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=1e9;
int n,m,k;
void _solve()
{
cin>>n>>m>>k;
if(k==m-n) {
if(m==1&&n==1)
{
cout<<"No"<<endl;
return;
}
else cout<<"Yes"<<endl;
}
else {
if(n%2==0&&m%2==0)
{
if(k>=(m-n)/2) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
else
{
if(k>(m-n)/2) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return;
}
int main()
{
int _test;
for(cin>>_test;_test;_test--){
_solve();
}
return 0;
}
C. Meximum Array
大致题意:给一个长度为n的序列,n个数都是0~n的整数,求能组合成最大的MEX;
样例
Example
inputCopy
6
5
1 0 2 0 3
8
2 2 3 4 0 1 2 0
1
1
5
0 1 2 3 4
4
0 1 1 0
10
0 0 2 1 1 1 0 0 1 1
outputCopy
1
4
2
5 1
1
0
1
5
2
2 2
4
3 2 2 0
C++代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=2e5+10;
int n,a[N],b[N],c[N];
vector<int> ans;
void _solve()
{
cin>>n;
memset(a,0,sizeof a);
memset(b,0,sizeof b);
memset(c,0,sizeof c);
ans.clear();
for(int i=1;i<=n;i++) cin>>a[i],b[a[i]]++;
int p=0,last=0;
for(int i=1;i<=n;i++){
c[a[i]]++;
while(c[p]) p++;
if(b[p]==0){///p 是 mex
ans.push_back(p);
for(int j=last+1;j<=i;j++){
b[a[j]]--;
c[a[j]]=0;
}
last=i;
p=0;
}
}
cout<<ans.size()<<endl;
for(auto t: ans) cout<<t<<" ";
cout<<endl;
return ;
}
int main()
{
int _test;
for(cin>>_test;_test;_test--){
_solve();
}
return 0;
}
D. Peculiar Movie Preferences
大致题意:给出n个长度不超过3的子字符串, 问是否能拼成回文子序列(要有顺序,我前几次写的就栽坑了);
我先说说我的思路吧: 模拟: 1:如果当前子串是单个字符串 则肯定能单独满足条件
2:如果长度不是1:如果s[0]==s.back() 也是能满足条件的
3:不满足以上两种条件的 我们放到 哈希表中 mp[s]=i;//这里我们的values要存位置,后面会用到比较
4: 在遍历一遍哈希表 如果长度为2 直接查看表中是否存在当前翻转的串
5: 如果长度为3 同上, 如果不存在,分别去掉左边第一个 和 右边第一个同上
样例
Example
inputCopy
6
5
zx
ab
cc
zx
ba
2
ab
bad
4
co
def
orc
es
3
a
b
c
3
ab
cd
cba
2
ab
ab
outputCopy
YES
NO
NO
YES
YES
NO
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<unordered_map>
using namespace std;
const int N=2e5+10;
void _solve()
{
int n;
cin>>n;
bool flag=false;
unordered_map<string ,int > mp;
for(int i=1;i<=n;i++){
string s;
cin>>s;
int len=s.size();
if(len==1)
{
flag=true;
}
else if(s[0]==s[len-1]) {
flag=true;
}
if(len>1&&!mp.count(s)) mp[s]=i;
}
if(flag) {
cout<<"Yes"<<endl;
return;
}
for(auto [k,v]: mp){
string t=k;
int len=t.size();
reverse(t.begin(),t.end());
if(len==2)
{
if(mp.count(t)) {
flag=true;
}
}
else {
if(mp.count(t)) {
flag=true;
}
else {
string p=k.substr(0,2);
reverse(p.begin(),p.end());
if(mp.count(p)&&mp[k]<mp[p]) {
flag=true;
}
else{
p=k.substr(1,2);
reverse(p.begin(),p.end());
if(mp.count(p)&&mp[k]>mp[p]) {
flag=true;
}
}
}
}
}
if(flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return;
}
int main()
{
int _test;
for(cin>>_test;_test;_test--){
_solve();
}
return 0;
}
