NOIP2018 货币系统

一道看起来像数论题的完全背包问题。
幸好我前一天没有仔细看数论,使得我想的是写暴力…要不然我可能真的会推一个小时的\(EXGCD\)或\(CRT\)或者高斯消元之类的东西。
总之是小凯的疑惑迷惑了我,以为是一道数论题,所以到最后我都以为自己写的是暴力。
结果发现其实是正解思路的,已经写到了正解的倒数第二步,随便一优化就通过了。
但是始终以为是打暴力。
果然还是太菜了。
题意简述:你有\(n\)个正整数,要求,确定一个最小的\(m\),使得用\(m\)种正整数数能够表示的数集与题目给出数能够表示的数集的完全一致。
首先我们证明一个定理:答案的\(m\)个数一定是原有数的子集。
下面我们分两类考虑这个问题。
如果新的数可以被原有数表示,那么显然它是没有意义的。
如果新的数不能被原有数表示,那么显然它是不合法的。
那么我们只需要考虑删除哪些数即可。
我们发现,一个数需要删除,当且仅当它可以被其他数表达出来。
反证法:如果它不可被其他数表示的话,那么删除它以后它就无法表示出来了。
并且,我们可以发现,这个问题满足最优子结构:如果一个数可以被当前的系统表达出来,那么删除当前系统中任意一些可以被表达出来的数,都不会导致这个数不能被表达出来。
故而,先删哪个其实都不影响答案的正确性。
因此我们可以从小往大删(可能可以节省时间)
暴力地考虑,我们需要枚举值域内每一个已经可以被表达出来的数,然后将这个数加上当前数的任意倍(值域范围内)
这么做最坏可能是\(O(T*n*a^2)\)的。
考虑优化。用欧拉筛的思想,对于每一个数,我们只需要加上当前数的一倍即可。
因为,如果加上当前数的两倍的话,就会在之后再一次访问到这个数,这时候就产生了访问次数上的浪费。
这样做是\(O(T*n*a)\)。
那就做完了。

#include<cstdio>
#include<iostream>
#include<algorithm> 
#include<cstring>

int n,a[105];
bool usf[25005];
void init(){
	std::memset(usf,0,sizeof(usf));
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	if(n==1){
		puts("1");
		return;
	}
	std::sort(a+1,a+1+n);
	int cnt=n;
	usf[0]=1;
	for(int i=1;i*a[1]<=25000;++i){
		usf[i*a[1]]=1;
	}
	for(int i=2;i<=n;++i){
		if(usf[a[i]]){
			a[i]=0;
			--cnt;
		}else{
			for(int j=0;j+a[i]<=25000;++j){
				if(!usf[j]){
					continue;
				}else{
					usf[j+a[i]]=1;
				}
			}
		}
	}
	printf("%d\n",cnt);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

 

lp2831 NOIP2016 愤怒的小鸟

看到\(n<=18\),很容易可以想到状压\(DP\)。
最大力的做法就是,枚举原集合和转移的目的集合,然后考虑一条抛物线能否穿过其中的所有点。
但是这样的复杂度显然是不可接受的,考虑优化。
易知,三点确定一条抛物线,故而在给定\(c=0\)的时候,确定两点即可确定第三点。具体的方程组是:
$$a=\frac{x_{j}*y_{i}-x_{i}*y{j}}{x_{i}*x_{j}*(x_{i}-x_{j})}$$
$$b=\frac{y_{i}}{x_{i}}-a*x_{i}$$
从而我们可以预处理出,通过某两个点的抛物线通过的点的集合,然后对于每一个状态,选择哪两个点拓展即可。
但这个时候的时间复杂度是\(O(T*n^2*2^n)\),对于较大的数据还是很难通过的。
这时候我们可以发现,第一个选择的点是可以固定的,也就是第一个可选择的点。因为如果选择其他点开始拓展的话,到最后依然要拓展那个点。
那么就成功地将复杂度压缩到了\(O(T*n*2^n)\),这时候就可以通过了。
PS:凡是Double的题都应该注意精度。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define eps 1E-6
int n,m;
int f[1<<18],A[20][20];
double x[20],y[20];
inline int lwbt(const int &_X){
    return _X&-_X;
}
inline int Min(const int &_X,const int &_Y){
    return _X<_Y?_X:_Y;
}
inline int cnt(int _X){
    int rt=0;
    while(_X&1){
        ++rt;
        _X>>=1;
    }
    return rt;
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i){
        scanf("%lf%lf",&x[i],&y[i]);
    }
    double a,b;
    for(int i=0;i<n;++i){
        for(int j=i;j<n;++j){
            if(x[i]-x[j]<=eps&&x[i]-x[j]>=-eps){
                if(!(y[i]-y[j]<=eps&&y[i]-y[j]>=-eps)){
                    A[i][j]=0;
                    continue;
                }else{
                    A[i][j]=(1<<i)|(1<<j);
                    continue;
                }
            }
            a=(x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j]));
            b=y[i]/x[i]-a*x[i];
            A[i][j]=0;
            if(a>=-eps){
                continue;
            }
            for(int k=0;k<n;++k){
                if(a*x[k]*x[k]+b*x[k]-y[k]<=eps&&a*x[k]*x[k]+b*x[k]-y[k]>=-eps){
                    A[i][j]|=(1<<k);
                }
            }
        }
    }
    /*
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            printf("%d ",A[i][j]);
        }
        puts("");
    }
    */
    const int MAX=1<<n;
    int loc;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    
    for(int i=0;i<MAX;++i){
        loc=cnt(i);
        for(int j=loc;j<n;++j){
            f[i|A[loc][j]]=Min(f[i|A[loc][j]],f[i]+1);
        }
    }
    printf("%d\n",f[MAX-1]);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

