Codeforces Round #608 (Div. 2) 题解

• Suits
• Blocks
• Shawarma Tent
• Portals
• Common Number

Suits

[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>
#include <unordered_map>
#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>

typedef unsigned long long int ull;
typedef long long int ll;
const int    maxn = 1e5 + 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,b,c,d,e,f;

int main(){
	scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
	int ans1 = min(a, d), ans2 = min({b, c, d});
	int ans = e>f ? ans1*e + min({ans2, d-ans1})*f :  ans2*f + min({ans1, d-ans2})*e;
	printf("%d
", ans);
}

Blocks

[Time Limit: 2 squad Memory Limit: 256 MB ]

最后肯定全是 (W) 或者全是 (B) 的，那么直接暴力扫两遍就可以了。

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>
#include <unordered_map>
#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>

typedef unsigned long long int ull;
typedef long long int ll;
const int    maxn = 1e5 + 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];
char ss[maxn];
vector<int> ans;

bool solve() {
	ans.clear();
	for(int i=1; i<=n; i++)	ss[i] = s[i];
	for(int i=1; i<n; i++) {
		if(ss[i] == 'B')	continue;
		ss[i] = 'B';
		ss[i+1] = s[i+1]=='B' ? 'W':'B';
		ans.pb(i);
	}
	if(ans.size() <= 3*n && ss[n] == 'B')	return true;
	return false;
}

int main() {
    // freopen("in", "r", stdin);
	scanf("%d", &n);
	scanf("%s", s+1);
	if(!solve()) {
		for(int i=1; i<=n; i++) {
			s[i] = s[i]=='B' ? 'W':'B';
		}
		if(!solve()) {
			return 0*puts("-1");
		}
	}
	int sz = ans.size();
	printf("%d
", sz);
	for(int i=0; i<sz; i++)	printf("%d%c", ans[i], i==sz-1 ? '
':' ');
    return 0;
}

Shawarma Tent

[Time Limit: 1 squad Memory Limit: 256 MB ]

假设学校处于 ((sx, sy)) 位置，可以看成 ((sx, sy)) 为原点，其他学生到这里的最近距离，那么容易发现，最好的一定可以选成 ((sx-1, sy)、(sx+1, sy)、(sx, sy-1)、(sx, sy+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>
#include <unordered_map>
#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>

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 sx, sy;
ll x, y;
struct Node {
	ll x, y, st;
	bool operator < (Node a) const{
		return st>a.st;
	}
} p[5];

bool ok(Node t) {
	ll ans = abs(sx-x) + abs(sy-y);
	ll ans1 = abs(sx-t.x) + abs(sy-t.y);
	ll ans2 = abs(x-t.x) + abs(y-t.y);
	return ans == ans1+ans2;
}

int main() {
    // freopen("in", "r", stdin);
	scanf("%lld%lld%lld", &n, &sx, &sy);
	p[1] = {sx-1, sy, 0};
	p[2] = {sx+1, sy, 0};
	p[3] = {sx, sy-1, 0};
	p[4] = {sx, sy+1, 0};
	for(int i=1; i<=n; i++) {
		scanf("%lld%lld", &x, &y);
		for(int j=1; j<=4; j++) {
			if(ok(p[j]))	p[j].st++;
		}
	}
	sort(p+1, p+1+4);
	printf("%lld
%lld %lld
", p[1].st, p[1].x, p[1].y);
    return 0;
}

Portals

[Time Limit: 2 squad Memory Limit: 256 MB ]

对于一个 (v) 点，如果有多条 (u->v)，那么我完全可以到最大的 (u) 的时候在派士兵过来，这样做一定不会使结果更劣，并且能够保证尽量占领多的城市。

那么用 (dp[i][j]) 表示目前的到达第 (i) 个城市，手上有 (j) 个士兵时，可以获得的最大价值。

贪心处理 (j)，如果有多个城市的最大的 (u) 为 (i)，既然每个城市都只需派一个人，那么我肯定先派人去可以获得价值大的城市。

view

#include <map>
#include <set>
#include <list>
#include <tuple>
#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>
#include <unordered_map>
#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 = 5e3 + 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, k;
int cas, tol, T;

vector<int> g[maxn];
int a[maxn], b[maxn], c[maxn], p[maxn];
ll dp[2][maxn];

bool cmp(int x, int y) {
	return c[x] > c[y];
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i=1, x, y, z; i<=n; i++) {
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
		p[i] = i, g[i].clear();
	}
	for(int i=1, u, v; i<=m; i++) {
		scanf("%d%d", &u, &v);
		p[v] = max(p[v], u);
	}
	for(int i=1; i<=n; i++)	g[p[i]].pb(i);
	for(int i=1; i<=n; i++)	sort(g[i].begin(), g[i].end(), cmp);
	for(int i=0; i<=5000; i++)dp[0][i] = dp[1][i] = -INF;
	dp[0][k] = 0;
	int f = 0;
	for(int i=1; i<=n; i++) {
		f = !f;
		for(int j=0; j<=5000; j++)	dp[f][j] = -INF;
		for(int j=a[i]; j<=5000; j++) {
			if(dp[!f][j] == -INF)	continue;
			ll w = j+b[i], d = 0;
			dp[f][w] = max(dp[f][w], dp[!f][j]);
			for(auto k : g[i]) {
				d += c[k], w--;
				dp[f][w] = max(dp[f][w], dp[!f][j]+d);
				if(!w)  break;
			}
		}
	}
	ll ans = -1;
	for(int i=0; i<=5000; i++)	ans = max(ans, dp[f][i]);
	printf("%lld
", ans);
	return 0;
}

Common Number

[Time Limit: 2 squad Memory Limit: 256 MB ]

对于一个数 (x)

1. (x) 为偶数，那么它可以通过 (x) 得来，然后就是(2*x、2*x+1)。
2. (x) 为奇数，那么它可以通过 (x、x+1) 得来，然后就是 (2*x、2*x+1、2*x+2、2*x+3)。

当 (x) 的奇偶性相同时，显然对于同一个上届，(x) 越小，满足条件的数字越多，那么就可以对 (x) 奇偶然后二分答案，最后取两者较大值。

view

#include <map>
#include <set>
#include <list>
#include <tuple>
#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>
#include <unordered_map>
#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<ll, ll>
#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 = 1e5 + 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;

ll n, m;
int cas, tol, T;

bool ok(ll x) {
	queue<pii> q;
	if(x&1)	q.push({x, x});
	else	q.push({x, x+1});
	ll ans = 0;
	while(!q.empty()) {
		auto it = q.front();
		q.pop();
		ans += min(n, it.se)-it.fi+1;
		if(2ll*it.fi <= n)	q.push({2ll*it.fi, 2ll*it.se+1});
	}
	return ans>=m;
}

int main() {
	scanf("%lld%lld", &n, &m);
	ll ans = 0;
	{
		ll l=0, r=n/2, res=0;
		while(l<=r) {
			ll mid = l+r>>1;
			if(ok(mid<<1|1))	l = mid+1, res=mid;
			else	r = mid-1;
		}
		ans = max(ans, res<<1|1);
	}
	{
		ll l=1, r=n/2, res=0;
		while(l<=r) {
			ll mid = l+r>>1;
			if(ok(mid<<1))	l = mid+1, res=mid;
			else	r = mid-1;
		}
		ans = max(ans, res<<1);
	}
	printf("%lld
", ans);
	return 0;
}