Codeforces Round #560 (Div. 3) A-F解题报告

现场赛三题，先吐槽下。c意识到贪心太晚，d被卡坑点，e会做了发现时间不够，f我觉得不假啊，补题的时候一直wa。

比赛一开始，读题有点慢，读懂后A题，就开始写。B题在纠结用multiset还是优先队列，其实3分钟就写完了，觉得不会这么简单，稳了一手才交。C题，没有一眼秒就去看了D题，发现D题读不懂，才开始想C。发现不用那么复杂啊，直接贪心。比赛结束20分钟前一直在怼D，被卡坑点了好烦，E题读了下，找到了权值剩5分钟，急着写，最后一分钟放弃了。

A题：写了个小小的模拟 稳了一下上交。

#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn =2e5+5;

int a[maxn];

int main(){
    IO;
    int n,x,y;cin>>n>>x>>y;
    string s;cin>>s;
    forn(i,n) a[i] = s[i]-'0';
    int cnt = 0,ans = 0;
    for(int i=n-1;i>=0;i--){
        cnt++;
        if(cnt==y+1){
            if(!a[i]) ans++;
            break;
        }
    }
    cnt = 0;
    for(int i=n-1;i>=0;i--){
        cnt++;
        if(cnt==y+1){
            continue;
        }
        if(cnt==x+1) break;
        if(a[i]) ans++;
    }
    cout <<ans<<'
';
    return 0;
}

B题：用的multiset

#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

multiset<int>s;

int main(){
    IO;
    int n;cin>>n;
    forn(i,n){
        int x;
        cin>>x;
        s.insert(x);
    }
    int ans = 0,cnt = 1;
    for(auto x:s){
        //cerr<<x<<'
';
        if(cnt<=x){
            cnt++,ans++;
        }
    }
    cout <<ans<<'
';
    return 0;
}

C题贪心

#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn =2e5+5;

int main(){
    IO;
    int n;
    string s;cin>>n>>s;
    int ans = 0,cnt = 1;
    vector<char>a;
    forn(i,n){
        if(!(cnt&1)){
            if(a.back()==s[i]){
                ans++;
                continue;
            }
        }
        cnt++;
        a.push_back(s[i]);
    }
    if(a.size()&1){
        ans++;a.pop_back();
    }
    cout<<ans<<'
';
    if(!a.empty()){
        for(auto x:a) cout<<x;
    }
    cout<<'
';
    return 0;
}

D题再检测因子是否正确时，竟然循环跑到了longlong让我重新定义了复杂度

#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn  = 500;

ll a[maxn];

int main(){
    IO;
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        ll res = 1;
        forn(i,n) cin>>a[i];
        sort(a,a+n);
        forn(i,n){
            res = res/__gcd(a[i],res)*a[i];
        }
        if(n&1) res = a[n/2]*a[n/2];
        if(res>(1ll<<40)){
            cout<<-1<<'
';
            continue;
        }
        ll z = floor(sqrt(res)+0.5);
        int cnt = 0;
        for(ll i=2;i<=z;i++){
            if(res%i==0){
                cnt++;
                if(i*i!=res) cnt++;
            }
        }
        if(cnt!=n) cout<<-1<<'
';
        else cout<<res<<'
';
    }
    return 0;
}

E题：我觉得好题
思路： 我们来看一下a数组被计算的次数，也就是它的贡献。
对于1 2 3 4 5，我们发现，1被计算15次，2被计算24次，3被计算33次，4被计算42次，5被计算51次。
为什么呢？因为每一个位置的贡献和l-r区间有关。只要被包含在那个区间就计算一次。
所以每个位置的权值是i+1n-i
小学奥数学过，一个大的数×一个小的数相比两个数大小接近是更小的
所以a数组大小×权值排序
b数组逆排序
代码：

#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5+5;
const int mod = 998244353;
ll a[maxn],b[maxn],c[maxn];

int main(){
    IO;
    int n;cin>>n;
    forn(i,n){
        cin>>a[i];
        a[i]*=1ll*(i+1)*(n-i);
    }
    forn(i,n) cin>>b[i];
    sort(a,a+n);
    sort(b,b+n);
    reverse(b,b+n);
    ll ans = 0;
    forn(i,n) (ans+=a[i]%mod*b[i]%mod)%=mod;
    
    cout<<ans<<'
';
    return 0;
}

F题：我wa了，我觉得不假啊
—更：没有假，我把输入的顺序读错题了

#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5+5;
int n,m,sum = 0;
pair<int,int>b[maxn];//天数，第几个
bool vis[maxn];
vector<int>a(maxn),aa(maxn),e[maxn<<2];

bool judge(int mid){
    memset(vis,0,sizeof(vis));
    forn(i,mid+1) e[i].clear();
    forn(i,m)if(!vis[b[i].second]&&b[i].first<=mid){
        e[b[i].first].push_back(b[i].second);
        vis[b[i].second] = 1;
    }
    int cnt = 0,t = sum;
    for1(i,mid){
        cnt++;
        if(!e[i].empty()){
            for(auto x:e[i]){
                int z = min(a[x-1],cnt);
                cnt-=z;
                t-=z;
            }
        }
    } 
    return cnt>=t*2;
}

int main(){
    IO;
    cin>>n>>m;
    forn(i,n){
        cin>>a[i];sum+=a[i];
    }
    forn(i,m) cin>>b[i].first>>b[i].second;
    sort(b,b+m);
    reverse(b,b+m);
    int l = 1,r = sum<<1,ans = 0;
    while(l<=r){
        int mid = l+r>>1;
        if(judge(mid)){
            ans = mid;
            r = mid-1;
        }   
        else l = mid+1;
    }
    cout <<ans<<'
';
    return 0;
}