A

暴力
将一个字符串分为由长度为p或q的子串

可以用类似背包的方法标记

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 110;
int d[maxn*2];
char s[maxn];


int main()
{
// freopen("test.txt","r",stdin);
int n,p,q;
scanf("%d %d %d",&n,&p,&q);
scanf("%s",s);
memset(d,0,sizeof d);
d[0] = 1;
for(int i=0;i<n;++i)
{
if(d[i])
{
d[i+p] = 1;
d[i+q] = 1;
}
}
if(!d[n]) puts("-1");
else
{
int cnt = 0,cur = n;
vector<int> pos;
pos.push_back(n);
while(cur)
{
if(cur - p >= 0 && d[cur - p])
{
pos.push_back(cur - p);
cur -= p;
}
if(cur - q >= 0 && d[cur-q])
{
pos.push_back(cur - q);
cur -= q;
}
}
printf("%d\n",pos.size()-1);
cur = 0;
for(int i=pos.size()-1;i>0;--i)
{
for(int j=pos[i];j<pos[i-1];++j) putchar(s[j]);
puts("");
}
}
return 0;
}

B

模拟
给定一个排列,有一个机器人从1开始依此去往2,3…问机器人要走多少路程

依我们标记f[n] 为n所在的位置,最终答案为每两个位置间的差的绝对值的和

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
int f[maxn];

int main()
{
//freopen("test.txt"."r",stdin);
int n;
scanf("%d",&n);
for(int i=0;i<n;++i)
{
int x;
scanf("%d",&x);
f[x] = i+1;
}
long long ans = 0;
for(int i=1;i<n;++i)
{
ans += abs(f[i+1] - f[i]);
}
printf("%lld\n",ans);
return 0;
}

C


给定一个括号序列包括( ) { } < > [ ]八种括号,左右括号间可以相互替换,问最少多说次替换后可以形成一个合法的括号序列(括号间匹配)

直接用栈模拟即可,遇到不合法的情况,先考虑替换,不行则输出不可能

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
char s[maxn];

char match[] = {'[',']','<','>','(',')','{','}'};

stack<char> st;

int getpos(char c)
{
for(int i=0;i<8;++i) if(c == match[i]) return i;
return -1;
}

int main()
{
scanf("%s",s);
int n = strlen(s);
int ans = 0;
for(int i=0;i<n;++i)
{
if(!st.empty())
{
char ch = st.top();
int p1 = getpos(ch),p2 = getpos(s[i]);
if(p1&1)
break;
else
{
if(p2&1)
{
st.pop();
ans += (p1+1 != p2);
}
else
st.push(s[i]);
}
}
else st.push(s[i]);
}
if(st.empty()) printf("%d\n",ans);
else puts("Impossible");
return 0;
}

D

排序
给定n条线段,输出被覆盖k次的线段。

离散化,用1和-1表示出边和入边,排序后扫描一遍。

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
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second

vector<pair<int,int> > V,ans;

int main()
{
//freopen("test.txt","r",stdin);
int n,k;
scanf("%d %d",&n,&k);
for(int i=0;i<n;++i)
{
int x,y;
scanf("%d %d",&x,&y);
V.push_back(make_pair(x,-1));
V.push_back(make_pair(y,1));
}
sort(V.begin(),V.end());
int lst = 0,cur = 0;
for(int i=0;i<V.size();++i)
{
if(cur == k-1 && V[i].se == -1)
{
lst = V[i].fi;
}
if(cur == k && V[i].se == 1)
{
ans.push_back(make_pair(lst,V[i].fi));
}
cur -= V[i].se;
}
printf("%d\n",ans.size());
for(int i=0;i<ans.size();++i) printf("%d %d\n",ans[i].fi,ans[i].se);
return 0;
}