I:双向排序
题目描述
给定序列 (a1,a2,⋅⋅⋅,an)=(1,2,⋅⋅⋅,n)，即ai=i。
小蓝将对这个序列进行 mm 次操作，每次可能是将 a1,a2,⋯,aqi 降序排列，或者将 aqi,aqi+1,⋯,an 升序排列。
请求出操作完成后的序列。
输入描述
输入的第一行包含两个整数 n,m，分别表示序列的长度和操作次数。
接下来 mm 行描述对序列的操作，其中第 i 行包含两个整数 pi,qi 表示操作类型和参数。当 pi=0 时，表示将 a1,a2,⋅⋅⋅,aqi 降序排列；当 pi=1 时，表示将 a_{q_i} , a_{q_{i+1}}, \cdots, a_naqi,aqi+1,⋯,an 升序排列。
输出描述
输出一行，包含 nn 个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。
输入输出样例
示例
输入
3 3 0 3 1 2 0 2
输出
3 1 2
样例说明
原数列为 ((1,2,3)。
第 11 步后为 (3,2,1)。
第 22 步后为(3,1,2)。
第 33 步后为 (3,1,2)。与第 22 步操作后相同，因为前两个数已经是降序了。
评测用例规模与约定
对于 30% 的评测用例，1n,m≤1000；
对于 60\%60% 的评测用例， 1<n,m≤5000；
对于所有评测用例，1≤n,m≤100000，0≤pi≤1，1≤qi≤n。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
| C++ | 1s | 256M |
| C | 1s | 256M |
| Java | 1s | 256M |
| Python3 | 1s | 256M |
用sort只能通过60,
#include <iostream> #include <algorithm> using namespace std; int n,m; int a[100005]; bool pai(int x,int y){ return x>y; } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ a[i]=i+1; } for(int i=0;i<m;i++){ int x,y; cin>>x>>y; if(x==0){ sort(a,a+y,pai); } else{ sort(a+y-1,a+n); //注意是n } } for(int i=0;i<n;i++){ if(i!=n-1){ cout<<a[i]<<' '; } else{ cout<<a[i]; } } return 0; }
AC代码
#include <iostream> using namespace std; const int N = 100010; pair<int, int> stk[N]; int ans[N]; int main() { int n, m, top = 0; cin >> n >> m; while (m--) { int p, q; cin >> p >> q; if (p == 0) { while (top && stk[top].first == 0) { q = max(q, stk[top--].second); } while (top >= 2 && stk[top - 1].second <= q) { // 如果当前操作比上一次相同操作的范围要大，那此次操作的前两次操作都将被无效化 top -= 2; } stk[++top] = {0, q}; } else if (top) { while (top && stk[top].first == 1) { q = min(q, stk[top--].second); } while (top >= 2 && stk[top - 1].second >= q) { // 如果当前操作比上一次相同操作的范围要大，那此次操作的前两次操作都将被无效化 top -= 2; } stk[++top] = {1, q}; } } int left = 1, right = n, k = n; for (int i = 1; i < top + 1; i++) { if (stk[i].first == 0) { while (right > stk[i].second && left < right + 1) { ans[right--] = k--; } } else { while (left < stk[i].second && left < right + 1) { ans[left++] = k--; } } if (left > right) { break; } } if (top % 2) { while (left < right + 1) { ans[left++] = k--; } } else { while (left < right + 1) { ans[right--] = k--; } } for (int i = 1; i < n + 1; i++) { cout << ans[i] << " "; } return 0; }
J:括号队列
题目描述
给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。
两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和((()))。
输入描述
输入一行包含一个字符串 s，表示给定的括号序列，序列中只有左括号和右括号。
输出描述
输出一个整数表示答案，答案可能很大，请输出答案除以 1000000007 (即 10^9 + 7)109+7) 的余数。
输入输出样例
示例 1
输入
((()
输出
5
评测用例规模与约定
对于 40%的评测用例，∣s∣≤200。
对于所有评测用例，1≤∣s∣≤5000。
运行限制
最大运行时间：5s
最大运行内存: 512M
与其说一个规则，不如说是一个判断是否添加括号方法，在正常遍历字符串的时候，如果在当前遍历的位置的条件下，左括号数量大于右括号的数量，那么还不添括号，因为再往后遍历字符串的过程中还可能遇见右括号。如果在当前遍历的位置的条件下，左括号数量小于右括号的数量，那么需要添括号，因为再往后遍历字符串的过程中即使可能遇见左括号，也无法匹配之前的右括号 例如：）（ 这样是不匹配的。
大佬的代码：
#include <iostream> #include <cstring> #include <algorithm> using namespace std; using LL=long long; const int N = 5005; int f[N][N]; int mod=1e9+7; string s; int n; LL get(){ memset(f,0,sizeof f); f[0][0]=1; for(int i=1;i<=n;i++){ if(s[i-1]=='('){ for(int j=1;j<=n;j++) f[i][j]=f[i-1][j-1]; } else{ f[i][0]=(f[i-1][1]+f[i-1][0])%mod; for(int j=1;j<=n;j++) f[i][j]=(f[i-1][j+1]+f[i][j-1])%mod; } } for(int i=0;i<=n;i++) if(f[n][i]) return f[n][i]; return -1; } int main(){ cin>>s; n=s.size(); LL x=get(); reverse(s.begin(),s.end()); for(int i=0;i<n;i++){ if(s[i]==')') s[i]='('; else s[i]=')'; } LL y=get(); cout<<(x*y)%mod; }
