1.奖券数目
作答：52488，正确
#include <iostream>
using namespace std; bool check(int x) {
int a[] = { };
while (x) {
a[x % ]++;
x /= ;
}
if (a[] != )return false;
return true;
} int main() {
int res = ;
for (int i = ; i <= ; i++) {
if (check(i)) {
res++;
}
}
cout << res << endl;
return ;
}
2.星系炸弹
作答：2017-8-5，正确
算法基本功，日期判断 -_-。
#include <iostream>
using namespace std; int main() {
//根据2014年的来写的
int days[] = { ,,,,,,,,,,,, };
int year = , month = , day = ; for (int i = ; i < ; i++) {
cout << year << " " << month << " " << day << ": " << i << endl;
day++;
if (day == days[month] + ) {
month++;
day = ;
if (month == ) {
year++;
if (year % == || (year % == && year % != ))days[] = ;
else days[] = ;
month = ;
}
}
}
cout << year << " " << month << " " << day << endl;
return ;
}
3.三羊献瑞
作答：1085，正确
有进位，那么“三”一定是1，那么“祥”一定是9，那“羊”一定是0，但是“瑞”+“羊”又不是“瑞”，所以“生”+“献”有进位，那“生”就是“瑞”+1。（我只剪枝到加粗的部分，答案就一秒跑出来了，不需要继续剪枝了。）
有头脑的暴力搜索：
#include <iostream>
using namespace std; bool check1(int x) {
int a[] = {};
while (x) {
a[x % ]++;
x /= ;
}
for (int i = ; i <= ; i++) {
if (a[i] > )return false;
}
return true;
}
bool check2(int i,int j) {
int a[] = { };
int rui = j % ;
if (i / % != j % )return false;
while (i&&j) {
a[i % ]++; a[j % ]++; i /= ; j /= ;
}
for (int i = ; i <= ; i++) {
if (i == rui)continue;
if (a[i] > )return false;
}
return true;
}
bool check3(int i, int j, int k) {
int a[] = { };
if (k / != )return false;
if (k / % != )return false;
if (k / % != i / % )return false;
if (k / % != j % )return false;
while (i&&j) {
a[i % ]++; a[j % ]++; i /= ; j /= ;
}
if (a[k % ] != )return false;
return true;
} int main() {
for (int i = ; i <= ; i++) {
if (!check1(i))continue;
for (int j = ; j <= ; j++) {
if (!check2(i, j))continue;
if (check3(i, j, i + j)) {
cout << i << " " << j << " " << i + j << endl;
//system("pause");
}
}
}
return ;
}
4.格子中输出
实话实说，不百度，我之前真不知道这个%*s，是怎么用的，比较狠。
printf("%*s", 10, s); /*意思是输出字符串s，但至少占10个位置，不足的在字符串s左边补空格，这里等同于printf("%10s", s);*/
作答：
printf("%*s%s%*s", width/,"", buf, width/,""); //填空
正确答案：(width-strlen(s)-)/,"",s,(width-strlen(s)-)/,"" 备注：答案可以形式多样性，只要代入使得代码成立即可
5.九数组分数
回溯，没看代码猜出来的，那个位置，还能写啥，送人头 -_-
{t = x[i]; x[i] = x[k]; x[k] = t; }
6. 加法变乘法
作答：16，正确
#include <iostream>
#include <queue>
using namespace std; int sum(int *a,int i,int j) {
int s = ;
for (int k = ; k < ; k++) {
if (k == i) {
s += a[k + ] * a[k];
k++; }
else if (k == j) {
s += a[k + ] * a[k];
k++;
}
else
s += a[k];
}
return s;
}
int flag = ;
void DFS(int *a, int i, int j) {
if (i == j - )return;
if (sum(a, i, j) == &&(i!=)) {
flag = ;
cout << i << ' ' << j << endl;
return;
}
if (flag)return;
DFS(a, i, j - );
DFS(a, i + , j);
} int main() {
int a[];
for (int i = ; i < ; i++)a[i] = i;
//1,48
DFS(a, , );
}
7.牌型种数
答案：3598180
思路：DFS，相当于13个桶，每个桶选的牌数量五种情况 0,1,2,3,4, 到牌数量达到13张。
#include <iostream>
#include <algorithm>
using namespace std; int res = ;
void dfs(int pos, int cnt) {
if (cnt == ) {
res++;
return;
}
if (pos == ) {
return;
}
int num = min( - cnt, );
for (int i = ; i <= num; i++) {
dfs(pos + , cnt + i);
}
return;
}
int main() {
dfs(, );
cout << res << endl;
return ;
}
8.移动距离
刚看题目本来以为是最短路径的计算，其实简单很多，应该是有更便捷的方法，通过运算 O（1）解决，但这样也已经很快了。
#include <iostream>
using namespace std; int si, sj, ei, ej;
void initialize(int W,int L,int m,int n) {
int cnt = ;
for (int i = ; i < L; i++) {
if (si != && ei != && sj != && ej != )break;
if (i & ) {
for (int j = W - ; j >= ; j--) {
if (cnt == m) {
si = i;
sj = j;
}
if (cnt == n) {
ei = i;
ej = j;
}
cnt++;
}
}
else {
for (int j = ; j < W; j++) {
if (cnt == m) {
si = i;
sj = j;
}
if (cnt == n) {
ei = i;
ej = j;
}
cnt++;
}
} }
} int main() {
int W, m, n;
cin >> W >> m >> n;
//得到最大值
int MAX = m > n ? m : n;
//获取当前宽度、最大门牌号下需要的长度是多少
int L = MAX / W + ; initialize(W, L, m, n); int res = abs(si - ei) + abs(sj - ej);
cout << res << endl;
return ;
}
9. 垒骰子
百度首页推荐的很多都是错的，找了四份代码除了之外，别的数据，输出四种答案。
这题想要做的话大概三种程度，DFS→DFS+记忆搜索→矩阵快速幂，但是难度跳跃太大 ~_~。
1. 作死算法
：
DFS（纯暴力，数字大于5就hold不住，但是可以用来验证代码正确性）：
思想：侧面是不受应影响的，算出第height层，以p为底面的数量，乘上4^n就是结果。
LL DFS(int height, int p){
if (height == n) return ;
else{
LL t = ;
for (int i = ; i <= ; i++){
if (flag[i][opposite[p]])continue;
t = (t% N + DFS(height + , i) % N) % N;
}
return t;
}
}
完整代码：
给几个测试数据
2. 有头脑的作死算法：
DFS + 记忆搜索（跑到4000层多一点就 栈溢出 了）：
纯DP层数可以再飞跃一次，大概10^6吧，但纯DP要从下往上，我没想出来怎么写。
3. 超级无敌哇塞碉堡了666挖掘机哪家强算法：
矩阵快速幂难点就在于怎么找矩阵递推方程。
记六阶矩阵 M 中，第 i 行第 j 列表示相邻两层是否能成功连接的情况。i 和 j 能连则为1，i 和 j 不能连则为0（注意是相邻两层的底面，不是衔接面
，所以要取相反面。）
比如，我们以1 和 1 不能连接为例。
这个M矩阵应该是右边这个：
现在我们只需要右边这个图了，红色底面与蓝色地面满足的是矩阵M， 蓝色底面与黄色底面满足的也是矩阵M， 递推关系就出来了。
An = An-1 × M ，An = Mn-1 ，（A1是单位矩阵E，这里省略了）
完整代码：
10.生命之树
第一次树形DP，不知道是我有没有写错，比别人写的要简单，有时间再写一次，但思路上我觉得没有错误。
判断每个子树（包括叶子节点）的权值和是否大于0，
- 比0小就把这个子树砍去，给父节点一个0。
- 比0大就返回给父节点这个数。
用一个全局变量 MAX = INT_MIN; 记录DP过程中的最大值。
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std; int dp[];
int v[];
bool fuck[];
int MAX = INT_MIN; vector<int>nodes[]; void dfs(int u) {
dp[u] = v[u];
fuck[u] = true;
for (int i = ; i < nodes[u].size(); i++) {
int son = nodes[u][i];
if (fuck[son])continue;
dfs(son);
dp[u] += max(, dp[son]);
}
MAX = dp[u] > MAX ? dp[u] : MAX;
} int main() {
int n,t;
cin >> n;
for (int i = ; i <= n; i++) {
//10^5级别的输入，慎用cin
scanf("%d",&v[i]);
}
for (int i = ; i < n - ; i++) {
int from, to;
scanf("%d%d",&from,&to);
nodes[from].push_back(to);
nodes[to].push_back(from);
}
dfs();
cout << MAX << endl;
return ;
}