lp1850 NOIP2016 换教室

一道优\(d\acute{u}\)秀\(li\acute{u}\)的期望DP。
简述题意:
原有一个包括\(n\)个节点的路径,你可以用\(m\)次操作,每一次操作可以把第\(i\)个节点从\(c_{i}\)换到\(b_{i}\)。
对于每一次操作,有\(p_{i}\)的概率成功。求最优决策下路径长度的期望。

首先考虑到是稠密图,故考虑用邻接矩阵来处理。不过需要注意读入时应当取较小值,以及每个点到其本身的距离为\(0\)
首先用\(Floyd\)预处理出所有点之间的距离。然后我们定义\(f_{i,j,k}\)表示,当前在决定第\(i\)个节点,已经使用了\(j\)次机会,当前选择为\(k\)时的期望路径长度。
那么我们考虑转移。
对于每一个状态,我们有两种选择:使用机会或者不使用机会。故而我们尝试推理状态转移方程:
首先,如果不使用机会的话,有两种情况可以转移过来,分别是,上一次使用了机会,或者上一次没有使用机会,故:
$$f_{i,j,0}=Min(f_{i-1,j,0}+mp_{c_{i-1},c_{i}},$$
$$f_{i-1,j,1}+mp_{d_{i-1},c_{i}}*p_{i-1}+mp_{c_{i-1},c_{i}}*(1-p_{i-1}));$$
如果在这个点使用机会且成功的话,则有:
$$f_{i,j-1,1}=Min(f_{i-1,j-1,0}+mp_{c_{i-1},d_{i}}*p_{i}+mp_{c_{i-1},c_{i}}*(1-p_{i}),$$
$$f_{i-1,j-1,1}+m(p_{d_{i-1},d_{i}}*p_{i-1}+mp_{c_{i-1},d_{i}}*(1-p_{i-1}))*p_{i}+$$
$$(mp_{d_{i-1},c_{i}}*p_{i-1}+mp_{c_{i-1},c_{i}}*(1-p_{i-1}))*(1-p_{i});$$
然后,只需要走到终点即可,因此:
$$ Ans=Min(f_{N,i,j})\ (i\in [0,M],j\in [0,1])$$

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int mp[305][305],N,M,V,E;
int c[2005],d[2005];
double p[2005],f[2005][2005][2];
void init(){
    memset(mp,0x3f,sizeof(mp));
    scanf("%d%d%d%d",&N,&M,&V,&E);
    for(int i=1;i<=N;++i){
        scanf("%d",&c[i]);
    }
    for(int i=1;i<=N;++i){
        scanf("%d",&d[i]);
    }
    for(int i=1;i<=N;++i){
        scanf("%lf",&p[i]);
    }
    int u,v,w;
    for(int i=1;i<=E;++i){
        scanf("%d%d%d",&u,&v,&w);
        mp[u][v]=Min(mp[u][v],w),mp[v][u]=Min(mp[u][v],w);
    }
    for(int i=1;i<=V;++i){
        mp[i][i]=0;
    }
    for(int k=1;k<=V;++k){
        for(int i=1;i<=V;++i){
            for(int j=1;j<=V;++j){
                mp[i][j]=Min(mp[i][j],mp[i][k]+mp[k][j]); 
            }
        }
    }
    for(int i=1;i<=N;++i){
        for(int j=0;j<=M;++j){
            for(int k=0;k<=1;++k){
                f[i][j][k]=1000007;
            }
        }
    }
    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=N;++i){
        for(int j=0;j<=M;++j){
            f[i][j][0]=Min(f[i-1][j][0]+mp[c[i-1]][c[i]],f[i-1][j][1]+mp[d[i-1]][c[i]]*p[i-1]+mp[c[i-1]][c[i]]*(1-p[i-1]));
            if(!j){
                continue;
            }
            f[i][j][1]=Min(f[i-1][j-1][0]+mp[c[i-1]][d[i]]*p[i]+mp[c[i-1]][c[i]]*(1-p[i]),f[i-1][j-1][1]+(mp[d[i-1]][d[i]]*p[i-1]+mp[c[i-1]][d[i]]*(1-p[i-1]))*p[i]+(mp[d[i-1]][c[i]]*p[i-1]+mp[c[i-1]][c[i]]*(1-p[i-1]))*(1-p[i]));
        }
    }
    double ans=1000007;
    for(int i=0;i<=M;++i){
        for(int j=0;j<2;++j){
            ans=Min(ans,f[N][i][j]);
        }
    }
    /*
    for(int i=1;i<=N;++i){
        for(int j=0;j<=M;++j){
            for(int k=0;k<2;++k){
                printf("%.2lf ",f[i][j][k]);
            }
            printf("|");
        }
        puts("");
    }
    */
    printf("%.2lf",ans);
}
int main(){
    init();
    return 0;
}

 

