題庫鏈接戳這里
A. Choosing Ice Cream
給出n曙痘，k腰耙。即有n種冰淇淋源请，你有一個k面骰子枪芒，問最少搖幾次骰子能公平地決定出選擇。不可公平抉擇出的話輸出"unbounded"巢钓。
如果n=1病苗，那么不必抉擇，直接為0.
否則解應(yīng)該是使得k^(i) mod n 成立的最小i症汹。留意，K范圍10^9贷腕，那么要用long long背镇，否則溢出。因為n也是10^9內(nèi)泽裳，所以解i，最多就是log2(n)，即29掘鄙，寫30也可以掌栅，越出這個還沒找到應(yīng)該認(rèn)為無解。
#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
有一幅圖瀑梗，某些點壞了之后烹笔，經(jīng)一定延遲（邊權(quán)）會導(dǎo)致以他為基礎(chǔ)的點的損壞。給出N抛丽，D谤职，C，即點數(shù)亿鲜，邊數(shù)允蜈，初始壞點編號，問這個點會導(dǎo)致多少壞點（包括自己），以及所有點壞了之后饶套，用時多少漩蟆。
建立邊的struct，記錄終點和邊權(quán)妓蛮，再來一個dis爆安，dis[i]表示源點蔓延至i點的最少耗時，初始化為inf仔引。那么能蔓延到的必將非inf扔仓，可更新的時候更新為更小值，這個用bfs完成更新咖耘。最后非inf的個數(shù)和非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]層)高的樓，一開始有很多人儿倒，認(rèn)為在第0層版保。電梯從0層收完人后開始往上統(tǒng)計憤怒值。先給出每一層樓欲停的人數(shù)夫否。若還沒到自己想到的樓層而提早電梯開門（停）了彻犁，這部分人憤怒值+1。若經(jīng)過自己想停的樓層而沒停凰慈，這部分人憤怒值+1汞幢，而且會在下一次停的時候，即在更高樓層出來微谓，走樓梯回自己的目的地森篷，可以認(rèn)為消失。問：運完所有人豺型，憤怒值最少可以是多少仲智？
一開始想的貪心，其實有漏洞姻氨。原因在于：決策的時候钓辆，判斷的根據(jù)是不完整的。我一開始想肴焊，假設(shè)在b1層有a1人要停前联，下一次停的地方是b2層，有a2人要下抖韩。那么在b1層蛀恩，根據(jù)電梯停與不停，計算出兩種憤怒值茂浮，取小的進(jìn)行貪心決策双谆。關(guān)鍵在于：下一次停的地方未知壳咕，所以思路錯誤。
正確方法是dp顽馋。令dp[i]為在i層停的時候的最小憤怒值谓厘。然后搜索所有直接到達(dá)i層的方式，在這所有方式中寸谜，找憤怒值最小的作為答案即可竟稳。最終答案是dp[N]。
進(jìn)一步解析：第i層停的最小憤怒值熊痴，應(yīng)該是比自己低的樓層j的最小憤怒值加上由于從j直接到i他爸，這之間由于跳過一些樓層產(chǎn)生的 skipAnger，以及果善，比i層高的那些樓層因為在i層停而產(chǎn)生的憤怒值诊笤。
這里有個小地方可以留意：按理說j習(xí)慣從0到i-1掃過去，找dp最小值巾陕，但是每一層都要統(tǒng)計該層到i-1層的skipAnger讨跟，不如從i-1層往前遍歷，skipAnger逐層遞增鄙煤，利用后綴和順暢地去掉了一個for循環(huán)晾匠。
#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
水題，給一個數(shù)字n梯刚，n/10后的小數(shù)四舍五入后取整凉馆。如果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;
}
