Cf#741-C. Rings(构造)_阅读,动手的博客-程序员秘密_c. rings

技术标签: 算法  c++  # 思维,贪心  数据结构  

C. Rings

先贴上我错误的代码:

#include <bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define f(i,a,n) for(int i=a;i<n;++i)
#define ff(i,a,n) for(int i=a;i<=n;++i)
#define OP freopen("D:\\Users\\HP ZBook15\\CLionProjects\\untitled\\demo\\in.TXT","r",stdin);
#define CL freopen("D:\\Users\\HP ZBook15\\CLionProjects\\untitled\\demo\\out.TXT","w",stdout);
const int INF=0x3f3f3f3f;
using namespace std;
typedef long long ll;
typedef double dbl;
typedef pair<int, int> pi;
//
int n;
void solve(){
    
	cin>>n;
	string s;
	cin>>s;
	int flag=0,p=0;
	for(int i=n-1;i>=n/2;i--){
    
		if(s[i]=='0'){
    
			flag=i;
			break;
		}
	}
	if(flag){
    
		cout<<1<<" "<<flag+1<<" "<<1<<" "<<flag<<endl;
	}
	else{
    
		cout<<n/2<<" "<<n-1<<" "<<n/2+1<<" "<<n<<endl;
	}
}
int main(){
    
    multiCase solve();
    return 0;
}

错误原因:

else里面判断失误,错误样例

2
4
1011
5
10111

我的错解:

2 3 3 4
2 4 3 5

正解1:

1 2 2 3 
1 2 2 3 

正解2:

2 4 3 4
2 5 3 5

解释:

当后一半(n为奇数的时候后一半多一个元素)没有0的时候,要用到前面一个数字去构造,如果前面一个是1,那么可以用,如果前面的不是1,那么就不能用这个数字了,下面两个代码看个人 思维习惯 理解吧

ac代码:

一种思维习惯:

#include <bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define f(i,a,n) for(int i=a;i<n;++i)
#define ff(i,a,n) for(int i=a;i<=n;++i)
#define OP freopen("D:\\Users\\HP ZBook15\\CLionProjects\\untitled\\demo\\in.TXT","r",stdin);
#define CL freopen("D:\\Users\\HP ZBook15\\CLionProjects\\untitled\\demo\\out.TXT","w",stdout);
const int INF=0x3f3f3f3f;
using namespace std;
typedef long long ll;
typedef double dbl;
typedef pair<int, int> pi;
//
int n;
void solve(){
    
	cin>>n;
	string s;
	cin>>s;
	int flag=0,p=0;
	for(int i=n-1;i>=n/2;i--){
    
		if(s[i]=='0'){
    
			flag=i;
			break;
		}
	}
	if(flag) cout<<1<<" "<<flag+1<<" "<<1<<" "<<flag<<endl;
	else cout<<n/2<<" "<<(s[n/2-1]=='1'?n-1:n)<<" "<<n/2+1<<" "<<n<<endl;
}
int main(){
    
    multiCase solve();
    return 0;
}
/*
4
4
1011
5
10111
4
1111
5
11111
*/

另一种思维习惯:

#include <bits/stdc++.h>
using namespace std;
void solve() {
    
    int n;
    cin >> n;

    string s;
    cin >> s;

    for (int i = 0; i < n; i++) {
    
        if (s[i] == '0') {
    
            if (i < n / 2) {
    
                cout << i + 1 << " " << n << " " << i + 2 << " " << n << "\n";
            } else {
    
                cout << 1 << " " << i + 1 << " " << 1 << " " << i << "\n";
            }
            return;
        }
    }

    cout << 1 << " " << n / 2 * 2 << " " << 1 << " " << n / 2 << "\n";
}

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
    
        solve();
    }

    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_45550375/article/details/119949721

智能推荐

脉冲星 10 月脉动 | Pulsar 2.5.0 功能预览,Pulsar Meetup 上海站报名中_StreamNative的博客-程序员秘密

????️阅读本文需要 8 分钟&gt; PIP-45 Pluggable metadata interface该方案提供一个统一的可插拔的接口,抽象出 Pulsar 的元数据实现。重构...

工欲善其事,必先利其器_bravegogo的博客-程序员秘密

-37 内存泄露监测http://www.alonemonkey.com/2016/05/15/fbretaincycledetector-analyse/ FBRetainCycleDetector源码分析https://blog.csdn.net/java2013liu/article/details/52242969精准 iOS 内存泄露检测工具MLeaksFind...

