26

专题测试复习之搜索专题 题解

 5 years ago
source link: https://beyondlimits.site/432.html?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

哇真的很难受。搜索作为NOIP中常可以用来骗分的方法，我居然在考试中只得了130，真心难受。

考完试重新想想，发现其实并不难，之所以想不出来是因为刷题量没有达到。

不扯了，看题吧。

1.水题（ 这只是题目 ）

原题题目链接： https://www.luogu.org/problemnew/show/P1215

题目大意：给出a,b,c三个容器，分别拥有其对应的大小，最开始c中是满的，c可以向其余两个容器中倒水，要么倒满，要么把自己所有剩余的水倒进去，要求出当a容器为空时，c容器中的水有多少的所有情况（升序）。

思路：纯dfs，加个记忆化搜索，就能过了。如其名，较水。

代码：

#include <cstdio>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
int a,b,c,num,ans[1050];
bool vis[25][25][25];
set<int> water;
inline void dfs(int nowa,int nowb,int nowc)
{
    if(vis[nowa][nowb][nowc]) return ;
    if(nowa==0) water.insert(nowc);
    vis[nowa][nowb][nowc]=true;
    if(nowc)//如果还有水
    {
        if(nowa<a) dfs(min(nowa+nowc,a),nowb,nowc-(min(nowa+nowc,a)-nowa));//判断是倒满还是倒光
        if(nowb<b) dfs(nowa,min(nowb+nowc,b),nowc-(min(nowb+nowc,b)-nowb));
    }
    if(nowb)//同上
    {
        if(nowa<a) dfs(min(nowa+nowb,a),nowb-(min(nowa+nowb,a)-nowa),nowc);
        if(nowc<c) dfs(nowa,nowb-(min(nowc+nowb,c)-nowc),min(nowc+nowb,c));
    }
    if(nowa)
    {
        if(nowb<b) dfs(nowa-(min(nowb+nowa,b)-nowb),min(nowb+nowa,b),nowc);
        if(nowc<c) dfs(nowa-(min(nowc+nowa,c)-nowc),nowb,min(nowc+nowa,c));
    }
    return ;
}
int main()
{
    cin>>a>>b>>c;
    dfs(0,0,c);
    for(set<int>::iterator it=water.begin();it!=water.end();it++) cout<<*it<<" ";
    return 0;
}

