Educational Codeforces Round 70

A. You Are Given Two Binary Strings…

题意：给定二进制下两个数，把第二个数左移k位，与第一个数相加，再把数字倒过来，要求字典序最小，求k。

第二个数最低位的1要和第一个数对应位置之前的1对齐。再移位只会增大位数。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int T;
char s[N], t[N];
int main() {
	cin >> T;
	while (T--) {
		scanf("%s", s);
		scanf("%s", t);
		int n = strlen(s), m = strlen(t);
		int p;
		for (int i = m - 1; i >= 0; i--) {
			if (t[i] == '1') { p = i; break; }
		}
		int ans = 0;
		for (int i = n - m + p; i >= 0; i--) {
			if (s[i] == '1')break;
			ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}

B. You Are Given a Decimal String…

题意：给定i，j要求从0开始，只能+i或者+j，每次取个位数放入答案序列中。现在给出一个残缺的答案序列，问对于0到9的每一对i，j，至少补多少位能使答案序列成为可能的序列。

序列中每个数只与他后面那个数有联系，只要遍历序列，每次补最少位，使得能到达后面那个数即可。

floyed预处理出每对i，j下每个数字到其他数字的最小距离。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
int T;
int G[20][20];
int d[20][20][20][20];
char s[N];
int main() {
	scanf("%s", s);
	int n = strlen(s);
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			for (int u = 0; u < 10; u++) {
				for (int v = 0; v < 10; v++) {
					d[i][j][u][v] = INF;
				}
			}
			for (int k = 0; k < 10; k++) {
				d[i][j][k][(k + i) % 10] = 1;
				d[i][j][k][(k + j) % 10] = 1;
			}
			for (int k = 0; k < 10; k++) {
				for (int u = 0; u < 10; u++) {
					for (int v = 0; v < 10; v++) {
						d[i][j][u][v] = min(d[i][j][u][v], d[i][j][u][k] + d[i][j][k][v]);
					}
				}
			}
		}
	}
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			int ans = 0;
			for (int k = 0; k < n - 1; k++) {
				ans += d[i][j][s[k] - '0'][s[k + 1] - '0'] - 1;
				if (ans >= INF-1) { ans = -1; break; }
			}
			printf("%d%s", ans, j == 9 ? "\n" : " ");
		}
	}
	return 0;
}

C. You Are Given a WASD-string…

题意：WASD操作机器人，现给定操作序列，问至少要多大的矩形网格，能使机器人不会出界。可以向操作序列中插入一个操作。

横向纵向无关，所以考虑分开求。插入一个操作必须要使得该方向的宽度减小。

以横向为例，记录向左走的最远距离，即每次的左边减去右侧最远到过的坐标，向右走的最远距离类似。如果两个距离相等，则插入操作也没有用。因为最大的宽度一定了，再移动也不会减小。

否则再判断如果左边的最远坐标大于1，则可以插入一次向右走，或者如果左边的最远坐标为1，但是右侧最远坐标大于等于1，则也可以插入一次向右走。对称方向类似。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
int T, n;
char s[N], tt[]{ "WASD" };
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%s", s + 1);
		n = strlen(s + 1);
		ll a = 0, b = 0, c = 0, d = 0;
		ll x = 0, y = 0, mu = 0, md = 0, ml = 0, mr = 0;
		for (int i = 1; s[i]; i++) {
			if (s[i] == 'W')y++, c = max(c, y);
			else if (s[i] == 'S')y--, d = min(d, y);
			else if (s[i] == 'A')x--, b = min(b, x);
			else x++, a = max(a, x);
			mu = max(mu, y - d);
			md = max(md, c - y);
			mr = max(mr, x - b);
			ml = max(ml, a - x);
		}
		ll ans = (a - b + 1)*(c - d + 1);
		if (ml != mr) {
			if (a >= 1 && b <= -1 || a > 1 || b < -1)
				ans = min(ans, (a - b)*(c - d + 1));
		}
		if (mu != md) {
			if (c >= 1 && d <= -1 || c > 1 || d < -1)
				ans = min(ans, (a - b + 1)*(c - d));
		}
		printf("%lld\n", ans);
	}
	return 0;
}

D. Print a 1337-string…

题意：构造一个只含1，3，7的数列，且子序列中1337的个数等于n。

假设有k个3，左边是1，右边是7，则1337个数为 $C_k^2$ ，此时向左边增加1，则每增加一个1，就增多 $C_k^2$ ，而如果向中间插入1，则要看插入的位置右边有多少3，再增加对应个数的组合数。

所以可以先确定3的个数，然后向中间插入3，可以知道一定是可以凑出来的，并且由于排列数增长很快，所以到6000的时候就已经大于1e9了，那么不管再怎么插入1，最后的长度也不会超过1e5.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
int T;
ll n;
ll C(ll n) { return n * (n - 1) / 2; }
vector<ll>vc;
int main() {
	vc.push_back(0); vc.push_back(0);
	for (ll i = 2; i <= 6000; i++)vc.push_back(C(i));
	scanf("%d", &T);
	while (T--) {
		scanf("%lld", &n);
		int p = upper_bound(vc.begin(), vc.end(), n) - vc.begin() - 1;
		while (p >= 2) {
			ll a = n / vc[p]; n = n % vc[p];
			p--;
			for (int i = 0; i < a; i++)printf("1");
			printf("3");
		}
		printf("37\n");
	}
	return 0;
}