程序员经验分享-hwhale

关于暴力&瞎搞骗分的一些实例

2023-11-13

骗分的实质：不会做的题用最少的时间写代码得到最多的分数

下面是几个乱搞骗分的实例，抛砖引玉让大家感受下骗分的强大：

1、NOI 2008 志愿者招募

http://codevs.cn/problem/1803/

根据题目范围可以想到直接搜索骗分，期望得分30分，实际得分30分，代码长度62行，写代码时间20分钟

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

#define MAXN 1100
#define INF 0x3f3f3f3f

using namespace std;

struct info
{
    int s,t,c,id;
}infos[MAXN];

int n,m;
bool used[MAXN];
int minCost;
int a[MAXN];
int ans=INF;

void dfs(int x,int cost) //到第x种志愿者花费为cost
{
    if(x>m)
    {
        for(int i=1;i<=n;i++)
            if(a[i]>0)
                return;
        if(ans>cost) ans=cost;
        return;
    }
    dfs(x+1,cost);
    int L=infos[x].s,R=infos[x].t;
    int minNeed=0;
    for(int i=L;i<=R;i++)
    {
        if(a[i]>minNeed) minNeed=a[i];
    }
    for(int need=1;need<=minNeed;need++)
    {
        for(int i=L;i<=R;i++)
            a[i]-=need;
        dfs(x+1,cost+infos[x].c*need);
        for(int i=L;i<=R;i++)
            a[i]+=need;
    }

}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&infos[i].s,&infos[i].t,&infos[i].c);
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}

正确做法：图论、网络流，代码长度： (代码来源：https://www.byvoid.com/blog/noi-2008-employee/)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1003,MAXM=10002*4,INF=0x7FFFFFFF;
using namespace std;
struct edge
{
    edge *next,*op;
    int t,c,v;
}ES[MAXM],*V[MAXN];
struct Queue
{
    int Q[MAXN],QH,QL,Size;
    bool inq[MAXN];
    inline void ins(int v)
    {
        if (++QL>=MAXN)
            QL=0;
        Q[QL]=v;
        inq[v]=true;
        Size++;
    }
    inline int pop()
    {
        int r=Q[QH];
        inq[r]=false;
        Size--;
        if (++QH>=MAXN)
            QH=0;
        return r;
    }
    inline void reset()
    {
        memset(Q,0,sizeof(Q));
        QH=Size=0;
        QL=-1;
    }
}Q;
int N,M,S,T,EC=-1;
int demond[MAXN],sp[MAXN],prev[MAXN];
edge *path[MAXN];
inline void addedge(int a,int b,int v,int c=INF)
{
    edge e1={V[a],0,b,c,v} , e2={V[b],0,a,0,-v};
    ES[++EC]=e1; V[a]=&ES[EC];
    ES[++EC]=e2; V[b]=&ES[EC];
    V[a]->op=V[b]; V[b]->op=V[a];
}
void init()
{
    int i,a,b,c;
    freopen("employee.in","r",stdin);
    freopen("employee.out","w",stdout);
    scanf("%d%d",&N,&M);
    for (i=1;i<=N;i++)
        scanf("%d",&demond[i]);
    for (i=1;i<=M;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        addedge(a,b+1,c);
    }
    S=0,T=N+2;
    for (i=1;i<=N+1;i++)
    {
        c = demond[i] - demond[i-1];
        if (c>=0)
            addedge(S,i,0,c);
        else
            addedge(i,T,0,-c);
        if (i>1)
            addedge(i,i-1,0);
    }
}
bool spfa()
{
    int u,v;
    for (u=S;u<=T;u++)
        sp[u]=INF;
    Q.reset();
    Q.ins(S);
    sp[S]=0;
    prev[S]=-1;
    while (Q.Size)
    {
        u=Q.pop();
        for (edge *k=V[u];k;k=k->next)
        {
            v=k->t;
            if (k->c>0 && sp[u] + k->v <sp[v])
            {
                sp[v]=sp[u] + k->v;
                prev[v]=u;
                path[v]=k;
                if (!Q.inq[v])
                    Q.ins(v);
            }
        }
    }
    return sp[T]!=INF;
}
int argument()
{
    int i,delta=INF,flow=0;
    edge *e;
    for (i=T;prev[i]!=-1;i=prev[i])
    {
        e=path[i];
        if (e->c<delta)
            delta=e->c;
    }
    for (i=T;prev[i]!=-1;i=prev[i])
    {
        e=path[i];
        e->c-=delta;e->op->c+=delta;
        flow+=e->v*delta;
    }
    return flow;
}
int maxcostflow()
{
    int Flow=0;
    while (spfa())
        Flow += argument();
    return Flow;
}
int main()
{
    init();
    printf("%dn",maxcostflow());
    return 0;
}
NOI时此题平均得分只有12.56分！可见暴力骗分的强大！

2、NOIP 2013 华容道

http://codevs.cn/problem/3290/

根据题目范围，80%数据的q<=10，出题者很明显给我们留好了退路：正解写不出来就暴力。

暴力做法：纯BFS+判重，期望得分80分，实际得分70分（可能是非官方数据更紧的缘故，实际上NOIP 2013时wjk神犇同一做法得到了85分）

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>

#define MAXN 33

using namespace std;

bool visit[MAXN][MAXN][MAXN][MAXN];
int map[MAXN][MAXN];

struct node
{
    int bx,by,x,y; //绿色棋子为(x,y),空白格子为(bx,by)
    int step;
}first;

queue<node>q;

int xx[]={1,-1,0,0},yy[]={0,0,1,-1};
int ex,ey,sx,sy,tx,ty;
int n,m,Q;

bool inMap(int bx,int by,int x,int y)
{
    if(bx==x&&by==y) return false;
    if(bx<1||bx>n||by<1||by>m) return false;
    if(map[bx][by]) return false;
    if(x<1||x>n||y<1||y>m) return false;
    if(map[x][y]) return false;
    return true;
}

int bfs()
{
    while(!q.empty()) q.pop();
    q.push(first);
    visit[first.bx][first.by][first.x][first.y]=true;
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(now.x==tx&&now.y==ty) return now.step;
        if(abs(now.bx-now.x)+abs(now.by-now.y)==1) //棋子与空格相邻
        {
            node next=now;
            next.step++;
            swap(next.x,next.bx);
            swap(next.y,next.by);
            if(inMap(next.bx,next.by,next.x,next.y)&&!visit[next.bx][next.by][next.x][next.y])
            {
                visit[next.bx][next.by][next.x][next.y]=true;
                q.push(next);
            }
        }
        for(int dir=0;dir<4;dir++) //白格移动方向
        {
            node next=now;
            next.step++;
            next.bx+=xx[dir],next.by+=yy[dir];
            if(inMap(next.bx,next.by,next.x,next.y)&&!visit[next.bx][next.by][next.x][next.y])
            {
                visit[next.bx][next.by][next.x][next.y]=true;
                q.push(next);
            }
        }
    }
    return -1;
}

