当前位置：首页 > news >正文

编程技巧：优化

news 2025/5/11 2:35:05

第一种：构造回文串---构造法

题目描述

[NOIP2016 普及组] 回文日期 - 洛谷

那么这道题我们总结一些题目要求：

1.输入两个字符串，为起始和终止日期

2.年份不会出现前导0

3.如果是回文日期，答案+1

4.如果月份是2，要判断闰年

5.如果月份或年份有前导0，转string时要把前导0加上判回文

第一种60pts做法：

因为题目说60%数据date1 = date2

那这样就只用判断回文就行了

$O(1)$

第二种80pts做法

我们模拟整个年，月，日，来判断回文不回文

#include<bits/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;
}

$O((M-N) * 12 * 31)$

100pts做法

方法1：

那么我们根据题意可知，年份不能有前导0，也就意味着前4位一定是年份，那么我们知道年份根据年份映射另一半，在判断日期合不合法， $O(M-N)$ 的做法

方法2：

既然可以用年份映射月份，也可以用月份映射年份，也就是枚举日期，最大366，常数级别100分 $O(1)$ 神操作

小结

我们既然枚举天数判回文超时，那就试一下构造回文串来判断是否合法

第二种：记忆路径----剪枝

题目描述：

https://www.luogu.com.cn/problem/P2010?contestId=202430

总结题目要求~~~：

1.我们每一步往外走的格子上标记的数字不能和当前格子一样

2.求最多走几步

那我们一看数据范围，这么大！！！

那么我们就想着记忆路径

通过上面这张图可看出我们可以分割成多个01块，每个块中个个点的最大扩散值都一样，所以我们可以整一个标记数组，来记下块的编号，在有一个ans数组，存储编号为vis[x][y]的点最大扩散范围

深搜代码：

#include<cstdio>
#include<cstring>
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 (r<0 || r>=n || c<0 || c>=n || f[r][c]!=-1 || s[r][c]-'0'!=z)return;f[r][c]=lll;ans[lll]++;dfs(r-1,c,!z,lll);dfs(r+1,c,!z,lll);dfs(r,c-1,!z,lll);dfs(r,c+1,!z,lll);
}
int main()
{scanf("%d%d",&n,&m);for (int i=0;i<n;i++)scanf("%s",s[i]);memset(f,-1,sizeof(f));for (int i=0;i<m;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 i=0;i<m;i++)printf("%d\n",ans[i]);return 0;
}

广搜代码：

#include<bits/stdc++.h>//万头
using namespace std;
int n,m,x,y;
struct queue
{char c;bool is;
}a[1000][1000];
int quex[1000002],quey[1000002],l=1,r=0;
int dx[5]={0,0,0,-1,1},dy[5]={0,-1,1,0,0};
//定义一坨东西
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf(" %c",&a[i][j].c);//输入while(m--){scanf("%d%d",&x,&y);quex[++r]=x;quey[r]=y;//将输入点压入队列a[x][y].is=1;//输入点已走过int cnt=1;//记录有几种方法while(l<=r){for(int k=1;k<=4;k++){int tx=quex[l]+dx[k],ty=quey[l]+dy[k];if(tx<1||tx>n||ty<1||ty>n) continue;if(a[tx][ty].c==a[quex[l]][quey[l]].c) continue;if(a[tx][ty].is==1) continue;//判断a[tx][ty].is=1;quex[++r]=tx;quey[r]=ty;//将当前点推入队列cnt++;//方法++}l++;//已经搜完，出队}printf("%d\n",cnt);//输出l=1,r=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j].is=0;}return 0;
}