Problem A 虫食算
题目链接：https://ac.nowcoder.com/acm/contest/1082/A
题意: 给你一个N进制加法，加法里的三个数字都有N位，用大写字母前N个字母来映射0~N-1，允许有前导零，N个字母均出现，求每个字母代表的数字
思路: 依次枚举每个字母代表哪个数字。
为了方便后续的剪枝，我们按照从右到左出现的次序枚举每个字母的选法：
- 从后往前枚举每一列，记当前这列的被加数、加数、和分别为 a,b,c，如果右边所有数均以确定，则当前这位的进位也是确定的，记为t，则如果a+b+t≠c，那么当前方案不合法；
- 如果右边存在某个未知数尚未确定，则上一位的进位t可能取0或1，那么如果 a+b≠c,a+b+1≠c 同时成立，则说明当前方案不合法；
- 另外对于最高位，判断是否有进位，如果有进位，则说明不合法(因为和也是n位数).
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30;
int n, Q[MAXN], p[MAXN];
bool vis[MAXN];
char spt[5][MAXN];
bool Judge() {
int t = 0;
for (int i = n - 1; ~i; i--) {
int a = spt[0][i] - 'A', b = spt[1][i] - 'A', c = spt[2][i] - 'A';
if (~p[a] && ~p[b] && ~p[c]) {//都已经赋过值了
a = p[a], b = p[b], c = p[c];
if (~t) {//右边的值已经确定
if ((a + b + t) % n != c)
return false;
if (!i)//最高位
if (a + b + t >= n)//有进位
return false;
t = (a + b + t) / n;
}
else {//右边有不确定的值
if ((a + b) % n != c && (a + b + 1) % n != c)//无论进不进位都不满足
return false;
if (!i)
if (a + b >= n)
return false;
}
}
else t = -1;//有不确定的值
}
return true;
}
bool DFS(int u) {
if (u >= n)
return true;
int x = Q[u];
for (int i = 0; i < n; i++) {
if (!vis[i]) {//i没有出现过
p[x] = i;//为x赋值
vis[i] = true;
if (Judge() && DFS(u + 1))
return true;
p[x] = -1;//回溯
vis[i] = false;
}
}
return false;
}
int main() {
int cnt = 0;
scanf("%d", &n);
for (int i = 0; i < 3; i++)
scanf("%s", spt[i]);
for (int i = n - 1; ~i; i--) {
for (int j = 0; j < 3; j++) {
int t = spt[j][i] - 'A';
if (!vis[t]) {
vis[t] = true;
Q[cnt++] = t;//统计所有未知字母
}
}
}
memset(p, -1, sizeof(p));
memset(vis, false, sizeof(vis));
DFS(0);
for (int i = 0; i < n; i++)
printf("%d ", p[i]);
return 0;
} Problem B Allowance
题目链接：https://ac.nowcoder.com/acm/contest/1082/B
题意: 一共有N种不同的面额，每个星期至少给Bessie某个零花钱的数目C，请帮他计算他最多能支付多少个星期的零花钱。
思路: 要使每个月的钱都大于常数C，就要使每次花的冤枉钱最少。
每一次给钱时，从大的钱开始给，但每次给到要浪费钱的一次就不给了，用小一些的钱给。给到已经没有小钱了以后，再给怎么也会产生浪费，就从小到大给，用面值尽可能小的钱产生浪费。也就是，当需要产生浪费时，用面值尽可能小的钱产生。注意那些大于C的面额，可以直接加，不需要存下来。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
struct edge {
int a, b;
edge() {}
edge(int a, int b) : a(a), b(b) {}
bool operator < (const edge &s) const {
return s.a > a;
}
}spt[MAXN];
int main() {
int n, m, ans = 0;
int cnt = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
int a, b;
scanf("%d%d", &a, &b);
if (a >= m)
ans += b;
else spt[cnt++] = edge(a, b);
}
sort(spt, spt + cnt);
while (true) {
int x = m;
for (int i = cnt - 1; ~i; i--) {
if (spt[i].b && spt[i].a <= x)
while (spt[i].b && spt[i].a <= x)
x -= spt[i].a, spt[i].b--;
}
if (x > 0) {
for (int i = 0; i < cnt && x > 0; i++) {
if (spt[i].b)
x -= spt[i].a, spt[i].b--;
}
}
if (x > 0)
break;
ans++;
}
printf("%d\n", ans);
return 0;
} Problem C 合唱队形
题目链接：https://ac.nowcoder.com/acm/contest/1082/C
题意: 已知所有N位同学的身高，计算最少需要几位同学出列，使其满足T1<...<Ti>Ti+1>…>TK。
思路: 正反都求一次最长上升子序列，然后枚举Ti的位置，取出队最小的就行了(即正反之和最大的)。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int n, a[MAXN], dp[2][MAXN], ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
a[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (a[i] > a[j])
dp[0][i] = max(dp[0][i], dp[0][j] + 1);
a[n + 1] = 0;
for (int i = n; i; i--)
for (int j = n + 1; j > i; j--)
if (a[i] > a[j])
dp[1][i] = max(dp[1][i], dp[1][j] + 1);
for (int i = 1; i <= n; i++)
ans = max(dp[0][i] + dp[1][i] - 1, ans);
printf("%d\n", n - ans);
return 0;
} Problem D Even? Odd?
题目链接：https://ac.nowcoder.com/acm/contest/1082/D
题意: 判断一个大数的奇偶性。
思路: 直接判断个位数是奇是偶。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 65;
const int MAXM = 45005;
char str[MAXN];
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%s", str);
int len = strlen(str);
if ((str[len - 1] - '0') & 1)
printf("odd\n");
else printf("even\n");
}
return 0;
} Problem E Invasion of the Milkweed
题目链接：https://ac.nowcoder.com/acm/contest/1082/E
题意: 首先，是八个方向，也就是一圈。入侵的范围关于时间是成辐射型扩散，最少需要多少时间才能占领整个草地。
思路: BFS, 题目主要坑点就是坐标，"(1,1)是左下角的格(也就是说坐标排布跟一般的X,Y坐标相同)" ,所以我们只要能把给出的坐标转化成正常数组的下标就可以正常搜索了。将一个含有坐标及当前的步数的结构体读入到队列里面，然后正常搜索就行了。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int dir[8][2]{{1, 0}, {-1, 0}, {1, 1}, {0, 1}, {-1, 1}, {1, -1}, {0, -1}, {-1, -1}};
char mp[MAXN][MAXN];
bool vis[MAXN][MAXN];
struct edge {
int x, y, t;
edge() {}
edge(int x, int y, int t) : x(x), y(y), t(t) {}
}p;
int BFS(int x, int y, int n, int m) {
int t = 0;
queue <edge> Q;
Q.push(edge(x, y, 0));
vis[x][y] = true;
while (!Q.empty()) {
p = Q.front();
Q.pop();
t = max(t, p.t);
for (int j = 0; j < 8; j++) {
int tx = p.x + dir[j][0];
int ty = p.y + dir[j][1];
if (tx > 0 && tx <= m && ty > 0 && ty <= n && mp[tx][ty] == '.' && !vis[tx][ty]) {
vis[tx][ty] = true;
Q.push(edge(tx, ty, p.t + 1));
}
}
}
return t;
}
int main() {
int n, m, x, y;
scanf("%d%d%d%d", &n, &m, &y, &x);
for (int i = m; i >= 1; i--) {
for (int j = 1; j <= n; j++) {
scanf(" %c", &mp[i][j]);
}
}
printf("%d\n", BFS(x, y, n, m));
return 0;
} Problem F Heat Wave
题目链接：https://ac.nowcoder.com/acm/contest/1082/F
题意: 求从起始的城镇Ts到终点的城镇Te最小的总费用。
思路: 最短路，直接上Spfa。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2505;
const int MAXM = 6205;
struct List {
int v, w, ne;
List() {}
List(int v, int w, int ne) : v(v), w(w), ne(ne) {}
}list_[MAXM << 1];
bool vis[MAXN];
int head[MAXN], dis[MAXN], Adj = 0;
void Add(int u, int v, int w) {
list_[++Adj] = List(v, w, head[u]);
head[u] = Adj;
}
void init() {
Adj = 0;
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
memset(head, -1, sizeof(head));
}
int Spfa(int s, int e) {
queue <int> Q;
Q.push(s);
dis[s] = 0;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
vis[u] = false;
for (int i = head[u]; ~i; i = list_[i].ne) {
int v = list_[i].v;
if (dis[v] > dis[u] + list_[i].w) {
dis[v] = dis[u] + list_[i].w;
if (!vis[v]) {
Q.push(v);
vis[v] = true;
}
}
}
}
return dis[e];
}
int main() {
init();
int T, C, Ts, Te;
scanf("%d%d%d%d", &T, &C, &Ts, &Te);
for (int i = 0; i < C; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
Add(u, v, w), Add(v, u, w);
}
printf("%d\n", Spfa(Ts, Te));
return 0;
} Problem G The Leisurely Stroll
题目链接：https://ac.nowcoder.com/acm/contest/1082/G
题意: 问Bessie最多能走过多少分岔节点，也就是求树的深度。
思路: DFS(BFS也可以)。判断左右分岔是否为牧场，如果不是就继续向下走，边搜索边更新答案。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
struct Tree {
int lson, rson;
}seg[MAXN];
int DFS(int rt, int dep) {//到达分岔节点rt，共走过了dep个分岔节点
int cnt = dep;
if (seg[rt].lson)//如果不是牧场就前往这个分岔节点
cnt = max(cnt, DFS(seg[rt].lson, dep + 1));
if (seg[rt].rson)
cnt = max(cnt, DFS(seg[rt].rson, dep + 1));
return cnt;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, l, r;
scanf("%d%d%d", &u, &l, &r);
seg[u].lson = l, seg[u].rson = r;
}
printf("%d\n", DFS(1, 1));
return 0;
} Problem H Papaya Jungle
题目链接：https://ac.nowcoder.com/acm/contest/1082/H
题意: Bessie总是走到那个有最多没有被吃掉的木瓜的邻接的格子(保证这样的格子只有一个)。按照这种移动方法，最终Bessie总是会在(R,C)停止然后吃掉那里的木瓜,求Bessie一共吃了多少个木瓜。
思路: 从起点开始，每次走到四周最多的那个，然后一直递归直到走到(r, c)为止。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 45;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int n, m, spt[MAXN][MAXN];
int DFS(int x, int y) {
int ans = spt[x][y];
if (x >= n - 1 && y >= m - 1)
return ans;
int mx, my, cnt = 0;
spt[x][y] = 0;
for (int i = 0; i < 4; i++) {
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (tx >= 0 && tx < n && ty >= 0 && ty < m && cnt < spt[tx][ty]) {//找最多的
mx = tx, my = ty;
cnt = spt[tx][ty];
}
}
return ans + DFS(mx, my);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &spt[i][j]);
printf("%d\n", DFS(0, 0));
return 0;
} Problem I Barn Echoes
题目链接：https://ac.nowcoder.com/acm/contest/1082/I
题意: 求两个字符串最长的重复部份的长度。两个字符串的重复部份指的是同时是一个字符串的前缀和另一个字符串的后缀的字符串。
思路: 直接暴力可以，用STL也可以，这里我就讲一下用KMP来解决这道题。
这一题很明显就是一道字符串匹配的问题。
KMP在匹配的时候，当子串去匹配主串的时候，当主串匹配完的时候，那么此时子串匹配的长度就是主串的后缀和子串的前缀的最长重复值。
见下图：
此时j就是最长的重复值，两个串一个当主串，一个当子串，取最大值就是答案。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int nex[MAXN];
char sa[MAXN], sb[MAXN];
void Next(char str[], int len) {
int i = 0, j = -1;
nex[0] = -1;
while (i < len) {
if (~j && str[i] != str[j])
j = nex[j];
else nex[++i] = ++j;
}
}
int KMP(char sa[], int la, char sb[], int lb) {
Next(sb, lb);
int i = 0, j = 0;
while (i < la) {
if (~j && sa[i] != sb[j])
j = nex[j];
else i++, j++;
}
return j;
}
int main() {
scanf("%s%s", sa, sb);
int la = strlen(sa);
int lb = strlen(sb);
int cnta = KMP(sa, la, sb, lb);
int cntb = KMP(sb, lb, sa, la);
printf("%d\n", max(cnta, cntb));
return 0;
} Problem J The Robot Plow
题目链接：https://ac.nowcoder.com/acm/contest/1082/J
题意: 每次给你一个矩形，将矩形里面的地给犁了，求最后犁过地的面积。
思路: 因为数据过小，直接暴力就可以过了。在这里我们可以将一个方向转化为差分来解决，减小了一个循环。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 255;
int p[MAXN][MAXN];
int main() {
int n, m, t;
scanf("%d%d%d", &n, &m, &t);
for (int i = 0; i < t; i++) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
for (int i = x1; i <= x2; i++)//每行做一次差分
p[i][y1]++, p[i][y2 + 1]--;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
p[i][j] += p[i][j - 1];
if (p[i][j])//犁过地了
ans++;//计数器加一
}
}
printf("%d\n", ans);
return 0;
} Problem K Bessie's Weight Problem
题目链接：https://ac.nowcoder.com/acm/contest/1082/K
题意: 求Bessie在限制范围内最多可以吃多少公斤的干草。
思路: 01背包。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const int MAXM = 45005;
int dp[MAXM], spt[MAXN];
int main() {
int n, m;
scanf("%d%d", &m, &n);
for (int i = 0; i < n; i++) {
scanf("%d", &spt[i]);
for (int j = m; j >= spt[i]; j--)
dp[j] = max(dp[j], dp[j - spt[i]] + spt[i]);
}
printf("%d\n", dp[m]);
return 0;
} Problem L 津津的储蓄计划
题目链接：https://ac.nowcoder.com/acm/contest/1082/L
题意: 每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100或恰好100，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。判断会不会出现，在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果不会，计算津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。
思路: 直接模拟就行了。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, ans = 0, da = 0, money = 0;
for (int i = 1; i <= 12; i++) {
scanf("%d", &a);
money += 300 - a;
if (money < 0) {
da = i;
break;
}
ans += money / 100;
money %= 100;
}
if (da)
printf("%d\n", -da);
else printf("%d\n", money + ans * 120);
return 0;
} 
京公网安备 11010502036488号