A. Treasure
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Malek has recently found a treasure map. While he was looking for a treasure he found a locked door. There was a stringswritten on the door consisting of characters ‘(‘, ‘)’ and ‘#’. Below there was a manual on how to open the door. After spending a long time Malek managed to decode the manual and found out that the goal is to replace each ‘#’ with one or more ‘)’ characters so that the final string becomesbeautiful.
Below there was also written that a string is calledbeautifulif for eachi(1≤i≤|s|) there are no more ‘)’ characters than ‘(‘ characters among the firsticharacters ofsand also the total number of ‘(‘ characters is equal to the total number of ‘)’ characters.
Help Malek open the door by telling him for each ‘#’ character how many ‘)’ characters he must replace it with.
Input
The first line of the input contains a strings(1≤|s|≤105). Each character of this string is one of the characters ‘(‘, ‘)’ or ‘#’. It is guaranteed thatscontains at least one ‘#’ character.
Output
If there is no way of replacing ‘#’ characters which leads to a beautiful string print-1. Otherwise for each character ‘#’ print a separate line containing a positive integer, the number of ‘)’ characters this character must be replaced with.
If there are several possible answers, you may output any of them.
Sample test(s)
input
(((#)((#)
output
12
input
()((#((#(#()
output
221
input
#
output
-1
input
(#)
output
-1
贪心。
(表示1，)表示-1。
满足条件则前缀和时刻都要>=0。
那么遇到#我们只让他表示一个)，前缀和只-1，遇到最后一个#再把前面的债还清。
一开始WA了，因为我遇到最后一个#就不管前缀和了。。
因此(#(这样的数据就过不了。
#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <cmath>#define M 100000+5using namespace std;char s[M];int ans[M];int main(){scanf("%s",s);int l=strlen(s);int la,now=0,tot=0;for (int i=0;i<l;i++){if (s[i]=='#'){ans[++tot]=1;now–;la=i;}if (s[i]=='(') now++;if (s[i]==')') now–;if (now<0){puts("-1");return 0;}}int x=0;for (int i=l-1;i>la;i–){if (s[i]=='(')x–;else x++;if (x<0){puts("-1");return 0;}}ans[tot]+=now;for (int i=1;i<=tot;i++)printf("%d\n",ans[i]);return 0;}
B. Obsessive String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Hamed has recently found a stringtand suddenly became quite fond of it. He spent several days trying to find all occurrences oftin other strings he had. Finally he became tired and started thinking about the following problem. Given a stringshow many ways are there to extractk≥1non-overlapping substrings from it such that each of them contains stringtas a substring? More formally, you need to calculate the number of ways to choose two sequencesa1,a2,…,akandb1,b2,…,bksatisfying the following requirements:
k≥1tis a substring of stringsaisai+1…sbi(stringsis considered as1-indexed).
As the number of ways can be rather large print it modulo109+7.
Input
你不能左右天气，但你能转变你的心情