int main()
{
    scanf("%d%d%d",&n,&m,&Q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&map[i][j]);
            map[i][j]=1-map[i][j];
        }
    for(int i=1;i<=Q;i++)
    {
        memset(visit,0,sizeof(visit));
        first.step=0;
        scanf("%d%d%d%d%d%d",&first.bx,&first.by,&first.x,&first.y,&tx,&ty);
        int ans=bfs();
        //if(ans>1000000) ans=-1;
        printf("%d\n",ans);
    }
    return 0;
}


正确解法：BFS建图+SPFA，非常复杂而且写起来容易错。

#include<iostream>
#include<cstdio>
#include<cstring>
#include <queue>

#define MAXN 32
#define MAXV 50010
#define INF (1<<26)

using namespace std;

int xx[]={1,-1,0,0},yy[]={0,0,1,-1};

struct edge
{
    edge *next; //上一条边的指针
    int t,w; //目标节点,边权
    edge()
    {
        next=NULL;
    }
}*head[MAXV];

struct node //保存棋子状态
{
    int x,y;
    node(int xx,int yy):x(xx),y(yy) {}
};

int map[MAXN][MAXN],n,m,Q,ex,ey,sx,sy,tx,ty; //空白格子(ex,ey),指定棋子(sx,sy),目标位置(tx,ty)
int v[MAXN][MAXN][4],dist[MAXN][MAXN],move[MAXN][MAXN][4][4];
int Dis[MAXV],S,T,V=0;
bool visit[MAXV];

struct cmp
{
    bool operator()(int x,int y)
    {
        return Dis[x]>Dis[y];
    }
};

queue<node>q; //保存状态的bfs队列
priority_queue<int,vector<int>,cmp>pq;

void AddEdge(int s,int t,int w) //建立有向边s->t,边权为w
{
    edge *p=new(edge); //新建一个边
    p->t=t;
    p->w=w;
    p->next=head[s];
    head[s]=p;
}

int bfs(int SX,int SY,int TX,int TY) //求出(SX,SY)到(TX,TY)的距离
{
    if(SX==TX&&SY==TY) return 0;
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            dist[i][j]=INF;
    dist[SX][SY]=0; //出发点到出发点费用为0
    q.push(node(SX,SY));
    while(!q.empty())
    {
        node now=q.front();
        q.pop(); //队首出队
        for(int i=0;i<4;i++)
        {
            if(map[now.x+xx[i]][now.y+yy[i]]&&dist[now.x+xx[i]][now.y+yy[i]]==INF) //移动后的点的距离没有被拓展过，且没有越界
            {
                dist[now.x+xx[i]][now.y+yy[i]]=dist[now.x][now.y]+1;
                if(now.x+xx[i]==TX&&now.y+yy[i]==TY) return dist[now.x][now.y]+1; //移动到了目标节点，返回距离
                q.push(node(now.x+xx[i],now.y+yy[i])); //新状态入队
            }
        }
    }
    return INF;
}

