首页 > 代码库 > 去清北的第一天
去清北的第一天
值得一提,动态规划很重要
那么来上课的第一天,就讲了一道练手的很友善的题目,计数问题
1 3291 记数问题 2013年NOIP全国联赛普及组 2 时间限制: 1 s 3 空间限制: 128000 KB 4 题目等级 : 黄金 Gold 5 题解 6 题目描述 Description 7 试计算在区间1到n的所有整数中,数字x(0≤x≤9)共出现了多少次?例如,在1到11中,即在1、2、3、4、5、6、7、8、9、10、11中,数字1出现了4次。 8 9 输入描述 Input Description 10 输入共1行,包含2个整数n、x,之间用一个空格隔开。 11 12 输出描述 Output Description 13 输出共1行,包含一个整数,表示x出现的次数。 14 15 样例输入 Sample Input 16 11 1 17 18 样例输出 Sample Output 19 4
那么话不多,直接上代码
答案
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int main(){ 6 int n,x; 7 scanf("%d%d",&n,&x); 8 int ans=0; 9 for (int i=1;i<=n;++i){ 10 int j=i; 11 while (j){ 12 if (j%10==x) ++ans; 13 j/=10; 14 } 15 } 16 printf("%d\n",ans); 17 return 0; 18 }
很明显简单的一个,直接枚举就可以的一道题,枚举他,判断他的最后一位其出现X的次数即可。
从这里引出了一种很简单的算法:枚举。
很快来到了例二
bzoj扫雷Mine 1088
1 1088: [SCOI2005]扫雷Mine 2 3 Time Limit: 10 Sec Memory Limit: 162 MB 4 Submit: 3651 Solved: 2140 5 [Submit][Status][Discuss] 6 Description 7 8 相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷,要你根据一些信息找出雷来。万圣节到了 9 ,“余”人国流行起了一种简单的扫雷游戏,这个游戏规则和扫雷一样,如果某个格子没有雷,那么它里面的数字 10 表示和它8连通的格子里面雷的数目。现在棋盘是n×2的,第一列里面某些格子是雷,而第二列没有雷,如下图: 11 由于第一列的雷可能有多种方案满足第二列的数的限制,你的任务即根据第二列的信息确定第一列雷有多少种摆放 12 方案。 13 14 Input 15 16 第一行为N,第二行有N个数,依次为第二列的格子中的数。(1<= N <= 10000) 17 18 Output 19 20 一个数,即第一列中雷的摆放方案数。 21 22 Sample Input 23 24 2 25 26 1 1 27 Sample Output 28 29 2
和一般的扫雷不同,这个只有两列,所以对于这个题也可以用枚举,从而得出了这个题的两种思路
1)枚举左边每个位置是否有雷,那么时间复杂度O(n*2n)
2)只枚举前两个位置,颇似递推关系
那么可以讲一下题了
1 #include <bits/stdc++.h> 2 #define N 10004 3 4 using namespace std; 5 6 int a[N],n; 7 8 9 int check(int x){ 10 int last=0; 11 for (int i=1;i<n;++i){//枚举中间所有的情况与可能性 12 int now=a[i]-last-x; 13 if (now<0||now>1) return 0;//最多空3个,已知两个,最坏情况还有一个雷,最好情况没雷 14 last=x; 15 x=now; 16 } 17 if (last+x!=a[n]) return 0;//单独判断最后一位即可 18 return 1; 19 } 20 21 int main(){ 22 scanf("%d",&n); 23 for (int i=1;i<=n;++i) scanf("%d",&a[i]); 24 printf("%d\n",check(0)+check(1));//从第0项和第1项开始检查 25 return 0; 26 }
然后是巨恶心的例3
子矩阵
3904 子矩阵 2014年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题解 查看运行结果 题目描述 Description 给出如下定义: 子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与 列的相对顺序)被称为原矩阵的一个子矩阵。 例如,下面左图中选取第 2、4 行和第 2、4、5 列交叉位置的元素得到一个 2*3 的子矩阵如右图所示。 相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。 矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。 本题任务:给定一个 n 行 m 列的正整数矩阵,请你从这个矩阵中选出一个 r 行 c 列的 子矩阵,使得这个子矩阵的分值最小,并输出这个分值。 输入描述 Input Description 第一行包含用空格隔开的四个整数 n,m,r,c,意义如问题描述中所述,每两个整数之间用一个空格隔开。 接下来的 n 行,每行包含 m 个用空格隔开的整数,用来表示问题描述中那个 n 行 m 列的矩阵。 输出描述 Output Description 输出共 1 行,包含 1 个整数,表示满足题目描述的子矩阵的最小分值。 样例输入 Sample Input 样例输入1 5 5 2 3 9 3 3 3 9 9 4 8 7 4 1 7 4 6 6 6 8 5 6 9 7 4 5 6 1 样例输入2 7 7 3 3 7 7 7 6 2 10 5 5 8 8 2 1 6 2 2 9 5 5 6 1 7 7 9 3 6 1 7 8 1 9 1 4 7 8 8 10 5 9 1 1 8 10 1 3 1 5 4 8 6 样例输出 Sample Output 样例输出1 6 样例输出2 16
这个题一看,呀,这是dp啊,然后老师就开始讲了,让我这个对dp一无所知的人很他妈尴尬。
那么就用时间去磨平他吧。//码着,等会了dp再说吧
1 #include <bits/stdc++.h> 2 #define N 18 3 4 using namespace std; 5 6 int n,m,r,c; 7 int a[N][N]; 8 9 int R[N]; 10 11 int val[N],cost[N][N]; 12 13 int dp[N][N]; 14 15 int DP(){ 16 int ret=1e9; 17 // for (int i=1;i<=r;++i) printf("%d ",R[i]);puts(""); 18 for (int i=1;i<=m;++i){ 19 val[i]=0; 20 for (int j=1;j<r;++j) 21 val[i]+=abs(a[R[j]][i]-a[R[j+1]][i]); 22 } 23 memset(cost,0,sizeof(cost)); 24 for (int i=1;i<=m;++i)for (int j=i+1;j<=m;++j){ 25 cost[i][j]=0; 26 for (int k=1;k<=r;++k) 27 cost[i][j]+=abs(a[R[k]][i]-a[R[k]][j]); 28 } 29 30 dp[0][0]=0; 31 for (int i=1;i<=n;++i) dp[i][0]=0; 32 for (int i=1;i<=m;++i)for (int k=1;k<=i&&k<=c;++k){ 33 dp[i][k]=1e9; 34 for (int j=k-1;j<i;++j) 35 dp[i][k]=min(dp[i][k],dp[j][k-1]+cost[j][i]+val[i]); 36 } 37 38 for (int i=c;i<=m;++i) 39 ret=min(ret,dp[i][c]); 40 41 return ret; 42 } 43 44 int ans; 45 46 void dfs(int u,int cnt){ 47 if (u>n){ 48 if (cnt==r) ans=min(ans,DP()); 49 return; 50 } 51 dfs(u+1,cnt); 52 R[cnt+1]=u; 53 dfs(u+1,cnt+1); 54 } 55 56 int main(){ 57 scanf("%d%d%d%d",&n,&m,&r,&c); 58 for (int i=1;i<=n;++i) 59 for (int j=1;j<=m;++j) 60 scanf("%d",&a[i][j]); 61 ans=1e9; 62 dfs(1,0); 63 printf("%d\n",ans); 64 return 0; 65 }
例三跳过
例四
N皇后问题
1295 N皇后问题 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题解 题目描述 Description 在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后,任何2个皇后不妨在同一行或同一列或同一斜线上。 输入描述 Input Description 给定棋盘的大小n (n ≤ 13) 输出描述 Output Description 输出整数表示有多少种放置方法。 样例输入 Sample Input 8 样例输出 Sample Output 92 数据范围及提示 Data Size & Hint n<=13 (时限提高了,不用打表了)
简单明了的题目,就是很难
显而易见,这个题应该搜索,然后直接枚举每一行的皇后放的位置。
可以做的优化就是
1)不放之前放过的列
2)用链表维护没有用过的列
3)位运算加速
1 #include <bits/stdc++.h> 2 #define N 233 3 4 using namespace std; 5 6 int n; 7 int ans; 8 9 int a[N]; 10 11 void dfs(int u){ 12 if (u>n){ 13 ++ans; 14 return; 15 } 16 for (int i=r[0];i<=n;i=r[i]) 17 { 18 bool valid=1; 19 for (int j=1;j<u&&valid;++j) 20 if (a[j]+j==i+u||a[j]-j==i-u) 21 valid=0; 22 if (!valid) continue; 23 a[u] = i ; 24 dfs(u+1); 25 } 26 } 27 28 int main(){ 29 scanf("%d",&n); 30 ans=0; 31 dfs(1); 32 printf("%d\n",ans); 33 return 0; 34 }
去清北的第一天
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。