这场题目真的很简单，感觉如果能回复手速的话，以后类似的div3能做到AK？
叽你太美，叽你实在是太美，hiahiahia
咳咳……进入正题
Rating:1361 → 1418，四题末尾，要是手速快一点就好了
本场关键词
手速、贪心、最短路、DP、DP、DP
A. Three Friends
模拟题，我居然四发才过……直接GG
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll q,a[3];
cin>>q;
while(q--)
{
for(int i=0;i<3;i++)
cin>>a[i];
sort(a,a+3);
if(a[0]<a[1])
a[0]++;
else if(a[1]<a[2]-1)
a[0]++;
if(a[0]<a[1])
a[1]--;
else if(a[1]<a[2]-1)
a[1]++;
if(a[1]<a[2])
a[2]--;
ll ans=abs(a[2]-a[1])+abs(a[1]-a[0])+abs(a[2]-a[0]);
cout<<ans<<endl;
}
return 0;
}
|
B.Snow Walking Robot
机器人有一系列操作指令，可以将这一系列指令从中敲除一些，并将剩下指令打乱顺序。
机器人可以向上、下、左、右走，且必须回到原点，且中间不能重复走到同一位置，且要求删除的指令数最少，输出符合要求的指令。
思路
统计指令数量，绕一个圈，直接贪心
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
char s[100005];
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>s;
int len=strlen(s);
int cnt=0,a[4]={0};
for(int i=0;i<len;i++)
if(s[i]=='U')
a[0]++;
else if(s[i]=='D')
a[1]++;
else if(s[i]=='L')
a[2]++;
else
a[3]++;
int x=min(a[2],a[3]),y=min(a[0],a[1]);
if(x==0)
y=min(y,1);
if(y==0)
x=min(x,1);
cout<<2*x+2*y<<endl;
for(int i=0;i<x;i++)
cout<<"R";
for(int i=0;i<y;i++)
cout<<"U";
for(int i=0;i<x;i++)
cout<<"L";
for(int i=0;i<y;i++)
cout<<"D";
cout<<endl;
}
return 0;
}
|
C. Yet Another Broken Keyboard
一个字符串s，仅由小写英文字母构成。
Norge想打出所有连续非空子串。
可是，他发现他的键盘坏了，只能打出26字母中的k个。
请求出用这个坏掉的键盘，最多能打出多少个字符串s的连续非空子串。
思路
线性DP，dp[i]表示以s串第i个字符结尾的非法子串数量。
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[200005];
bool mp[30];
ll dp[200005];
int main()
{
ll n,k;
cin>>n>>k>>s+1;
for(int i=0;i<k;i++)
{
char ch;
cin>>ch;
mp[ch-'a']=1;
}
ll ans=0;
for(int i=1;i<=n;i++)
{
if(!mp[s[i]-'a'])
dp[i]=i;
else
dp[i]=dp[i-1];
ans+=dp[i];
}
cout<<n*(n+1)/2-ans<<endl;
return 0;
}
|
D.Remove One Element(1500)
一个长度为n的序列，你可以选择是否删除其中一个元素。
求出操作后序列中可能存在的最长连续严格上升子序列长度。
思路
两次DP
第一次DP求出$dp[i]$表示以第i个元素结尾的LIS
第二次DP反向求，$dp_2[i]$表示以第i个元素开头的LIS
记录上述过程中最大长度$ans$
枚举元素$i$，当$a_{i-1}<a_{i+1}$时，$ans=max(ans,dp[i-1]+dp_2[i+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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int a[maxn],rec[maxn],dp[maxn],des[maxn];
int main()
{
int n,m=0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
if(a[i]>a[i-1])
dp[i]=dp[i-1]+1;
else
dp[i]=1;
m=max(m,dp[i]);
}
for(int i=n;i>=1;i--)
{
if(a[i]<a[i+1])
des[i]=des[i+1]+1;
else
des[i]=1;
}
for(int i=2;i<n;i++)
if(a[i-1]<a[i+1])
m=max(m,dp[i-1]+des[i+1]);
cout<<m<<endl;
return 0;
}
|
E.Nearest Opposite Parity(2000)
给出一个长度为$n$的序列$a$
在位置$i$时，可以跳到$i+a_i$或$i-a_i$(不越界)
对于每一个位$i$，你想知道最少需要多少步可以到达一个位置$j$，使得$a_j$与$a_i$的奇偶性不同
思路
嘤嘤嘤，这题我一眼就觉得是DP，然后交了一发DFS实现的记忆化搜索，MLE了……
要是做出来就快乐上分了(ノ｀Д)ノ
没想到居然是图论……我最短路没学懂，太菜了╥﹏╥…
看了半天大佬们的博客，才有点头绪。
初始化$dist$为-1，这样输出就不用特判了。
本题我们反向建图$G$，对点$i$，我们从$i+a[i]$和$i-a[i]$向$i$建一条权值为1的边，$(u,v)$含义即为$u$可到达$v$。
然后再正向判断一下每个点$i$，如果$i$能一步到达奇偶性不同的点，则将$dist[i]$置为1，并将$i$点加入队列，并且在$G$上以$i$为源点进行多源BFS，计算剩下所有能多步到达点某个奇偶性不同节点的节点的距离。
因为每条边权值都为1，很明显后出队的权值不会比之前出队的权值小，可以不用优先队列。
因为之前进行判断，所以$dist[v]=-1$时，一定没有奇偶性不同节点能一步到达$v$，所以当前的$x$点奇偶性一定与出点$v$点相同，$dist[v]=dist[x]+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
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int a[maxn],dist[maxn];
vector<int> G[maxn];
int main()
{
memset(dist,-1,sizeof(dist));
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
queue<int> QAQ;
for(int i=1;i<=n;i++)
{
if(i+a[i]<=n)
G[i+a[i]].push_back(i);
if(i-a[i]>=1)
G[i-a[i]].push_back(i);
}
for(int i=1;i<=n;i++)
{
int x=i+a[i];
if(x<=n&&(a[x]^a[i])&1)
dist[i]=1;
x=i-a[i];
if(x>=1&&(a[x]^a[i])&1)
dist[i]=1;
if(dist[i]==1)
QAQ.push(i);
}
while(!QAQ.empty())
{
int x=QAQ.front();
QAQ.pop();
for(auto &v:G[x])
if(dist[v]==-1)
{
dist[v]=dist[x]+1;
QAQ.push(v);
}
}
for(int i=1;i<=n;i++)
{
cout<<dist[i]<<' ';
}
return 0;
}
|
F. Two Bracket Sequences(2400)
一个DP……
应该不会，以后会了再补……
2019年12月18日11点01分