Codeforces Round #598 (Div. 3) A,B,C,D{E,F待补}
2024-09-01 14:57:08
A. Payment Without Change
#include<bits/stdc++.h> using namespace std;
#define int long long
#define N 100500
int arr[N];
signed main(){
int _;
cin>>_;
while(_--){
int a,b,n,s;
cin>>a>>b>>n>>s;
int y=s/n;
int x=min(a,y);
s-=x*n;
if(b>=s){
printf("YES\n");
} else{
printf("NO\n");
}
}
return ;
}
B. Minimize the Permutation
按照题意暴力就行。从1到n枚举,每个数尽量地往前和比他大的数交换。并且保证相邻的位置只能换一次。【比赛·的时候读错题意,还想错了思路QAQ难受====】
#include<bits/stdc++.h> using namespace std;
#define int long long
#define N 150
int arr[N];int vis[N];
signed main(){
int _;
cin>>_;
while(_--){ int n;cin>>n;
for(int i=;i<=n;i++)
cin>>arr[i];
int m=n-;
while(){
int flag=;
for(int i=n-;i>=;i--){
if(vis[i])
continue;
if(arr[i]>arr[i+]){
int t=arr[i];
arr[i]=arr[i+];
arr[i+]=t;
m--;
flag=;
vis[i]=;
if(m<=){
break;
}
}
}
if(m<=){
break;
}
if(!flag){
break;
}
}
for(int i=;i<=n;i++){
printf("%lld ",arr[i]);
} printf("\n");
for(int i=;i<=n+;i++)
arr[i]=vis[i]=;
}
return ;
}
C. Platforms Jumping(贪心)【补题】
贪心:在板之间加水。这样保证了所有的板都用上了。最后再特盘一个不能到达的情况即可。开始模拟。【这题调了一会BUG,好久没刷题的,代码都打不清楚了QAQQAQQAQ】
#include<bits/stdc++.h> using namespace std;
#define int long long
#define N 150000
int arr[N];int n,m,k;
int c[N];
struct str{
int id;
int length;
}st[N]; signed main(){
cin>>n>>m>>k;
int Sum=;
int POS=;
for(int i=;i<=m;i++){
POS+=k;
scanf("%lld",&st[i].length);
st[i].id=i;
POS+=st[i].length-;
Sum+=st[i].length;
}
POS+=k;
if(POS<n+){
printf("NO\n");
return ;
}
printf("YES\n");
int tot=n-Sum;
int flag=;
int dis=k-;int now=;
int pos=;
//out<<tot<<endl;
for(int i=;i<=m;i++){
if(flag==){
int temp=min(dis,tot);
tot-=temp;
if(tot<=){
flag=;
}
while(temp--)
arr[++now]=;
temp=st[i].length;
// Sum-=temp;
while(temp--)
arr[++now]=i;
}else{
int _;_=st[i].length;
while(_--)
arr[++now]=i;
}
if(now>=n+){
break;
}
}
for(int i=;i<=n;i++)
cout<<arr[i]<<" ";
printf("\n"); return ;
}
D. Binary String Minimizing(贪心)
从左到右每个0依次和当前最左边的1交换,消耗这两个数下标之差的交换次数。
如果次数不够用,就让这个0和最远的能交换的1交换位置。
直接模拟就行。
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int _;
cin>>_;
while(_--){
int left=;
int n,m;cin>>n>>m;string str;cin>>str;
for(int i=;i<str.size();i++){
if(str[i]==''){
left=i;
break;
}
}
for(int i=;i<str.size();i++){
if(str[i]==''&&i!=){
while(str[left]!=''&&left<str.size())
left++;
if(left<i){ if(m>=(i-left)){
m-=(i-left);
str[left]='';
str[i]='';
}else{
str[i-m]='';
str[i]='';
m=;
}
if(m<=){
break;
}
}
}
}
cout<<str<<endl;
}
return ;
}
用vector记录0的位置,然后模拟
#include<bits/stdc++.h> using namespace std;
#define int unsigned long long
#define N 1000500
int vis[N];
vector<int> v;
signed main(){
int _;
cin>>_;
while(_--){
int n,m;
cin>>n>>m;string str;
v.clear();cin>>str;
int left=;
int sum0=;int sum1=;
for(int i=;i<str.size();i++){
if(str[i]==''){
if(m>=(i-left)){
m-=(i-left);
sum0++;
left++;
}else{ if(m){
v.push_back(i-m);m=;
}else{
v.push_back(i);
}
}
}else{
sum1++;
}
}
int len=v.size();
for(int i=;i<sum0;i++){
cout<<"";
}int cnt=;
for(int i=sum0;i<n;i++){
if(cnt<len){
if(v[cnt]==i){
cout<<"";
cnt++;
}else{
cout<<"";
}
}else{
cout<<"";
}
}
printf("\n"); }
return ;
} /*
11011010
01111010
*/
E,F待补。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
一场掉了分的DIV3。。。
最新文章
- Ajax操作如何实现跨域请求 (JSONP和CORS实现Ajax跨域的原理)
- ASP.NET MVC中使用Unity Ioc Container
- 解决 笔记本键盘打字母却跳出数字来,每次都要按一遍Fn+Num LK 的问题
- flex 遍历Object或者JSON对象内容的实现代码
- c#遍历并判断实体或类的成员属性
- hadoop2的伪分布部署
- log4net 开箱即用
- A low-cost wear-leveling algorithm for block-mappingsolid-state disks
- MacBook IDEA激活码(附视频)
- js 动态添加class封装(es6语法)
- [1] YOLO 图像检测 及训练
- while和do-while语句的异同之处
- [LeetCode&;Python] Problem 925. Long Pressed Name
- Codeforces 15E Triangles - 组合数学
- 一个web项目web.xml的配置中<;context-param>;配置作用
- Redis记录-Redis高级应用
- 简单工厂模式&;策略模式-简介与区别
- Ubuntu下pycharm设定任务栏图标后打开出现问号图标
- LintCode-376.二叉树的路径和
- Linux网络编程基础