CF723div2 vp

小鱼儿 2024-03-26 15:51 46阅读 0赞

**哈哈，我是弱智**

**谢谢你xcpc，让我认识到我就是个什么都不会的dinner**

![cafe464664a699c7748235ab14887301.png][]

[Dashboard - Codeforces Round \#723 (Div. 2) - Codeforces][Dashboard - Codeforces Round _723 _Div. 2_ - Codeforces]

A. Mean Inequality

构造

[Problem - A - Codeforces][]

题意：

给定一个数列，让你重新排列这个数列，使其满足：

![e9a5ab4409d2a1ce9a561acc0920dc45.png][]

思路：

当一个数两边都比这个数大或都小的时候，一定满足，那么直接这样构造就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e2+10;
    
    int n;
    int a[mxn],b[mxn];
    void solve(){
        cin>>n;
        n*=2;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n);
        int idx=0;
        for(int i=1;i<=n;i+=2){
            b[i]=a[++idx];
        }
        for(int i=2;i<=n;i+=2){
            b[i]=a[++idx];
        }
        for(int i=1;i<=n;i++) cout<<b[i]<<" \n"[i==n];
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

B. I Hate 1111

[Problem - B - Codeforces][]

题意：

给定一个数，问你能不能用11，111，1111，....去表示出这个数

思路：

首先有个结论：

两个互质的数a,b,其最大不能表示出来的数是a\*b-a-b

这个结论记住就好了

然后，比这个大的数一定能被表示出来

因此对于小于a\*b-a-b的数，直接去暴力枚举11的倍数和111的倍数就行

Code：

#include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int mxn=2e3+10;
    const int Inf=1e9;
    
    
    
    map<int,int> mp;
    int n;
    void solve(){
        cin>>n;
        if(n>1099||mp.count(n)) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
    void init(){
        for(int i=0;i<=1100;i+=11){
            for(int j=0;j<=1100;j+=111){
                if(i+j<=1100) mp[i+j]=1;
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        init();
        while(__--)solve();return 0;
    }

C1C2  Potions

[Problem - C1 - Codeforces][]

题意：

给定一个序列，在序列里选几个数，使其选的数最多，且选的过程中选的数之和不能是负数

思路：

一开始想的是dp，但是赛后才调出来

状态设计：设dp\[i\]\[j\]表示考虑前i个数，已经选了j个数的最大和，不重不漏

答案就是dp\[n\]\[j\]>=0对应的最大j

状态转移：

考虑枚举决策：选与不选

dp\[i\]\[j\]=max(dp\[i\]\[j\],dp\[i-1\]\[j\])

dp\[i\]\[j\]=max(dp\[i\]\[j\],dp\[i-1\]\[j-1\]+a\[i\])

关于这个状态设计，一开始想的是考虑前i个数，和为j的选的个数

但是注意到a\[i\]会到1e9，开不下

**所以这里可以总结一个技巧，就是如果dp参数数据范围比较小的话，可以把dp值和dp参数更换一下**

**然后再去考虑设计状态**

然后在状态转移的过程中，我写的代码非常低能

很喜欢卷b说的话：

![ebde1ee8b719984ed135076bac5f430c.png][]

![106ea3045fc9b58d3d16c2d1a7f18c43.png][]

![be1dd12241296224c1ea6164836134f0.png][]

好骂.jpg

确实该喷喷了

还有一个问题就是初始化：

当前选的数的个数为0，dp值也应该为0

因此在考虑初始化的时候，考虑i==0的时候，也要考虑j==0的时候

Code：

#include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int mxn=2e3+10;
    const int Inf=1e9;
    int n;
    int a[mxn],dp[mxn][mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++) dp[i][j]=-Inf;
        }
        for(int i=0;i<=n;i++) dp[i][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                if(dp[i-1][j]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j]);
                if(dp[i-1][j-1]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+a[i]);
            }
        }
        for(int j=n;j>=0;j--){
            if(dp[n][j]>=0){
                cout<<j<<'\n';
                return;
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

但是这样只能过C1

C2得用反悔贪心

先把能选的全都选了，直到加上这个数之后和为负数，此时把前面选的最小的负数后悔掉，然后改成选当前这个数

Code：

#include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int mxn=2e3+10;
    const int Inf=1e9;
    
    
    priority_queue<int,vector<int>,greater<int> > q;
    int n,x;
    void solve(){
        cin>>n;
        int sum=0,ans=0;
        for(int i=1;i<=n;i++){
            cin>>x;
            if(x>=0){
                sum+=x;
                ans++;
                continue;
            }else{
                if(sum+x>=0){
                    q.push(x);
                    sum+=x;
                    ans++;
                    continue;
                }else{
                    if(!q.empty()&&q.top()<x){
                        sum-=q.top();
                        sum+=x;
                        q.pop();
                        q.push(x);
                    }
                }
            }
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[cafe464664a699c7748235ab14887301.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/5a82391f2f4c4e16bc736f76b3863035.png
[Dashboard - Codeforces Round _723 _Div. 2_ - Codeforces]: https://codeforces.com/contest/1526
[Problem - A - Codeforces]: https://codeforces.com/contest/1526/problem/A
[e9a5ab4409d2a1ce9a561acc0920dc45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/00b6d1cdcb60412f95c67f1fcd8c5f1b.png
[Problem - B - Codeforces]: https://codeforces.com/contest/1526/problem/B
[Problem - C1 - Codeforces]: https://codeforces.com/contest/1526/problem/C1
[ebde1ee8b719984ed135076bac5f430c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6262fcfe3c2a4072aaadaaa9bf7b0af3.png
[106ea3045fc9b58d3d16c2d1a7f18c43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c8d7d6c1cd894eb3bac84c42033da317.png
[be1dd12241296224c1ea6164836134f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/2e01b6b630c14d5ba409b2bb16d6047c.png