Codeforces Round #551 (Div. 2) A-E

A. Serval and Bus

• 算出每辆车会在什么时候上车， 取min即可

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define ll long long

#define M 101

#define mmp make_pair

using namespace std;

int read() {

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

int ans[M], n, t;

int main() {

	n = read(), t = read();

	for(int i = 1; i <= n; i++)

	{

		int a = read(), b = read();

		while(a < t) a += b;

		ans[i] = a;

	}

	int minn = 0x3e3e3e3e, pl = 0;

	for(int i = 1; i <= n; i++) if(ans[i] < minn) minn = ans[i], pl = i;

	cout << pl << "\n";

	return 0;

}

B. Serval and Toy Bricks

• 贪心每个位置假如能放， 就放横看数看的较小值

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define ll long long

#define M 110

#define mmp make_pair

using namespace std;

int read() {

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

int a[M][M], h[M], l[M];

int main() {

	int x = read(), y = read(), z = read();

	for(int i = 1; i <= y; i++) h[i] = read();

	for(int i = 1; i <= x; i++) l[i] = read();

	for(int i = 1; i <= x; i++) for(int j = 1; j <= y; j++) a[i][j] = read();

	for(int i = 1; i <= x; i++) for(int j = 1; j <= y; j++) if(a[i][j]) a[i][j] = min(l[i], h[j]);

	for(int i = 1; i <= x; i++) {

		for(int j = 1; j <= y; j++) cout << a[i][j] << " ";

		cout << "\n";

	}

	return 0;

}

C. Serval and Parenthesis Sequence

• 转化成第一个括号一定要和最后一个括号匹配， 对于2到n-1位置的串进行构造即可

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define ll long long

#define M 300010

#define mmp make_pair

using namespace std;

int read() {

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

char s[M];

int n;

int main() {

	n = read();

	scanf("%s", s + 1);

	if(n & 1) return 0 * puts(":(");

	if(s[1] == ')' || s[n] == '(') return 0 * puts(":(");

	s[1] = '(', s[n] = ')';

	int tot = n - 2, a = 0, b = 0, c;

	for(int i = 2; i < n; i++) {

		if(s[i] == '(') a++;

		else if(s[i] == ')') b++;

		else c++;

	}

	if(a > tot / 2 || b > tot / 2) return 0 * puts(":(");

	a = tot / 2 - a;

	for(int i = 2; i < n; i++) {

		if(s[i] == '?') {

			if(a) s[i] = '(', a--;

			else s[i] = ')';

		}

	}

	int cnt = 0;

	for(int i = 2; i < n; i++) {

		if(s[i] == '(') cnt++;

		else cnt--;

		if(cnt < 0) return 0 * puts(":(");

	}

	puts(s + 1);

	return 0;

}

D. Serval and Rooted Tree

• 树形dp， 考虑dp每颗子树的影响， 最大值的话选择影响最小的， 最小值的话影响求和

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define ll long long

#define M 300010

#define mmp make_pair

using namespace std;

int read() {

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

int n, ver[M], fa[M], k, f[M];

vector<int> to[M];

bool cmp(int a, int b) {

	return f[a] < f[b];

}

void dfs(int now) {

	for(int i = 0; i < to[now].size(); i++) {

		int vj = to[now][i];

		dfs(vj);

	}

	if(to[now].size() == 0) {

		f[now] = 1;

		return;

	}

	sort(to[now].begin(), to[now].end(), cmp);

	if(ver[now]) {

		f[now] = f[to[now][0]];

	} else {

		for(int i = 0; i < to[now].size(); i++) f[now] += f[to[now][i]];

	}

}

int main() {

	n = read();

	for(int i = 1; i <= n; i++) ver[i] = read();

	for(int i = 2; i <= n; i++) fa[i] = read(), to[fa[i]].push_back(i);

	for(int i = 2; i <= n; i++) if(to[i].size() == 0) k++;

	dfs(1);

	cout << k - f[1] + 1<< "\n";

	return 0;

}

E. Serval and Snake

• 先枚举找到边界， 然后二分找位置

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define ll long long

#define M 101

#define mmp make_pair

using namespace std;

bool rev = false;

vector<int>row, col;

int ask(int x1, int y1, int x2, int y2) {

	if(rev) {

		swap(x1, y1);

		swap(x2, y2);

	}

	cout << "? " << x1 + 1 << ' ' << y1 + 1 << ' ' << x2 + 1 << ' ' << y2 + 1 << endl;

	int res;

	cin>>res;

	return res;

}

void answer(int x1, int y1, int x2, int y2) {

	if(rev) {

		swap(x1, y1);

		swap(x2, y2);

	}

	cout << "! " << x1 + 1 << ' ' << y1 + 1 << ' ' << x2 + 1 << ' ' << y2 + 1 << endl;

}

int main() {

	int n;

	cin>>n;

	for(int i = 0; i < n; i++) {

		int res = ask(i, 0, i, n - 1);

		if(res % 2 == 1)row.push_back(i);

		res = ask(0, i, n - 1, i);

		if(res % 2 == 1)col.push_back(i);

	}

	vector<pair<int, int> >ans;

	if(row.size() == 2 && col.size() == 2) {

		for(int x:row)for(int y:col) {

				if(ask(x, y, x, y) % 2 == 1) {

					ans.push_back(mmp(x, y));

				}

			}

		answer(ans[0].first, ans[0].second, ans[1].first, ans[1].second);

		return 0;

	}

	if(row.size() == 0) {

		rev = true;

		swap(row, col);

	}

	int ok = n - 1, ng =  - 1;

	while(ok - ng>1) {

		int t = (ok + ng)/2;

		if(ask(0, 0, row[0], t) % 2 == 1)ok = t;

		else ng = t;

	}

	answer(row[0], ok, row[1], ok);

	return 0;

}