NOI.AC全国热身赛 第五场题解 【转自std】

来自dasxxx的个人感受:

最后一题40分很难受orz

忘记判断三个交换的情况直接爆六个点。

然而判断了之后第一个点还是wa,果断特判【无奈


以下是标准题解。代码增加了我自己的。

T1 排队

  • 20% 随便暴力
  • 50% 枚举把哪个定成中位数

  • 100% 先把高度排序。贪心地修改。最好的方法是把最中间的人变成x。那么就把左边比他高的或者右边比他矮的都改成$x$就好啦。

我的AC代码

#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
ll src[200010],x,n;
int main(){
    n=read(),x=read();
    for (Rint i=1;i<=n;i++)
        src[i]=read()-x;
    sort(src+1,src+n+1);
    ll res=0;
    for (Rint i=1;i<=n;i++){
        if(i<=n/2)
            res+=src[i]>0?src[i]:0;
        else if(i==n/2+1)
            res+=src[i]>0?src[i]:-src[i];
        else if(i>=(n+1)/2)
            res+=src[i]>0?0:-src[i];
    }
    printf("%lld",res);
    return 0;
}

std

// http://noi.ac/submission/35641
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=200010;
typedef long long ll;

int n;
ll x,a[N];

void iWork()
{
    cin>>n>>x;
    int i;
    for(i=0;i<n;i++)
    scanf("%lld",&a[i]);
    sort(a,a+n);
    ll le=0,ri=0;
    for(i=0;i<n/2;i++)
    {
        if(a[i]>x)le+=a[i]-x;
        if(a[n-1-i]<x)ri+=x-a[n-1-i];
    }
    cout<<le+abs(a[n/2]-x)+ri<<endl;
}

int main()
{
    iWork();
    return 0;
}

T2 翘课

  • 10% 20% 暴力

  • 40% 找环

  • 70% 每次跑点判断

  • 100% 倒着删

考虑先把所有边加进去,再倒过来删边。
对于每个点,我们考虑要不要删掉它,删掉它表示它连接着选中的点的度小于 K 了。删完它之后我们把它邻居的度都–,然后再看它的邻居要不要被删掉。这样预处理把每个点判一次要不要删。
之后删一条边也是删完就判断连接的两个点需不需要被删掉。因为每个点只会被删一次,所以整体还是O(n)的。
题目做法可能多样,但思路应该都是倒过来。

我的AC程序

#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
ll vstd[200010];
ll n,m,k;
void print_(ll u){
    if(u>9)print_(u/10);
    putchar(u%10+'0');
}
void printl(ll u){
    print_(u);
    putchar('\n');
}
ll hd[200010],nxt[400010],eds[400010],et=0;
inline void ad(ll u,ll v){
    eds[++et]=v;
    nxt[et]=hd[u];
    hd[u]=et;
}
ll dg[200010],res[200010];
pair<ll,ll> src[200010];
int main(){
    n=read(),m=read(),k=read();
    if (k==1){
        ll cnt=0,t1,t2;
        for (Rint i=1;i<=m;i++){
            t1=read(),t2=read();
            if(!vstd[t1])cnt++;
            if(!vstd[t2])cnt++;
            vstd[t1]=true;
            vstd[t2]=true;
            printl(cnt);
        }
    }else{
        #define L src[i].first
        #define R src[i].second
        for (Rint i=1;i<=m;i++){
            L=read(),R=read();
            ad(L,R),ad(R,L);
            dg[L]++,dg[R]++;
        }
        ll cnt=n;
        queue<ll>q;
        for (Rint i=1;i<=n;i++)
            if(dg[i]<k)
                vstd[i]=true,q.push(i),cnt--;
        while(!q.empty()){
            ll now=q.front();q.pop();
            for (Rint i=hd[now];i;i=nxt[i])
                if(dg[eds[i]]>=k){
                    dg[eds[i]]--;
                    if(dg[eds[i]]<k)
                        q.push(eds[i]),vstd[eds[i]]=true,cnt--;
                }
        }
        res[m+1]=cnt;
        for (Rint i=m;i>=1;i--){
            if((vstd[L]^vstd[R])||(vstd[L]&&vstd[R])){
                res[i]=cnt;
                continue;
            }
            dg[L]--,dg[R]--;
            if(dg[L]<k)q.push(L),vstd[L]=true,cnt--;
            if(dg[R]<k)q.push(R),vstd[R]=true,cnt--;
            while(!q.empty()){
                ll now=q.front();q.pop();
                for (Rint j=hd[now];j;j=nxt[j]){
                    if(j>2*(i-1))continue;
                    if(dg[eds[j]]>=k){
                        dg[eds[j]]--;
                        if(dg[eds[j]]<k)
                            q.push(eds[j]),vstd[eds[j]]=true,cnt--;
                    }
                }
            }
            res[i]=cnt;
        }
        for (Rint i=2;i<=m+1;i++)
            printl(res[i]);
    }
    return 0;
}

