当前位置:   article > 正文

Codeforces Educational Round 95 解题报告_codeforces education round95

codeforces education round95
Codeforces Educational Round 95 解题报告

A. 题解:

​ 计算出所需要的棍子数量 sticks = k * ( y + 1),然后答案是
( s t i c k − 1 ) / ( x − 1 ) + ( ( s t i c k − 1 ) m o d    ( x − 1 ) = = 0 ? 1 : 0 ) + k (stick - 1)/(x - 1) + ((stick-1)\mod (x-1) == 0 ? 1 : 0) + k (stick1)/(x1)+((stick1)mod(x1)==0?1:0)+k
B. 题解:

​ 将unlocked的元素进行从大到小排序放置即可。

C. 题解:

​ 简单DP:

​ 假定dp的i,j代表当前第i个怪物已经被打死的情况下,第j个人操作时候的状态(j只有0,1)

​ 那么对于friends来说,其可以推导出
d p [ i + 2 ] [ j + 1 ] , d p [ i + 1 ] [ j + 1 ] 的 状 态 dp[i+2][j+1],dp[i+1][j+1]的状态 dp[i+2][j+1],dp[i+1][j+1]
同理对于I来说也是如此,只是要注意"我"不能进行先手打败怪物,所以要加一定的限制,然后输出即可
m i n ( d p [ n ] [ 0 ] , d p [ n ] [ 1 ] ) min(dp[n][0],dp[n][1]) min(dp[n][0],dp[n][1])

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int a[maxn];
int dp[maxn][2];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;  cin >> T;
    while(T--){
        int n;  cin >> n;
        for(int i = 1; i <= n; ++i){
            cin >>a[i];
        }
        memset(dp,0x3f,sizeof(dp));
        dp[0][0] = 0;
        for(int i = 0; i <= n; ++i){
            for(int j = 0; j < 2; ++j){
                if(j==0){
                    if(i+2 <= n)
                        dp[i+2][j+1] = min(dp[i+2][j+1],dp[i][j] + a[i+1]+a[i+2]);
                    if(i+1 <= n)
                        dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j] + a[i+1]);
                }
                else{
                    if(i >= 1){
                        if(i+2 <= n)
                            dp[i+2][j-1] = min(dp[i+2][j-1],dp[i][j]);
                        if(i+1 <= n)
                            dp[i+1][j-1] = min(dp[i+1][j-1],dp[i][j]);
                    }
                }
            }
        }cout << min(dp[n][0],dp[n][1]) << endl;
    }
    return 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
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

D 题解:

​ 当时没想出来,考虑的比较复杂,后面看题解才恍然大悟,还是自己太菜了…

​ 因为每次move可以移动任意数量堆的垃圾,那么应该从两端往内压缩是最优的,因此实际上如果我们确定了最终选择的两个坐标点x,y

​ 假定最大的坐标点为b,最小的坐标点为a
a n s = x b − x a − ( x y − x x ) ans= x_b - x_a - (x_y - x_ x) ans=xbxa(xyxx)
​ 显然对于每次query来说
x b − x a x_b-x_a xbxa
​ 应该是恒定的,因此需要去最大化后者,故建立差分,用数据结构维护即可.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
set<int> st1;    multiset<int> st2;
void add(int x){
    auto iter = st1.lower_bound(x);
    if(iter!=st1.begin())   st2.insert(x - *prev(iter));
    if(iter!=st1.end())   st2.insert(*iter - x);
    if(iter!= st1.begin() && iter!=st1.end()){
        st2.erase(st2.find(*iter - *prev(iter)));
    }
    st1.insert(x);
}
void del(int x){
    st1.erase(x);
    auto iter = st1.lower_bound(x);
    if(iter!=st1.begin())   st2.erase(st2.find(x - *prev(iter)));
    if(iter!=st1.end())   st2.erase(st2.find(*iter - x));
    if(iter!=st1.end() && iter!=st1.begin()){
        st2.insert(*iter - *prev(iter));
    }
}
typedef long long ll;
ll get_ans(){
    if(st1.size() <= 2) return 0;
    return *st1.rbegin() - *st1.begin() - *st2.rbegin();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n,q;    cin >> n >> q;
 
    for(int i = 0; i < n; ++i){
        int x;  cin >> x;
        add(x);
    }
    cout <<get_ans() <<endl;
    for(int i = 0; i < q;++i){
        int t,x;    cin >> t >> x;
        if(t == 0){
            del(x);
        }else add(x);
    cout <<get_ans() <<endl;
    }
    return 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
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

其他题目待补

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/1003955
推荐阅读
相关标签
  

闽ICP备14008679号