当前位置：首页 > news >正文

Codeforces Round 1019 (Div. 2)（A-D）

news 2025/8/16 22:43:03

题目链接：Dashboard - Codeforces Round 1019 (Div. 2) - Codeforces

A. Common Multiple

思路

从a种选出几个数然后让这些数*y变成公倍数，要保证y各不相同，那么我们在选择数的时候没有相等的数即可，所以此问题的答案便是a种不同数的个数

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;void solve(){int n;cin>>n;vi a(n+10);int cnt=0;map<int,bool> mp;for(int i=1;i<=n;i++){cin>>a[i];if(!mp[a[i]]){cnt++;mp[a[i]]=true;}}cout<<cnt<<"\n";}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

B. Binary Typewriter

思路

贪心，我们先统计出未操作前的总次数，然后我们再考虑什么情况下能够让次数减少

我们发现当出现10串的时候我们总能将之后的一个0放到前面，1放到后面要么和1挨着要么放到最后，这样可以使得次数-1

在出现10串之后又出现01串，我们能够将10串的1放到01串的1前面，将0移到前面要么和0挨着要么放到最前面，这样又能够使得次数-1

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n;cin>>n;string s;cin>>s;s=" "+s;bool f=false;int cnt=0;for(int i=1;i<=n;i++){if(!f&&s[i]=='1'){cnt+=2;f=true;}else if(f&&s[i]=='0'){cnt+=2;f=false;}else cnt++;}bool f1=false,f2=false;//f1标记是否有10串，f2为在前面已经存在10串时有01串存在for(int i=1;i<n;i++){if(s[i]=='1'&&s[i+1]=='0'){f1=true;}if(f1&&s[i]=='0'&&s[i+1]=='1'){f2=true;}}if(f1) cnt--;if(f2) cnt--;cout<<cnt<<"\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

C. Median Splits

思路

1.在最后统计时我们只需要有至少两个<=k的数就是yes

2.在判断一个区间内中位数是否<=k,我们只需要<=k的数量不低于一半即可

3.贪心我们截取前缀和后缀只要中位数小于等于k时就截取

如果截取的前后区间不交叉就保证了有两个数<=k输出yes，否则我们需要遍历中间的区间看其是否有中位数<=k的情况

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n,k;cin>>n>>k;vi a(n+10);for(int i=1;i<=n;i++){cin>>a[i];}bool f1=false;bool f2=false;int ck=0;   //大于k的元素int ct=0;   //小于等于k的元素int pre=n;for(int i=1;i<n;i++){if(a[i]>k) ck++;else ct++;if(ct>=ck){if((ct==ck+1)&&(i!=n-1)&&a[i+1]>k) f1=true;pre=i;break;}}ck=0;ct=0;int suf=1;for(int i=n;i>=2;i--){if(a[i]>k) ck++;else ct++;if(ct>=ck){if((ct==ck+1)&&i!=2&&a[i-1]>k) f2=true;suf=i;break;}}if(pre<suf){cout<<"YES\n";return;}ck=0;ct=0;for(int i=pre+1;i<=n-1;i++){if(a[i]>k) ck++;else ct++;if(ct>=ck){cout<<"YES\n";return;}}ck=0;ct=0;for(int i=suf-1;i>=2;i--){if(a[i]>k) ck++;else ct++;if(ct>=ck){cout<<"YES\n";return;}}if(f1){ck=0;ct=0;for(int i=pre+2;i<=n-1;i++){if(a[i]>k) ck++;else ct++;if(ct>=ck){cout<<"YES\n";return;}}}if(f2){ck=0;ct=0;for(int i=suf-2;i>=2;i--){if(a[i]>k) ck++;else ct++;if(ct>=ck){cout<<"YES\n";return;}}}cout<<"NO\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

D. Local Construction

思路

构造题果然还得靠猜结论

首先我们再构造过程中发现，如果执行操作1的时候我们删除不是局部最小的数的时候发现当数列为(以下假设n=9)

(9 8 7 6 5)或(5 6 7 8 9)这样构造的时候无论中间插入的数(比这串数要小)是什么都会使得这一串数都不是局部最小的,并且插入的数为局部最小从而不删除

同理执行操作2删除不是局部最大的时候，(1 2 3 4 5)或(5 4 3 2 1)中间插入6 7 8 9都不会影响

然后便是往里面插数，然后再把玩一下样例，发现 -1 前后正好是倒过来的，那么直接大胆尝试

严谨的证明的话emmm...

关于此题好像还可以逆向思考，从-1 ----1开始填数建图，然后走一遍拓扑排序得到顺序，过几天再补上

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;void solve(){int n;cin>>n;vi a(n+10);for(int i=1;i<=n;i++) cin>>a[i];vector<vi> g(n+10);int x=0;int imx=0;int l=1,r=n;vi ans(n+10);for(int i=1;i<=n;i++){if(a[i]==-1) {x=i;break;}else{g[a[i]].push_back(i);imx=max(imx,a[i]); }}for(int i=1;i<=imx;i++){if(i%2){for(auto y:g[i]){ans[y]=r--;}}else{for(auto y:g[i]){ans[y]=l++;}}g[i].clear();}imx=0;for(int i=n;i>=x+1;i--){g[a[i]].push_back(i);imx=max(imx,a[i]); }for(int i=1;i<=imx;i++){if(i%2){for(auto y:g[i]){ans[y]=r--;}}else{for(auto y:g[i]){ans[y]=l++;}}}ans[x]=l;for(int i=1;i<=n;i++){cout<<ans[i]<<" \n"[i==n];}
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

查看全文

http://www.xdnf.cn/news/88111.html