A - 4:
Problem:
快速排序
排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。
其思想是：先选一个“标尺”，
用它把整个队列过一遍筛子，
以保证：其左边的元素都不大于它，其右边的元素都不小于它。
这样，排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。
下面的代码是一种实现，请分析并填写划线部分缺少的代码。
#include <stdio.h>
void swap(int a[], int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int partition(int a[], int p, int r)
{
int i = p;
int j = r + 1;
int x = a[p];
while(1){
while(i<r && a[++i]<x);
while(a[--j]>x);
if(i>=j) break;
swap(a,i,j);
}
______________________;
return j;
}
void quicksort(int a[], int p, int r)
{
if(p<r){
int q = partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
int main()
{
int i;
int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
int N = 12;
quicksort(a, 0, N-1);
for(i=0; i<N; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Solution:
while(1){
while(i<r && a[++i]<x); //1）前半部分必须小于标尺值
while(a[--j]>x); //2）后半部分必须大于标尺值
if(i>=j) break; //分割部分完成
swap(a,i,j); //将不符合 1）和2）的两个值调换位置 ，继续循环
}
swap(a,p,j); //填空
Ans:
swap(a,i,j);
B - 2:
Problem:
标题：方格分割
6x6的方格，沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。
如图：p1.png, p2.png, p3.png 就是可行的分割法。
试计算：
包括这3种分法在内，一共有多少种不同的分割方法。
注意：旋转对称的属于同一种分割法。
请提交该整数，不要填写任何多余的内容或说明文字。
Sulotion:
利用了类似状压DP的思想+BFS
不要考虑青蛙如何跳 转换一种思路,变成空盘子怎么跳
盘子跳法有四种
初始状态为"012345678"
目标状态为"087654321"
每一种状态有四种状态变换的可能
随后用BFS走到目标状态即可
Ans:
20
Code:
#include<string>
#include<queue>
#include<set>
#include<iostream>
using namespace std;
struct node {
string s = "";
short pos;
node(string str, int pos) :s(str), pos(pos) {};
};
int dir[4] = { 1,2,-1,-2 };
string flag = "";
string nextFlag = "";
queue<node> q;
set<string> visited;
void change(node & tmp, int index);
int main(void) {
node tmp("012345678", 0);
string end = "087654321";
q.push(tmp);
visited.insert("012345678");
flag = "012345678";
int step = 0;
while (!q.empty()) {
node temp = q.front();
if (temp.s == end) {
break;
}else {
for (int i = 0; i < 4; i++) {
change(temp, dir[i]);
}
if (flag == temp.s) {
flag = nextFlag;
step++;
}
q.pop();
}
}
cout << step;
return 0;
}
void change(node & tmp, int index) {
string s = tmp.s;
int tIndex = (tmp.pos + 9 + index) % 9;
swap(s[tmp.pos], s[tIndex]);
if (visited.count(s) == 0) {
nextFlag = s;
visited.insert(s);
node t(s, tIndex);
q.push(t);
}
}
B - 4:
Problem:
标题：方格分割
6x6的方格，沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。
如图：p1.png, p2.png, p3.png 就是可行的分割法。
试计算：
包括这3种分法在内，一共有多少种不同的分割方法。
注意：旋转对称的属于同一种分割法。
请提交该整数，不要填写任何多余的内容或说明文字。
Solution:
最开始的思路是在方格的两个对角格子设立初始面积,随后从初始面积的临界格子按一定规则纳入面积内,
两个初始面积分别纳入格子都是对称 用dfs得到全部一半的格子就ans++
后面发现了一种更简单的方法:
不以格子作为参考, 而是将网格的点作为参考, 相当于我们再看函数图线, 只要从中心点(3, 3) 开始两头出发 走到边界便可得出ans++
由于对称和旋转 所以最终答案为ans/4
Ans:
509
Code:
#include<iostream>
using namespace std;
struct node{
int x;
int y;
};
int ans = 0;
int dirX[4] = { 0,0,-1,1 };
int dirY[4] = { -1,1,0,0 };
int book[7][7] = { 0 };
void dfs(node x, node y)
{
if (x.x == 0 || x.x == 6 || y.y == 0 || y.y == 6)
{
ans++;
return;
}
node tmp, temp;
for (int i = 0; i < 4; i++)
{
tmp.x = x.x + dirX[i];
tmp.y = x.y + dirY[i];
temp.x = y.x - dirX[i];
temp.y = y.y - dirY[i];
if (book[tmp.x][tmp.y] != 1)
{
book[tmp.x][tmp.y] = 1;
book[temp.x][temp.y] = 1;
dfs(tmp, temp);
book[tmp.x][tmp.y] = 0;
book[temp.x][temp.y] = 0;
}
}
}
int main()
{
node p;
p.x = 3;
p.y = 3;
book[p.x][p.y] = 1;
dfs(p, p);
cout << ans / 4;
return 0;
}
Problem:
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)
输出
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。
样例输入
2
4
5
样例输出
6
Solution:
引入:
欧几里德定理：
对于不完全为 0 的整数 a，b，gcd（a，b）表示 a，b 的最大公约数。那么一定存在整数 x，y 使得 gcd（a，b）=ax+by。
由此可知:
如果a, b互为素数, 则不能凑出的数目为有限
简要证明(不严谨):
假设gcd（a，b）= 1, 则 x, y 分别一正一负
x, y的取值为 min(| x - y |)
假设N = x1*a + y1*b
x1>=0 y1>=0
(x1, y1)代表x1, y1至少一个
(x1, y1) >> x
(x1, y1) >> y
则N+1 可由 a,b 表达出来
N ~ N+ min(a, b) - 1
均可由 a, b表达出来
且x1>=0 y1>=0
由此可知 N 以上都可由a,b表达(其实已经证明完了)
只要不断缩小N的值最终就可求出最小N
推广
只要n个数的最小公约数为1 则不可凑出的数为有限个
具体思路 :
1.先求出是否为INF(欧几里得求公约数)
2.取一个较大值 用类似筛法的方法填满 最后计数出不可凑数的个数
Code
#include<iostream>
#include<vector>
using namespace std;
int n;
int gcd(int a, int b);
int main(void) {
cin >> n;
int size = 10010;
int count = 0;
vector<int> arr(n);
vector<bool> dp(size, false);
for (int i = 0; i < n; i++)
cin >> arr[i];
int tmp = arr[0];
for (int i = 1; i < n; i++)
tmp = gcd(tmp, arr[i]);
if (tmp != 1) {
cout << "INF";
}
else {
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j + arr[i] <= 10000; j++) {
if (dp[j] == 1)
dp[j + arr[i]] = 1;
}
}
for (int i = 1; i <= 10000; i++) {
if (dp[i] == 0) {
count++;
}
}
}
cout << count;
return 0;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
