AC源Day2模拟赛复盘

· · 个人记录

单击此处添加标题

T1（30 WA）

签到题，套公式+快速幂可解（不知道为什么写了快速幂但只有30分 后记：~其实是公式打错了~，下面的是满分代码）

#include<bits/stdc++.h>
#define mod 200907
#define int unsigned long long
using namespace std;

int a,b,c,x,m,k;
int ksm(int u,int p){
    if(p==0) return 1;
    int tmp=u,cnt=1;
    while(p>0){
        if(p%2){
            cnt*=tmp;
            cnt%=mod;
        }
        p>>=1;
        tmp*=tmp;
        tmp%=mod;
    }
    return cnt;
}

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("seq.in","r",stdin);
    // freopen("seq.out","w",stdout);

    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c>>x;
        if(b-a==c-b){
            k=b-a;
            k%=mod,a%=mod,x%=mod;
            // cout<<k<<" "<<a<<" "<<x<<"\n";
            cout<<(a+(k*(x-1))%mod)%mod<<"\n";
        }
        else{
            k=b/a;
            a%=mod,k%=mod;
            // cout<<k<<" "<<a<<" "<<x<<"\n";
            cout<<(a*ksm(k,x-1))%mod<<"\n";

        }
    }
    return 0;
}

T2（100 AC）

对偶数u进行分割，最后会得到lowbit(u)份，O(n)就可以拆完（我暴力拆然后线段树查询过的 ~然而在洛谷评测时MLE了~）

#include<bits/stdc++.h>
#define int unsigned long long
#define N 200005
using namespace std;

int n,m,cnt=0,sum[4*N];
struct www{
    int num,cnt;
} a[N];
void upd(int u){
    sum[u]=sum[u*2]+sum[u*2+1];
}
void dfs(int u,int l,int r){
    if(l==r){
        sum[u]=a[l].cnt;
        return;
    }
    int mid=(l+r)>>1;
    dfs(u*2,l,mid);
    dfs(u*2+1,mid+1,r);
    upd(u);
}
int query(int x,int u,int l,int r){
    if(l==r) return a[l].num;
    int mid=(l+r)>>1;
    if(x>sum[u*2]) return query(x-sum[u*2],u*2+1,mid+1,r);
    else return query(x,u*2,l,mid);
}

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("cake.in","r",stdin);
    freopen("cake.out","w",stdout);

    cin>>n;
    for(int i=1;i<=n;i++){
        int u;
        cin>>u;
        a[i].num=u;
        a[i].cnt++;
    }
    for(int i=1;i<=n;i++){
        while(a[i].num%2==0){
            a[i].num>>=1;
            a[i].cnt<<=1;
        }
    }
    dfs(1,1,n);
    cin>>m;
    for(int i=1;i<=m;i++){
        int u;
        cin>>u;
        cout<<query(u,1,1,n)<<"\n";
    }
    return 0;
}

T3（没写）

二分最小值，相当于有M*N课时时间，注意只能选最多M次Ai（一周只有一节课），贪心选课程/自习

T4（没写）

按左端点排序然后搜索线思想，贪心优先往左填，同左端点区间长度小的优先填，填不了了就cout<<"No"。

#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;

int m,n,u,r;
struct www{
    int l,r;
    friend bool operator < (www x,www y){
        return x.r>y.r;
    }
} a[N];
bool cmp(www x,www y){
    return x.l<y.l;
}

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i].l>>a[i].r;
        }
        sort(a+1,a+n+1,cmp);
        bool nf=0;
        r=1,u=a[r].l;
        priority_queue<www> q;
        a[n+1].l=0,a[n+1].r=0;
        while(r<=n){
            while(r<=n&&a[r].l<=u){
                q.push(a[r]);
                r++;
            }
            if(q.empty()){
                if(r>n) break;
                u=a[r].l;
                q.push(a[r]);
                r++;
            }
            if(q.top().r<u){
                nf=1;
                break;
            }
            else{
                u++;
                q.pop();
            }
        }
        while(!q.empty()){
            if(q.top().r<u){
                nf=1;
                break;
            }
            else{
                u++;
                q.pop();
            }
        }
        if(nf) cout<<"No\n";
        else cout<<"Yes\n";
    }
    return 0;
}

T5（0 WA）

先考虑无环情况：前缀和的绝对值之和就是答案，再考虑有环：复制一遍消环，滑动窗口取小的（30分），观察转化问题为数轴选点使所有点与其距离最小，结论知选中位数（我写了贪心）

T6（没写）

二分最小值，将区间挂在端点上，遇到要加的数就从大根堆（维护区间长度）取出一个

总结：

OIer啊，要多想。

想了以后呢？

我只能告诉你在那之前要多想。