为了更好的备战蓝桥杯,笔者将按照每日更新两道题的速度,争取在赛前刷穿真题,同样希望本文也可以帮助到大家。
2017 年 省赛填空题 迷宫
答案 = 31
简单 dfs
AC code
#include<bits/stdc++.h>
using namespace std;
char g[15][15];
bool vis[15][15];
bool dfs(int i,int j)
{
if(i < 1|| i > 10 ||j < 1|| j > 10) return true;
if(vis[i][j]) return false;
vis[i][j] = true;
if(g[i][j] == 'U') dfs(i - 1,j);
else if(g[i][j] == 'D') dfs(i + 1,j);
else if(g[i][j] == 'L') dfs(i,j - 1);
else if(g[i][j] == 'R') dfs(i,j + 1);
}
int main()
{
for(int i = 1;i <= 10;i ++)
for(int j = 1;j <= 10;j ++)
cin >> g[i][j];
int cnt = 0;
for(int i = 1;i <= 10;i ++)
for(int j = 1;j <= 10;j ++)
{
memset(vis,false,sizeof vis);
if(dfs(i,j)) cnt ++;
}
cout << cnt << endl;
return 0;
}
2017 年 省赛填空题 跳蚱蜢
答案 = 20
类似八数码问题,想要将012345678 => 087654321
每次跳跃其实就是和 0 交换位置,每次的转移为 -2,-1,1,2 ,那么负数转移的时候可以注意到
可以通过 (i + 9) % 9 的方式滚动数组模拟环,解决了这些问题就可以开始愉快的bfs了
AC code
#include<bits/stdc++.h>
using namespace std;
struct node
{
string str;
int pos;
int step;
};
queue<node> q;
set<string> vis;
void change(node now,int key)
{
string s = now.str;
swap(s[now.pos],s[(now.pos + key + 9) % 9]);
if(vis.count(s) == 0)
{
vis.insert(s);
q.push({s,(now.pos + key + 9) % 9,now.step + 1});
}
}
int main()
{
string start = "012345678";//初始状态
q.push({start,0,0});
while(q.size())
{
auto t = q.front();
if(t.str == "087654321")//目标状态
{
cout << t.step << endl;
break;
}
else
{
//将一层全都拓展完以后 再弹出
change(t,-2);
change(t,-1);
change(t,1);
change(t,2);
q.pop();
}
}
return 0;
}
2017 年 省赛填空题 方格分割
答案 = 509
我们可以注意到倘若我们要切成完全相同的图形那么切割的路线必定是会经过 (3,3) 点的,因为他是一个中心对称图形。
而且一个图形要被切断的条件是到达了这个6 * 6方块的边界,因为我们只需要从 (3,3) 开始 dfs ,碰到边界即存在一个合法方案,因为一个点抵达了边界,他的对称点必然也在边界之上,必定能将图形切断。然后最后要注意的是需要将答案除 4 ,因为中心对称的缘故会存在重复,比如说一直向上,向下,向左,向右切出来的图形是一样的。
AC code
#include<bits/stdc++.h>
using namespace std;
int cnt = 0;
const int N = 10;
int g[N][N];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};
void dfs(int i,int j)
{
if(i == 0 || i == 6 || j == 0 || j == 6)
{
cnt ++;
return ;
}
for(int k = 0;k < 4;k ++)
{
int nx = i + dx[k];
int ny = j + dy[k];
if(g[nx][ny] == 0)
{
g[nx][ny] = 1;
g[6 - nx][6 - ny] = 1;
dfs(nx,ny);
g[nx][ny] = 0;
g[6 - nx][6 - ny] = 0;
}
}
}
int main()
{
memset(g,0,sizeof g);
g[3][3] = 1;
dfs(3,3);
cout << cnt / 4 << endl;
return 0;
}
2017 年 省赛代码填空题 字母组串
运用 dp 的思想,长度为 $n$ 的包含 a 个 A，b 个 B，c 个 C 字母的答案一定是会从
1.长度为 $n$ 的包含 a - 1 个 A，b 个 B，c 个 C 字母的答案
2.长度为 $n$ 的包含 a 个 A，b - 1 个 B，c 个 C 字母的答案
3.长度为 $n$ 的包含 a 个 A，b 个 B，c - 1 个 C 字母的答案
转移而来的,因此把 dp 的转移按递归写法写就成了
return f(a - 1,b,c,n - 1) + f(a,b - 1,c,n - 1) + f(a,b,c - 1,n - 1);
AC code
#include <stdio.h>
// a 个 A，b 个 B，c 个 C 字母，能组成多少个不同的长度为n的串。
int f(int a, int b, int c, int n)
{
if(a < 0 || b < 0 || c < 0) return 0;
if(n == 0) return 1;
return f(a - 1,b,c,n - 1) + f(a,b - 1,c,n - 1) + f(a,b,c - 1,n - 1);
}
int main()
{
printf("%d\n", f(1,1,1,2));
printf("%d\n", f(1,2,3,3));
return 0;
}
2017 年 省赛代码填空题 字母组串
思路
题目提示了用矩阵的思想解决,那么我们就将 s1 和 s2 作为行列
ex.
b a a b c d a d a b c
a 0 1 1 0 0 0 1 0 1 0 0
b 1 0 0 2 0 0 0 0 0 2 0
c 0 0 0 0 3 0 0 0 0 0 3
d 0 0 0 0 0 4 0 1 0 0 0
k 0 0 0 0 0 0 0 0 0 0 0
k 0 0 0 0 0 0 0 0 0 0 0
k 0 0 0 0 0 0 0 0 0 0 0
很容易就可以想到若 $a[i][j]$ 匹配结果,那必然是 $a[i - 1][j - 1]$ 匹配上的结果再 $ + 1$
即串 $s1$ 在第 $i$ 位和 $s2$ 的第 $j$ 位匹配上了,那么匹配数必定是 $s1$ 前 $i - 1$ 位和 $s2$ 的 $j - 1$ 的匹配情况 $+ 1$
AC code
#include <stdio.h>
#include <string.h>
#define N 256
int f(const char* s1, const char* s2)
{
int a[N][N];
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j;
memset(a,0,sizeof(int)*N*N);
int max = 0;
for(i=1; i<=len1; i++){
for(j=1; j<=len2; j++){
if(s1[i-1]==s2[j-1]) {
a[i][j] = a[i - 1][j - 1];
if(a[i][j] > max) max = a[i][j];
}
}
}
return max;
}
int main()
{
printf("%d\n", f("abcdkkk", "baabcdadabc"));
printf("%d\n", f("aaakkkabababa", "baabababcdadabc"));
printf("%d\n", f("abccbaacbcca", "ccccbbbbbaaaa"));
printf("%d\n", f("abcd", "xyz"));
printf("%d\n", f("ab", "ab"));
return 0;
}
2017 年 省赛 正则问题
分析
有同学可能没读懂题意,我在这里举个例子应该就能看懂了
((xx|xxx)x|(x|xx))xx
xx | xxx => 或上的结果要么是 xx 要么就是 xxx 在这里为了保证字符串最长 我们留下了 xxx
(xxx)x就是直接连接为 xxxx
然后(x|xx) 同理 我们留下了 xx
那么现在就是(xxxx | xx) => xxxx
(xxxx)xx => xxxxxx
因此答案为 6
解法: 将正则表达式构建成一颗树,用 dfs 遍历求解即可
Java
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main
{
static String s;
static int k = 0;
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
s = in.next();
in.close();
System.out.println(dfs());
}
public static int dfs()//计算(.....)中的值
{
int res = 0;
while(k < s.length())
{
if(s.charAt(k) == ')') return res;//遇到 ) 就说明 () 内的已经计算完毕 直接返回即可
else if(s.charAt(k) == '(')
{
k ++;//跳过 (
res += dfs();
k ++;// 跳过 )
}
else if(s.charAt(k) == '|')
{
k ++;
res = Math.max(res,dfs());// 左右取大
}
else
{
k ++;//跳过 x
res ++;//字符串长度增加
}
}
return res;
}
}
C ++
#include<bits/stdc++.h>
using namespace std;
string str;
int k;
int dfs()
{
int res = 0;
while(k < str.size())
{
if(str[k] == ')') break;
if(str[k] == '(')
{
k ++;
res += dfs();
k ++;
}
else if(str[k] == '|')
{
k ++;
res = max(res,dfs());
}
else
{
k ++;
res += 1;
}
}
return res;
}
int main()
{
cin >> str;
cout << dfs() << endl;
return 0;
}
2017 年 省赛 包子凑数
分析
由裴蜀定理可知:若$a,b$是整数,且 $gcd(a,b)=d$，那么对于任意的整数$x,y,ax+by$都一定是$d$的倍数，特别地，一定存在整数$x,y$，使 $ax + by = d$ 成立,那么倘若 $gcd(a,b) != 1$ 必然会有无数个数字不能被表示。
那么$ INF $的情况我们就已经讨论出来了
再来看看非$ INF $的情况,即 $gcd(a,b) = 1$
若$a , b$互质,那么任何大于$a * b$ 的数都可以表示为$ k1 * a + k2 * b$
因此当$ ai <= 100$ 时,大于 $10000$ 的数都可以被表示,我们只需要对 $10000$ 以内的数判断一下就好了
状态转移
$f[i]$ 表示 数 $i$ 能被 $f[i]$ 种方式表示 若 $f[i] = 0$ 那么就是不能被表示的
f[0] = 1;
for(int i = 1;i <= n;i ++)//枚举 i 种不同的笼子
for(int j = 1;j <= 10010;j ++)//枚举 1 ~ 10000 这些数
{
if(j - a[i] >= 0 && f[j - a[i]] >= 1) f[j] ++;//倘若 j-a[i] 可以被表示 那么j一定可以被表示
}
Java
import java.util.Scanner;
public class Main
{
static int f[] = new int[10100];
static int a[] = new int[10100];
public static int gcd(int a,int b)
{
if(b != 0) return gcd(b,a % b);
else return a;
}
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for(int i = 1;i <= n;i ++)
a[i] = in.nextInt();
in.close();
int tmp = a[1];
for(int i = 2;i <= n;i ++)
tmp = gcd(tmp,a[i]);
if(tmp != 1)
{
System.out.printf("INF");
return ;
}
else
{
f[0] = 1;
for(int i = 1;i <= n;i ++)
for(int j = 0;j <= 10010;j ++)
if((j - a[i] >= 0) && (f[j - a[i]] != 0)) f[j] ++;
int cnt = 0;
for(int i = 1;i <= 10010;i ++) if(f[i] == 0) cnt ++;
System.out.printf("%d\n",cnt);
}
return ;
}
}
C ++
#include<bits/stdc++.h>
using namespace std;
const int N = 20000;
int f[N],a[N];
int gcd(int a,int b)
{
return b ? gcd(b,a % b) : a;
}
int main()
{
int n; cin >> n;
for(int i = 1;i <= n;i ++) cin >> a[i];
int tmp = a[1];
for(int i = 2;i <= n;i ++)
{
tmp = gcd(tmp,a[i]);
}
//cout << tmp << endl;
if(tmp != 1)
{
puts("INF");
return 0;
}
else
{
f[0] = 1;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= 10010;j ++)
{
if(j - a[i] >= 0 && f[j - a[i]] >= 1) f[j] ++;
}
}
int cnt = 0;
for(int i = 1;i <= 10010;i ++)
{
if(f[i] == 0) cnt ++;
}
cout << cnt << endl;
return 0;
}
2017 年 省赛 分巧克力
分析
二分答案
C ++
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n,k;
struct Cho
{
int h;
int w;
}cho[N];
bool check(int x)
{
int sum = 0;
for(int i = 1;i <= n;i ++)
{
sum += ((cho[i].h / x) * (cho[i].w / x));
}
if(sum >= k) return true;
else return false;
}
int main()
{
cin >> n >> k;
for(int i = 1;i <= n;i ++)
{
scanf("%d%d",&cho[i].h,&cho[i].w);
}
int l = 1,r = 1e5;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}
Java
import java.util.Scanner;
public class Main
{
static int [] h = new int [100010];
static int [] w = new int [100010];
static int n,k;
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
n = in.nextInt();
k = in.nextInt();
for(int i = 1;i <= n;i ++)
{
h[i] = in.nextInt();
w[i] = in.nextInt();
}
int l = 1,r = 100000;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(check(mid) == 1) l = mid;
else r = mid - 1;
}
System.out.printf("%d\n",l);
in.close();
}
public static int check(int x)
{
int sum = 0;
for(int i = 1;i <= n;i ++)
{
sum += ((h[i] / x) * (w[i] / x));
}
if(sum >= k) return 1;
else return 0;
}
}
