题意
一串括号字符串,里面存在一些‘?’,其中‘?’既可以当作 '(' 又可以当作 ')' ,计算有多少对(l,r),在s中[sl,s(l+1),s(l+2),.....sr],内的括号是匹配的。n=strlen(s)<=5000。
分析
这个题还是卡了很久的,我果然是很菜的。
(错误思路)
一开始的时候想,用一个变量cur表示还未匹配的左括号 '(' ,用变量num记录‘?’的数量,‘?’尽量当右括号使用,在判断(l,r)是否匹配的时候从左往右扫,遇到'(' 的时候cur++,遇到 ')'cur--,如果最左边的字符是'?'那么直接将其变成'(' num--,cur++;因为它如果是')'不再有作用。当cur==num的时候说明当前长度是匹配的。如果num>cur,且(num-cur)%2==0则说明问好可以和‘(’匹配,剩下的‘?’自己互相匹配。
错误代码:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=+;
char s[maxn];
int n;
int main(){
scanf("%s",s);
n=strlen(s);
int ans=;
for(int i=;i<n;i++){
int cur=,num=;
if(s[i]==')')continue;
else cur++;
for(int j=i+;j<n;j++){
bool jud=;
if(s[j]=='(')cur++;
if(s[j]==')')cur--;
if(s[j]=='?')num++;
if(cur==&&num==)jud=;
else if(cur==&&num){cur++;num--;}
if(cur==num)jud=;
else if(num>cur&&(num-cur)%==)jud=;
if(jud)ans++;
}
}
cout<<ans<<endl;
return ;
}
思路纠正:
上面一开始我考虑最左边的'?'只能被当作(使用,可以在深入考虑一下,如果当前?的数量大于(的数量,那么多的?就只能被当作(使用否则没法匹配。这样可以消除对于右边的影响 "(??(()"也就是‘?’当作‘)’来匹配左边的‘(’。
正确代码:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=+;
char s[maxn];
int n;
int main(){
scanf("%s",s);
n=strlen(s);
int ans=;
for(int i=;i<n;i++){
int cur=,num=;
if(s[i]==')')continue;
else cur++;
for(int j=i+;j<n;j++){
bool jud=;
if(s[j]=='(')cur++;
if(s[j]==')')cur--;
if(s[j]=='?')num++;
if(cur==&&num==)jud=;
else if(cur==&&num){cur++;num--;}
if(cur==num)jud=;
else if(num>cur&&(num-cur)%==)jud=;
if(jud)ans++;
}
}
cout<<ans<<endl;
return ;
}
codeforce 459DIV2 C题的更多相关文章
-
codeforce 461DIV2 F题
题意 题目给出n,k,要求找出一个1到n的子集,(a,b)的对数等于k:(a,b)满足a<b且b%a==0: 分析 还记不记得求素数的时候的欧拉筛!对就那样!如果把每个数字看作一个点的话,可以通 ...
-
codeforce 461DIV2 E题
题意 有n棵树排成一排,每个树上都有c[i]只小鸟,只有站在树下才可以召唤小鸟,在i-th树下召唤k(k<=c[i])只小鸟需要消耗cost[i]*k的法力值,但是每召唤一只小鸟可以将法力值的上 ...
-
codeforce 462DIV2 C题
题意 给出一个只含有1和2的序列,有n个元素,可以选择一段区间进行翻转操作,求再反转后的最大非递减子序列的长度 分析 太菜了只想出了N^2的做法.序列只有1和2,那么每个非递减子序列都会有一个分界点, ...
-
codeforce 460DIV2 D题
感觉这个题不错,对拓扑排序有了更深的了解,用两种拓扑排序都写了些试试. dfs #include <cstdio> #include <algorithm> #include ...
-
Two progressions CodeForce 125D 思维题
An arithmetic progression is such a non-empty sequence of numbers where the difference between any t ...
-
codeforce 457DIV2 C题
题意 你需要构造一个n个点m条边的无向有权图,要求这个图的MST中边权的和与从1到n的最短路长度都为素数 分析 可以想到这样一种贪心,在i到i+1直接连一条边,这样最短路和MST都会是同样的一些边.只 ...
-
codeforce 457DIV2 B题
题意: 题目给出两个整数n,k,(n<=10^18,k<=10^5),求一个含有k个整数的序列,要求以2为底,以序列内数字为幂的和为n,其中序列内最大的数最小,若有多个序列满足条件,输出 ...
-
DSU on Tree浅谈
DSU on tree 在之前的一次比赛中,学长向我们讲了了这样一个神奇的思想:DSU on tree(树上启发式合并),看上去就非常厉害--但实际上是非常暴力的一种做法;不过暴力只是看上去暴力,它在 ...
-
ACDream手速赛2
地址:http://acdream.info/onecontest/1014 都是来自Codeforce上简单题. A. Boy or Girl 简单字符串处理 B. Walking in ...
随机推荐
-
Java学习之LinkedHashMap学习总结
前言: 在学习LRU算法的时候,看到LruCache源码实现是基于LinkedHashMap,今天学习一下LinkedHashMap的好处以及如何实现lru缓存机制的. 需求背景: LRU这个算法就是 ...
-
Sql server2012 常见异常处理
网络相关 无法通过IP(127.0.0.1 或者其他本机)连接 确保TCP/IP功能开启 打开1433端口 权限相关 代理的权限,通过更改有最高权限的用户,或者给该用户指定的权限 给域用户开通SQLS ...
-
Java 集合系列 12 TreeMap
java 集合系列目录: Java 集合系列 01 总体框架 Java 集合系列 02 Collection架构 Java 集合系列 03 ArrayList详细介绍(源码解析)和使用示例 Java ...
-
iOS开发之构建Widget
原文出处: 陈凯 在 jianshu 的博客(@chenkaiHome) 欢迎分享原创到伯乐头条 伴随这iOS 8 系统多达4000项API更新而来同样还有Today Extension.而对iO ...
-
Oracle 创建和使用视图
一.what(什么是视图?) 1.视图是一种数据库对象,是从一个或者多个数据表或视图中导出的虚表,视图所对应的数据并不真正地存储在视图中,而是存储在所引用的数据表中,视图的结构和数据是对数据表进行查询 ...
-
OpenSuse13.2硬盘安装
直接参考文章:OpenSuse硬盘安装 补充: Win7引导Grub4dos时,本人尝试根据xp引导方式中使用boot.ini来引导,引导成功,不需要bcdedit命令,简化了引导步骤.
-
windows server 2008 应用程序池自动关闭 C:\Windows\system32\RpcProxy\RpcProxy.dll failed to load
Sign In Join Search IIS Home Downloads Learn Reference Solutions Blogs Forums HomeIIS.NET Forums64-b ...
-
判断json数据是否包含key
1.("key" in jsonObj) 如果有返回true 没有返回false 2.jsonObj.hasOwnProperty("key") 如果有返回tr ...
-
Java知多少(36)内部类及其实例化
在 Java 中,允许在一个类(或方法.语句块)的内部定义另一个类,称为内部类(Inner Class),有时也称为嵌套类(Nested Class). 内部类和外层封装它的类之间存在逻辑上的所属关系 ...
-
ORACLE managed file(OMF)
ORACLE managed file (OMF) Oracle自动创建和删除OMF文件 不用操心文件的命名约定 在手动管理文件时容易错误删除数据文件(OMF降低这种风险) Oracle自动删除不再需 ...