https://ac.nowcoder.com/acm/contest/3732#question

A. City

 

题意：给定一个 (n+1)* (m+1) 的网格，找到有几条线段满足：长度大于0，两端点都是格点，中点也是格点。

找规律。

如果条直线x坐标和为偶数，则中点x为整数，y同理。则枚举出有几对这样的x，y。相乘后减去长度为0的情况，再除2去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
ll n, m;
ll cnt1, cnt2;
int main() {
    cin >> n >> m;
    for (ll i = 0; i <= n; i++) {
        for (ll j = 0; j <= n; j++)if (!((i + j) & 1))cnt1++;
    }
    for (ll i = 0; i <= m; i++) {
        for (ll j = 0; j <= m; j++)if (!((i + j) & 1))cnt2++;
    }
    ll ans = cnt1 * cnt2;
    ans -= (n + 1)*(m + 1);
    ans /= 2;
    cout << ans << endl;
    return 0;
}

 

E. Flow

 

题意：给一个起点和终点，以及k条有向简单路径，每条路径除两端外不相交，并且长度都相等。每条有向边有一个容量，每次操作可以使任一边容量减1，同时另一边容量加1.问最少需要多少次操作使得流量最大。

每移动一点容量，一定要能使总流量增加一点，否则不如不动。

最终的最大流量一定是所有边容量和除以路径长度。

初始流量可以直接算出，即每条路径上的边最小容量乘以路径长度。

则现在问题变为移动一些容量，使得新增的流量等于最终最大流量与初始流量的差。

但这并不是直接减一下，因为只要增加一点流量可能需要改几条边的容量。而现在要改的边数* 每条边改的容量。

对于一条路径，将路径上的边按照容量从小到大排列。改第一条边最容易，之后难度递增，相当于阶梯式的高度递增，所以把所有路径的每一个难度的可修改的容量放在一起，按照难度排序，优先选难度低的，难度相同的选谁都一样。

注意特判n=2.

还有，按照难度递增选取修改容量的时候用优先队列会T，vector不会。卡常了？

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
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n, m;
ll sum;
struct E
{
	int v, w;
};
vector<E>G[maxn];
priority_queue<int, vector<int>, greater<int> >que;
vector<pii>vc;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		sum += w;
		G[u].push_back(E{ v,w });
	}
	ll tmp = 0;
	int l = 0;
	int u = 1;
	while (u != n) {
		u = G[u][0].v;
		l++;
	}
	if (l == 1) {
		cout << 0 << endl;
		return 0;
	}
	sum /= l;
	for (E e : G[1]) {
		int u = e.v;
		que.push(e.w);
		while (u != n) {
			que.push(G[u][0].w);
			u = G[u][0].v;
		}
		int tp = que.top(), cnt = 1;
		tmp += tp;
		que.pop();
		while (!que.empty()) {
			vc.push_back(pii(cnt++, que.top() - tp));
			tp = que.top();
			que.pop();
		}
	}
	sum -= tmp;
	ll ans = 0;
	sort(vc.begin(), vc.end());
	int i = 0;
	while (sum >= vc[i].second) {
		ans += 1ll * vc[i].first*vc[i].second;
		sum -= vc[i].second;
		i++;
	}
	ans += 1ll * vc[i].first*sum;
	cout << ans << endl;
	return 0;
}

 

M. Value

 

题意：从 1 到 n 中选一些不相等的数，value 等于选中的数的 a 值之和，若存在 i>1, j>1，且 ik=ji^k=j ，则 value 要减去 b[j]。求最大的 value。

由数据范围可知，有 ik=ji^k=j 关系的数组成的集合大小不超过18.

则每个集合内部可以状压，暴力求出最大 value。而不同集合之间没有影响，所以可以直接把各个集合的 value 相加。

比较坑的是题目要求的是每一对满足条件的 i，j 都要减去 b[j]，而不是存在满足条件的 i，j，所以一个 j 可能被减多次。

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
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 0x3f3f3f3f;
const ll maxn = 1e5 + 10;
ll n;
ll a[maxn], b[maxn];
ll ans;
ll vis[maxn];
vector<ll>vc[maxn];
ll cnt;
ll use[maxn];
ll solve(const vector<ll>& vc) {
    ll N = (ll)vc.size();
    ll res = 0;
    for (ll i = 0; i < (1 << N); i++) {
        for (ll u : vc)use[u] = 0;
        ll tmp = 0;
        for (ll j = 0; j < N; j++) {
            if ((i&(1<<j))) {
                tmp += a[vc[j]];
                ll x = vc[j]*vc[j];
                while (x <= n) {
                    use[x]++;
                    x *= vc[j];
                }
            }
        }
        for (int j = 0; j < N;j++) {
            int u=vc[j];
            if (use[u]&&(i&(1<<j)))tmp -= b[u]*use[u];
        }
        res = max(res, tmp);
    }
    return res;
}
int main() {
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)scanf("%lld", &a[i]);
    for (ll i = 1; i <= n; i++)scanf("%lld", &b[i]);
    ans += a[1];
    for (ll i = 2; i <= n; i++) {
        if (vis[i])continue;
        ll x = i;
        cnt++;
        while (x <= n) {
            vc[cnt].push_back(x);
            vis[x] = 1;
            x *= i;
        }
    }
    for (ll i = 1; i <= cnt; i++) {
        ans += solve(vc[i]);
    }
    printf("%lld\n", ans);
    return 0;
}