第一次 AK & Room Rank 1
(虽然最后挂了e

E

一个括号序列,有三种操作

  • L 向左移一个位置
  • R 向右移一个位置
  • D 删除从当前括号到与之对应的括号的所以括号,然后移动到序列右边一个位置,若不能则,左边一个位置

模拟
记录po[]为每个括号对应括号的位置(用栈处理),然后记录l[],r[]当前位置的左边一个位置,和右边一个位置
然后模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;
int n,m,p;
char s[maxn],op[maxn];
int l[maxn],r[maxn],po[maxn];
stack<int> st;

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %d %d",&n,&m,&p);
scanf("%s %s",s,op);
for(int i=1;i<=n;++i)
{
if(s[i-1] == '(') st.push(i);
else
{
po[st.top()] = i;
po[i] = st.top();
st.pop();
}
}
for(int i=0;i<=n;++i) l[i] = i-1,r[i] = i+1;
for(int i=0;i<m;++i)
{
if(op[i] == 'R') p = r[p];
else if(op[i] == 'L') p = l[p];
else
{
if(p > po[p]) p = po[p];
int ll = l[p],rr = r[po[p]];
r[ll] = rr;
l[rr] = ll;
p = rr;
if(p == n+1) p = ll;
}
}
for(int i=r[0];i<=n;i=r[i]) putchar(s[i-1]);
puts("");
return 0;
}

F

给定一个n位数,随机打乱每个位置,然后再将n的各位随机加进去
给定这个数的一个子序列,还原最小的这个数

贪心
首先我们发现位数只有一种情况,比如len - 1 = 9len - 2 < 10
我们找到n,然后把n从中删去,把子序列从中删去
因为要找最小的数,所以考虑这个数每个位置从小到大排列(首位先放一个非0的数)
然后再考虑加入子序列,我们发现其要么加在子序列首位的数前面要么后面,取决于第一个不等于首位的数与之的大小关系。
注意有情况其有可能放在第一个位置,此时就应该用子序列与从0开始的序列循环比较了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
char s[maxn],ss[maxn];
int cnt[10],n,m;

void dec(int t)
{
do
{
--cnt[t%10];
t /= 10;
}while(t);
}

int main()
{
//freopen("test.txt","r",stdin);
scanf("%s %s",s,ss);
n = strlen(s);
for(int i=0;i<n;++i) ++cnt[s[i]-'0'];
if(n == 1)
{
puts("0");
return 0;
}
int cur = 1;
for(int i=1;i<9;++i)
{
if(cur <= n-i && n-i < cur*10)
{
n -= i;
dec(n);
break;
}
cur *= 10;
}
m = strlen(ss);
for(int i=0;i<m;++i) --cnt[ss[i]-'0'];
int p = 0;
while(p < m && ss[p] == ss[0]) ++p;
if(p < m && ss[p]>ss[0]) p = 1;
else p = 0;
for(int i=1;i<10;++i)
{
if(ss[0]-'0' == i)
{
if(!cnt[ss[0]-'0'])
{
printf("%s",ss);
p = -1;
break;
}
else
{
int t = 1;
int flag = -1;
while(1)
{
for(int j=0;j<=i;++j)
{
if(t >= m)
{
flag = 1;
break;
}
if(!cnt[j]) continue;
for(int k=0;k<cnt[j];++k)
{

if(t >= m)
{
flag = 1;
break;
}
if(ss[t]-'0' > j)
{
flag = 0;
break;
}
else if(ss[t]-'0' < j)
{
flag = 1;
break;
}
++t;
}
if(flag != -1) break;
}
if(flag != -1) break;
}
if(flag == 1)
{
printf("%s",ss);
p = -1;
break;
}
}
}
if(cnt[i])
{
putchar('0'+i);
--cnt[i];
break;
}
}
for(int i=0;i<10;++i)
{
if(ss[0]-'0' == i && p==0)
{
printf("%s",ss);
p = -1;
}
if(cnt[i])
{
for(int j=0;j<cnt[i];++j) putchar('0'+i);
}
if(ss[0]-'0' == i && p>0)
{
printf("%s",ss);
p = -1;
}
}
puts("");
return 0;
}