重走长征路---OI每周刷题记录---2月1日 2014
总目录详见
做题原则，找不到测评地址的题不做。2018-11-28
重走长征路---OI每周刷题记录---2月1日 2014
本周共计23题+题
测评地址：
dfs20分
1.「codevs2800」送外卖
迭代dfs20分
2.「codevs2495」水叮当的舞步
迭代dfs
3.「codevs1049」棋盘染色
kruskal
4.「JoyOI1307」联络员
5.「bzoj1821」Group 部落划分
网络流
7.「codevs1022」覆盖
8.「codevs1993」草地排水（边表）
spfa
9.「JoyOI1136」火焰巨魔的惆怅
10.「JoyOI1326」剑人合一
背包dp
11.「JoyOI1028」Bessie的体重问题
快速幂
12.「JoyOI1118-1119」a^b1-2
模拟
13.「JoyOI1081」最近距离
bfs
14.「JoyOI1083」分糖果
线段树
15.「NOIP2012」借教室
16.「bzoj3038」上帝造题的七分钟2
17.「codevs1299」切水果
状压DP
18.「bzoj1087」互不侵犯King
数学
19.「bzoj1041」圆上的整点
20.「JoyOI1109」幻方
A*+dfs
21.「bzoj1085」骑士精神
tarjan
22.「codevs2822」爱在心中
dfs
23.「bzoj3109」新数独
题解：
dfs20分
1.「codevs2800」送外卖
迭代dfs20分
2.「codevs2495」水叮当的舞步
迭代dfs
3.「codevs1049」棋盘染色
kruskal
4.「JoyOI1307」联络员
5.「bzoj1821」Group 部落划分
网络流
7.「codevs1022」覆盖
8.「codevs1993」草地排水（边表）
spfa
9.「JoyOI1136」火焰巨魔的惆怅
10.「JoyOI1326」剑人合一
背包dp
11.「JoyOI1028」Bessie的体重问题
快速幂
12.「JoyOI1118-1119」a^b1-2
模拟
13.「JoyOI1081」最近距离
bfs
14.「JoyOI1083」分糖果
线段树
15.「NOIP2012」借教室
16.「bzoj3038」上帝造题的七分钟2
17.「codevs1299」切水果
状压DP
18.「bzoj1087」互不侵犯King
//P1896 [SCOI2005]互不侵犯 //在线测评地址https://www.luogu.org/problemnew/show/P1896 //深搜，估计能拿30分 //r=a[j]/n,c=a[j]%n;//此处写成r=a[i]/n,c=a[i]%n;出现段错误 //r=a[j]/n,c=a[j]%n,flag=0;//此处写成r=a[i]/n,c=a[i]%n,flag=0; //提交50分，测试点6-10TLE。很是满意。2019-3-8 20:09 //以下为50分代码。 #include <stdio.h> #include <string.h> int next[][2]={ {0,-1},{0,1},{-1,0},{1,0},{-1,-1},{-1,1},{1,-1},{1,1}};//上，下，左，右，左上，左下，右上，右下 int n,k,a[100],map[15][15]; long long cnt=0; void dfs(int step){ int i,j,p,r,c,nr,nc,flag; if(step==k+1){ memset(map,0,sizeof(map)); for(j=1;j<=k;j++){ r=a[j]/n,c=a[j]%n;//此处写成r=a[i]/n,c=a[i]%n;出现段错误 map[r][c]=1; } for(j=1;j<=k;j++){ r=a[j]/n,c=a[j]%n,flag=0;//此处写成r=a[i]/n,c=a[i]%n,flag=0; for(p=0;p<8;p++){ nr=r+next[p][0],nc=c+next[p][1]; if(0<=nr&&nr<n*n&&0<=nc&&nc<n*n&&map[nr][nc]){//判断是否冲突 flag=1; break; } } if(flag==1)break; } if(flag==0)cnt++; return ; } for(i=a[step-1]+1;i<n*n;i++){ a[step]=i; dfs(step+1); } } int main(){ scanf("%d%d",&n,&k); a[0]=-1; dfs(1); printf("%lld ",cnt); return 0; }
数学
19.「bzoj1041」圆上的整点
20.「JoyOI1109」幻方
A*+dfs
21.「bzoj1085」骑士精神
tarjan
22.「codevs2822」爱在心中
dfs
23.「bzoj3109」新数独