03 类加载机制解析四:打破双亲委派机制_wyaoyao93的博客-程序员秘密

文章目录1 打破双亲委派机制1 打破双亲委派机制上节自定义的类加载器,实现了加载指定目录的class,但是还是遵循了双亲委派机制如何打破双亲委派机制很简单,我们已经知道了双亲委派机制就是在ClassLoader的loadClass方法实现的,只要我们重写该方法就可以了呗package study.wyy.jvm.classLoader;import java.io.FileInputStream;public class MyClassLoader extends ClassLoader

JSP带中文请求参数乱码的解决方法_RabbitEatPumpkin的博客-程序员秘密_jsp 带中文

<br />一、在请求页面的请求参数需要用encodeURI进行转码,然后在接收请求的页面需要进行字符集转换。<br />本例中的请求和接收页面的字符集都是UTF-8:<br />1.请求的JSP页面用JavaScript的encodeURI()方法将参数转码:<br />function toView(param){<br />     var encodeparam = encodeURI(param) ;<br />     window.location.href="/naias/advAna_fo

构建NVDLA vp时的错误_chifredhong的博客-程序员秘密

1、make: * No rule to make target错误ake[4]: *** No rule to make target '/home/chifred/NVDLA/NVDLA_debug/vp_large/libs/qbox/dtc/libfdt/fdt.c', needed by 'libfdt/fdt.o'。 停止。Makefile:342: recipe for t...

数组与Object的关系及其反射类型,数组反射应用实例,通过Array类实现数组的反射_wjw_java的博客-程序员秘密

package com.lianxi;import java.lang.reflect.Array;import java.util.Arrays;/** * 数组与Object的关系,及其反射类型 * * Array:可以对数组进行反射的类 * * 数组的反射: * 相同数据类型,相同维度的数组的Class都属于同一个 * * @author zjw */p

随便推点

uniapp 自定义基座调试(Android)_一个博客的博客-程序员秘密

1、Android Studio -》src-》main-》assets-》data-》dcloud_control.xml添加 debug=“true” syncDebug=“true”

Contributor等你解锁! | PPSIG报名开始啦~_飞桨PaddlePaddle的博客-程序员秘密

点击左上方蓝字关注我们开源的开放性使得诸多的开发者可以加入其中,自2016年开源以来,飞桨一直致力于建设开源开放的开发者社区,也正是有了众多contributor们的加入,飞桨社区得以不断...

洛谷P1296 奶牛的耳语_水蛙菌的博客-程序员秘密

题目链接题目描述在你的养牛场,所有的奶牛都养在一排呈直线的牛栏中。一共有 nn 头奶牛,其中第 ii 头牛在直线上所处的位置可以用一个整数坐标 pi (0 ≤ pi ≤ 108) 来表示。在无聊的日子里,奶牛们常常在自己的牛栏里与其它奶牛交流一些八卦新闻。每头奶牛发出的声音响度是一样的,而由于声波的能量衰减,某头奶牛发出的声音只能被与它距离不超过 d(0 ≤ d ≤ 104 ) 的奶牛所听到,这样这对奶牛就称为可以相互交流的。现在给出所有奶牛的位置和声音所能传播的最远距离 d ,请你编个程序来计算你的养

【iOS取证篇】iPhone6及以下版本进入恢复模式和DFU模式操作方法_蘇小沐的博客-程序员秘密

过程中,如果手机没有任何反应,或者电脑上打开的iTunes显示无法识别设备等,均为进入DFU模式失败,需要重新操作。此方法不排除因后续iOS系统升级或其它原因等而失效,取证时应找相关设备再次验证后再对检材操作!由于本人能力有限,纯粹做个记录,文中如有不妥和错漏之处欢迎批评指正。【著作所有权归作者蘇小沐所有,转载请注明文章出处】名称时间开始编辑日期2021 年 11 月 18 日最后编辑日期2022 年 11 月 28 日。

Mifare S50与Mifare S70_River-D的博客-程序员秘密

射频识别技术漫谈(13)——Mifare S50与Mifare S70

HDU 2093 考试排名 (水题)_xcatf的博客-程序员秘密

考试排名Time Limit: 1000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 19617Accepted Submission(s): 6788Proble...

推荐文章

热门文章

相关标签