题库链接戳这里
A. Choosing Ice Cream
给出n，k。即有n种冰淇淋，你有一个k面骰子，问最少摇几次骰子能公平地决定出选择。不可公平抉择出的话输出"unbounded"。
如果n=1，那么不必抉择，直接为0.
否则解应该是使得k^(i) mod n 成立的最小i。留意，K范围10^9，那么要用long long，否则溢出。因为n也是10^9内，所以解i，最多就是log2(n)，即29，写30也可以，越出这个还没找到应该认为无解。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxN = 1e5 + 5;
ll N, M, K, T;
int main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld %lld", &N, &K);
if (N == 1) {
puts("0");
continue;
}
int ans = 0;
int tk = K;
K = 1;
int cnt = 1;
while (K != 0) {
K = (K * tk) % N;
ans += 1;
if (cnt++ > 30) {
puts("unbounded");
break;
}
}
if (cnt <= 30)
printf("%d\n", ans);
}
return 0;
}
B. Failing Components
有一幅图，某些点坏了之后，经一定延迟（边权）会导致以他为基础的点的损坏。给出N，D，C，即点数，边数，初始坏点编号，问这个点会导致多少坏点（包括自己），以及所有点坏了之后，用时多少。
建立边的struct，记录终点和边权，再来一个dis，dis[i]表示源点蔓延至i点的最少耗时，初始化为inf。那么能蔓延到的必将非inf，可更新的时候更新为更小值，这个用bfs完成更新。最后非inf的个数和非inf的最大值即为解。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = 0x3f3f3f3f, maxN = 1e5 + 5;
int N, M, K, T, D, C;
int dis[maxN];
struct Edge {
int to, cost;
Edge(int a = 0, int b = 0, int c = 0) :
to(a), cost(b) {}
};
vector<Edge> E[maxN];
void bfs(int s) {
queue<int> Q;
memset(dis, inf, sizeof(dis));
dis[s] = 0;
Q.push(s);
while (!Q.empty()) {
int t = Q.front();
Q.pop();
for (int i = 0; i < E[t].size(); ++i) {
int nxt = E[t][i].to;
if (dis[nxt] > dis[t] + E[t][i].cost) {
dis[nxt] = dis[t] + E[t][i].cost;
Q.push(nxt);
}
}
}
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &N, &D, &C);
for (int i = 1; i <= N; ++i)
E[i].clear();
int u, v, w;
for (int i = 0; i < D; ++i) {
scanf("%d%d%d", &u, &v, &w);
E[v].push_back(Edge(u, w));
}
bfs(C);
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= N; ++i) {
if (dis[i] != inf) {
++ans1;
ans2 = max(ans2, dis[i]);
}
}
printf("%d %d\n", ans1, ans2);
}
return 0;
}
D. Lift Problems
题意: 有一栋N层([1,N]层)高的楼，一开始有很多人，认为在第0层。电梯从0层收完人后开始往上统计愤怒值。先给出每一层楼欲停的人数。若还没到自己想到的楼层而提早电梯开门（停）了，这部分人愤怒值+1。若经过自己想停的楼层而没停，这部分人愤怒值+1，而且会在下一次停的时候，即在更高楼层出来，走楼梯回自己的目的地，可以认为消失。问：运完所有人，愤怒值最少可以是多少？
一开始想的贪心，其实有漏洞。原因在于：决策的时候，判断的根据是不完整的。我一开始想，假设在b1层有a1人要停，下一次停的地方是b2层，有a2人要下。那么在b1层，根据电梯停与不停，计算出两种愤怒值，取小的进行贪心决策。关键在于：下一次停的地方未知，所以思路错误。
正确方法是dp。令dp[i]为在i层停的时候的最小愤怒值。然后搜索所有直接到达i层的方式，在这所有方式中，找愤怒值最小的作为答案即可。最终答案是dp[N]。
进一步解析：第i层停的最小愤怒值，应该是比自己低的楼层j的最小愤怒值加上由于从j直接到i，这之间由于跳过一些楼层产生的 skipAnger，以及，比i层高的那些楼层因为在i层停而产生的愤怒值。
这里有个小地方可以留意：按理说j习惯从0到i-1扫过去，找dp最小值，但是每一层都要统计该层到i-1层的skipAnger，不如从i-1层往前遍历，skipAnger逐层递增，利用后缀和顺畅地去掉了一个for循环。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = 0x3f3f3f3f, maxN = 2e3 + 5;
int N, M, T;
ll S[maxN], dp[maxN];
// dpi 在第i层停留的最小愤怒值
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &N);
ll sum = 0;
for (int i = 1; i <= N; ++i) {
scanf("%lld", &S[i]);
sum += S[i];
}
dp[0] = 0;
for (int i = 1; i <= N; ++i) {
sum -= S[i];
ll skipAnger = 0;
dp[i] = inf;
for (int j = i - 1; j >= 0; --j) {
dp[i] = min(dp[i], dp[j] + skipAnger + sum);
skipAnger += (i - j) * S[j];
}
}
printf("%lld\n", dp[N]);
}
return 0;
}
F.Runway Planning
水题，给一个数字n，n/10后的小数四舍五入后取整。如果n=0，则改为取18，记得不足2位补零。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int N, T;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &N);
N += 5;
N /= 10;
N %= 18;
if (N == 0)
N = 18;
printf("%02d\n", N);
}
return 0;
}
网友评论