好无聊，然后就参加了洛谷 7 月月赛。
据说题目很简单所以是 oi 赛制？

T1

一看：啊！贪心！好水！
再看：啊！可以卡空间！
又看：不卡？太水了吧！
然后就交代码了。
因为如果有两个盒子里的糖果超过了 $k$ ，那么优先吃后面那个盒子里的好些，因为后面那个盒子还可能产生贡献，但前面那个盒子不行了。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<climits>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int x,las,kl,n,m;
int main()
{
    long long ans=0;
    n=read();m=read();
    for(int i=1;i<=n;i++){
        x=read();
        if(i==1){las=x;continue;}
        kl=x+las;if(kl<m){las=x;continue;}
        ans+=kl-m;
        if(kl-m<x)x-=kl-m;
        else x=0;
        las=x;
    }
    printf("%lld",ans);
    return 0;
}

T2

一看：搜索？太水了吧！
然后就没有然后了。代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<climits>
using namespace std;
bool vis[1005][1005][2];
//走到哪个格子，是否使用药品。
char ma[1005][1005];
int mvx[5]={0,1,-1,0,0},mvy[5]={0,0,0,1,-1};
int n,m,d,r;
struct node{int x,y;bool uss;int bs;}q[2000005],t;
//bs: 走的步数，uss: 是否用了药品。
int main()
{
    int i,j,he=1,ta=1;
    scanf("%d%d%d%d\n",&n,&m,&d,&r);
    for(i=0;i<n;i++)scanf("%s",ma[i]);
    q[1].x=0;q[1].y=0;q[1].uss=0;q[1].bs=0;vis[0][0][0]=1;
    while(he<=ta){
        for(i=1;i<=4;i++){//走路
            int tx=q[he].x+mvx[i],ty=q[he].y+mvy[i];
            if(tx>=0&&tx<n&&ty>=0&&ty<m&&ma[tx][ty]!='#'&&!vis[tx][ty][q[he].uss]){
                vis[tx][ty][q[he].uss]=1;
                ta++;q[ta].x=tx;q[ta].y=ty;q[ta].uss=q[he].uss;
                q[ta].bs=q[he].bs+1;
                if(tx==n-1&&ty==m-1){printf("%d",q[ta].bs);return 0;}
            }
        }
        if(!q[he].uss){//用药（药不能停 2333）
            int tx=q[he].x+d,ty=q[he].y+r;
            if(tx>=0&&tx<n&&ty>=0&&ty<m&&ma[tx][ty]!='#'&&!vis[tx][ty][1]){
                vis[tx][ty][1]=1;
                ta++;q[ta].x=tx;q[ta].y=ty;q[ta].uss=1;
                q[ta].bs=q[he].bs+1;
                if(tx==n-1&&ty==m-1){printf("%d",q[ta].bs);return 0;}
            }   
        }
        he++;
    }
    printf("-1");
    return 0;
}

T3

做完 T2 就去吃了个午饭，回来看了一下 T3，一眼没有看出题解，不爽。发现三十分暴力很好拿，枚举就行。后来发现 70 分暴力也很好拿，因为每个点之间的转移是 O（1）的（这个见下），后来 boshi 说可能车站建在房子处一定能取最优解，我随便瞎写了写，发现样例 3 都过了（样例 1 的解释很坑人，因为车站建在坐标 50 也可以取最优解），于是就写了一个枚举车站的程序，后来下午无聊证明了一下：

假设在建车站的房子处有 r 个人，左边的路段上有 A 个人，右边的路段上有 B 个人。 $A \textlesst B$
如果我现在把车站向右移动 dis，那么答案更新量为 $dis×(A+r)-dis×B$ , 显然是不明智的。
如果我把车站向左移 dis，那么答案更新量为 $disc×(B+r)-dis×A$ 如果 $A \textless B+r$ , 不用移动，否则在移到下一个房子之前，肯定越往左移动，能获得越优的解，所以有 r 个人的那个房子不会是最优解。
综上：车站建在一个房子处可以得到最优解。那么枚举每一个房子即可。