int spfa()
{
    for(int i=1;i<=V;i++) Dis[i]=INF;
    memset(visit,true,sizeof(visit));
    while(!pq.empty()) pq.pop();
    Dis[S]=0;
    pq.push(S);
    while(!pq.empty())
    {
        int now=pq.top();
        pq.pop();
        if(!visit[now]) continue;
        visit[now]=false;
        if(now==T) return Dis[T]; //求得了到达终点的距离，返回
        for(edge *p=head[now];p;p=p->next)
        {
            if(Dis[p->t]>Dis[now]+p->w) //有优化的空间
            {
                Dis[p->t]=Dis[now]+p->w;
                visit[p->t]=true;
                pq.push(p->t);
            }
        }
    }
    return Dis[T]<INF?Dis[T]:-1;
}

int main()
{
    cin>>n>>m>>Q;
    memset(map,0,sizeof(map));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>map[i][j];
            for(int k=0;k<4;k++)
                v[i][j][k]=++V;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<4;k++)
                for(int h=0;h<4;h++)
                    move[i][j][k][h]=INF;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(map[i][j])
            {
                map[i][j]=0;
                for(int k=0;k<4;k++)
                {
                    if(map[i+xx[k]][j+yy[k]])
                    {
                        for(int h=0;h<4;h++)
                        {
                            if(map[i+xx[h]][j+yy[h]])
                            {
                                move[i][j][k][h]=bfs(i+xx[k],j+yy[k],i+xx[h],j+yy[h])+1;
                            }
                        }
                    }
                }
                map[i][j]=1;
            }
        }
    }
    memset(head,0,sizeof(head));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<4;k++)
                for(int h=0;h<4;h++)
                    if(move[i][j][k][h]<INF)
                        AddEdge(v[i][j][k],v[i+xx[h]][j+yy[h]][h^1],move[i][j][k][h]);
    while(Q--)
    {
        cin>>ex>>ey>>sx>>sy>>tx>>ty;
        if(sx==tx&&sy==ty) //不合法情况1:初始棋子位置和目标位置一样
        {
            cout<<0<<endl;
            continue;
        }
        S=++V; //新建一个起点
        T=++V; //新建一个终点
        if(map[sx][sy]==0||map[tx][ty]==0) //不合法情况2:初始位置或目标位置不能走，有障碍物
        {
            cout<<-1<<endl;
            continue;
        }
        map[sx][sy]=0;
        for(int i=0;i<4;i++)
        {
            if(map[sx+xx[i]][sy+yy[i]]) //该点为起点相邻的点，若该点可走
            {
                int D=bfs(ex,ey,sx+xx[i],sy+yy[i]); //求出它到空白格子之间的距离
                if(D<INF) //能走通
                    AddEdge(S,v[sx][sy][i],D); //在起点状态和图中的S点之间建边
            }
        }
        map[sx][sy]=1;
        for(int i=0;i<4;i++)
            if(map[tx+xx[i]][ty+yy[i]]) //该点为终点相邻的点，若该点可走
                AddEdge(v[tx][ty][i],T,0); //终点和图中T点建边，边权为0
        cout<<spfa()<<endl;
    }
    return 0;
}


3、Codevs 2818 为了信仰

http://codevs.cn/problem/2818/

暴力做法：BFS建图+kruscal最小生成树，期望得分60分，实际得分66分

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>

#define MAXN 110

using namespace std;

struct node
{
    int x,y,step;
    bool operator<(const node &b)const{return step>b.step;}
};

struct edge
{
    int u,v,w,next;
}edges[MAXN*MAXN];

priority_queue<node>q;

int head[MAXN],nCount=0;
int map[MAXN][MAXN];
int tmp[MAXN][MAXN];
int n,m,k;
int blackx[MAXN],blacky[MAXN];
bool visit[MAXN][MAXN];
int xx[]={1,-1,0,0},yy[]={0,0,1,-1};

void AddEdge(int U,int V,int W)
{
    edges[++nCount].u=U;
    edges[nCount].v=V;
    edges[nCount].w=W;
    edges[nCount].next=head[U];
    head[U]=nCount;
}

bool inMap(int x,int y)
{
    if(x<1||x>n||y<1||y>m) return false;
    return true;
}

int bfs(int sx,int sy,int tx,int ty)
{
    memset(visit,0,sizeof(visit));
    memcpy(tmp,map,sizeof(map));
    while(!q.empty()) q.pop();
    node first;
    first.step=0;
    first.x=sx,first.y=sy;
    visit[sx][sy]=true;
    q.push(first);
    while(!q.empty())
    {
        node now=q.top();
        q.pop();
        if(now.x==tx&&now.y==ty) return now.step;
        for(int dir=0;dir<4;dir++)
        {
            node next=now;
            next.x+=xx[dir],next.y+=yy[dir];
            if(!inMap(next.x,next.y)) continue;
            if(visit[next.x][next.y]) continue;
            if(!map[next.x][next.y])
                next.step++;
            visit[next.x][next.y]=true;
            q.push(next);
        }
    }
    memcpy(map,tmp,sizeof(tmp));
    return -1;
}