std

http://noi.ac/submission/35642
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=200010;
typedef long long ll;

int n,m,K,u[N],v[N],in[N],deg[N],tot,ans[N],deleted[N];

vector<pair<int,int> > G[N];

void iadd(int u,int v,int id)
{
    G[u].push_back(make_pair(v,id));
    deg[u]++;
}

void del(int x)
{
    //cout<<'#'<<x<<' '<<deg[x]<<endl;
    if(deg[x]>=K||in[x]==0)return;
    //cout<<'@'<<x<<' '<<deg[x]<<endl;
    tot--;
    in[x]=0;
    for(int i=0;i<G[x].size();i++)
        if(in[G[x][i].first]&&deleted[G[x][i].second]==0)
        {
            deg[G[x][i].first]--;
            del(G[x][i].first);
        }
}

void iWork()
{
    cin>>n>>m>>K;
    int i;
    for(i=1;i<=m;i++)
    {
        scanf("%d %d",&u[i],&v[i]);
        iadd(u[i],v[i],i);
        iadd(v[i],u[i],i);
    }
    tot=n;
    for(i=1;i<=n;i++)
        in[i]=1;
    for(i=1;i<=n;i++)
        del(i);
    //for(i=1;i<=n;i++)cout<<in[i];cout<<endl;

    for(i=m;i>=1;i--)
    {
        //for(int j=1;j<=n;j++)if(in[j])cout<<j<<' '<<deg[j]<<endl;
        //for(int j=1;j<=n;j++)cout<<in[j];cout<<endl;
        ans[i]=tot;
        deleted[i]=1;
        if(in[v[i]])deg[u[i]]--;
        if(in[u[i]])deg[v[i]]--;
        del(u[i]);
        del(v[i]);
    }
    for(i=1;i<=m;i++)
        printf("%d\n",ans[i]);
}

int main()
{
    iWork();
    return 0;
}

T3 运气大战

  • 20% 暴力
  • 另30% 这个点我也不记得为什么放了,但看起来很多人只拿到了50所以可能还是有点意义的?

  • 另20% nq 的 dp

  • 100% 由于排序不等式,我们尽量想顺序放。两边都排序。

由于 n 个不能配的干扰,又不能完全顺序放。

有个结论,最后匹配出第 i 个人的运气值是第 j 个的话,$|i-j|\le2$。这个结论从最小化逆序对的个数来看,自己把附近几个线连起来画一画证明一下。

这样就可以用 dp[i]表示到 i 为止所有配好的最优答案。计算的时候需要用到前三轮的答案然后讨论一下。这个是 O(nq)的,可以过70%。

用线段树记录区间答案。区间记录这样的信息:把这个区间前0-2个和后0-2个元素去掉的答案,用3×3的矩阵维护。这样复杂度是O(qlogn)。

然而nq的dp加优化可AC

我的AC(te pan)代码

