2016 ACM-ICPC,CHINA-Final shanghai

字数统计: 1.6k字   |   阅读时长: 8分
训练题解
solved A B C D E F G H I J K L
solved O - - Ø Ø - - - - - - O
  • O：比赛时通过
  • Ø：赛后通过
  • !：比赛时尝试了未通过
  • ·：比赛时未尝试

REPLY

lllllan:

  • 开什么题什么题不会，感觉需要停下来好好学一下了。

Sstee1XD:

  • 这场好自闭，一直让队友开新题把队友心态搞炸了，对不起。

比赛链接

A - Number Theory Problem【签到】

solved by Tryna. 0:05(+)

题意： 给出一个N，计算小于 2N2^N 的正整数中有多少个 2k−12^k - 1能够被7整除

题解: 因为 23−12^3 - 1 是 7， 所以当k为3的倍数时，2k−12^k - 1能被7整除，所以N/3N / 3就是答案了。

AC代码 
1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
int t, n; 
int main () {
	scanf("%d", &t);
	for(int k = 1; k <= t; k++){
		scanf("%d", &n);
		printf("Case #%d: %d\n", k, n / 3);
	}
    return 0;
}

D - Ice Cream Tower

Solved by Sstee1XD. (-)

题意： 给你NN个冰激凌球的大小，问最多能叠几个拥有kk个冰激凌球，下一层比上一层大一倍及以上的冰激凌。

题解： 没有比较好的贪心策略，我们考虑二分答案，发现验证答案的正确性的贪心策略是比较明显的。

AC代码 
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
#include<bits/stdc++.h>
using namespace std;

#define sit multiset<ll>::iterator
#define endl "\n"
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {	cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
cout << arg << ' '; err(args...);}

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5 + 7;
int n, k, cas;
ll a[maxn], b[maxn];
void run () {
    int ans = 0;
	scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    sort(a + 1, a + 1 + n);
    int l = 1, r = n / k, mid;
    while (l <= r) {
        mid = l + r >> 1;
        int now = 1, cnt = 0;
        for (int i = 1; i <= mid; ++i) b[i] = 0;
        for (int i = 1; i <= n; ++i) {
            if (b[now] * 2 <= a[i]) {
                b[now++] = a[i];
            }
            if (now > mid) now = 1, cnt++;
            if (cnt == k) break;
        }
        if (cnt ^ k) r = mid - 1;
        else l = mid + 1, ans = mid;
    }
	printf("Case #%d: ", ++cas);
	printf("%d\n", ans);
}

int main () {
	int _T;
	scanf("%d", &_T);
	while (_T--) run();
    return 0;
}

E - Bet

Solved by Sstee1XD. (-)

题意： 给你NN支队伍的赔率，问你最多能买几支队伍，使得你买的队伍中
任意一支队伍取胜，你皆能获利。

题解： 我们假设本金为11，对第i只球队下注金额为pip_i，它的赔率是biai\frac{b_i}{a_i}，获利的条件是pi+pi∗biai>1p_i + p_i * \frac{b_i}{a_i} > 1，即pi>ai+biaip_i > \frac{a_i + b_i}{a_i}。我们算出后面的结果后从小到大排序，然后一直加到 ≥1\geq 1就好了。C++11会有精度问题。

AC代码 
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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define double long double
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err() { cout << endl; }
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);
}
ll gcd(ll a, ll b) {
    return a == 0? b : gcd(b % a, a);
}
const int maxn = 1e2 + 7;
int n;
double a[maxn], b[maxn], c[maxn];
double t, tt;
ll d, di;
int cas;
void solve() {
    scanf("%d", &n);
    d = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%Lf:%Lf", &t, &tt);
        a[i] = t;
        b[i] = tt;
        c[i] = a[i] / (a[i] + b[i]);
    }
    sort(c + 1, c + 1 + n);
    double now = 0;
    printf("Case #%d: ", ++cas);
    for (int i = 1; i <= n; ++i) {
        now += c[i];
        if (now >= 1) {
            printf("%d\n", i - 1);
            return;
        }
        if (i == n) printf("%d\n", n);
    }
}

int main() {
    int _T;
    scanf("%d", &_T);
    while(_T--) solve();
}

H - Great Cells

solved by Tryna. (-)

题意: 一个矩阵中的一个格子如果满足它严格大于它所在的行和列，那么我们称这个格子为great cell， AgA_{g}代表有g个 great cell 时的方案数。给出一个n行m列的矩阵和一个数k，k表示每个格子可以从[1,k]\left [1 ,k\right ]中选取一个数放进当前格子。要我们计算这个公式的结果 $$\sum_{g=0}^{NM} (g + 1) · A_g mod (10^9 + 7)$$

题解： 刚开始被这个公式陷进去了，一直在想AgA_g如何计数，后来发现完全数不过来，赛后看了dalao的博客，才发现一开始就像错了，我的思维太局限了。上面那个公式可以拆分成$$\sum_{g=0}^{NM} g · A_g mod (10^9 + 7) + \sum_{g=0}^{NM} A_g mod(10^9 + 10)$$
后面那个公式代表所有的AgA_g矩阵数量，其实也就是所有矩阵的数量，所以后面那个公式就是KNMK^{NM}
对于前面的公式，AgA_{g}代表有g个 great cell 时的方案数，g代表当前的 great cell 的个数， 所以对于当前这种方案AgA_g，我如果给它乘上一个g，那么代表每个 great cell 都分到了1，也就是当前这种方案下的g个格子对答案的贡献都为1。所以$$\sum_{g=0}^{NM} g · A_g mod (10^9 + 7)$$对于这个公式就是所有格子作为great cell的情况总和。
所以可以转化一下求法，从矩阵中选取一个格子，计算这个格子作为great cell的总数，只需要保证这行这列严格小于当前格子就行，所有受限制的格子有N−1+M−1N - 1 + M - 1个，其余的(N−1)∗(M−1)(N-1)*(M-1)个格子是不受限制的，所以我们就能把题目给的公式化简为下列公式$$NM\sum_{i = 1}^{K} (i - 1)^{N + M - 2} * K^{(N - 1) * (M - 1)} + K^{NM}$$

AC代码 
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
#include<bits/stdc++.h>
using namespace std;    
#define ll long long
const int maxn = 110;
const int mod = 1e9 + 7;
int quick_power(ll n, ll k){
	int ans=1;
	while(k){
		if(k&1){
			ans=(ans*n)%mod;
		}
		n=n*n%mod;
		k>>=1;
	}
	return ans%mod;
}
int t;
ll n, m, k;
int main() {
	scanf("%d", &t);
    for(int case1 = 1; case1 <= t; case1++){
        scanf("%lld %lld %lld", &n, &m, &k);
        if(n == 1 && m == 1){
            printf("Case #%d: %lld\n", case1, k);
            continue;
        }
        ll ans = quick_power(k, n * m);
        ll cnt = 0;
        for(int i = 1; i <= k; i++){
            cnt = (cnt + quick_power(i - 1, n + m - 2)) % mod;
        }
        cnt = cnt * n % mod * m % mod * quick_power(k, (n - 1) * (m - 1)) % mod;
        ans = (ans + cnt) % mod;
 
        printf("Case #%d: %lld\n", case1, ans);
    }
	return 0;
}
文章目录
  1. A - Number Theory Problem【签到】
  2. D - Ice Cream Tower
  3. E - Bet
  4. H - Great Cells
|