int f[MAXN];

int findSet(int x)
{
    if(f[x]==x) return f[x];
    return f[x]=findSet(f[x]);
}

bool cmp(edge a,edge b)
{
    return a.w<b.w;
}

int kruscal()
{
    int ans=0;
    sort(edges+1,edges+nCount+1,cmp);
    for(int i=1;i<=nCount;i++)
    {
        int rootu=findSet(edges[i].u),rootv=findSet(edges[i].v);
        if(rootu!=rootv)
        {
            ans+=edges[i].w;
            f[rootu]=rootv;
        }
    }
    return ans;
}

int main()
{
    char in[MAXN];
    for(int i=0;i<MAXN;i++) f[i]=i;
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",in+1);
        for(int j=1;j<=m;j++)
            map[i][j]=in[j]-'0';
    }
    scanf("%d",&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&blackx[i],&blacky[i]);
        blackx[i]++;
        blacky[i]++;
    }
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
            if(i<j)
            {
                if(blackx[i]==blackx[j]&&blacky[i]==blacky[j])
                {
                    AddEdge(i,j,0);
                    continue;
                }
                int w=bfs(blackx[i],blacky[i],blackx[j],blacky[j]);
                if(w!=-1) AddEdge(i,j,w);
            }
    printf("%d\n",kruscal());
    return 0;
}
正确解法：状压DP


4、NOI 2014 起床困难综合症

http://codevs.cn/problem/3311

暴力做法：直接枚举，期望得分30分，实际得分30分

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXN 100100
#define INF 0x3f3f3f3f

using namespace std;

char op[MAXN];
int t[MAXN];
int ans=INF;
int n,m;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        char cmd[10];
        scanf("%s%d",cmd,&t[i]);
        op[i]=cmd[0];
    }
    int maxAns=0,ans;
    for(int tmp=0;tmp<=m;tmp++)
    {
        ans=tmp;
        for(int i=1;i<=n;i++)
        {
            if(op[i]=='A')
                ans=ans&t[i];
            else if(op[i]=='O')
                ans=ans|t[i];
            else
                ans=ans^t[i];
        }
        if(ans>maxAns) maxAns=ans;
    }
    printf("%d\n",maxAns);
    return 0;
}

正确解法：二进制(代码来源：http://hzwer.com/3841.html)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
inline ll read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,a[100005],b[100005],f[35],ans,tot;
int cal(int x)
{
	for(int i=1;i<=n;i++)
		if(a[i]==1)x=(x&b[i]);
		else if(a[i]==2)x=(x|b[i]);
		else x=(x^b[i]);
	return x;
}
int main()
{
	//freopen("sleep.in","r",stdin);
	//freopen("sleep.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		char ch[5];
		scanf("%s",ch);
		if(ch[0]=='A')a[i]=1;
		else if(ch[0]=='O')a[i]=2;
		else a[i]=3;
		b[i]=read();
	}
	int t=cal(0);
	for(int i=0;i<=30;i++)f[i]=(cal(1<<i)&(1<<i));
    for(int i=30;i>=0;i--)
	{
		if((1<<i)&t)ans+=(1<<i);
		else if((tot+(1<<i)<=m)&&f[i])
		{
			tot+=f[i];
			ans+=f[i];
		}
	}
	printf("%d",ans);
	return 0;
}


5、NOI 2014 魔法森林

http://codevs.cn/problem/3314

暴力做法：DFS乱搞，得分10分

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXV 1000010
#define MAXE 50100
#define INF 0x3f3f3f3f

using namespace std;

struct edge
{
    int u,v,a,b,next;
}edges[MAXV];

int head[MAXE],nCount=0;
bool visit[MAXE];
int maxa=0,maxb=0;
int n,m;

void AddEdge(int U,int V,int A,int B)
{
    edges[++nCount].u=U;
    edges[nCount].v=V;
    edges[nCount].a=A;
    edges[nCount].b=B;
    edges[nCount].next=head[U];
    head[U]=nCount;
}

int dfs(int u) //从点u下去dfs，找一个路上a和b总个数最大值最小的路
{
    int ans=INF;
    if(u==n) return maxa+maxb;
    visit[u]=true;
    for(int p=head[u];p!=-1;p=edges[p].next)
    {
        int v=edges[p].v;
        if(visit[v]) continue;
        int tmpa=maxa,tmpb=maxb;
        if(edges[p].a>maxa) maxa=edges[p].a;
        if(edges[p].b>maxb) maxb=edges[p].b;
        int tmp=dfs(v);
        if(tmp<ans) ans=tmp;
        maxa=tmpa,maxb=tmpb;
    }
    return ans;
}