2 .愚蠢的 质监员(NOIP2011 提高组day2 第二题）

原题题目链接： https://www.luogu.org/problemnew/show/P1314

题目大意：给定一批石头，以及其重量与价值，给定几个区间，让你选一个参照值，利用一个给定的公式算出匹配值，使得区间内匹配值的和与给定的标准值绝对值之差最小，输出这个差。

思路：在考试的时候我是直接按着这个公式模拟，通过观察数据，我选择从后往前遍历，最后获得了30分的暴力分，其余点都超时。其实正解是 二分查找+前缀和优化 。看题中所给的公式，因为是和*和，所以前缀和应该是很容易想到的。不加前缀和复杂度为o(m*n),而加上前缀和后成为了o(2*n)，大大减少了时间。而二分查找，我们发现公式求出来的和其实是一个递增到递减的过程，所以我们就很容易写出二分查找时边界改变的条件。

代码：

30分：直接模拟没有任何其他的技术含量 

#include <cstdio>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,f,wf,l[200001],r[200001],Max=-1,Min=1<<30;
long long s,sum,x,y;
struct fyn
{
    int w,v;
}stone[400001];
inline int read()
{
    int w=0,x=0;
    char ch=0;
    while(!isdigit(ch))
    {
        w|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return w?-x:x;
}
inline void calc(int wmax)
{
    sum=0;
    for(register int i=1;i<=m;i++)
    {
        int left=l[i],right=r[i];
        x=y=0;
        for(register int j=left;j<=right;j++)
        {
            if(stone[j].w<wmax) continue;
            else
            {
                x++;
                y+=stone[j].v;
            }
        }
        sum+=x*y;
    }
}
int main()
{
    n=read();
    m=read();
    s=read();
    for(register int i=1;i<=n;i++) stone[i].w=read(),stone[i].v=read(),Max=max(Max,stone[i].w);
    for(register int i=1;i<=m;i++) l[i]=read(),r[i]=read();
    for(register int i=n;i>=1;i--)
    {
        calc(stone[i].w);
        if(abs(sum-s)<Min) Min=abs(sum-s);
    }
    cout<<Min<<endl;
    return 0;
}

100分：

#include <cstdio>
#include <iostream>
#include <cctype>
#include <cmath>
#include <cstring>
#include <algorithm>
const long long INF=9999999999999999;
typedef long long ll;
using namespace std;
int w[200001],v[200001],MAXW=-1,MINW=2147483647,mid,n,m,l[200001],r[200001];
ll abss,sum,pw[200001],pv[200001],s;
inline long long read()
{
    long long e=0,x=0;
    char ch=0;
    while(!isdigit(ch))
    {
        e|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return e?-x:x;
}
inline bool check(int W)
{
    sum=0,abss=0;
    memset(pw,0,sizeof(pw));
    memset(pv,0,sizeof(pv));
    for(register int i=1;i<=n;i++)
    {
        if(w[i]>=W) pw[i]=pw[i-1]+1,pv[i]=pv[i-1]+v[i];//如果大于参考值，就一定可以选上
        else pw[i]=pw[i-1],pv[i]=pv[i-1];
    }
    for(register int i=1;i<=m;i++) abss+=(pw[r[i]]-pw[l[i]-1])*(pv[r[i]]-pv[l[i]-1]);//边界问题十分重要!!!
    sum=llabs(abss-s);
    if(abss>s) return true;
    else return false;
}
int main()
{
    n=read();
    m=read();
    s=read();
    for(register int i=1;i<=n;i++)
    {
        w[i]=read();
        v[i]=read();
        MAXW=max(MAXW,w[i]);
        MINW=min(MINW,w[i]);//记录边界
    }
    for(register int i=1;i<=m;i++)
    {
        l[i]=read();
        r[i]=read();
    }
    int left=MINW-1,right=MAXW+2,mid;//把left开成MINW-1,right开成MAXW+2(取MAXW+1时即为W比所有都大，Y是0，这个情况要考虑，所以+2包含MAXN+1)就可以包含左右端点的情况了。
    ll ans=INF;
    while(left<=right)
    {
        mid=(left+right)>>1;
        if(check(mid)) left=mid+1;
        else right=mid-1;
        ans=min(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}

3.麻将

题目链接： https://www.luogu.org/problemnew/show/U36377

题目大意：给出14张麻将，给出麻将的规则，求出打出哪张牌会使自己听的牌更多，输出编号靠前的最优解。

思考：当时考试的时候看到这道题完全懵逼，因为自己完全不会打麻将，看到题目也懵逼了，20mins后才推出了样例。所以这道题最后只骗了个样例和特殊值，最后得了0分。很惨。其实考完试后看题解，又是个纯搜索。判断一些情况。

我们可以暴力枚举打出每一张牌，并从牌堆中再摸一张牌，用dfs判断是否为胡牌。

按照三种牌的类型和9个点数依次搜索，当前点数和类型的牌搜完指的是它和之前点数的牌都得到应有的安排，每层搜索都必须确保搜完才能进入下一层，否则，如果有牌没法和别的牌凑成句子或将，就证明当前情况不能胡牌。

用全局变量flag记录是否胡牌，当某种情况可以胡牌时，赋值true，之后回溯时再不进行任何向下搜索，直接返回退出dfs。

用变量gen记录是否已经凑出将牌，如果已经凑出，此后不再考虑将牌的情况。

分为几种情况：

（1)当前搜到了点数10，即当前类型的牌搜完了，继续搜下一种类型的牌，如果已经彻底搜完了，就证明可以胡牌.

（2）当前点数和类型没有牌，继续下一层搜索；

（3）当前点数小于等于7并且其后两个点数都有牌，那么这三张牌可以当做一个句子。

（4）当前点数和类型牌的张数大于3，那么这三张牌可以当做一个句子。

（5）当前点数和类型牌的张数大于2，那么这两张牌可以当做一副将牌。

最后可以用一个数组在输入时就记录这种牌出现的位置。

代码：（建议先看懂上面总结出来的情况后阅读，基本上看一遍就懂了）

#include <cstdio>
#include <iostream>
using namespace std;
int x,a,spe,num1,num2,p[4][20],f[4][20];
bool flag;
char b;
void dfs(int kind,int num,bool gen)
{
    if(num==10)//刚才的情况1
    {
        if(kind==4) flag=true;
        else if(!flag) dfs(kind+1,1,gen);
        return ;
    }
    if(!p[kind][num])
    {
        dfs(kind,num+1,gen);
        return ;
    }
    if(num<=7)
    {
        if(p[kind][num+1]&&p[kind][num+2])
        {
            --p[kind][num];
            --p[kind][num+1];
            --p[kind][num+2];
            if(!flag) p[kind][num]?dfs(kind,num,gen):dfs(kind,num+1,gen);
            ++p[kind][num];
            ++p[kind][num+1];
            ++p[kind][num+2];//回溯
        }
    }
    if(p[kind][num]>=3)
    {
        p[kind][num]-=3;
        if(!flag) p[kind][num]?dfs(kind,num,gen):dfs(kind,num+1,gen);
        p[kind][num]+=3;
    }
    if(p[kind][num]>=2&&!gen)
    {
        p[kind][num]-=2;
        if(!flag) p[kind][num]?dfs(kind,num,true):dfs(kind,num+1,true);
        p[kind][num]+=2;
    }
    return ;
}
int main()
{
    for(register int i=1;i<=14;i++)
    {
        scanf("%d %c",&a,&b);
        if(b=='w')
        {
            ++p[1][a];
            if(!f[1][a]) f[1][a]=i;//记录第一次出现的位置因为标号要求靠前
        } 
        else if(b=='p')
        {
            ++p[2][a];
            if(!f[2][a]) f[2][a]=i;
        } 
        else if(b=='s')
        {
            ++p[3][a];
            if(!f[3][a]) f[3][a]=i;
        } 
    }
    for(register int i=1;i<=3;i++)
    {
        for(register int j=1;j<=9;j++)//枚举目前的每一种情况
      {
      	if(!p[i][j]) continue;
      	--p[i][j];//模拟打出这张牌
      	spe=0;//临时变量，记录听牌数量，需要及时清零
      	for(register int k=1;k<=3;k++)
      	{
      		for(register int l=1;l<=9;l++)
      	  	{
      	  		++p[k][l];
      	  		dfs(1,1,false);//false表示目前还未找到将牌
      	  		if(flag)
      	  		{
      	  			spe+=4-p[k][l]+1;//每张牌的数量开始为4，用4减去自己拥有的，+1是因为刚刚我们模拟又摸进来了一张牌
      	  			flag=false;
      	  		}
      	  		--p[k][l];
      		}
      	}
      	if(spe>num2)
      	{
      		num2=spe;
      		num1=f[i][j];
      	}
      	++p[i][j];//“回溯”
     } 
   }
    cout<<num1<<" "<<num2<<endl;
    return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK