2018 CCPC 网络选拔赛（部分题解）

发表于
2018中国大学生程序设计竞赛

Buy and Resell

解题思路

这道题和 Codeforces 867E基本相同：Codeforces867E题解
但是这道题要求输出最少买卖操作数，其实就是让我们尽可能地多反悔，由分析，第一次弹出是反悔，第二次弹出是真的买卖，于是优先队列里加一个元素个数的信息，把元素个数大的放在前面（这样下一次弹出时就是反悔操作了）。

Code

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
# include<bits/stdc++.h>

using namespace std;

typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pll;

# define mp make_pair
# define pb push_back
# define fir first
# define sec second

# define fo0(i,a,b) for(int i=(a);i<(b);i++)
# define fo1(i,a,b) for(int i=(a);i<=(b);i++)
# define fd0(i,a,b) for(int i=(a);i>(b);i--)
# define fd1(i,a,b) for(int i=(a);i>=(b);i--)
# define mset(a,b) memset(a,(b),sizeof(a))

# define max(a,b) (a > b ? a : b)
# define min(a,b) (a < b ? a : b)
# define abs(a) (a < 0 ? -a : a)
# define fabs(a) (a < 0 ? -a : 0)

template<typename T> inline void in(T &x){
	x = 0; int fl = 1; char ch = getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=fl;
}
template<typename T> void out(T x){if(x<0){putchar('-');x=-x;}if(x/10)out(x/10);putchar(x%10+'0');}
template<typename T> inline void outln(T x){out(x);putchar(10);}
template<typename T> inline void outsp(T x){out(x);putchar(' ');}
template<typename T> inline T gcd(T a, T b){T t;if(a>b){while(b){t=b;b=a%b;a=t;}return a;}else{while(a){t=a;a=b%a;b=t;}return b;}}
template<typename T> inline T lcm(T a, T b){return a/gcd(a,b)*b;}

const int N = 100005;

int CASES, n, p;
LL ans, tim;

struct Node{
	int p, num;
	bool operator < (const Node &a) const{
		if(p == a.p)	return num > a.num;
		return p < a.p;
	}
};
multiset<Node> s;

inline void init(){
	ans = tim = 0;
	s.clear();
}

int main(){
	in(CASES);
	while(CASES--){
		init();
		in(n);
		fo1(i, 1, n){
			in(p);
			Node cur = *s.begin();
			if(s.empty() || p <= cur.p)
				s.insert((Node){p, 1});
			else{
				ans += 1ll * p - cur.p;
				if(cur.num == 1){
					tim++;
					s.erase(s.begin());
				}
				else{
					s.erase(s.begin());
					cur.num--;
					s.insert(cur);
				}
				s.insert((Node){p, 2});
			}
		}
		outsp(ans);
		outln(tim*2);
	}
	return 0;
}

Dream ( hdu6440 )

解题思路

定义 $a+b$ 为 $(a+b) \mod p$
定义 $a\cdot b$ 为 $a\cdot b \mod p$

Code

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;

typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pll;

# define mp make_pair
# define pb push_back
# define fir first
# define sec second

# define fo0(i,a,b) for(int i=(a);i<(b);i++)
# define fo1(i,a,b) for(int i=(a);i<=(b);i++)
# define fd0(i,a,b) for(int i=(a);i>(b);i--)
# define fd1(i,a,b) for(int i=(a);i>=(b);i--)
# define mset(a,b) memset(a,(b),sizeof(a))

# define max(a,b) (a > b ? a : b)
# define min(a,b) (a < b ? a : b)
# define abs(a) (a < 0 ? -a : a)
# define fabs(a) (a < 0 ? -a : 0)

template<typename T> inline void in(T &x){
	x = 0; int fl = 1; char ch = getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=fl;
}
template<typename T> void out(T x){if(x<0){putchar('-');x=-x;}if(x/10)out(x/10);putchar(x%10+'0');}
template<typename T> inline void outln(T x){out(x);putchar(10);}
template<typename T> inline void outsp(T x){out(x);putchar(' ');}
template<typename T> inline T gcd(T a, T b){T t;if(a>b){while(b){t=b;b=a%b;a=t;}return a;}else{while(a){t=a;a=b%a;b=t;}return b;}}
template<typename T> inline T lcm(T a, T b){return a/gcd(a,b)*b;}

int T, p;

int main(){
	in(T);
	while(T--){
		in(p);
		fo0(i, 0, p){
			fo0(j, 0, p)
				outsp((i + j) % p);
			putchar(10);
		}
		fo0(i, 0, p){
			fo0(j, 0, p)
				outsp((i * j) % p);
			putchar(10);
		}
	}
	return 0;
}

Find Integer ( hdu6441 )

