Educational Codeforces Round 70 (Rated for Div. 2) A.B.C.D

A. You Are Given Two Binary Strings...

找出第二个串最后一个1的位置在第一个串的这个位置及之前找第一个1的位置，两个位置相减就是答案

#include<bits/stdc++.h>
using namespace std;
int main() {
	int t;
	for(cin>>t; t; t--){
		string s, t;
		cin>>s>>t;
		reverse(s.begin(), s.end());
		reverse(t.begin(), t.end());
		int n = 0;
		while(t[n] != '1'){
			n++;
		}
		int m = n;
		while(s[m] != '1'){
			m++;
		}
		cout<<m-n<<endl;
	}
	return 0;
}

B. You Are Given a Decimal String...

先预处理处理出当x和y为不同情况的时候当个位数差值为多少时，最少需要多少个x和y相加（不可以为0个）

然后暴力枚举所有情况，取最小的情况

#include<bits/stdc++.h>
#define ll long long
#define maxn 2000005
#define mod 1e9 + 7
using namespace std;

ll num[11][11];
int qq[11][11][13];
char ss[maxn];
int main() {
	int n;
	memset(num, 0, sizeof(num));
	scanf("%s", ss);
	int len = strlen(ss);
	ll ans = 0;
	int cnt;
	for(int x = 0; x < 10; x++) {
		for(int y = 0; y <= x; y++) {
			for(int i = 0; i <= 9; i++) {
				int minn = 1000;
				for(int j = 0; j <= 10; j++) {
					for(int k = 0; k <= 10; k++) {
						int gg = (j*x+k*y) % 10;
						if(gg == i) {
							if(k+j == 0) continue;
							minn = min(k+j, minn);
						}
					}
				}
				if(minn == 1000) {
					qq[x][y][i] = -1;
					qq[y][x][i] = -1;
				} else {
					qq[x][y][i] = minn-1;
					qq[y][x][i] = minn-1;
				}
			}		
		}
	}
	for(int x = 0; x < 10; x++) {
		for(int y = 0; y <= x; y++) {
			for(int i = 1; i < len; i++) {
				cnt = (ss[i]-'0') + 10 - (ss[i-1]-'0');
				cnt %= 10;
				if(qq[x][y][cnt] == -1) {
					num[x][y] = -1;
					num[y][x] = -1;
					break;
				} else {
					num[x][y] += qq[x][y][cnt];
					num[y][x] += qq[x][y][cnt];
				}
			}
		}
	}
	for(int i = 0; i < 10; i++) {
		for(int j = 0; j < 10; j++) {
			if(i == j && num[i][j] != -1) {
				num[i][j] /= 2;
			}
			printf("%d ", num[i][j]);
		}
		puts("");
	}
	return 0;
}

C. You Are Given a WASD-string...

每走一步记录一下当前最大最小的横坐标，纵坐标

由此得出当前向左向右向上向下都最多移动了多少距离

当相反方向的移动的距离都不为0的时候，且不相等的情况下，可以减去该方向上的面积

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 240000;
char s[maxn];
int main() {
	int T;
	for(cin >> T; T; T -= 1) {
		cin >> s;
		int cw = 0, cd = 0;
		int ma = 0, md = 0, mw = 0, ms = 0;
		int sa = 0, sd = 0, sw = 0, ss = 0;
		for(int i = 0; s[i]; i += 1) {
			if(s[i] == 'W') cw += 1;
			if(s[i] == 'S') cw -= 1;
			if(s[i] == 'D') cd += 1;
			if(s[i] == 'A') cd -= 1;
			mw = max(mw, cw);
			ms = min(ms, cw);
			md = max(md, cd);
			ma = min(ma, cd);
			sw = max(sw, cw - ms);//往上面移动了最多多少 
			ss = max(ss, mw - cw);//往下面移动了最多多少 
			sd = max(sd, cd - ma);//往左面移动了最多多少 
			sa = max(sa, md - cd);//往右面移动了最多多少 
		}
		ll x[2], y[2];
		x[0] = max(sw, ss);//上下的距离 
		x[1] = max(ll(sw or ss), x[0] - !(sw == ss));//当 sw 和 ss 相等的时候 不用加 加了反而面积变大  都为0的时候不操作 
		y[0] = max(sd, sa);// 左右的距离 
		y[1] = max(ll(sd or sa), y[0] - !(sd == sa));//同理 
		ll ans = min((x[0] + 1) * (y[1] + 1), (x[1] + 1) * (y[0] + 1));
		cout << ans << endl;
	}
	return 0;
}

D. Print a 1337-string...

对于n 我们可以拆分成 + x
我们只要构造出

1个1 + (m-2)个3 + x个1 + 1个7 这样绝对是正确的

#include<bits/stdc++.h>
using namespace std;

int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		int n;
		scanf("%d", &n);
		string s = "1";
		int x = 1;
		while(x * (x - 1) / 2 <= n) {
			++x;
		}
		--x;
		s += string(x,'3');
		n -= x * (x - 1) / 2;
		if(n) {
			s.pop_back();
			s.pop_back();
			s += string(n,'1');
			s += "33";
		}
		s += "7";
		cout<<s<<endl;
	}
	return 0;
}