int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,a,b;
        scanf("%d%d%d%d",&x,&y,&a,&b);
        AddEdge(x,y,a,b);
        AddEdge(y,x,a,b);
    }
    printf("%d\n",dfs(1));
    return 0;
}
正确解法：Link Cut Tree(代码来源： http://hzwer.com/3845.html) 

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define inf 1000000000
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int top,n,m,tot,ans=inf;
struct edge{int u,v,a,b;}e[100005];
int f[150005];
int c[150005][2],fa[150005];
int q[150005],val[150005],mx[150005];
bool rev[150005];
int find(int x)
{
	return x==f[x]?x:f[x]=find(f[x]);
}
bool operator<(edge a,edge b)
{
	return a.a<b.a;
}
bool isroot(int x)
{
	return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
}
void update(int x)
{
	int l=c[x][0],r=c[x][1];
	mx[x]=x;
	if(val[mx[l]]>val[mx[x]])mx[x]=mx[l];
	if(val[mx[r]]>val[mx[x]])mx[x]=mx[r];
}
void pushdown(int x)
{
	int l=c[x][0],r=c[x][1];
	if(rev[x])
	{
		rev[x]^=1;rev[l]^=1;rev[r]^=1;
		swap(c[x][0],c[x][1]);
	}
}
void rotate(int x)
{
	int y=fa[x],z=fa[y],l,r;
	if(c[y][0]==x)l=0;else l=1;r=l^1;
	if(!isroot(y))
	{
		if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;
	}
	fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
	c[y][l]=c[x][r];c[x][r]=y;
	update(y);update(x);
}
void splay(int x)
{
	top=0;q[++top]=x;
	for(int i=x;!isroot(i);i=fa[i])
		q[++top]=fa[i];
	for(int i=top;i;i--)
		pushdown(q[i]);
	while(!isroot(x))
	{
		int y=fa[x],z=fa[y];
		if(!isroot(y))
		{
			if(c[y][0]==x^c[z][0]==y)rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
	update(x);
}
void access(int x)
{
	int t=0;
	while(x)
	{
		splay(x);c[x][1]=t;t=x;x=fa[x];
	}
}
void makeroot(int x)
{
	access(x);splay(x);rev[x]^=1;
}
void link(int x,int y)
{
	makeroot(x);fa[x]=y;
}
void cut(int x,int y)
{
	makeroot(x);access(y);splay(y);c[y][0]=fa[x]=0;
}
int query(int x,int y)
{
	makeroot(x);access(y);splay(y);return mx[y];
}
void solve(int k)
{
	int u=e[k].u,v=e[k].v,w=e[k].b;
	int t=query(u,v);
	if(w<val[t])
	{	
		cut(e[t-n].u,t);cut(e[t-n].v,t);
		link(u,k+n);link(v,k+n);
	}
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++)
	{
		e[i].u=read();e[i].v=read();e[i].a=read();e[i].b=read();
	}
	sort(e+1,e+m+1);
	for(int i=1;i<=m;i++)
	{
		val[n+i]=e[i].b;mx[n+i]=n+i;
	}
	for(int i=1;i<=m;i++)
	{
		int u=e[i].u,v=e[i].v,w=e[i].b;
		int p=find(u),q=find(v);
		if(p!=q)
		{
			f[p]=q;
			link(u,n+i);link(v,n+i);
		}
		else solve(i);
		if(find(1)==find(n))ans=min(ans,val[query(1,n)]+e[i].a);
	}
	if(ans!=inf)printf("%d\n",ans);
	else puts("-1");
	return 0;
}


5、Codevs 1135 选择客栈(NOIP 2011提高组)

http://codevs.cn/problem/1135/

暴力思路:for循环枚举，最差复杂度O(n^3),最好复杂度O(1),期望得分50分，实际得分60分，代码长度38行，写代码时间20分钟

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXN 2000100
#define INF 0x3f3f3f3f

using namespace std;

int color[MAXN],cost[MAXN];

int main()
{
    int n,k,p,ans=0;
	scanf("%d%d%d",&n,&k,&p);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&color[i],&cost[i]);
	for(int L=1;L<=n;L++)
		for(int R=L;R<=n;R++)
		{
		    if(R==L) continue;
			bool flag=false;
			if(color[L]==color[R])
			{
				for(int i=L;i<=R;i++)
				{
					if(cost[i]<=p)
						flag=true;
				}
			}
			if(flag)
				ans++;
		}
	printf("%d\n",ans);
    return 0;
}


加了前缀和优化后，节省了求和的那一维时间，最差复杂度变为O(n^2),但是得分还是60分，TLE的4个点数据太大了

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXN 2000100
#define INF 0x3f3f3f3f

using namespace std;

int color[MAXN],cost[MAXN];
int sum[MAXN]; //sum[i]=前i个客栈<=p的个数

int main()
{
    int n,k,p,ans=0;
	scanf("%d%d%d",&n,&k,&p);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&color[i],&cost[i]);
		if(cost[i]<=p) sum[i]=sum[i-1]+1;
		else sum[i]=sum[i-1];
	}
	for(int L=1;L<=n;L++)
		for(int R=L;R<=n;R++)
		{
		    if(R==L) continue;
			bool flag=false;
			if(color[L]==color[R])
			{
				if(sum[R]-sum[L-1]>0) ans++;
			}
		}
	printf("%d\n",ans);
    return 0;
}


