A - ABD
大意：
输入1-999就输出ABC，否则输出ABD
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int n;
int main(){
cin >> n;
if (n >= 1000) cout << "ABD" << endl;
else
cout << "ABC" << endl;
return 0;
}
B - Stone Monument
大意：
从左到右有999个塔，塔高分别为1 1+2 1+2+3 1+2+3+4.....
现在因为积雪，使得相邻两个塔的塔高变为了a和b，问积雪有多高
思路：
b-a代表b是第几个塔，算一下原来是多少，现在是多少，相减即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int a, b, sum[N];
int main() {
for (int i = 1; i <= 999; i++) {
sum[i] += sum[i - 1] + i;
}
cin >> a >> b;
cout << sum[b - a - 1] - a;
return 0;
}
C - Strange Bank
大意：
给出金额n，现在一次取钱只能取出1块钱或者是6或9的幂次块钱，问最少需要取多少才能正好取出n块钱
思路：
完全背包dp即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int n, s6[N], s9[N], dp[N];
int main() {
s6[1] = 6, s9[1] = 9;
for (int i = 2; i <= 9; i++) {
s6[i] = s6[i - 1] * 6;
s9[i] = s9[i - 1] * 9;
}
cin >> n;
for (int i = 0; i <= n; i++) {
dp[i] = i;
}
for (int i = 1; i <= 9; i++) {
for (int j = s6[i]; j <= n; j ++) {
dp[j] = min(dp[j], dp[j - s6[i]] + 1);
}
}
for (int i = 1; i <= 9; i++) {
for (int j = s9[i]; j <= n; j ++) {
dp[j] = min(dp[j], dp[j - s9[i]] + 1);
}
}
int res = 0x3f3f3f3f;
for (int i = 0; i <= n; i++) {
res = min(n - i + dp[i], res);
}
cout << res << endl;
return 0;
}
D - Good Grid
大意：
给出一个nxn的矩阵，每个位置都涂着1-c之间任意一种颜色，从颜色i变为颜色j需要花费(D_{i,j})，现在要求横坐标+纵坐标的和模3相同的位置颜色必须相同，不同的位置颜色必须不同，最少的代价是多少
c<=30
思路：
因为颜色种类比较少，所以可以先统计对3取模的位置用各个颜色多少次，然后枚举对3取模的位置取什么颜色，计算花费即可，这样复杂度为(30^3)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int n, c, C[505][505], D[35][35], num[3][35];
int main() {
cin >> n >> c;
for (int i = 1; i <= c; i++) {
for (int j = 1; j <= c; j++) {
cin >> D[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> C[i][j];
num[(i + j) % 3][C[i][j]]++;
}
}
int res = 0x3f3f3f3f;
for (int i = 1; i <= c; i++) {
int sum1 = 0;
for (int j = 1; j <= c; j++) {
sum1 += num[0][j] * D[j][i];
}
for (int j = 1; j <= c; j++) {
if (i == j) continue;
int sum2 = 0;
for (int k = 1; k <= c; k++) {
sum2 += num[1][k] * D[k][j];
}
for (int k = 1; k <= c; k++) {
if (k == j||k==i) continue;
int sum3 = 0;
for (int l = 1; l <= c; l++) {
sum3 += num[2][l] * D[l][k];
}
res = min(res, sum1 + sum2 + sum3);
}
}
}
cout << res << endl;
return 0;
}