当前位置：首页 > news >正文

搜索——P5194 [USACO05DEC]Scales S+P5440 【XR-2】奇迹+P1378 油滴扩展

news 来源：原创 2024/11/30 0:49:06

传送门：[USACO05DEC]Scales S - 洛谷

思路: 题意简化为给出一堆数字，求不超过给定限制C的情况下最大可以拼出的数字,第一眼看过去感觉可以用01背包，但是C的范围太大不行，用搜索的话也没什么特征，只能2^n爆搜，n的范围1000....，这时候根据题目中的一个重要条件，第三项开始每一项大于等于前两项的和，根据斐波那契数列，最多好像到40还是50项就已经超过2^30了，因此题目里面的n的实际范围最多也就到50，根本就没有1000，这时候再给它一点小小的剪枝震撼就能过了

剪枝1:从大到小开始枚举，这样子搜索分支会少很多

剪枝2:利用前缀和的思想，当某个数后面所有数字的和都当前的数字和加起来都已经小于C时就直接可以全部加上了

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int d[50],sum[50];
int n,ans,c;
void dfs(int idx,int x)
{
    ans=max(ans,x);
    if(idx>n)
        return;
    if(sum[idx]<=c-x)
    {
        ans=max(sum[idx]+x,ans);
        return;
    }
    if(d[idx]+x<=c)
        dfs(idx+1,d[idx]+x);
    dfs(idx+1,x);
}
signed main()
{
    scanf("%lld%lld",&n,&c);
    for(int i=n;i>=1;i--)
    {
        cin>>d[i];
        sum[i]=sum[i+1]+d[i];
    }
    dfs(1,0);
    cout<<ans<<endl;
	return 0;
}

传送门:【XR-2】奇迹 - 洛谷

思路: 题意如题面所示，按照出题人的解法就是将所有符合条件的8位数日期都预处理出来，每输入一个新的不确定日期就遍历所有预处理出来的日期看在相应位置有没有符合条件的。

1.处理出(日:xx)以及(月日:xxxx)是质数的4位数日期

2.再找(年份:xxxx)加上(月日:xxxx)是质数的8位数日期

3.对于闰年的特殊判断因为29和229都是质数，找出所有xxxx0229是质数的日期

4.对输入进行一一比对

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int p[]={0,3,5,7,11,13,17,19,23,29,31,9999};
map<int,int>mp;
int ans[N],cnt;
int b[200],cnt1;
char s[10];
bool is_primes(int x)
{
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
            return false;
    }
    return true;
}
signed main()
{
    for(int i=1;i<=12;i++)
    {
        for(int j=3;j<=d[i];j++)
            if(is_primes(j)&&is_primes(i*100+j))
             b[++cnt1]=i*100+j;
    }
    for(int i=4;i<=9999;i+=4)
        if((i%100!=0||i%400==0)&&is_primes(i*10000+229))
           ans[++cnt]=i*10000+229;

    for(int i=1;i<=9999;i++)
    for(int j=1;j<=cnt1;j++)
        if(is_primes(i*10000+b[j]))
           ans[++cnt]=i*10000+b[j];
    int T;
    scanf("%lld",&T);
    while(T--)
    {
        int t=0;
        scanf("%s",s+1);
        for(int i=1;i<=cnt;i++)
        {
            int k=ans[i];
            int flag=1;
            for(int j=8;flag&&j>=1;j--,k/=10)
                if(s[j]!='-'&&s[j]-'0'!=k%10)
                flag=0;
           t+=flag;
        }
        cout<<t<<endl;

    }

	return 0;
}

传送门:油滴扩展 - 洛谷

思路: n个数全排列的时间复杂度，从一个点扩展时要看点到四个墙壁的最短距离以及另一些油滴圈的最短距离

有一个注意的要点就是:如果当前要扩展的点已经在别的油滴圈内则不能再扩展了

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const double PI=3.1415926535;
const int N=1e6+10;
int n;
struct{
    double r;
    double x,y;
    bool in;
}a[10];
bool st[10];
double x,y,x1,y11;
double ans;
double cal(int i)
{
    double s=min(abs(a[i].x-x),abs(a[i].x-x1));
    s=min(s,min(abs(a[i].y-y),abs(a[i].y-y11)));
    for(int j=1;j<=n;j++)
    if(i!=j&&st[j])
    {
        double d=sqrt(pow(a[i].x-a[j].x,2)+pow(a[i].y-a[j].y,2));
        s=min(s,max(0.0,d-a[j].r));
    }
    return s;
}
void dfs(int t,double sum)
{
    if(t>n)
    {
        ans=max(ans,sum);

    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            a[i].r=cal(i);
            st[i]=true;
            dfs(t+1,sum+a[i].r*a[i].r*PI);
            st[i]=false;
        }
    }
}
signed main()
{
    scanf("%lld",&n);
    cin>>x>>y>>x1>>y11;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    dfs(1,0);
    double sum=abs(x1-x)*abs(y11-y);
    cout<<(int)(sum-ans+0.5)<<endl;
	return 0;
}