你是？不会是文山的吧。
专题三 NOIP2009
//by wanda1416 版权归原作者
第二题(Hankson 的趣味题, son)
Gcd(x,a0)=a1, Gcd(x,b0)=xb0/b1
设f(a,b) 代表b这个质因子在a中有多少个.
对于a0的任意质因子t, 若f(a0,t)=f(a1,t) 则只需保证f(x,t)≥f(a1,t), 否则f(x,t)=f(a1,t)
对于b1的任意质因子t, 若f(b1,t)=f(b0,t) 则只需保证0≤f(x,t)≤f(b1,t), 否则f(x,t)=f(b1,t)
由于x的所有因子都是b1的子集, 所以我们只需对b1的质因子按如上方法逐个检查这个质因子在x里面的取值范围(若为空则说明无解), 并按照乘法原理统计即可.
关于分解质因子: 由于b1不会超过2*10^9, 大于50000的质因子不会超过1个, 所以我们只要打出50000以内的素数表即可, 若最后除剩的b1仍未除尽, 说明此时b1一定是一个大于50000的素数.
第三题(最优贸易, trade):
做法1:
设Low[i]为从1到i当前所有路径中最便宜的价格. Profit[i]为从1到i当前所有路径中最大获利. 初始时Low[1]=P[1], Low[2..n]=infinity, Profit[1..n]=0.
那么我们可以从1开始广搜, 要注意一个点有可能多次被更新.
从i可以更新到j的条件是:
1. 存在有向/无向边(i,j)
2. Low[j]>Low[i] 或 Profit[j]
做法2:
首先考虑没有环的情况, 此时1,n之间要么无法连通, 要么只存在一些单向的无环路径. 对于每一条路径, 由于不能”回头”, 走到某个点i的极优获利显然是i的费用-路径上此点之前的点的最小费用, 而此路径的最大获利便是取获利最大的点.
但是还有很多数据是有环的, 也就是对于有些点对(a,b), 在a走到b之后, b仍然可以走回到a. 在图论中, 我们把点集V, 其中任意两个点可以互达, 叫做强连通分量.
由于强连通分量中的点可以互相到达, 所以在一个强连通中的最大获利就是强连通中最贵的-最便宜的. 我们把所有强连通分量求出来缩为两个点之后. 1与n之间只存在一些无环路径, 对于这些单向的无环路径我们只需要扫描一遍便可求出最大获利.
强连通缩为两个点的具体做法: 把一个强连通缩为a,b 两个点, 连(a,b)边, a的费用为强连通中最便宜的, b的费用为强连通中最贵的. 把指向强连通中任何一个点的所有边改为指向a, 把强连通中任何一点指向强连通外部的边改为由b指出. 这样构出来的保证与原图等价.
第四题(靶形数独, sudoku)
注：很直白的搜索, 由于数独是NP-H问题, 所以我们肯定只能用搜索, 那么关键就在于剪枝了, 我们发现, 对于每个格子都有一个取值范围, 这个范围由其横行/纵行/小九宫格中已填的数决定, 那么无疑我们每次搜索选取值范围最小的格子搜是比较优的.
NOIP2009靶形数独解题报告
这题困扰了我差不多有一年之久，今天终于解出来了。以下是我的解题报告：
【题目大意】
给出一个数独，部分位置已经填上了数，每个格子(x, y) (1 <= x, y <= 9)有一个权值w(x, y)，试找出一种填数独的方案，使得所有格子所填的数字乘以权值之积的和最大，并将这个最大值输出。如果该数独无解，输出-1。
【题目分析】
数独问题是个非常经典的NP完全问题，没有多项式的算法，只能搜索。
首先可以想到枚举，但数据给出的数独空格非常多，最多可能有9^57种状态，是效率极低的算法，对于本题的数据是无法得分的。
进一步分析可以想到递归回溯，遇到每个空格，枚举该空格所在的行、列、小九宫已填了哪些数，得出空格可填的数，分别填上这些数并进行下一层的搜索。这样的方法已经远优于枚举，但对于本题大部分数据还是无法出解（实际测试可以得到40%的分数）。为了加快计算一个格子可填的数的速度，我们可以把每行、每列、每个九宫格可填的数用二进制集合表示，每个格子(x, y)当前可填的数的集合就是第x行、第y列以及(x, y)所在小九宫的可填的数集求交。这个操作可以用位运算实现。这样，找可填的数的时间就大大缩短了。实际测试中可以得到75%的分数。
上面的方法所得的分数在考场上已经是相当可观，但本题还有进一步的优化余地。
有时在数独下方会有一些格子只有一两个可填的数字，而在数独上方的一些格子可能会有很多可填的数字。这时如果按照从上往下搜索的顺序搜索，将会扩展出很多无用的状态。如果是用人脑来做数独的话，必定会先填可行方案少的格子，来给其它格子更多的限制，这样可以剪去很多不可行的分支。所以我们可以预处理求出每个空格可填的方案数，并对它们进行排序。按照这个顺序搜索，将可以得到85%的分数。
注意到前面填的数会对后面与它同行、同列、同小九宫的格子造成影响，后面的可填数大小顺序可能有改变。可以考虑在填了一个格子之后，找出后面待填的格子中可填数最少的格子，进行进一步的搜索。这个方法的表现非常优秀，在实际测试中得到了满分。
//靶形数独代码
#include
#include
#include
#define INF 2000000000
#define CE 5.0
using namespace std;
const int score[9][9]={
6,6,6,6,6,6,6,6,6,
6,7,7,7,7,7,7,7,6,
6,7,8,8,8,8,8,7,6,
6,7,8,9,9,9,8,7,6,
6,7,8,9,10,9,8,7,6,
6,7,8,9,9,9,8,7,6,
6,7,8,8,8,8,8,7,6,
6,7,7,7,7,7,7,7,6,
6,6,6,6,6,6,6,6,6
};
bool grd[9][9];
bool row[9][9],col[9][9];
int a[9][9];
int list[9*9],rsl[9*9];
bool used[9*9];
int maxs,stC,num;
void input(){
memset(grd,0,sizeof(grd));
memset(row,0,sizeof(row));
memset(col,0,sizeof(col));
memset(a,0,sizeof(a));
memset(used,0,sizeof(used));
int x;
stC=0;
num=0;
for(int i=0;i<9;++i)
for(int j=0;j<9;++j)
{
scanf("%d",&x);
stC+=x*score[i][j];
a[i][j]=x;
if(x!=0) {
x--;
row[i][x]=col[j][x]=true;
grd[i/3*3+j/3][x]=true;
}else {
list[num]=i*9+j;
rsl[num++]=score[i][j];
}
}
}
template
void swap(Type &x,Type &y)
{
Type tm=x;x=y;y=tm;
}
void dfs(int sc)
{
if(sc>maxs) maxs=sc;
int cur;
int x,y,z,w=-1;
double scr,Min=INF;//find the minimal point
for(int i=0;i
{
x=list[i]/9;
y=list[i]%9;
scr=0;
for(int j=0;j<9;++j)
if(!row[x][j]&&!col[y][j]&&!grd[x/3*3+y/3][j])
scr+=1;
scr+=(score[x][y]/CE);
if(scr
if(w==-1) return ;
cur=w;
used[cur]=true;
//main process
x=list[cur]/9;
y=list[cur]%9;
z=x/3*3+y/3;
for(int i=8;i>=0;--i)
{
if(!row[x][i]&&!col[y][i]&&!grd[z][i])
{
row[x][i]=col[y][i]=grd[z][i]=true;
dfs(sc+(i+1)*rsl[cur]);
row[x][i]=col[y][i]=grd[z][i]=false;
}
}
used[cur]=false;
}
int main()
{
freopen("sudoku.in","r",stdin);
freopen("sudoku.out","w",stdout);
input();
maxs=-INF;
dfs(stC);
if(maxs==-INF) printf("-1\n");
else printf("%d\n",maxs);
return 0;
}
附：A*搜索
来源于: GameDev.net
作 者: Patrick Lester [pwlester@policyalmanac.org]
翻 译: 孙璨 [tlwanan@gmail.com]
虽然A*（读作A星）算法对初学者来说是比较深奥难懂，但是一旦你找到门路了，它又会变得非常简单。网上有很多解释A*算法的文章，但是大多数是写给那些有一定基础的人看的，而您看到的这一篇呢，是真正写给菜鸟的。
本篇文章并不想给这个算法题目作一些权威性论断，而是阐述它的基本原理，并为你理解更多相关资料与讨论打下基础。文章末尾给出了一些比较好的链接，放在“进阶阅读”一节之后。
最后，本文不是编程规范，你将可能使这里讲述的东西编写成任何计算机语言。在本文的末尾我还给出了一个例子程序包的下载链接，也许正合你意。在这个包中有C++和Blitz Basic两个版本的程序代码，如果你只是想看看A*算法是如何运作的，该包中也有可直接执行的文件供你研究。
我们还是要超越自己的（把算法弄懂），所以，让我们从头开始吧！
初步：搜索区域
我们假设某个人要从A点到达B点，而一堵墙把这两个点隔开了，如下图所示，绿色部分代表起点A，红色部分代表终点B，蓝色方块部分代表之间的墙。
[图一]
你首先会注意到我们把这一块搜索区域分成了一个一个的方格，如此这般，使搜索区域简单化，正是寻找路径的第一步。这种方法将我们的搜索区域简化成了一个普通的二维数组。数组中的每一个元素表示对应的一个方格，该方格的状态被标记为可通过的和不可通过的。通过找出从A点到B点所经过的方格，就能得到AB之间的路径。当路径找出来以后，这个人就可以从一个格子中央移动到另一个格子中央，直到抵达目的地。
这些格子的中点叫做节点。当你在其他地方看到有关寻找路径的东西时，你会经常发现人们在讨论节点。为什么不直接把它们称作方格呢？因为你不一定要把你的搜索区域分隔成方块，矩形、六边形或者其他任何形状都可以。况且节点还有可能位于这些形状内的任何一处呢？在中间、靠着边，或者什么的。我们就用这种设定，因为毕竟这是最简单的情况。
开始搜索
当我们把搜索区域简化成一些很容易操作的节点后，下一步就要构造一个搜索来寻找最短路径。在A*算法中，我们从A点开始，依次检查它的相邻节点，然后照此继续并向外扩展直到找到目的地。
我们通过以下方法来开始搜索：
1. 从A点开始，将A点加入一个专门存放待检验的方格的“开放列表”中。这个开放列表有点像一张购物清单。当前这个列表中只有一个元素，但一会儿将会有更多。列表中包含的方格可能会是你要途经的方格，也可能不是。总之，这是一个包含待检验方格的列表。
2. 检查起点A相邻的所有可达的或者可通过的方格，不用管墙啊，水啊，或者其他什么无效地形，把它们也都加到开放列表中。对于每一个相邻方格，将点A保存为它们的“父方格”。当我们要回溯路径的时候，父方格是一个很重要的元素。稍后我们将详细解释它。
3. 从开放列表中去掉方格A，并把A加入到一个“封闭列表”中。封闭列表存放的是你现在不用再去考虑的方格。
此时你将得到如下图所示的样子。在这张图中，中间深绿色的方格是你的起始方格，所有相邻方格目前都在开放列表中，并且以亮绿色描边。每个相邻方格有一个灰色的指针指向它们的父方格，即起始方格。
[图二]
接下来，我们在开放列表中选一个相邻方格并再重复几次如前所述的过程。但是我们该选哪一个方格呢？具有最小F值的那个。
路径排序
决定哪些方格会形成路径的关键是下面这个等式：
F = G + H
这里 G＝从起点A沿着已生成的路径到一个给定方格的移动开销。
H＝从给定方格到目的方格的估计移动开销。这种方式常叫做试探，有点困惑人吧。其实之所以叫做试探法是因为这只是一个猜测。在找到路径之前我们实际上并不知道实际的距离，因为任何东西都有可能出现在半路上（墙啊，水啊什么的）。本文中给出了一种计算H值的方法，网上还有很多其他文章介绍的不同方法。
我们要的路径是通过反复遍历开放列表并选择具有最小F值的方格来生成的。本文稍后将详细讨论这个过程。我们先进一步看看如何计算那个等式。
如前所述，G是从起点A沿着已生成的路径到一个给定方格的移动开销，在本例中，我们指定每一个水平或者垂直移动的开销为10，对角线移动的开销为14。因为对角线的实际距离是2的平方根（别吓到啦），或者说水平及垂直移动开销的1.414倍。为了简单起见我们用了10和14这两个值。比例大概对就好，我们还因此避免了平方根和小数的计算。这倒不是因为我们笨或者说不喜欢数学，而是因为对电脑来说，计算这样的数字也要快很多。不然的话你会发现寻找路径会非常慢。
我们要沿特定路径计算给定方格的G值，办法就是找出该方格的父方格的G值，并根据与父方格的相对位置（斜角或非斜角方向）来给这个G值加上14或者10。在本例中这个方法将随着离起点方格越来越远计算的方格越来越多而用得越来越多。
有很多方法可以用来估计H值。我们用的这个叫做曼哈顿（Manhattan）方法，即计算通过水平和垂直方向的平移到达目的地所经过的方格数乘以10来得到H值。之所以叫Manhattan方法是因为这就像计算从一个地方移动到另一个地方所经过的城市街区数一样，而通常你是不能斜着穿过街区的。重要的是，在计算H值时并不考虑任何障碍物。因为这是对剩余距离的估计值而不是实际值（通常是要保证估计值不大于实际值――译者注）。这就是为什么这个方式被叫做试探法的原因了。想要了解更多些吗？这里还有更多式子和关于试探法的额外说明。
G和H相加就得到了F。第一步搜索所得到的结果如下图所示。每个方格里都标出了F、G和H值。如起点方格右侧的方格标出的，左上角显示的是F值，左下角是G值，右下角是H值。
[图三]
我们来看看这些方格吧。在有字母的方格中，G＝10，这是因为它在水平方向上离起点只有一个方格远。起点紧挨着的上下左右都具有相同的G值10。对角线方向的方块G值都是14。
H值通过估算到红色目标方格的曼哈顿距离而得出。用这种方法得出的起点右侧方格到红色方格有3个方格远，则该方格H值就是30。上面那个方格有4个方格远（注意只能水平和垂直移动），H就是40。你可以大概看看其他方格的H值是怎么计算出来的。
每一个方格的F值，当然就不过是G和H值之和了。
继续搜索
发了
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ号：24596024