正确思路：动态规划，代码不是很长，但是不是很好想，而且容易错

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXN 200100

int cheapMaxNum[MAXN],colorMaxNum[MAXN],sameColorNum[MAXN],ans[MAXN],colorNum[MAXN],maxNum[MAXN];

/*
	声明：便宜的客栈就是价格低于最高消费的客栈
	cheapMaxNum[i]=1~i中编号最大的便宜客栈
	colorMaxNum[i]=1~i-1中与i颜色相同的编号最大的客栈
	sameColorNum[i]=1~i-1中和i颜色相同的客栈个数
	ans[i]=1~i-1中与i颜色相同，且其到i之间有便宜客栈的个数
	DP方程为:
	ans[i]=ans[colorMaxNum[i]],cheapMaxNum[i]<=colorMaxNum[i]
	ans[i]=sameColorNum[i],cheapMaxNum[i]>colorMaxNum[i]
	colorNum[i]=之前所有客栈中色调为i的个数，maxNum[i]=之前所有客栈中色调为i的最大客栈编号
*/

int main()
{
	int n,k,p,color,price;
	scanf("%d%d%d",&n,&k,&p);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&color,&price);
		colorMaxNum[i]=maxNum[color]; //前i-1个客栈中与i相同颜色的客栈最大编号就是之前color色调的最大客栈编号
		sameColorNum[i]=colorNum[color]; //同理
		if(price<=p) //i号客栈是便宜客栈
			cheapMaxNum[i]=i; //前i个客栈中便宜客栈的最大编号就是i自己
		else cheapMaxNum[i]=cheapMaxNum[i-1]; //否则前i个客栈中便宜客栈最大编号和前i-1个的相同
		if(cheapMaxNum[i]<colorMaxNum[i])
			ans[i]=ans[colorMaxNum[i]];
		else
			ans[i]=sameColorNum[i];
		colorNum[color]++;
		maxNum[color]=i;
	}
	int Ans=0;
	for(int i=2;i<=n;i++) //找客栈尾巴,统计方案总个数
			Ans+=ans[i];
	printf("%d\n",Ans);
	return 0;
}














本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

灌水

搜索DFSBFSA*IDA*

NOIP

wikioi

模拟贪心

