Educational Codeforces Round 80 解题目报告

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

A.Deadline

题意

有一个工作时间为 $n$ 的任务,但是你却需要花费 $d$ 天来完成,但是你可以优化你的工作,问你能否找到一个 $x$ ,使得 $x+\lceil \dfrac {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$

代码

#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$ 的值就可以了

代码

#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

#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^_{2m+n-1}$,

代码

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

D.Minimax Problem

待补

题意

题解

代码


E.Messenger Simulator

题意

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

题解

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

代码

#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;
}