广东微信网站制作报价,培训体系,动漫制作专业可以专升本考什么,查询建筑企业网站目录 1、毕业旅行问题#xff08;今日头条2019笔试题#xff09; 2、蒙德里安的梦想#xff08;算法竞赛进阶指南#xff09; 3、最短Hamilton路径#xff08;《算法竞赛进阶指南》模板#xff09; 4、国际象棋#xff08;第十二届蓝桥杯省赛第二场C A组/B组#… 目录 1、毕业旅行问题今日头条2019笔试题 2、蒙德里安的梦想算法竞赛进阶指南 3、最短Hamilton路径《算法竞赛进阶指南》模板 4、国际象棋第十二届蓝桥杯省赛第二场C A组/B组 5、小国王《信息学奥赛一本通》 SGU223 1、毕业旅行问题今日头条2019笔试题
小明目前在做一份毕业旅行的规划。
打算从北京出发分别去若干个城市然后再回到北京每个城市之间均乘坐高铁且每个城市只去一次。
由于经费有限小明希望能够通过合理的路线安排尽可能的省些路上的花销。
给定一组城市和每对城市之间的火车票的价钱找到每个城市只访问一次并返回起点的最小车费花销。
注意北京为 1 号城市。
输入格式
第一行包含一个正整数 n表示城市个数。
接下来输入一个 n 行 n 列的矩阵表示城市间的车票价钱。
输出格式
输出一个整数表示最小车费花销。
数据范围
1n≤20,包括北京 车票价格均不超过 1000 元。
输入样例
4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0输出样例
13说明
共 4 个城市城市 1 和城市 1 的车费为0城市 1 和城市 2 之间的车费为 2城市 1 和城市 3 之间的车费为 6城市 1 和城市 4 之间的车费为 5以此类推。
假设任意两个城市之间均有单程票可买且价格均在 1000 元以内无需考虑极端情况。
思路
经典的状态压缩求最短路问题每个城市只有两个状态去过或者没去过去过则为1没去过则为0 代码
#includebits/stdc.husing namespace std;int n; const int N20,M120;int w[N][N];int f[M][N];//M表示状态的压缩N代表最后到哪一个城市了 int main()
{cinn;memset(f,0x3f,sizeof f);//每个状态为正无穷表示还没取min for(int i0;in;i){for(int j0;jn;j){scanf(%d,w[i][j]);}}f[1][0]0;//初始的状态需要费用为0 //从1开始表示北京已经去过了 二进制表示为000.....1 for(int i1;i1n;i)//1n-1就是111....1//例如n5的时候15就是100000,减去1就是11111 {for(int j0;jn;j)//北京开始 {//这个状态下终点为j,状态为i if(ij1)//ij表示要到第j个城市这个状态的j位就要是1否则到不了 {for(int k0;kn;k)//从第k个城市转移过来{if((i-(1j))k1)//i中减去第j个城市后还包含k//说明这个状态到过k可以从k转移过来f[i][j]min(f[i][j],f[i-(1j)][k]w[k][j]); } }}}int res131-1;for(int i1;in;i){resmin(res,f[(1n)-1][i]w[i][0]);}coutres;return 0;
} 2、蒙德里安的梦想算法竞赛进阶指南
求把 N×M 的棋盘分割成若干个 1×2 的长方形有多少种方案。
例如当 N2M4 时共有 5 种方案。当 N2M3时共有 3 种方案。
如下图所示 输入格式
输入包含多组测试用例。
每组测试用例占一行包含两个整数 N 和 M。
当输入用例 N0M0 时表示输入终止且该用例无需处理。
输出格式
每个测试用例输出一个结果每个结果占一行。
数据范围
1≤N,M≤11
输入样例
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0输出样例
1
0
1
2
3
5
144
51205思路
先放置完横着放的之后竖着放的方法就是固定的
一个重要的任务就是判断放置的方法是否合法
基本框架 预处理 dp 代码
#includebits/stdc.husing namespace std;const int N12;
const int M111;int n,m;long long f[N][M];//第i列的状态为M j表示出头的方格数量 bool st[M];//用来表示某一种状态是否合法 int main()
{while(cinnm,n || m){memset(f,0,sizeof f);//开始预处理for(int i0;i1n;i)//枚举每一种状态 {int cnt0;//记录连续的空格数量 st[i]true; for(int j0;jn;j){if(ij1)//这个位置不是空格 {if(cnt1)st[i]false;//这个位置之前的连续空格数量是奇数不合法 cnt0;}else cnt;}if(cnt1)st[i]false; }f[0][0]1;//第0列没有上一列所以没有戳出来的//小方块里什么都没有放只有这一种状态 for(int i1;im;i)//枚举列 {for(int j0;j1n;j)//枚举这一列的状态 {for(int k0;k1n;k)//枚举上一列的状态 {if(((jk)0) st[j|k])//(k列加上j列向后伸的格子后要合法){f[i][j]f[i-1][k];}}}} coutf[m][0]endl;}return 0;
}
3、最短Hamilton路径《算法竞赛进阶指南》模板
给定一张 n 个点的带权无向图点从 0∼n−1 标号求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0到 n−1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数 n。
接下来 n 行每行 n 个整数其中第 i 行第 j 个整数表示点 i 到 j 的距离记为 a[i,j]。
对于任意的 x,y,z数据保证 a[x,x]0a[x,y]a[y,x]并且 a[x,y]a[y,z]≥a[x,z]。
输出格式
输出一个整数表示最短 Hamilton 路径的长度。
数据范围
1≤n≤20 0≤a[i,j]≤1e7
输入样例
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0输出样例
18
思路
状态压缩dp模板
代码
#includebits/stdc.husing namespace std;const int N20,M120;int n;int w[N][N];int f[M][N];int main()
{int n;cinn;for(int i0;in;i){for(int j0;jn;j){scanf(%d,w[i][j]);}}//状态压缩dp memset(f,0x3f,sizeof f);//初始为0f[1][0]0;//i1表示第一个点已经走了j0表示目前在第一个点 //从0000.。。1开始 for(int i1;i1n;i){//从起点0开始 for(int j0;jn;j){//只有i包含j这个点才能从i这个状态转移到终点为j的状态 if(ij1){//f[i][k]---k-jfor(int k0;kn;k){if((i-(1j))k1){//(用不包含j点的状态来转移)f[i][j]min(f[i][j],f[i-(1j)][k]w[k][j]);}}}}}int res131-1;//for(int i1;in;i)//{// resmin(res,f[(1n)-1][i]);//}//coutresendl;//标明了终点是n-1所以说直接选终点是n-1的情况 coutf[(1n)-1][n-1];return 0;
}
4、国际象棋第十二届蓝桥杯省赛第二场C A组/B组
众所周知“八皇后” 问题是求解在国际象棋棋盘上摆放 8 个皇后使得两两之间互不攻击的方案数。
已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了意犹未尽。作为一个国际象棋迷他想研究在 N×M 的棋盘上摆放 K 个马使得两两之间互不攻击有多少种摆放方案。
由于方案数可能很大只需计算答案除以 1000000007 (即 1e97) 的余数。
如下图所示国际象棋中的马摆放在棋盘的方格内走 “日” 字位于 (x,y)格的马可以攻击 (x1,y2)、(x1,y−2)、(x−1,y2)、(x−1,y−2)、(x2,y1)、(x2,y−1)、(x−2,y1) 和 (x−2,y−1) 共 8 个格子。 输入格式
输入一行包含三个正整数 N,M,K分别表示棋盘的行数、列数和马的个数。
输出格式
输出一个整数表示摆放的方案数除以 1000000007(即 1e97) 的余数。
数据范围
对于 5%5% 的评测用例K1 对于另外 10%10% 的评测用例K2 对于另外 10%10% 的评测用例N1 对于另外 20%20% 的评测用例N,M≤6K≤5 对于另外 25%25% 的评测用例N≤3M≤20K≤12 对于所有评测用例1≤N≤61≤M≤1001≤K≤20。
输入样例1
1 2 1输出样例1
2输入样例2
4 4 3输出样例2
276输入样例3
3 20 12输出样例3
914051446
思路
枚举思路 代码
#includebits/stdc.husing namespace std;
typedef long long LL;
const int N 110,M6,MOD1e97;
int f[N][1M][1M][21];
int n,m,k;
int get_count(int x)//返回x的二进制有多少个1
{int res0;while(x){res;x-(x-x);}return res;
}
int main()
{scanf(%d%d%d,n,m,k);f[0][0][0][0]1;//状态初始化第0行时状态只能是0只能是放0个马//5层循环比较乱把图画出来照着图写for(int i1;im;i){for(int c0;c1n;c){for(int a0;a1n;a){if((c(a2))||(a(c2))) continue;for(int b0;b1n;b){if(b(a2)||a(b2)) continue;if(b(c1)||c(b1)) continue;int tget_count(b);for(int jt;jk;j)f[i][a][b][j](f[i][a][b][j]f[i-1][c][a][j-t])%MOD;//对应集合划分枚举j,f[i-1][c][a][j-t]都能到达f[i][a][b][j]}}}}int res0;for(int a0;a1n;a){for(int b0;b1n;b){res(resf[m][a][b][k])%MOD;//m,k固定a,b随意}}printf(%d,res);return 0;
}5、小国王《信息学奥赛一本通》 SGU223
在 n×n 的棋盘上放 k 个国王国王可攻击相邻的 8 个格子求使它们无法互相攻击的方案总数。
输入格式
共一行包含两个整数 n 和 k。
输出格式
共一行表示方案总数若不能够放置则输出0。
数据范围
1≤n≤10, 0≤k≤n**2
输入样例
3 2输出样例
16
思路 代码
#includebits/stdc.husing namespace std;typedef long long LL;const int N 11, M 1 N, C N * N;int n, m, K;
LL f[N][C][M];
int cnt[M];
vectorint legal_state;
vectorint state_trans[M];bool check(int state)
{return !(state state 1);
}
int count(int state)
{int res0;while(state){res;state-state -state;}return res;
}
int main()
{cin n K;//预处理所有合法状态for (int st 0; st 1 n; st)//检查当前状态是否合法if (check(st))legal_state.push_back(st),cnt[st] count(st);m legal_state.size();//预处理所有合法状态的合法转移for (auto cur_st: legal_state)for (auto to_st: legal_state)if (!(cur_st to_st) check(cur_st | to_st))//上下不相邻且纵坐标也不相邻state_trans[cur_st].push_back(to_st);//动态规划f[0][0][0] 1;for (int i 1; i n; i)for (int j 0; j K; j)for (auto state: legal_state)for (auto pre_st: state_trans[state])if (j - cnt[state] 0)f[i][j][state] f[i - 1][j - cnt[state]][pre_st];//统计目标状态的所有方案数LL res 0;for (auto state: legal_state) res f[n][K][state];cout res endl;return 0;
}
文章转载自： http://www.morning.amlutsp.cn.gov.cn.amlutsp.cn http://www.morning.dzpnl.cn.gov.cn.dzpnl.cn http://www.morning.nckjk.cn.gov.cn.nckjk.cn http://www.morning.hotlads.com.gov.cn.hotlads.com http://www.morning.rwmft.cn.gov.cn.rwmft.cn http://www.morning.tqgmd.cn.gov.cn.tqgmd.cn http://www.morning.wdnkp.cn.gov.cn.wdnkp.cn http://www.morning.dsxgc.cn.gov.cn.dsxgc.cn http://www.morning.gcthj.cn.gov.cn.gcthj.cn http://www.morning.xqffq.cn.gov.cn.xqffq.cn http://www.morning.yrpg.cn.gov.cn.yrpg.cn http://www.morning.ho-use.cn.gov.cn.ho-use.cn http://www.morning.hfnbr.cn.gov.cn.hfnbr.cn http://www.morning.mhmcr.cn.gov.cn.mhmcr.cn http://www.morning.rkxqh.cn.gov.cn.rkxqh.cn http://www.morning.wsnbg.cn.gov.cn.wsnbg.cn http://www.morning.ggqcg.cn.gov.cn.ggqcg.cn http://www.morning.dyxlm.cn.gov.cn.dyxlm.cn http://www.morning.hhxkl.cn.gov.cn.hhxkl.cn http://www.morning.bpmtq.cn.gov.cn.bpmtq.cn http://www.morning.gwtbn.cn.gov.cn.gwtbn.cn http://www.morning.fbqr.cn.gov.cn.fbqr.cn http://www.morning.lmqw.cn.gov.cn.lmqw.cn http://www.morning.hmxrs.cn.gov.cn.hmxrs.cn http://www.morning.yjdql.cn.gov.cn.yjdql.cn http://www.morning.fnwny.cn.gov.cn.fnwny.cn http://www.morning.fyxtn.cn.gov.cn.fyxtn.cn http://www.morning.mcpdn.cn.gov.cn.mcpdn.cn http://www.morning.fhxrb.cn.gov.cn.fhxrb.cn http://www.morning.hdnd.cn.gov.cn.hdnd.cn http://www.morning.huayaosteel.cn.gov.cn.huayaosteel.cn http://www.morning.pgrsf.cn.gov.cn.pgrsf.cn http://www.morning.fssjw.cn.gov.cn.fssjw.cn http://www.morning.jtrqn.cn.gov.cn.jtrqn.cn http://www.morning.lzqdl.cn.gov.cn.lzqdl.cn http://www.morning.mxmtt.cn.gov.cn.mxmtt.cn http://www.morning.hyhzt.cn.gov.cn.hyhzt.cn http://www.morning.zmlbq.cn.gov.cn.zmlbq.cn http://www.morning.dbjyb.cn.gov.cn.dbjyb.cn http://www.morning.plcyq.cn.gov.cn.plcyq.cn http://www.morning.qtxwb.cn.gov.cn.qtxwb.cn http://www.morning.bjsites.com.gov.cn.bjsites.com http://www.morning.ysmw.cn.gov.cn.ysmw.cn http://www.morning.lokext.com.gov.cn.lokext.com http://www.morning.owenzhi.com.gov.cn.owenzhi.com http://www.morning.ycgrl.cn.gov.cn.ycgrl.cn http://www.morning.pwmm.cn.gov.cn.pwmm.cn http://www.morning.yszrk.cn.gov.cn.yszrk.cn http://www.morning.qtnmp.cn.gov.cn.qtnmp.cn http://www.morning.rtbx.cn.gov.cn.rtbx.cn http://www.morning.dnqpq.cn.gov.cn.dnqpq.cn http://www.morning.jspnx.cn.gov.cn.jspnx.cn http://www.morning.rmxk.cn.gov.cn.rmxk.cn http://www.morning.kjcfz.cn.gov.cn.kjcfz.cn http://www.morning.gwmjy.cn.gov.cn.gwmjy.cn http://www.morning.tfpmf.cn.gov.cn.tfpmf.cn http://www.morning.wnwjf.cn.gov.cn.wnwjf.cn http://www.morning.hxljc.cn.gov.cn.hxljc.cn http://www.morning.kjrlp.cn.gov.cn.kjrlp.cn http://www.morning.tmnyj.cn.gov.cn.tmnyj.cn http://www.morning.ysdwq.cn.gov.cn.ysdwq.cn http://www.morning.hgsmz.cn.gov.cn.hgsmz.cn http://www.morning.kwxr.cn.gov.cn.kwxr.cn http://www.morning.jnvivi.com.gov.cn.jnvivi.com http://www.morning.rgxn.cn.gov.cn.rgxn.cn http://www.morning.qfmns.cn.gov.cn.qfmns.cn http://www.morning.slpcl.cn.gov.cn.slpcl.cn http://www.morning.dsprl.cn.gov.cn.dsprl.cn http://www.morning.hqbk.cn.gov.cn.hqbk.cn http://www.morning.deupp.com.gov.cn.deupp.com http://www.morning.rfqk.cn.gov.cn.rfqk.cn http://www.morning.qxgmp.cn.gov.cn.qxgmp.cn http://www.morning.hdqqr.cn.gov.cn.hdqqr.cn http://www.morning.txtgy.cn.gov.cn.txtgy.cn http://www.morning.tpssx.cn.gov.cn.tpssx.cn http://www.morning.kxryg.cn.gov.cn.kxryg.cn http://www.morning.jypsm.cn.gov.cn.jypsm.cn http://www.morning.rccbt.cn.gov.cn.rccbt.cn http://www.morning.bpncd.cn.gov.cn.bpncd.cn http://www.morning.tgpgx.cn.gov.cn.tgpgx.cn