后来听 boshi 大佬说其实就是在人数中位数处的房子是最优解，我发现接着我上面那个证明也可以证。既然 A>B+r 的时候就可以继续左移获得更优解，那么左移到中位数位置不就没法继续移了吗？
我当时交的程序：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<climits>
#include<algorithm>
using namespace std;
#define ll long long
ll read(){
    ll q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=(ll)q*10+(ll)(ch-'0'),ch=getchar();
    return q;
}
ll lo;int n;
struct node{ll x,r;}p[100005];
bool cmp(node a,node b){return a.x<b.x;}
int main()
{
    int i,j;ll ans=LLONG_MAX,rs=0,cd=0,tot=0;
    lo=read();n=read();
    for(i=1;i<=n;i++){p[i].x=read();p[i].r=read();tot+=p[i].r;}
    sort(p+1,p+1+n,cmp);
    for(i=2;i<=n;i++)cd+=p[i].r*(p[i].x-p[1].x);
    rs=p[1].r;
    for(i=2;i<=n;i++){
        cd-=(tot-rs)*(p[i].x-p[i-1].x);
        cd+=rs*(p[i].x-p[i-1].x);
        ans=min(ans,cd);rs+=p[i].r;
    }
    printf("%lld",ans);
    return 0;
}

T4

懒得想了，打了 30 分暴力走人。
下午大 jay 形说是并查集，然后我一开始想到了并查集，觉得很有道理，所以就愉快的开始打。
打了一个小时后，出了组数据把自己 HAKE 掉了，因为我是对于点进行并查集，在水改陆地的时候直接删掉这个点，但是如果这个点是一个集的父亲节点的话就会出大问题，后来和 boshi 还有大 jay 形讨论了一下（这不会算集体作弊吧 QAQ）说可以不用删掉节点，直接缩小这个集的大小即可，感觉很有道理，于是我愉快地改了改，用上午打的暴力进行对拍，80 分？诶诶诶？
boshi 也借了我的暴力去对拍（又是集体作弊 QAQ），他的程序 70 分，好尴尬。
最后 boshi 检查数据发现数据有分割两块温泉，他很高兴地说那应该没问题是数据的锅，于是我就把新程序交了。
最后结果出来我 50 分，boshi 40 分，很符合对拍结果 QAQ
考后看了题解，原来并查集不是对于每个节点做，而是对于每个节点所在的连通块做，这样即使这个连通块里已经被删的没有节点了，它还是可以作为一个虚拟父亲存在，就不会出现问题。
好吧，就这样，AC 代码：

#include<cstdio>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int maxn=1000005;
int n,m,que,tot;
char s[maxn];
int bj[maxn],sum[maxn<<1],fa[maxn<<1];
//bj: 该点所处连通块编号，fa: 连通块的父亲，sum: 一个集的大小。
void add(int x,int y){
    if(s[x*m+y]!='.'||bj[x*m+y])return;
    sum[tot]++;bj[x*m+y]=tot;
    if(x)add(x-1,y);if(y)add(x,y-1);
    if(x<n-1)add(x+1,y);if(y<m-1)add(x,y+1);
}
int gf(int x){
    if(!fa[x])return x;
    fa[x]=gf(fa[x]);return fa[x];
}
void lian(int x,int y,int xx,int yy){
    if(s[xx*m+yy]!='.'||gf(bj[xx*m+yy])==gf(bj[x*m+y]))return;
    int r1=gf(bj[x*m+y]),r2=gf(bj[xx*m+yy]);
    sum[r1]+=sum[r2];sum[r2]=0;fa[r2]=r1;
}
int main()
{
    int i,j,num,lx,mx,ans,t,x,y;
    n=read();m=read();
    for(i=0;i<n;i++)scanf("%s",s+i*m);
    for(i=0;i<n;i++)for(j=0;j<m;j++)
        if(s[i*m+j]=='.'&&!bj[i*m+j]){tot++;add(i,j);}
    que=read();
    while(que--){
        lx=read();num=read();
        if(lx==1){
            mx=0;ans=1;
            for(i=1;i<=num;i++){
                x=read()-1;y=read()-1;
                if(s[x*m+y]=='.'&&sum[gf(bj[x*m+y])]>mx)
                {mx=sum[gf(bj[x*m+y])];ans=i;}
            }
            printf("%d\n",ans);
        }
        else  for(i=1;i<=num;i++){
                x=read()-1;y=read()-1;
                if(s[x*m+y]=='.'){
                    sum[gf(bj[x*m+y])]--;
                    bj[x*m+y]=0;s[x*m+y]='*';
                }
                else {
                    bj[x*m+y]=++tot;sum[tot]++;s[x*m+y]='.';
                    if(x)lian(x,y,x-1,y);if(y)lian(x,y,x,y-1);
                    if(x<n-1)lian(x,y,x+1,y);if(y<m-1)lian(x,y,x,y+1);
                }
            }
    }
    return 0;
}

洛谷 7 月月赛解题记—litble

于2017年7月2日2017年7月2日由litble发布

T1

T2

T3

T4

litble

0 条评论

发表回复取消回复

洛谷 7 月月赛解题记—litble

于2017年7月2日2017年7月2日由litble发布

T1

T2

T3

T4

litble

0 条评论

发表回复 取消回复

发表回复取消回复