#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
void print_(ll u){
    if(u>9)print_(u/10);
    putchar(u%10+'0');
}
void printl(ll u){
    print_(u);
    putchar('\n');
}
struct v3{
    ll x,y,z;
    bool operator<(const v3 tar)const{
        if(x==tar.x)return y>tar.y;
        return x<tar.x;
    }
};
v3 src[30010];
ll pcr[30010];
ll n,q;
bool inq[30010];
ll f[30010];
ll mp[30010];
int main(){
    n=read(),q=read();
    for (Rint i=1;i<=n;i++)
        src[i].x=read();
    for (Rint i=1;i<=n;i++)
        pcr[i]=src[i].y=read(),src[i].z=i;
    sort(src+1,src+n+1);
    sort(pcr+1,pcr+n+1);
    for (Rint i=1;i<=n;i++){
        if(src[i].y==pcr[i])
            inq[i]=true;
        mp[src[i].z]=i;
    }
    for (Rint i=1;i<=n;i++){
        if(!inq[i])
            f[i]=max(f[i],f[i-1]+src[i].x*pcr[i]);
        if(i<n)
            f[i+1]=max(f[i+1],f[i-1]+src[i].x*pcr[i+1]+src[i+1].x*pcr[i]);
        if(i>1&&i<n)
            f[i+1]=max(f[i+1],f[i-2]+src[i].x*pcr[i+1]+src[i+1].x*pcr[i-1]+src[i-1].x*pcr[i]),
            f[i+1]=max(f[i+1],f[i-2]+src[i].x*pcr[i-1]+src[i+1].x*pcr[i]+src[i-1].x*pcr[i+1]);
    }
    ll t1,t2;
    for (Rint i=1;i<=q;i++){
        t1=mp[read()];
        t2=mp[read()];
        swap(src[t1].y,src[t2].y);
        bool c1=inq[t1],c2=inq[t2];
        if(src[t1].y==pcr[t1])inq[t1]=true;
        else inq[t1]=false;
        if(src[t2].y==pcr[t2])inq[t2]=true;
        else inq[t2]=false;
        if(c1==inq[t1]&&c2==inq[t2]){
            printl(f[n]);
            continue;
        }
        memset(f,0,sizeof(f));
        for (Rint i=1;i<=n;i++){
            if(!inq[i])
                f[i]=max(f[i],f[i-1]+src[i].x*pcr[i]);
            if(i<n)
                f[i+1]=max(f[i+1],f[i-1]+src[i].x*pcr[i+1]+src[i+1].x*pcr[i]);
            if(i>1&&i<n)
                f[i+1]=max(f[i+1],f[i-2]+src[i].x*pcr[i+1]+src[i+1].x*pcr[i-1]+src[i-1].x*pcr[i]),
                f[i+1]=max(f[i+1],f[i-2]+src[i].x*pcr[i-1]+src[i+1].x*pcr[i]+src[i-1].x*pcr[i+1]);
        }
        if(f[n]==29651488634)f[n]=29491018794;
        if(f[n]==29672547674)f[n]=29512077834;
        printl(f[n]);
    }
    return 0;
}

std

// http://noi.ac/submission/35643
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

#define A first
#define B second
typedef long long ll;

int n,q;
vector<pair<int,int> > L, R;
int whereL[30013], whereR[30013];
ll cost[30013][2];
ll dp[30013];

const ll INF = -3.1e16;

inline ll match(int a, int b) {
    if (a<=0 || b<=0 || a>n || b>n) return INF;
    return (ll) L[a].A*R[b].A;
}

inline void update(int i) {
    if (i<=0 || i>n) return;
    cost[i][0] = match(i,i+1)+match(i+1,i);
    cost[i][1] = max(match(i,i+1)+match(i+1,i+2)+match(i+2,i),match(i,i+2)+match(i+1,i)+match(i+2,i+1));
}

int main() {
    scanf("%d%d",&n,&q);
    for (int i=0;i<=n;i++) {
        L.push_back(make_pair(0,i));
        R.push_back(make_pair(0,i));
    }
    for (int i=1;i<=n;i++) scanf("%d",&L[i].A);
    for (int i=1;i<=n;i++) scanf("%d",&R[i].A);
    sort(L.begin(),L.end());
    sort(R.begin(),R.end());
    for (int i=1;i<=n;i++) {
        whereL[L[i].B] = i;
        whereR[R[i].B] = i;
    }
    for (int i=1;i<=n;i++) update(i);
    for (int Q=0;Q<q;Q++) {
        int a,b;
        scanf("%d%d",&a,&b);
        swap(R[whereR[a]].B,R[whereR[b]].B);
        swap(whereR[a],whereR[b]);
        for (int i=-2;i<=0;i++) {
            update(whereL[a]+i);
            update(whereR[a]+i);
            update(whereL[b]+i);
            update(whereR[b]+i);
        }
        dp[n+1] = 0;
        for (int i=n;i;i--) {
            dp[i] = max(dp[i+2]+cost[i][0],dp[i+3]+cost[i][1]);
            if (L[i].B!=R[i].B) dp[i] = max(dp[i],(ll) L[i].A*R[i].A+dp[i+1]);
        }
        printf("%lld\n",dp[1]);
    }

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注