http://codeforces.com/contest/1271

C. Shawarma Tent

 

题意：直角坐标系上有一个起始点，和其他点，从起始点到其它点只能经过与最短路径长度相等的路径，现要在整个坐标系上找出一个点，使得从起始点到其他点的路径覆盖该点次数最多。

易证起始点的上下左右四个点一定至少有一个满足条件。因为其它满足条件的点一定有一条路径通过这四个点中的一个，则可以等价过去。

则枚举判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int maxn=1e6+10;
int n;
ll sx,sy;
ll x[maxn],y[maxn];
ll dx[]{-1,1,0,0};
ll dy[]{0,0,-1,1};
int ans[4];
int main(){
    scanf("%d%I64d%I64d",&n,&sx,&sy);
    for(int i=0;i<n;i++){
        scanf("%I64d%I64d",&x[i],&y[i]);
    }
    for(int i=0;i<4;i++){
        int nx=sx+dx[i],ny=sy+dy[i];
        for(int j=0;j<n;j++){
            if(i<2&&(nx-sx)*(x[j]-sx)>0)ans[i]++;
            else if(i>=2&&(ny-sy)*(y[j]-sy)>0)ans[i]++;
        }
    }
    int a=0,b=-1;
    for(int i=0;i<4;i++){
        if(a<=ans[i]){
            a=ans[i];
            b=i;
        }
    }
    cout<<a<<endl;
    cout<<sx+dx[b]<<' '<<sy+dy[b]<<endl;
    return 0;
}

 

D. Portals

 

从数据范围容易想到dp。

dp [i] [j] 表示在第 i 个城堡，且有 j 个战士时获得的最大value。

首先要看出只在最后一次经过某个城堡的时候选择占领或不占领。因为如果之前占领了，后面可能就走不下去了，而之后占领相比之前占领也并没有损失。

接下来就很直接了，对于每个 i ，先从 i−1i-1 转移过来，再枚举转移出去的传送门。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int n, m, k;
int a[maxn], b[maxn], c[maxn];
int dp[5010][10010];
vector<int>gg[maxn];
vector<int>G[maxn];
bool vis[maxn];
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		gg[u].push_back(v);
	}
	for (int i = 1; i <= n; i++)gg[i].push_back(i);
	for (int i = n; i >= 1; i--) {
		for (int v : gg[i]) {
			if (!vis[v]) {
				G[i].push_back(v);
				vis[v] = 1;
			}
		}
	}
	memset(dp, -1, sizeof(dp));
	dp[0][k] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = a[i]; j < 5001; j++) {
			if (dp[i - 1][j] != -1) {
				dp[i][j + b[i]] = max(dp[i][j + b[i]], dp[i - 1][j]);
			}
		}
		for (int v : G[i]) {
			for (int j = 1; j < 5001; j++) {
				if (dp[i][j] == -1)continue;
				dp[i][j - 1] = max(dp[i][j - 1], dp[i][j] + c[v]);
			}
		}
	}
	int ans = -1;
	for (int i = 0; i < 5001; i++) {
		ans = max(ans, dp[n][i]);
	}
	cout << ans << endl;
	return 0;
}

 

E. Common Number

 

感觉比D难。

考虑对于一个数 xx，有几条穿过它的路径。

对于奇数 xx，有 x,2x,2x+1,4x,4x+1,4x+2,4x+3⋯x,2x, 2x+1,4x,4x+1,4x+2,4x+3\cdots

对于偶数 xx，有 x,x+1,2x,2x+1,2x+2,2x+3,⋯x,x+1,2x,2x+1,2x+2,2x+3,\cdots

可以看到奇数可以表示为区间初始 L=x,R=xL=x,R=x，L*=2，R*=2+1。

偶数可以表示为区间初始 L=x,R=x+1L=x,R=x+1，L*=2，R=R*2+1。

每次更新区间并加上区间长度，直到 L>nL>n。

并且，对于奇偶性相同的两个数，越大的数路径数越少，有单调性，则二分，由于奇偶不同，所以要分别二分。

这里也是新学到了分奇偶二分的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
ll n, k;
bool check(ll x) {
	ll s = x, t = x + (x % 2 == 0);
	ll res = 0;
	while (s <= n) {
		res += min(n, t) - s + 1;
		s <<= 1;
		t = t * 2 + 1;
	}
	return res >= k;
}
int main() {
	cin >> n >> k;
	ll L = 0, R = (n + 1) / 2;
	while (L < R) {
		ll mid = L + (R - L + 1) / 2;
		if (check(2 * mid - 1))
			L = mid;
		else 
			R = mid - 1;
	}
	ll ans = 2 * L - 1;
	L = 0, R = n / 2;
	while (L < R) {
		ll mid = (L + R + 1) / 2;
		if (check(2 * mid)) 
			L = mid;
		else 
			R = mid - 1;
	}
	ans = max(ans, 2 * L);
	cout << ans << endl;
	return 0;
}