Educational Codeforces Round 80 解题目报告

ACM 阅读量

上分是不可能上分的了， 这辈子是不可能上分了，只能靠舔舔超哥，来维持我的分数，以及我卑微的补题。

A.Deadline

题意

有一个工作时间为 $n$ 的任务，但是你却需要花费 $d$ 天来完成，但是你可以优化你的工作，问你能否找到一个 $x$ ,使得 $x+\lceil \dfrac {d}{x+1}\rceil \leq n$ 成立

题解

直接化简这个不等式，得到 $x^{2}+\left( 1-n\right) x+\left( d-n\right) \leq 0$ 成立，然后直接二次函数的最大值小于等于 $0$ 成立即可，即 $4d-1-n^{2}-2*n\leq 0$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 7;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> P;
string s[MAXN];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T;
    cin >> T;
    while(T--){
        unsigned long long n, d;
        long long ans = 0;
        cin >> n >> d;
        ans = 4*d - 1 - n*n - 2*n;
        if(ans <= 0)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;

    }
    return 0;
}

B.Yet Another Meme Problem

题意

给你一个 $A$， 一个 $B$，问你能在这个范围内找到多少个 $a*b + a + b = conc(a,b)$ , $conc(a, b)$ 表示把 $a，b$ 直接连接起来

题解

打表找规 (一开始表打错了，死活不对) ，可以发现，这样的数只能是 $9$, $99$,$999$….这种，所以直接判断 $B$ 内 $9$ 的个数，在乘上 $A$ 的值就可以了

代码

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 3e5 + 7;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T;
    cin >> T;
    while(T--){
        ll a, b, cnt = 0,tb = 0;
        cin >> a >> b;
        while(tb <= b){
            tb = ll(tb * 10 + 9);
            if(tb > b)
                break;
            cnt++;
        }
        cout << cnt * a << endl;
    }
    return 0;
}

C.Two Arrays

题意

给你一个 $n$， 一个 $m$，让你构造两个序列 $a_i$ 和 $b_i$ 满足以下条件

  • 两个数组的长度都等于 $m$；
  • 每个数组的每个元素都是 $1$ 到 $n$ (含)之间的整数；
  • 对于数组中的每个数字保证 $a_i \leq b_i$
  • 数组 $a_i$ 按非降序排序；
  • 数组 $b_i$ 按非升序排序。

题解

(一开始，我还以为是打表找规律，害，还是太菜)

两种解法:

  1. dp
  2. 组合数学 （隔板法）

    解法1：

    $dp[i][j]$ 表示有 $j$ 个数每个数的范围为 $1～i$ 时的非递减排列种数，因为 $n$ 和 $m$ 的数据范围也不大，用记忆化搜索很快可以得出每一个值。

再来看满足条件时的 $(a,b)$，$a$ 为非递减序列，$b$ 为非递增序列，所以 $b$ 的最后一个数大于等于 $a$ 的最后一个数是充要条件，因此我们只需要遍历 $a$ 最后一个数即可得出答案，例如当 $a$ 的最后一个数为 $3$ 的时候，这部分的答案就应该是 $(dp[3][m]−dp[2][m])∗dp[n−3+1])$ ，括号里是 $a$ 的种数（利用容斥原理），括号外是 $b$ ，因为 $b$ 的范围是 $3～n$ ，它的排列种数与 $1～(n−3+1)$ 的排列种数相同。

注意取模！

代码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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 1e4 + 7;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
typedef pair<int,int> P;
long long dp[1005][15];
 
ll dfs(ll n, ll m){
    if(dp[n][m])
        return dp[n][m];
    if(m == 1){
        dp[n][m] = n;
        return dp[n][m];
    }
    ll ans = 0;
    for(ll i = 1;i <= n;i++)
        ans = (ans + dfs(i, m-1)) % MOD;
    dp[n][m] = (ans + MOD) % MOD;
    return dp[n][m];
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    ll n, m;
    cin >> n >> m;
    long long ans = 0;
    memset(dp,0,sizeof(dp));
    for(ll i = 1;i <= n;i++)
        ans=(ans+(dfs(i,m)-dfs(i-1,m))*dfs(n-i+1,m)%MOD+MOD)%MOD;
        //ans = (ans + (dfs(i, m)- dfs(i-1, m))) % MOD * dfs(n - i + 1, m) % MOD;
    cout << ans << endl;
    return 0;
}

解法2

由题目可知， $a$ 为非递减序列，$b$ 为非递增序列，那么就是找一个取值范围为 $1～n$ 的长度为 $2m$ 的非降序列，的数量。那么问题转化，假设对于每个数字取了 $x_1$ , $x_2$,…..$x_n$ 次，那么 $x_1$ + $x_2$ + ….. + $x_n$ = $2*m$，$x_i$ 可以为空，那么此时就可以套 隔板法的模型了。最后就是求 $C^{n-1}_{2m+n-1}$,

代码

随便找求组合数的板子都能过

D.Minimax Problem

待补

题意

题解

代码

1
2


E.Messenger Simulator

题意

给你一个消息队列，每次给你一个消息序号，会把该消息排放至序列首位，其他元素依次向后，问经过 $m$ 次修改后，每个消息最远到达的位置，和最近到达的位置分别是多少

题解

维护一个，记录这个序列每个数字的位置，把这个序列的前 $m$ 个位置空出来，用 $BIT$ 去维护每个数字前面有多少个数字即可

代码

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 3e6 + 7;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int tree[MAXN];
int mn[MAXN], mx[MAXN], a[MAXN], pos[MAXN];
int lowbit(int x){
    return x & (-x);
}
 
void Update(int pos,int val){
    for(int i = pos;i < MAXN;i += lowbit(i))
        tree[i] += val;
}
 
int get(int x){
    int ans = 0;
    for(int i = x;i > 0;i -= lowbit(i))
        ans += tree[i];
    return ans;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        mn[i] = mx[i] = i;
        pos[i] = m+i;
        Update(m+i, 1);
    }
    for(int i = 1;i <= m;i++){
    	cin >> a[i];
        mn[a[i]] = 1;
        mx[a[i]] = max(mx[a[i]],get(pos[a[i]]));
        Update(pos[a[i]], -1);
        pos[a[i]] = m - i + 1;
        Update(pos[a[i]], 1);
    }
    for(int i = 1;i <= n;i++){
        mx[i] = max(mx[i],get(pos[i]));
    }
    for(int i = 1;i <= n;i++)
        cout << mn[i] << " " << mx[i] <<endl;
    return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2018 - 2020 Never Give Up! All Rights Reserved.

访客数 : | 访问量 :