- Three Friends
- Snow Walking Robot
- Yet Another Broken Keyboard
- Remove One Element
- Nearest Opposite Parity
- Two Bracket Sequences
Three Friends
[Time Limit: 1 squad Memory Limit: 256 MB
]
根据题意，把最大的减一，最小的加一，然后答案就是两倍他们的差值
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
int main() {
scanf("%d", &T);
while(T--) {
ll a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
ll x = min({a, b, c});
ll y = max({a, b, c});
ll ans = y-x-2;
printf("%lld
", max(0ll, ans*2));
}
return 0;
}
Snow Walking Robot
[Time Limit: 2 squad Memory Limit: 256 MB
]
考虑放成长方形，那么 (L、R) 方向能放的个数就是 (L、R) 的较少值，(U、D) 方向能放的个数就是 (U、D) 方向的较少值。
特殊考虑一下存在 (L、R) 为 (0) 个，或 (U、D) 为 (0) 个的方案就可以了，
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
int a[5];
char ch[4];
char s[maxn], ans[maxn];
int getid(char x) {
if(x == 'L') return 0;
if(x == 'R') return 1;
if(x == 'U') return 2;
if(x == 'D') return 3;
}
void solve() {
tol = 0;
if(a[0]==0 || a[1]==0) {
if(a[2]>0 && a[3]>0) {
ans[++tol] = ch[2];
ans[++tol] = ch[3];
}
return ;
}
if(a[2]==0 || a[3]==0) {
if(a[0]>0 && a[1]>0) {
ans[++tol] = ch[0];
ans[++tol] = ch[1];
}
return ;
}
int mx = 0;
for(int i=1; i<=3; i++) {
if(a[i] > a[mx]) mx = i;
}
char f1 = ch[mx^1], f3 = ch[mx];
int c1 = a[mx^1];
a[mx] = a[mx^1] = 0;
mx = 0;
for(int i=1; i<=3; i++) {
if(a[i] > a[mx]) mx = i;
}
char f2 = ch[mx^1], f4 = ch[mx];
int c2 = a[mx^1];
for(int i=1; i<=c1; i++) ans[++tol] = f1;
for(int i=1; i<=c2; i++) ans[++tol] = f2;
for(int i=1; i<=c1; i++) ans[++tol] = f3;
for(int i=1; i<=c2; i++) ans[++tol] = f4;
}
int main() {
ch[0] = 'L';
ch[1] = 'R';
ch[2] = 'U';
ch[3] = 'D';
scanf("%d", &T);
while(T--) {
mes(a, 0);
scanf("%s", s+1);
n = strlen(s+1);
for(int i=1; i<=n; i++) a[getid(s[i])]++;
solve();
ans[++tol] = ' ';
tol--;
printf("%d
", tol);
printf("%s
", ans+1);
}
return 0;
}
Yet Another Broken Keyboard
[Time Limit: 2 squad Memory Limit: 256 MB
]
直接根据题目模拟，令连续可用字符的个数 (x)，答案就是所有的 (frac{x(x+1)}{2}) 之和。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
char s[maxn];
bool vis[222];
int main() {
scanf("%d%d", &n, &m);
mes(vis, 0);
scanf("%s", s+1);
s[n+1] = 'z'+1;
for(int i=1; i<=m; i++) {
char x[5];scanf("%s", x+1);
vis[x[1]-'a'+1] = 1;
}
ll ans = 0, cnt = 0;
for(int i=1; i<=n+1; i++) {
if(vis[s[i]-'a'+1]) {
cnt++;
continue;
}
ans += (cnt+1)*cnt/2;
cnt = 0;
}
printf("%lld
", ans);
return 0;
}
Remove One Element
[Time Limit: 2 squad Memory Limit: 256 MB
]
- 令数组 (b[]) 表示以 (i) 结尾，往左最多可以取多少个数字
- 令数组 (c[]) 表示以 (i) 开头，往右最多可以取多少个数字
假设不用删除元素，那么 (b[]) 中的最大值就是一个答案。
考虑删掉一个元素，也就是把 (a[i-1]) 和 (a[i+1]) 合在了一起，那么就考虑 (a[i-1]) 和 (a[i+1]) 是否满足递增。如果满足递增的话，就会产生新的合法序列，其长度就是 (b[i-1]+c[i+1])。
那么只要枚举删掉的元素是哪个，就可以计算答案了。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
ll a[maxn], b[maxn], c[maxn];
int main() {
scanf("%d", &n);
b[0] = b[n+1] = 0;
c[0] = c[n+1] = 0;
ll ans = 0;
for(int i=1; i<=n; i++) {
scanf("%lld", &a[i]);
b[i] = a[i]>a[i-1] ? b[i-1]+1 : 1;
ans = max(ans, b[i]);
}
for(int i=n; i>=1; i--) {
c[i] = a[i]<a[i+1] ? c[i+1]+1 : 1;
ans = max(ans, c[i]);
}
for(int i=1; i<=n; i++) {
if(i==1 || i==n || a[i+1]>a[i-1])
ans = max(ans, b[i-1]+c[i+1]);
}
printf("%lld
", ans);
return 0;
}
Nearest Opposite Parity
[Time Limit: 2 squad Memory Limit: 256 MB
]
令 (dp[maxn][0/1]) 表示从 (i) 位置到最近的 偶数/奇数 需要跳的最小步数。
反向建图，例如从 (i) 跳到 (j)，那么连一条 (j) 到 (i) 的边
初始时 (dp[i][a[i]\%2]=0)，然后暴力 (bfs) 就可以算出每个状态，如果结束后还有哪个状态没有计算出来，那就是无法到达。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
int a[maxn], c[maxn];
ll dp[maxn][2];
vector<int> vv[maxn];
struct Node {
int p, st, step;
};
int main() {
queue<Node> q;
scanf("%d", &n);
for(int i=1; i<=n; i++) {
scanf("%d", &a[i]);
c[i] = a[i]%2;
dp[i][0] = dp[i][1] = -1;
if(i-a[i]>=1) vv[i-a[i]].pb(i);
if(i+a[i]<=n) vv[i+a[i]].pb(i);
q.push({i, c[i], 0});
}
while(!q.empty()) {
Node now = q.front();
q.pop();
if(dp[now.p][now.st] != -1) continue;
dp[now.p][now.st] = now.step;
for(auto np : vv[now.p]) {
q.push({np, now.st, now.step+1});
}
}
for(int i=1; i<=n; i++) printf("%lld%c", dp[i][!c[i]], i==n ? '
':' ');
return 0;
}
Two Bracket Sequences
[Time Limit: 2 squad Memory Limit: 256 MB
]
考虑判断括号表达式是否合法的过程，整个栈中只会有 (()，如果空栈时遇到一个 ()) 就必然是不合法的。
如果全部字符串判断结束后栈中还有 (()，那么想要让他变成合法的式子，只要补上相应多的 ()) 就可以了。
因为要满足两个字符串都是构造出来的字符串的子序列，那么必然是可以贪心去判断是否是它的子序列的。
令 (dp[i][j][k]) 表示第一个字符串贪心到第 (i) 位，第二个字符串贪心匹配到第 (j) 位，栈中还有 (k) 个 (() 所需要的最少步数。
(dp) 的过程中，在保证满足 (k) 够的情况下，每次尝试在后面放一个 (() 或 ())，看放入的这个括号对整个 (dp) 状态的改变。
那么最后的合法状态就是 (dp[n][m][k]) 形成的字符串在加上 (k) 个 ())。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e2 + 10;
const int maxm = 4e2 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
struct Node {
int x, y, z;
} last[maxn][maxn][maxm];
int dp[maxn][maxn][maxm];
char s1[maxn], s2[maxn];
int main() {
scanf("%s%s", s1+1, s2+1);
n = strlen(s1+1);
m = strlen(s2+1);
tol = 0;
for(int i=1; i<=n; i++) tol += s1[i]=='(';
for(int i=1; i<=m; i++) tol += s2[i]=='(';
tol = max(tol, n+m-tol);
mes(dp, inf);
dp[0][0][0] = 0;
for(int i=0; i<=n; i++) {
for(int j=0; j<=m; j++) {
for(int k=0; k<=tol; k++) {
if(dp[i][j][k] == inf) continue;
// printf("dp[%d][%d][%d] = %d
", i, j, k, dp[i][j][k]);
if(s1[i+1] == '(' && s2[j+1] == '(') {
if(dp[i+1][j+1][k+1] > dp[i][j][k]+1) {
dp[i+1][j+1][k+1] = dp[i][j][k]+1;
last[i+1][j+1][k+1] = {i, j, k};
}
} else if(s1[i+1] == '(') {
if(dp[i+1][j][k+1] > dp[i][j][k]+1) {
dp[i+1][j][k+1] = dp[i][j][k]+1;
last[i+1][j][k+1] = {i, j, k};
}
} else if(s2[j+1] == '(') {
if(dp[i][j+1][k+1] > dp[i][j][k]+1) {
dp[i][j+1][k+1] = dp[i][j][k]+1;
last[i][j+1][k+1] = {i, j, k};
}
} else {
if(dp[i][j][k+1] > dp[i][j][k]+1) {
dp[i][j][k+1] = dp[i][j][k]+1;
last[i][j][k+1] = {i, j, k};
}
}
if(!k) continue;
if(s1[i+1] == ')' && s2[j+1] == ')') {
if(dp[i+1][j+1][k-1] > dp[i][j][k]+1) {
dp[i+1][j+1][k-1] = dp[i][j][k]+1;
last[i+1][j+1][k-1] = {i, j, k};
}
} else if(s1[i+1] == ')') {
if(dp[i+1][j][k-1] > dp[i][j][k]+1) {
dp[i+1][j][k-1] = dp[i][j][k]+1;
last[i+1][j][k-1] = {i, j, k};
}
} else if(s2[j+1] == ')') {
if(dp[i][j+1][k-1] > dp[i][j][k]+1) {
dp[i][j+1][k-1] = dp[i][j][k]+1;
last[i][j+1][k-1] = {i, j, k};
}
} else {
if(dp[i][j][k-1] > dp[i][j][k]+1) {
dp[i][j][k-1] = dp[i][j][k]+1;
last[i][j][k-1] = {i, j, k};
}
}
}
}
}
int id = 0;
for(int i=1; i<=tol; i++) {
if(dp[n][m][id]+id > dp[n][m][i]+i) id = i;
}
vector<char> vv;
Node now = {n, m, id};
for(int i=1; i<=id; i++) vv.push_back(')');
while(now.x || now.y || now.z) {
vv.push_back(now.z > last[now.x][now.y][now.z].z ? '(' : ')');
now = last[now.x][now.y][now.z];
}
for(int i=(int)vv.size()-1; i>=0; i--) putchar(vv[i]);
puts("");
return 0;
}