零陵网站建设,wordpress新文章数据库,新闻cms静态网站模板下载,做和别人一样的网站第一种#xff1a;构造回文串---构造法
题目描述
[NOIP2016 普及组] 回文日期 - 洛谷 那么这道题我们总结一些题目要求#xff1a;
1.输入两个字符串#xff0c;为起始和终止日期
2.年份不会出现前导0
3.如果是回文日期#xff0c;答案1
4.如果月份是2#xff0c;要…第一种构造回文串---构造法
题目描述
[NOIP2016 普及组] 回文日期 - 洛谷 那么这道题我们总结一些题目要求
1.输入两个字符串为起始和终止日期
2.年份不会出现前导0
3.如果是回文日期答案1
4.如果月份是2要判断闰年
5.如果月份或年份有前导0转string时要把前导0加上判回文
第一种60pts做法
因为题目说60%数据date1 date2
那这样就只用判断回文就行了 第二种80pts做法
我们模拟整个年月日来判断回文不回文
#includebits/stdc.h
using namespace std;
int mon[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};//月份数组
string sd;//起始日期start date
string ed;//结束日期end date
bool judge1(int x){//判断闰年if(x % 400 0 || (x % 100 ! 0 x % 4 0)) return true;else return false;
}
bool judge2(string x){//判断回文int len x.size();for(int i 0; i len / 2; i ){if(x[i] ! x[len - i - 1]) return false;//因为下标从0开始而len是从1开始所以减去1}return true;
}
int main(){cin sd ed;if(sd ed){if(judge2(sd)) cout 1;else cout 0;return 0;}int ans 0;int sy 0, ey 0;for(int i 0; i 4; i ){sy sy * 10 (sd[i] - 0);ey ey * 10 (ed[i] - 0);}for(int year sy; year ey; year ){//构造年份if(judge1(year)) mon[2] ;//如果是闰年把2月天数变成29for(int month 1; month 12; month ) {//月份for(int day 1; day mon[month]; day ){string s ;string xx, yy, zz;if(month 10) yy 0 to_string(month);//判断月10加前导0的情况else yy to_string(month);if(day 10) zz 0 to_string(day);//判断天10加前导0的情况else zz to_string(day);xx to_string(year);s xx yy zz;if(judge2(s)){cerr the huiwen year : s endl;//本地输出评测机不输出的cerrans ;}}}}cout ans;return 0;
} 100pts做法
方法1
那么我们根据题意可知年份不能有前导0也就意味着前4位一定是年份那么我们知道年份根据年份映射另一半在判断日期合不合法的做法
方法2
既然可以用年份映射月份也可以用月份映射年份也就是枚举日期最大366常数级别100分神操作
小结
我们既然枚举天数判回文超时那就试一下构造回文串来判断是否合法
第二种记忆路径----剪枝
题目描述
https://www.luogu.com.cn/problem/P2010?contestId202430 总结题目要求~~~
1.我们每一步往外走的格子上标记的数字不能和当前格子一样
2.求最多走几步
那我们一看数据范围这么大
那么我们就想着记忆路径 通过上面这张图可看出我们可以分割成多个01块每个块中个个点的最大扩散值都一样所以我们可以整一个标记数组来记下块的编号在有一个ans数组存储编号为vis[x][y]的点最大扩散范围
深搜代码
#includecstdio
#includecstring
int n,m,ans[100002],x,y,f[1002][1002];
char s[1002][1002];
void dfs(int r,int c,int z,int lll){if (r0 || rn || c0 || cn || f[r][c]!-1 || s[r][c]-0!z)return;f[r][c]lll;ans[lll];dfs(r-1,c,!z,lll);dfs(r1,c,!z,lll);dfs(r,c-1,!z,lll);dfs(r,c1,!z,lll);
}
int main()
{scanf(%d%d,n,m);for (int i0;in;i)scanf(%s,s[i]);memset(f,-1,sizeof(f));for (int i0;im;i){scanf(%d%d,x,y);x--;y--;if (f[x][y]-1)dfs(x,y,s[x][y]-0,i);else ans[i]ans[f[x][y]];}for (int i0;im;i)printf(%d\n,ans[i]);return 0;
}
广搜代码
#includebits/stdc.h//万头
using namespace std;
int n,m,x,y;
struct queue
{char c;bool is;
}a[1000][1000];
int quex[1000002],quey[1000002],l1,r0;
int dx[5]{0,0,0,-1,1},dy[5]{0,-1,1,0,0};
//定义一坨东西
int main()
{scanf(%d%d,n,m);for(int i1;in;i)for(int j1;jn;j)scanf( %c,a[i][j].c);//输入while(m--){scanf(%d%d,x,y);quex[r]x;quey[r]y;//将输入点压入队列a[x][y].is1;//输入点已走过int cnt1;//记录有几种方法while(lr){for(int k1;k4;k){int txquex[l]dx[k],tyquey[l]dy[k];if(tx1||txn||ty1||tyn) continue;if(a[tx][ty].ca[quex[l]][quey[l]].c) continue;if(a[tx][ty].is1) continue;//判断a[tx][ty].is1;quex[r]tx;quey[r]ty;//将当前点推入队列cnt;//方法}l;//已经搜完出队}printf(%d\n,cnt);//输出l1,r0;for(int i1;in;i)for(int j1;jn;j)a[i][j].is0;}return 0;
}
小结
通常数据量很大的搜索题我们用记忆路径来剪枝