关于暴力&瞎搞骗分的一些实例 的相关文章

  • NOIP 2002 普及组第四题 过河卒

    题目描述 棋盘上 A 点有一个过河卒 xff0c 需要走到目标 B 点 卒行走的规则 xff1a 可以向下 或者向右 同时在棋盘上 C 点有一个对方的马 xff0c 该马所在的点和所有跳跃一步可达的点称为对方马的控制点 因此称之为 马拦过河

  • [NOIP2014]珠心算测验 T1

    珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术 珠心算训练 既能够开发智力 又能够为日常生活带来很多便利 因而在很多学校得到普及 某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法 他随机生成一个正整数集合 集合中的

  • 20201206贪心法1课后总结

    文章目录 贪心法1题目总结 贪心法定义 贪心法技巧 贪心习题 选自题单 http wikioi cn training mission 10 10080 删数问题 http wikioi cn problem 10080 思路 注意 代码

  • 信息学奥赛一本通（C++版） 第一部分 C++语言 第一章 C++语言入门

    总目录详见 https blog csdn net mrcrack article details 86501716 信息学奥赛一本通 C 版 第一部分 C 语言 第一章 C 语言入门 http ybt ssoier cn 8088 100

  • 07:和为给定数

    总时间限制 1000ms 内存限制 65536kB 描述 给出若干个整数 询问其中是否有一对数的和等于给定的数 输入 共三行 第一行是整数n 0 lt n lt 100 000 表示有n个整数 第二行是n个整数 整数的范围是在0到10 8之

  • 【定理】算术基本定理（唯一分解定理）

    大蒟蒻来水贴了 算术基本定理 唯一分解定理 一句话 任何大于 的自然数 都可以唯一分解成有限个质数的乘积 例如对于大于1的自然数n 这里P i i均为质数 其指数a i i是正整数 这样的分解称为的标准分解式 唯一分解定理具有 唯一性 分配

  • 1929：【04NOIP普及组】火星人

    题干 这道题有好多废话 不过和全排列非常像 全排列题目 所以这道题数字的大小顺序与全排列的默认顺序一模一样 全排列的代码 在这里 本题就是一次次地调用全排列 不愿意麻烦的 就是我 可以用STL 非常方便 代码 100分 include

  • C++一行输入多个整数，每个整数用空格隔开，回车结束输入

    C 一行输入多个整数 每个整数用空格隔开 回车结束输入 include

  • 【并查集】黑魔法师之门

    黑魔法师之门 magician pas c cpp 题目描述 经过了16个工作日的紧张忙碌 未来的人类终于收集到了足够的能源 然而在与Violet星球的战争中 由于Z副官的愚蠢 地球的领袖applepi被邪恶的黑魔法师Vani囚禁在了Vio

  • 20201105枚举课后总结

    文章目录 枚举 210733 奶牛碑文 http wikioi cn problem 210733 题目描述 输入格式 输出格式 样例输入 样例输出 思路 1 2 代码 210792 分解质因数 http wikioi cn problem

  • NOIP 1998 普及组 复赛 幂次方

    NOIP 1998 普及组 复赛 幂次方 1208 2的幂次方表示 此文代码与本人极其相似 唯一不同就是此文代码成功了 http www cnblogs com bofengyu p 4477355 html 思路 先打印2 7 2 3 2

  • 最热门的9个超级SEX问题

    无从选择 女人的身体被造物设计成传宗接代的载体 而SEX就是当初那只引诱我们上钩的苹果 不会忘记新生命诞生时 那场撕裂心肺的痛 那是女人完成自己使命的另类礼赞 那个曾经代表忠贞 圣洁的标签 被男人心怀窃喜地撕下 并据为己有 女人从此无法原价

  • [Wikioi 2808][NOIP 1998普及组]二的幂次方---HBNU的童鞋过来看看

    题目描述 Description 任何一个正整数都可以用2的幂次方表示 例如 137 2 7 2 3 2 0 同时约定次方用括号来表示 即a b可表示为a b 由此可知 137可表示为 2 7 2 3 2 0 进一步 7 2 2 2 2 0

  • [NOIP 2014复习]第二章：搜索

    一 深度优先搜索 DFS 1 Wikioi 1066引水入城 题目描述 Description 在一个遥远的国度 一侧是风景秀美的湖泊 另一侧则是漫无边际的沙漠 该国的行政 区划十分特殊 刚好构成一个N行M列的矩形 如上图所示 其中每个格子

  • OpenJudge1.4编程基础之逻辑表达式与条件分支

    文章目录 01 判断数正负 02 输出绝对值 03 奇偶数判断 04 奇偶ASCII值判断 05 整数大小比较 06 判断是否为两位数 07 收集瓶盖赢大奖 08 判断一个数能否同时被3和5整除 09 判断能否被3 5 7整除 10 有一门

  • c++基础--另类的分支结构

    前言 本节课讲的主要知识点是三目运算符和switch语句 同时也是我们分支结构部分的结尾内容 而从第三课开始到第五课 都是讲述分支结构的相关知识点 他们的特点都是相辅相成的 因此建议通读三篇文章 加强理解 同时做题也是必不可少滴 三目运算符

  • 关于暴力&瞎搞骗分的一些实例

    骗分的实质 不会做的题用最少的时间写代码得到最多的分数 下面是几个乱搞骗分的实例 抛砖引玉让大家感受下骗分的强大 1 NOI 2008 志愿者招募 http codevs cn problem 1803 根据题目范围可以想到直接搜索骗分 期

  • NOIP1998普及组复赛第二题 贰的幂方 解题报告

    问题描述 任何一个正整数都可以用 2 的幂次方表示 例如 137 27 23 20 在这里我们约定次方用括号来表示 即 ab 可表示为 a b 由上面叙述可知 137 又可以表示为 2 7 2 3 2 0 进一步 7 22 2 20 2 2

  • [NOI 2015复习][BZOJ 1509][NOI 2003]逃学的小孩(树的直径)

    题目链接 http www lydsy com JudgeOnline problem php id 1509 题目大意 要从一棵树中找出三个点 X Y Z X Y Z 使得 min dis A C dis B C dis A B min

  • 原码，反码，补码，阶码，移码

    本文转载自本站大佬 不去上课 原文链接https blog csdn net ruidianbaihuo article details 87875178 原码 反码 补码 阶码 移码是什么 有什么区别 讨论机器数的表示 本文内容参考自王达

