Codeforces Round #605 (Div. 3)
A. Three Friends题意：给三个点，每个点至多往左边或者右边移动一次，可以不移动。问最后两两距离之和的最小值。思路：直接枚举每个点往左，不动和往右的情况。计算答案。AC代码：#include <iostream>#include <bits/stdc++.h>#include <unordered_map>//#define int long lon
·
A. Three Friends
题意：给三个点，每个点至多往左边或者右边移动一次，可以不移动。问最后两两距离之和的最小值。
思路：直接枚举每个点往左，不动和往右的情况。计算答案。
AC代码：
#include <iostream>
#include <bits/stdc++.h>
#include <unordered_map>
//#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 1e6+1;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
int res[N];
int cal(int i,int j,int k){
a[0] += i;
a[1] += j;
a[2] += k;
int res = abs(a[2]-a[1])+abs(a[2]-a[0])+abs(a[1]-a[0]);
a[0] -= i;
a[1] -= j;
a[2] -= k;
return res;
}
signed main(){
cin>>t;
while(t--){
cin>>a[0]>>a[1]>>a[2];
sort(a,a+3);
int res = a[2]-a[1]+a[2]-a[0]+a[1]-a[0];
for(int i = -1 ; i <= 1 ; i ++){
for(int j = -1 ; j <= 1 ; j ++){
for(int k = -1 ; k<= 1 ; k ++){
res = min(res,cal(i,j,k));
}
}
}
cout<<res<<endl;
}
return 0;
}
B. Snow Walking Robot
题意：一个机器人，可以上下左右移动。除了起点，每个点只能访问一次。起点最多两次。从起点出发并且回到起点。给出一堆操作。要删除一些，并重新组合。使得机器人走的路径满足上述条件。
思路：显然要回到起点，U D次数要相同。L R同理。所以对于U D，选择min(u,d)次U操作和min(u,d)次D操作。L R 同理。而当 UD 操作次数为0时。 最多只能往左右走一格 就得回来。同理当 LR次数为0，只能往上一格再回来。剩下的合法的操作就按照 左上右下，绕一大圈，就可以回去了。
AC代码：
#include <iostream>
#include <bits/stdc++.h>
#include <unordered_map>
//#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 1e6+1;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
int res[N];
signed main(){
cin>>t;
while(t--){
string s;
cin>>s;
int u = 0 ,d = 0 ,l = 0 ,r = 0;
for(int i = 0 ; i < s.size() ; i ++){
if(s[i] == 'U') u ++;
if(s[i] == 'D') d ++;
if(s[i] == 'R') r ++;
if(s[i] == 'L') l ++;
}
int remu = min(u,d);
int reml = min(l,r);
if(remu == 0 && reml == 0){
cout<<0<<endl<<endl;
}else if(remu == 0){
cout<<2<<endl;
cout<<"LR"<<endl;
}else if(reml == 0){
cout<<2<<endl;
cout<<"UD"<<endl;
}else{
cout<<remu*2+reml*2<<endl;
for(int i = 0 ; i < remu ; i ++){
cout<<"U";
}for(int i = 0 ; i < reml ; i ++){
cout<<"L";
}for(int i = 0 ; i < remu ; i ++){
cout<<"D";
}for(int i = 0 ; i < reml ; i ++){
cout<<"R";
}
cout<<endl;
}
}
return 0;
}
C. Yet Another Broken Keyboard
题意：给定一个串。现在只能选择 m 个字符。求在s串中，有多少个子串是仅由这几个字符组成的。
思路：对于一个连续的串，子串数量是k·(k+1)/2。所以只需要找出有多少个连续的区间，仅由这几个字符组成就够了。然后分别计算子串数量。最后求和。
AC代码：
#include <iostream>
#include <bits/stdc++.h>
#include <unordered_map>
#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 1e6+1;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
int res[N];
signed main(){
//cin>>t;
while(t--){
cin>>n>>m;
string s;
cin>>s;
map<char,int> mp;
for(int i = 0 ; i < m ; i ++){
char x;
cin>>x;
mp[x] = 1;
}
int res = 0;
for(int i = 0 ; i < s.size() ; i ++){
int tmp = 0;
while(i < s.size() && mp[s[i]]){
tmp ++;
i ++;
}
res += tmp*(tmp+1)/2;
}
cout<<res<<endl;
}
return 0;
}
D. Remove One Element
题意：n个元素的数组，求至多删掉一个元素的情况下，最长的严格上升的子串。
思路：因为是子串。那就很简单了。比如这样的 123 2 456，那显然删掉2是最佳的。而对于 123456 2，这种删不删都无所谓。如果考虑暴力做法，就是枚举删掉任意一个数，然后求LIS。但是显然会超时。这时候，如果删掉一个数时，我们已经知道他往左的LIS和往右的LIS，那么一合并，就是整个的LIS了。所以先从左往右，求一遍LIS，再从右往左求一遍LIS。然后再枚举每个位置删或者不删的情况的下的答案，取max就好了。
AC代码：
#include <iostream>
#include <bits/stdc++.h>
#include <unordered_map>
#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 1e6+1;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
int res[N];
int dp[N][2];
signed main(){
//cin>>t;
while(t--){
cin>>n;
for(int i = 0 ; i < n ; i ++){
cin>>a[i];
}
dp[0][0] = 1;
for(int i = 1 ; i < n ; i ++){
if(a[i] > a[i-1]){
dp[i][0] = dp[i-1][0]+1;
}else{
dp[i][0] = 1;
}
}
dp[n-1][1] = 1;
for(int i = n-2 ; i >= 0 ; i --){
if(a[i] < a[i+1]){
dp[i][1] = dp[i+1][1] +1;
}else{
dp[i][1] = 1;
}
}
int res = 1;
a[n] = -1;
for(int i = 0 ; i < n-1 ; i ++){
if(a[i] < a[i+1]){
res = max(res,dp[i][0]+dp[i+1][1]);
}
if(a[i] < a[i+2]){
res = max(res,dp[i][0]+dp[i+2][1]);
}
}
cout<<res<<endl;
}
return 0;
}
E. Nearest Opposite Parity
题意：一个数组，每个位置可以跳到a[i]+i或者a[i]-i的位置上去。求每个位置，最少需要跳多少次，可以碰到和自己奇偶性不同的元素。
思路：考虑BFS。首先可以求出只要跳一次就可以找到的位置。然后剩下的位置，肯定相互跳来跳去都是和自己奇偶性相同的。直到跳到一个可以一步跳到奇偶性不同的位置的点。如果正着跳，枚举每个点为起点，那肯定超时。这时候就可以用bfs去遍历。以一步就成功的点为起点。然后开始跳。这个过程逻辑上是逆过来的，其实是从别的点，跳到这个位置。所以建图的时候，要反着建。就变成从这个位置跳过去了。然后就转变成了最简单的bfs了。遍历完所有点答案就出来了。
AC代码：
#include <iostream>
#include <bits/stdc++.h>
#include <unordered_map>
#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 1e6+1;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
int res[N];
vector<int> edge[N];
struct node{
int pos;
int step;
node(int x,int y){
pos = x;
step = y;
}
};
queue<node> que;
int mark[N];
int vis[N];
bool check(int x,int y){
return (a[x]%2) != (a[y]%2);
}
signed main(){
//cin>>t;
while(t--){
cin>>n;
for(int i = 0 ; i < n ; i ++){
cin>>a[i];
}
for(int i = 0 ; i < n ; i ++){
int l = i-a[i];
int r = i+a[i];
int flag = 0;
if(r < n ){
if(check(i,r)) flag = 1;
edge[r].push_back(i);
}
if(l >= 0){
if(check(i,l)) flag = 1;
edge[l].push_back(i);
}
if(flag){
mark[i] = 1;
que.push(node(i,1));
}
}
while(!que.empty()){
node now = que.front();que.pop();
int pos = now.pos;
for(int i = 0 ; i < edge[pos].size() ; i ++){
int to = edge[pos][i];
if(mark[to] == 0){
mark[to] = mark[pos]+1;
que.push(node(to,now.step+1));
}
}
}
for(int i = 0 ; i < n ; i ++){
if(!mark[i]) cout<<-1<<" ";
else cout<<mark[i]<<" ";
}
cout<<endl;
}
return 0;
}
F. Two Bracket Sequences
题意：给出两个括号串，求一个最短的括号串，使得这两个串都是他的子序列。
思路：参考官方题解。BFS+DP。用dp[i][j][d]表示包含s1的前i个，s2的前j个，且度为d的情况下的最小长度。 度定义为 左括号的数量-右括号的数量。转移呢，肯定是从 dp[0][0][0]开始。然后如果填入一个左括号，那么d += 1。并且如果s1[i] == ‘(’，那么 i+=1，同理如果 s2[j] == ‘(’，j += 1。右括号同理。且在dp 的过程中，要记录每个节点的前驱。用于最后输出答案。整个转移过程(左括号的情况)：
node now = que.front(); que.pop();
int x,y,z;
x = now.x + (now.x < n && s1[now.x] == '(');
y = now.y + (now.y < m && s2[now.y] == '(');
z = now.z + 1;
if(z <= N && dp[x][y][z] == inf){
dp[x][y][z] = dp[now.x][now.y][now.z]+1;
pre[x][y][z] = node(now.x,now.y,now.z,'(');
que.push(node(x,y,z,0));
}
AC代码：
#include <iostream>
#include <bits/stdc++.h>
#include <unordered_map>
//#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int N = 2e2+7;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
struct node{
int x,y,z;
char val;
node(){}
node(int xx,int yy,int zz,char v){
x = xx;
y = yy;
z = zz;
val = v;
}
}pre[N][N][N];
int dp[N][N][N];
queue<node> que;
string s1,s2;
void bfs(){
memset(dp,inf,sizeof(dp));
dp[0][0][0] = 0;
que.push(node(0,0,0,0));
while(!que.empty()){
node now = que.front(); que.pop();
int x,y,z;
x = now.x + (now.x < n && s1[now.x] == '(');
y = now.y + (now.y < m && s2[now.y] == '(');
z = now.z + 1;
if(z <= N && dp[x][y][z] == inf){
dp[x][y][z] = dp[now.x][now.y][now.z]+1;
pre[x][y][z] = node(now.x,now.y,now.z,'(');
que.push(node(x,y,z,0));
}
x = now.x + (now.x < n && s1[now.x] == ')');
y = now.y + (now.y < m && s2[now.y] == ')');
z = now.z - 1;
if(z >= 0 && dp[x][y][z] == inf){
dp[x][y][z] = dp[now.x][now.y][now.z]+1;
pre[x][y][z] = node(now.x,now.y,now.z,')');
que.push(node(x,y,z,0));
}
}
}
signed main(){
//cin>>t;
while(t--){
cin>>s1>>s2;
n = s1.size();m = s2.size();
bfs();
char res[500];
int pos = 0;
node now = pre[n][m][0];
res[pos++] = now.val;
while(now.x+now.y+now.z){
now = pre[now.x][now.y][now.z];
res[pos++] = now.val;
}
res[pos] = 0;
reverse(res,res+pos);
cout<<res<<endl;
}
return 0;
}
/***
***/
为开发者提供学习成长、分享交流、生态实践、资源工具等服务，帮助开发者快速成长。
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)