解题思路

  • $n>2$：由费马大定理，$n>2$ 时方程无整数解。
  • $n=0$：$1+1=1$，不可能
  • $n=1$：略
  • $n=2$：$a^2=c^2-b^2=(c-b)(c+b)$
    当 $a$ 为奇数时，令 $c-b=1,c+b=a^2$；当 $a$ 为偶数时，令 $c-b=2,c+b=a^2/2$

Code

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;

typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pll;

# define mp make_pair
# define pb push_back
# define fir first
# define sec second

# define fo0(i,a,b) for(int i=(a);i<(b);i++)
# define fo1(i,a,b) for(int i=(a);i<=(b);i++)
# define fd0(i,a,b) for(int i=(a);i>(b);i--)
# define fd1(i,a,b) for(int i=(a);i>=(b);i--)
# define mset(a,b) memset(a,(b),sizeof(a))

# define max(a,b) (a > b ? a : b)
# define min(a,b) (a < b ? a : b)
# define abs(a) (a < 0 ? -a : a)
# define fabs(a) (a < 0 ? -a : 0)

template<typename T> inline void in(T &x){
    x = 0; int fl = 1; char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    x*=fl;
}
template<typename T> void out(T x){if(x<0){putchar('-');x=-x;}if(x/10)out(x/10);putchar(x%10+'0');}
template<typename T> inline void outln(T x){out(x);putchar(10);}
template<typename T> inline void outsp(T x){out(x);putchar(' ');}
template<typename T> inline T gcd(T a, T b){T t;if(a>b){while(b){t=b;b=a%b;a=t;}return a;}else{while(a){t=a;a=b%a;b=t;}return b;}}
template<typename T> inline T lcm(T a, T b){return a/gcd(a,b)*b;}

int CASES;
LL n, a;

int main(){
    in(CASES);
    while(CASES--){
        in(n); in(a);
        if(n > 2 || n == 0)    puts("-1 -1");
        else if(n == 1){
            outsp(1);
            outln(a+1);
            continue;
        }
        else if(n == 2){
            if(a % 2){
                outsp((a*a-1)/2);
                outln((a*a+1)/2);
            }
            else{
                outsp(a*a/4-1);
                outln(a*a/4+1);
            }
        }
    }
    return 0;
}

Tree and Permutation ( hdu6446 )

解题思路

单独计算每一条边的贡献：

  1. 设这条边一侧有 $a$ 个节点，另一侧有 $b$ 个节点，那么从两侧各选出一个节点连起来时就会经过该边一次，共有 $C_a^1\times C_b^1\times A_2^2 = 2\cdot a\cdot b$ 种选法。（注意顺序不同也要算进去）
  2. 将选出来的两个点绑在一起与其他所有点做全排列求得这两个点一起出现的次数，共 $A_{n-1}^{n-1} = (n-1)!$ 次。

故该条边对答案的贡献为 $len\cdot 2\cdot a\cdot b\cdot (n-1)!$
最后把所有边的贡献加起来即可。

Code

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# include<bits/stdc++.h>

using namespace std;

typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pll;

# define mp make_pair
# define pb push_back
# define fir first
# define sec second

# define fo0(i,a,b) for(int i=(a);i<(b);i++)
# define fo1(i,a,b) for(int i=(a);i<=(b);i++)
# define fd0(i,a,b) for(int i=(a);i>(b);i--)
# define fd1(i,a,b) for(int i=(a);i>=(b);i--)
# define mset(a,b) memset(a,(b),sizeof(a))

# define max(a,b) (a > b ? a : b)
# define min(a,b) (a < b ? a : b)
# define abs(a) (a < 0 ? -a : a)
# define fabs(a) (a < 0 ? -a : 0)

template<typename T> inline void in(T &x){
	x = 0; int fl = 1; char ch = getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=fl;
}
template<typename T> void out(T x){if(x<0){putchar('-');x=-x;}if(x/10)out(x/10);putchar(x%10+'0');}
template<typename T> inline void outln(T x){out(x);putchar(10);}
template<typename T> inline void outsp(T x){out(x);putchar(' ');}
template<typename T> inline T gcd(T a, T b){T t;if(a>b){while(b){t=b;b=a%b;a=t;}return a;}else{while(a){t=a;a=b%a;b=t;}return b;}}
template<typename T> inline T lcm(T a, T b){return a/gcd(a,b)*b;}

const int N = 100005;
const LL MOD = 1e9+7;

int n, u, v, p;
LL ans, fac[N];

struct Edge{
	int nxt, to, len;
}edge[N<<1];
int head[N], edgeNum = 0;
inline void addEdge(int from, int to, int len){
	edge[++edgeNum] = (Edge){head[from], to, len};
	head[from] = edgeNum;
}

