好无聊,然后就参加了洛谷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;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

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

你是机器人吗? =。= *