Codeforces Round #727 (Div. 2)

╰半夏微凉° 2022-10-10 09:48 77阅读 0赞

https://codeforc.es/contest/1541

### cf ###

*  
 *  a
 *  b
 *  c
 *  d

#  #

# a #

题意： n 、 x 、 t n、x、 t n、x、t三个数。  
有n个人，每个人工作  t t t。  
第一个人从 0 0 0开始，  
第二人从 x x x开始，  
第三个人从 2 x 2x 2x开始,  
一直到 ( n − 1 ) x (n-1)x (n−1)x开始。  
如果一个人工作结束之前（含结束时）有 y y y人在工作，那么这个人的不满意度是 y y y，求所有的不满意度之和。  
题解：数据给大了，只能 O ( n ) O(n) O(n)了  
注意：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    void solve()
    { 
        ll a,b,c;
        cin >> a >> b >> c;
        a--;
        ll m=c/b;
        if(a<=m)
        { 
            cout << a*(a+1)/2;
        }
        else
            cout << m*(m+1)/2 + (a-m)*m << endl;
    }
    
    
    int main(){ 
        int t; cin >> t;
        while(t--)
            solve();
        return 0;
    }

# b #

有手就行，可惜我的手不太灵活，数据给的范围其实不小，直接暴力是不行的，毕竟是div2，需要预处理。

#include<bits/stdc++.h>
    using namespace std;
    void solve()
    { 
        int n, q; scanf("%d %d",&n, &q);
        char str[n];scanf("%s",&str);
        int sum[n]; sum[0] = 0;
        for(ll i=1;i<=n;i++){ 
            ll j = str[i-1] - 'a' + 1;
            sum[i] = sum[i-1] + j;
        }
        while(q--){ 
            int l, r; scanf("%d %d", &l, &r);
            printf("%d\n",sum[r]-sum[l-1]);  
        }
    
    }
    int main(){ 
        solve();
        return 0;
    }

# c #

（1）  
c题真是交了n遍了  
要用c++17，不要用c++14，数据太大的时候，有差别，看了别人提交的代码大都选择c++17，主要是在ceil ()函数的区别吧  
（2）  
设置vector的时候：  
如果是固定长度，则需要设置成：`vl arr(n)`  
否则：`vl neg`  
如同这题的 n e g neg neg向量，一开始设置成长度为n， `neg.size()` 的值就很离谱。  
（3） `ceil` 如果是c++17，记得设置成`ceil((double)x / (double)y)`  
（4）这道题的思路，在做贪心的时候，需要先排序，不能默认第一个的区间长度是最小

#include<bits/stdc++.h>
    using namespace std;
    
    #define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
    #define pb push_back
    #define all(x) (x).begin(), (x).end()
    
    typedef long long ll;
    typedef vector<ll> vl;
    
    
    
    void solve()
    { 
        ll n, k, x;
    
        cin >> n >> k >> x;
        
        vl arr(n),neg;
    
        for (ll i = 0; i < n; ++i) cin >> arr[i];
        
        sort(all(arr));
    
        for (ll i = 1; i < n; ++i)
        { 
            ll tmp = arr[i] - arr[i-1];
            if(tmp<=x) continue;
            else neg.pb(tmp);
        }
        sort(all(neg));
        for (ll i = 0; i < neg.size(); ++i)
        { 
            if(k==0) break;
            // cel((float)x/(floaty)); 有一个float
            ll c = (ceil)((double)neg[i]/(double)x) - 1;
            //cout<<c<<" ";
            if(k-c<=0)
            { 
                neg[i] -= k*x; // 默认k是大于等于1的，能到这里，当然不是0，否则前面的条件（k==0）就过不了
                k==0;
                break;
            }
            neg[i] -= c*x;
            k-=c;
    
        }
        ll ans = 1;
        
        for (ll i = 0; i < neg.size(); ++i)
        { 
            if(neg[i]>x) ans++;
        }
        printf("%lld", ans);
    }
    
    int main(){ 
        ios;
        solve();
        return 0;
    }

# d #

这题被vector 绕进去了！

首先要熟悉定义：`vector<PII>q(n);`  
明确你要排序的对象（ff 还是ss）：因为sort排序的时候，默认是拿第一个来排序；

题目总的b变成了ss， a变成了ff，开始操作；

排序的基准：容易打折的，换句话就是，买得少也打折，那么这类物品排在前面，否则靠后，再通俗一点就是b小在前， b 大在后。

买对应b大的商品去凑b小的商品，这样容易达到打折的限度。

#include<bits/stdc++.h>
    using namespace std;
    
    #define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
    #define MOD 1000000007
    #define MOD1 998244353
    #define INF 1e18
    #define pb push_back
    #define ppb pop_back
    #define ff first
    #define ss second
    #define PI 3.141592653589793238462
    #define sz(x) ((int)(x).size())
    #define all(x) (x).begin(), (x).end()
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double lld;
    typedef vector<int> vi;
    typedef vector<vi> vvi;
    typedef vector<ll> vl;
    typedef vector<vl> vvl;
    typedef vector<bool> vb;
    typedef pair<ll,ll> PII;
    
    
    ll moduloExp(ll x, ll y){ 
        ll res = 1;
        x%=MOD;
        while(y){  if(y&1) res = (res*x)%MOD;y/=2; x = (x*x)%MOD;}
        return res;
    }
    
    void solve()
    { 
        ll n; cin >> n; 
    
        std::vector<PII> q(n);
    
        for (int i = 0; i < n; ++i) cin >> q[i].ss >> q[i].ff;
        
        sort(all(q));
        ll l = 0, r = n-1;
        ll ans = 0, cnt = 0, num = 0;
        while(l <= r)
        { 
            if(q[l].ff <= cnt){ 
                cnt += q[l].ss;
                ans += q[l].ss;
                l++;
            }else{ 
                num = min(q[r].ss, q[l].ff-cnt); 
                cnt += num; // 商品数
                ans += 2*num; // 价格
                q[r].ss -= num; 排在最后的(难以达到打折的物品数量减少)
                if(!q[r].ss) r--; // 如果减少完了，操作一下
            }
            
        }
        printf("%lld\n", ans);
    
    }
    
    int main(){ 
        ios;
        solve();
        return 0;
    }