lp3959 NOIP2017 宝藏

我们首先,如果两个点之间有连多条边,肯定只有最短的那条最优。
那么我们进行状压,对于某一个状态\(S_{0}\),我们维护它的所有拓展的集合\(T_{S_{1}}\)
然后,记\(f_{i,k}\)表示,当前状态为\(i\),当前的深度为\(k\)时的最小花费。
这样拓展,每一次拓展都相当于把深度加深了一层,因此就可以不要花费太多的精力去考虑\(k\)对贡献的影响。
而,从某一个根开始拓展,即相当于\(f_{(1<<i),0}\)
于是我们便可以开始DP。每一次拓展都会将可行集合纳入范围。这样拓展的花费也是可以被轻松计算出来的。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int n,m,f[1<<12][12],usf[1<<12];
int mp[15][15];
void init(){
    scanf("%d%d",&n,&m);
    int u,v,w;
    memset(mp,0x3f,sizeof(mp));
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        --u,--v; 
        mp[u][v]=Min(mp[u][v],w);
        mp[v][u]=Min(mp[v][u],w);
    }
    const int MAX=1<<n;
    for(int i=1;i<MAX;++i){
        for(int j=0;j<n;++j){
            if((i|(1<<j))!=i){
                continue;
            }
            for(int k=0;k<n;++k){
                if(mp[j][k]!=0x3f3f3f3f){
                    usf[i]|=(1<<k);
                }
            }
        }
    }
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<n;++i){
        mp[i][i]=0;
        f[1<<i][0]=0;
    }
    long long sm,nw,x;
    for(int i=2;i<MAX;++i){
        for(int j=i-1;j;j=(j-1)&i){
            if(((usf[i]|j)!=usf[i])){
                continue;
            }
            sm=0,nw=i^j;
            for(int k=0;k<n;++k){
                if((nw>>k)&1){
                    x=0x3f3f3f3f;
                    for(int l=0;l<n;++l){
                        if((j>>l)&1){
                            x=Min(x,mp[l][k]);
                        }
                    }
                    sm+=x;
                }
            }
            for(int k=1;k<n;++k){
                f[i][k]=Min(f[i][k],f[j][k-1]+sm*k);
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<n;++i){
        ans=Min(ans,f[MAX-1][i]);
    }
    printf("%d\n",ans);
}
int main(){
    init();
    return 0;
}