int size[N], a[N<<1], b[N<<1];
void dfs(int x, int f){
	size[x] = 1;
	for(int i = head[x]; i; i = edge[i].nxt){
		if(edge[i].to == f)	continue;
		dfs(edge[i].to, x);
		size[x] += (a[i] = size[edge[i].to]);
		b[i] = n - size[edge[i].to];
	}
}

void init(){
	edgeNum = 0;
	mset(head, 0);
	mset(edge, 0);
	mset(size, 0);
	mset(a, 0);
	mset(b, 0);
	ans = 0;
}

int main(){
	fac[0] = 1; fo1(i, 1, 100000)	fac[i] = fac[i-1] * i % MOD; 
	while(scanf("%d", &n) != EOF){
		init();
		fo0(i, 1, n){
			in(u); in(v); in(p);
			addEdge(u, v, p);
			addEdge(v, u, p);
		}
		dfs(1, 0);
		for(int i = 1; i <= edgeNum; i += 2)
			(ans += 1ll * edge[i].len * a[i] % MOD * b[i] * 2 % MOD) %= MOD;
		ans = (ans * fac[n-1]) % MOD;
		outln(ans);
	}
	return 0;
}

YJJ’s Salesman ( hdu6447 )

解题思路

对于两个点 $A$ 和 $B$，只要 $B$ 在 $A$ 的严格右上方，那么从 $A$ 走到 $B$ 就可以得到 $v_B$ 的收益。所以先以 $x$ 为第一关键字从小到大、$y$ 为第二关键字从大到小排序（这样可以保证dp时转移合法），然后可以dp。
设 $dp[i]$ 表示到走到第 $i$ 个点的最大收益，那么转移方程为：
$$dp[i] = \max\limits_{j<i 且 y[j]<y[i]}{dp[j]} + v[i]$$
所以可以用一个线段树来存dp值，线段树下标为纵坐标（这是一颗纵坐标的值域线段树），要先对纵坐标离散化一下。
然后dp转移即变成了区间查询最大值和单点修改。
时间复杂度：$O(n\log n)$

Code

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
# include<cstdio>
# include<cstring>
# include<algorithm>

using namespace std;

template<typename T> inline void read(T &x){
    x=0;int fl=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    x*=fl;
}

const int N = 100010;

int CASES, n, t[N], ans;

struct Node{
    int x, y, v;
}a[N];
bool cmp(Node a, Node b){
    if(a.x == b.x)    return a.y > b.y;
    return a.x < b.x;
}
inline void disc(){
    for(int i = 1; i <= n; i++)    t[i] = a[i].y;
    sort(t+1, t+n+1);
    int len = unique(t+1, t+n+1) - (t+1);
    for(int i = 1; i <= n; i++)
        a[i].y = lower_bound(t+1, t+n+1, a[i].y) - t + 1;
}

struct SegmentTree{
# define lid id<<1
# define rid id<<1|1
# define mid ((tr[id].l + tr[id].r) >> 1)
# define len(id) (tr[id].r - tr[id].l + 1)
    struct segTree{
        int l, r, mx;
        void init(){ l = r = mx = 0; }
    }tr[N<<2];
    inline void pushup(int id){
        tr[id].mx = max(tr[lid].mx, tr[rid].mx);
    }
    void build(int id, int l, int r){
        tr[id].init();
        tr[id].l = l, tr[id].r = r;
        if(tr[id].l == tr[id].r)    return;
        build(lid, l, mid);
        build(rid, mid+1, r);
        pushup(id);
    }
    int query(int id, int l, int r){
        if(tr[id].l == l && tr[id].r == r)
            return tr[id].mx;
        if(r <= mid)    return query(lid, l, r);
        else if(l > mid)    return query(rid, l, r);
        else    return max(query(lid, l, mid), query(rid, mid+1, r));
    }
    void set(int id, int pos, int v){
        if(tr[id].l == tr[id].r){
            tr[id].mx = max(tr[id].mx, v);
            return;
        }
        if(pos <= mid)    set(lid, pos, v);
        else    set(rid, pos, v);
        pushup(id);
    }
}seg;

inline void init(){
    memset(a, 0, sizeof a);
    memset(t, 0, sizeof t);
    ans = 0;
}

int main(){
    read(CASES);
    while(CASES--){
        init();
        read(n);
        for(int i = 1; i <= n; i++)
            read(a[i].x), read(a[i].y), read(a[i].v);
        a[n+1] = (Node){0, 0, 0};
        a[n+2] = (Node){1e9, 1e9, 0};
        n += 2;
        sort(a+1, a+n+1, cmp);
        disc();
        seg.build(1, 1, n);
        for(int i = 1; i <= n; i++){
            int t = seg.query(1, 1, a[i].y-1) + a[i].v;
            seg.set(1, a[i].y, t);
            ans = max(ans, t);
        }
        printf("%d\n", ans);
    }
    return 0;
}