随机推荐

  • linux 线程优先级设置

    include

  • 用iframe完美嵌入

  • SpringBoot秒杀系统实战13-秒杀商品详情页+秒杀倒计时功能实现

    程序鹏 于 2020 05 08 00 00 00 发布 1326 收藏 4 分类专栏 Spring Boot 秒杀系统 文章标签 java spring boot web 版权 Spring Boot 同时被 2 个专栏收录 29 篇文章

  • LeetCode【28】实现 strStr()

    题目 实现 strStr 函数 给定一个 haystack 字符串和一个 needle 字符串 在 haystack 字符串中找出 needle 字符串出现的第一个位置 从0开始 如果不存在 则返回 1 示例 1 输入 haystack h

  • 使用Python的requests库发送HTTPS请求时的SSL证书验证问题

    问题描述 使用python的requests库去发送https请求 有时候不设置verify False不报错 有时候又报错 问题原因 使用Python的requests库发送HTTPS请求时 设置verify False参数可以跳过SSL

  • java设置有时效的变量_java设置全局变量

    图片来源于网络 如有侵权请联系删除 前言 java系统自带的api很多 而设置全局变量也是有在System对象中一个具体的方法 而Springboot启动类一层层递进的过程中就有使用该方法来存储全局变量 1 实例 在Springboot中的

  • MAC Unity安装教程

    缘起 这边app要做一个简单调研 验证是否可以利用unity改善app中h5页面需要展示的3d和复杂报表效果 于是就此开始了调研 这边只是想简单将unity集成到工程中 然后想办法嵌入h5来进行展示测试 安装地址 https unity3d

  • Java：字符串中a出现的次数

    1 问题描述 求字符串 abcguegduauwdakolaa 中a出现的次数 2 题解 2 1 题解一 思路 每次返回当前下标 使用indexOf求当前下标的后一位到字符串结束出现的第一个a的下标 String s abcguegduau

  • JS的防抖函数理解、手动封装

    1 认识防抖函数 当事件触发时 相应的函数并不会立即触发 而是会等待一定的时间 当事件密集触发时 函数的触发会被频繁的推迟 只有等待了一段时间也没有事件触发 才会真正的执行响应函数 举个例子 防抖函数的引用场景 输入框中频繁的输入内容 搜索

  • 网站开发之DIV+CSS简单布局网站入门篇（五）

    这篇文章主要介绍如何使用DIV和CSS简单布局一个网站的首页 通常将网站划分为顶部 Logo 导航条 中部 页面主要内容 左右栏目 底部 制作方介绍 超链接 这是非常基础的一篇引入性文章 采用案例的方式进行介绍的 希望对你有所帮助 运行结果

  • elementUI的日期选择器获取选择时间的格式，获取时间戳等

    elementUI的日期选择器获取选择时间的格式 获取时间戳等 在使用日期选择器的时候 我们需要把时间进行格式化 然后再传给后端 比如传时间戳 value format timestamp

  • RAID（磁盘阵列)

    一 RAID的简述 RAID是英文 Redundant Array of Independent Disks 的缩写 翻译成中文是 独立磁盘冗余阵列 简称磁盘阵列 Disk Array 简单的说 RAID是一种把多块独立的硬盘 物理硬盘 按

  • vue 打印文件

    1 下载插件 npm install vue print nb save 2 全局注册 在main js 中引入 打印文件 import Print from vue print nb Vue use Print 3 需要打印部分设置 id

  • 三种通信方式——单工、半双工和双工通信

    数据通常是在两个站 点对点 之间进行传输 按照数据流的方向可分为三种传输模式 单 工 半双工 全双工 一 单工通信 simplex 单工通信只支持信号在一个方向上传输 正向或反向 任何时候不能改变信号的传输方向 为保证正确传送数据信号 接收

  • 锐捷6800 vrrp mstp配置实例

    直接把配置考出来了 大家先看看把 6810A show run System software version 2 42 5 Build Feb 2 2007Rel Building configuration Current config

  • 使用SSH远程连接安卓手机Termux - Android手机服务器

    文章目录 1 安装ssh 2 安装cpolar内网穿透 3 远程ssh连接配置 4 公网远程连接 5 固定远程连接地址 转载自cpolar极点云的文章 公网SSH远程连接Termux 电脑使用安卓Termux 无需公网IP 使用安卓机跑东西

  • 常用算法与设计模式

    时间复杂度 二 计算方法 1 一个算法执行所耗费的时间 从理论上是不能算出来的 必须上机运行测试才能知道 但我们不可能也没有必要对每个算法都上机测试 只需知道哪个算法花费的时间多 哪个算法花费的时间少就可以了 并且一个算法花费的时间与算法中

  • Disconnected: No supported authentication methods available (server sent: publickey)

    安装Git客户端后 进行PULL时报如下错误 disconnected no supported authentication methods available server sent publickey keyboard interac

  • Spring:@Valid 和 @Validated

    Validated 常用于对 RequestBody注解中的参数校验生效 用法 PostMapping public UserModel getUser Validated RequestBody UserModel model retur

  • 关于暴力&瞎搞骗分的一些实例

    骗分的实质 不会做的题用最少的时间写代码得到最多的分数 下面是几个乱搞骗分的实例 抛砖引玉让大家感受下骗分的强大 1 NOI 2008 志愿者招募 http codevs cn problem 1803 根据题目范围可以想到直接搜索骗分 期

热门标签