第一題：跳一跳

近來，跳一跳這款小游戲風(fēng)靡全國，受到不少玩家的喜愛。

簡化后的跳一跳規(guī)則如下：玩家每次從當(dāng)前方塊跳到下一個(gè)方塊，如果沒有跳到下一個(gè)方塊上則游戲結(jié)束。

如果跳到了方塊上，但沒有跳到方塊的中心則獲得?1?分；跳到方塊中心時(shí)，若上一次的得分為?1?分或這是本局游戲的第一次跳躍則此次得分為?2 分，否則此次得分比上一次得分多兩分（即連續(xù)跳到方塊中心時(shí)，總得分將?+2，+4，+6，+8…）。

現(xiàn)在給出一個(gè)人跳一跳的全過程，請你求出他本局游戲的得分（按照題目描述的規(guī)則）。

輸入格式

輸入包含多個(gè)數(shù)字，用空格分隔，每個(gè)數(shù)字都是?1，2，0 之一，1?表示此次跳躍跳到了方塊上但是沒有跳到中心，2?表示此次跳躍跳到了方塊上并且跳到了方塊中心，0?表示此次跳躍沒有跳到方塊上（此時(shí)游戲結(jié)束）。

輸出格式

輸出一個(gè)整數(shù)，為本局游戲的得分（在本題的規(guī)則下）。

數(shù)據(jù)范圍

對于所有評測用例，輸入的數(shù)字不超過?30?個(gè)，保證?0?正好出現(xiàn)一次且為最后一個(gè)數(shù)字。

輸入樣例：

1 1 2 2 2 1 1 2 2 0

輸出樣例：

22

?解題思路：

直接模擬

#include<iostream>using namespace std;int main()
{int last = 1;int n;int res = 0;while(cin >> n){if(n == 0) break;if(n == 1) res ++ , last = 1;else {if(last == -1 || last == 1) res += 2 , last = 2;else res += (last + 2) , last += 2;}}cout << res << endl;return 0;
}

第二題：碰撞的小球

數(shù)軸上有一條長度為?L（L?為偶數(shù))的線段，左端點(diǎn)在原點(diǎn)，右端點(diǎn)在坐標(biāo)?L?處。

有?n?個(gè)不計(jì)體積的小球在線段上，開始時(shí)所有的小球都處在偶數(shù)坐標(biāo)上，速度方向向右，速度大小為?1?單位長度每秒。

當(dāng)小球到達(dá)線段的端點(diǎn)（左端點(diǎn)或右端點(diǎn)）的時(shí)候，會立即向相反的方向移動，速度大小仍然為原來大小。

當(dāng)兩個(gè)小球撞到一起的時(shí)候，兩個(gè)小球會分別向與自己原來移動的方向相反的方向，以原來的速度大小繼續(xù)移動。

現(xiàn)在，告訴你線段的長度?L，小球數(shù)量?n?，以及?n?個(gè)小球的初始位置，請你計(jì)算?t?秒之后，各個(gè)小球的位置。

提示

因?yàn)樗行∏虻某跏嘉恢枚紴榕紨?shù)，而且線段的長度為偶數(shù)，可以證明，不會有三個(gè)小球同時(shí)相撞，小球到達(dá)線段端點(diǎn)以及小球之間的碰撞時(shí)刻均為整數(shù)。

同時(shí)也可以證明兩個(gè)小球發(fā)生碰撞的位置一定是整數(shù)（但不一定是偶數(shù)）。

輸入格式

輸入的第一行包含三個(gè)整數(shù)?n,L,t，用空格分隔，分別表示小球的個(gè)數(shù)、線段長度和你需要計(jì)算?t?秒之后小球的位置。

第二行包含?n?個(gè)整數(shù)?a1,a2,…,an，用空格分隔，表示初始時(shí)刻?n?個(gè)小球的位置。

輸出格式

輸出一行包含?n?個(gè)整數(shù)，用空格分隔，第?i?個(gè)整數(shù)代表初始時(shí)刻位于?ai?的小球，在?t?秒之后的位置。

數(shù)據(jù)范圍

對于所有評測用例，1≤n≤100，1≤t≤100，2≤L≤1000，0<ai<L。L?為偶數(shù)。

保證所有小球的初始位置互不相同且均為偶數(shù)。

輸入樣例1：

3 10 5
4 6 8

輸出樣例1：

7 9 9

樣例1解釋

初始時(shí)，三個(gè)小球的位置分別為?4,6,8。

一秒后，三個(gè)小球的位置分別為?5,7,9。

兩秒后，第三個(gè)小球碰到墻壁，速度反向，三個(gè)小球位置分別為?6,8,10。

三秒后，第二個(gè)小球與第三個(gè)小球在位置?9?發(fā)生碰撞，速度反向（注意碰撞位置不一定為偶數(shù)），三個(gè)小球位置分別為?7,9,9。

四秒后，第一個(gè)小球與第二個(gè)小球在位置8發(fā)生碰撞，速度反向，第三個(gè)小球碰到墻壁，速度反向，三個(gè)小球位置分別為?8,8,10。

五秒后，三個(gè)小球的位置分別為?7,9,9。

輸入樣例2：

10 22 30
14 12 16 6 10 2 8 20 18 4

輸出樣例2：

6 6 8 2 4 0 4 12 10 2

解題思路：

使用結(jié)構(gòu)體存儲小球當(dāng)前的狀態(tài) +1 表示向右 ， -1表示向左

第一種情況，到邊界的時(shí)候?qū)⒎较蛑梅醇纯?/span>

第二種情況，正常運(yùn)動時(shí)

? ? ? ? （1）下一秒的時(shí)候沒有遇到球，當(dāng)前位置加上方向信息

? ? ? ? （2）下一秒的時(shí)候遇到球的時(shí)候，將兩個(gè)球反向

#include<iostream>
#include<cstring>using namespace std;const int N = 110;
int n , l , t;
struct node
{int idx , dir; // +1 表示向右 ， -1表示向左
}a[N];void change()
{int cnt[10 * N];memset(cnt , -1 , sizeof cnt);for(int i = 0;i < n;i ++){if(a[i].idx == 0 || a[i].idx == l) a[i].dir = -a[i].dir;if(cnt[a[i].idx] != -1){a[i].dir = -a[i].dir;a[cnt[a[i].idx]].dir = -a[cnt[a[i].idx]].dir;}else cnt[a[i].idx] = i;}for(int i = 0;i < n;i ++)a[i].idx += a[i].dir;
}int main()
{cin >> n >> l >> t;for(int i = 0;i < n;i ++){int x;cin >> x;a[i] = {x , 1};}while(t --){change();}for(int i = 0;i < n;i ++)cout << a[i].idx << " ";return 0;
}

第三題：URL映射

題目略

解題思路：?

其中三個(gè)重要的函數(shù)

（1）get_number函數(shù)：獲取字符串中的數(shù)字并且返回該數(shù)的字符串

（2）get函數(shù)：將每一條URL映射解析

• ? ? ? 如果匹配，那么返回一個(gè)vector存儲的是對應(yīng)URL請求的解析后的結(jié)果
• ? ? ? 如果不匹配，?那么返回一個(gè)空的vector

（3）work函數(shù)：盡心處理每一條URL請求

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;const int N = 110;int n, m;
struct Url
{string path, name;
}url[N];string get_number(string& str)
{string res;for (auto c: str)if (c >= '0' && c <= '9')res += c;else{res.clear();return res;}// 去掉前導(dǎo)0int k = 0;while (k + 1 < res.size() && res[k] == '0') k ++ ;return res.substr(k);
}vector<string> get(string& path, string& str)
{vector<string> res(1);int i, j;for (i = 1, j = 1; i < path.size() && j < str.size();){int u = i + 1, v = j + 1;while (u < path.size() && path[u] != '/') u ++ ;while (v < str.size() && str[v] != '/') v ++ ;string a = path.substr(i, u - i), b = str.substr(j, v - j);if (a == "<str>"){res.push_back(b);i = u + 1, j = v + 1;}else if (a == "<int>"){auto t = get_number(b);if (t.empty()){res.clear();return res;}res.push_back(t);i = u + 1, j = v + 1;}else if (a == "<path>"){res.push_back(str.substr(j));return res;}else if (a != b){res.clear();return res;}else i = u + 1, j = v + 1;}if (i - path.size() != j - str.size()) res.clear();return res;
}void work(string& str)
{for (int i = 0; i < n; i ++ ){auto res = get(url[i].path, str);if (res.size()){cout << url[i].name;for (int j = 1; j < res.size(); j ++ )cout << ' ' << res[j];cout << endl;return;}}puts("404");
}int main()
{cin >> n >> m;for (int i = 0; i < n; i ++ ) cin >> url[i].path >> url[i].name;while (m -- ){string str;cin >> str;work(str);}return 0;
}

第四題：棋局評估

Alice 和 Bob 正在玩井字棋游戲。

井字棋游戲的規(guī)則很簡單：兩人輪流往?3×3 的棋盤中放棋子，Alice 放的是?X，Bob 放的是?O，Alice執(zhí)先。

當(dāng)同一種棋子占據(jù)一行、一列或一條對角線的三個(gè)格子時(shí)，游戲結(jié)束，該種棋子的持有者獲勝。

當(dāng)棋盤被填滿的時(shí)候，游戲結(jié)束，雙方平手。

Alice 設(shè)計(jì)了一種對棋局評分的方法：

• 對于 Alice 已經(jīng)獲勝的局面，評估得分為(棋盤上的空格子數(shù)+1)；
• 對于 Bob 已經(jīng)獲勝的局面，評估得分為 -(棋盤上的空格子數(shù)+1)；
• 對于平局的局面，評估得分為?0；

例如上圖中的局面，Alice 已經(jīng)獲勝，同時(shí)棋盤上有?2?個(gè)空格，所以局面得分為?2+1=3。

由于 Alice 并不喜歡計(jì)算，所以他請教擅長編程的你，如果兩人都以最優(yōu)策略行棋，那么當(dāng)前局面的最終得分會是多少？

輸入格式

輸入的第一行包含一個(gè)正整數(shù)?T，表示數(shù)據(jù)的組數(shù)。

每組數(shù)據(jù)輸入有?3?行，每行有?3 個(gè)整數(shù)，用空格分隔，分別表示棋盤每個(gè)格子的狀態(tài)。0?表示格子為空，1?表示格子中為X，2?表示格子中為?O。保證不會出現(xiàn)其他狀態(tài)。

保證輸入的局面合法。(即保證輸入的局面可以通過行棋到達(dá)，且保證沒有雙方同時(shí)獲勝的情況)

保證輸入的局面輪到 Alice 行棋。

輸出格式

對于每組數(shù)據(jù)，輸出一行一個(gè)整數(shù)，表示當(dāng)前局面的得分。

數(shù)據(jù)范圍

1≤T≤5

輸入樣例：

3
1 2 1
2 1 2
0 0 0
2 1 1
0 2 1
0 0 2
0 0 0
0 0 0
0 0 0

輸出樣例：

3
-4
0

樣例解釋

第一組數(shù)據(jù)：

Alice 將棋子放在左下角(或右下角)后，可以到達(dá)問題描述中的局面，得分為?3。

3?為 Alice 行棋后能到達(dá)的局面中得分的最大值。

第二組數(shù)據(jù)：

Bob 已經(jīng)獲勝(如圖)，此局面得分為??(3+1)=?4。

第三組數(shù)據(jù)：

井字棋中若雙方都采用最優(yōu)策略，游戲平局，最終得分為?0。

?解題思路：

其中有三個(gè)函數(shù)

（1）dfs函數(shù)：求最終的得分，使用深度優(yōu)先搜索進(jìn)行遍歷每一種情況

（2）cal函數(shù)：計(jì)算每一個(gè)狀態(tài)時(shí)的空格的數(shù)量

（3）check函數(shù)：對于一個(gè)人判斷是否是一個(gè)獲勝的情況

#include<iostream>using namespace std;const int N = 5 , INF = 1e8;
int g[N][N];bool check(int x)
{// 判斷行列for(int i = 0;i < 3;i ++){int s = 0;for(int j = 0;j < 3;j ++)if(g[i][j] == x) s ++;if(s == 3) return true;s = 0;for(int j = 0;j < 3;j ++)if(g[j][i] == x) s ++;if(s == 3) return true;}if(g[0][0] == x && g[1][1] == x && g[2][2] == x) return true;if(g[2][0] == x && g[1][1] == x && g[0][2] == x) return true;return false;
}int cal()
{int s = 0;// 計(jì)算空格的數(shù)量for(int i = 0;i < 3;i ++)for(int j = 0;j < 3;j ++)if(!g[i][j]) s ++;// alice贏if(check(1)) return s + 1;// bob贏if(check(2)) return -(s + 1);// 平局if(!s) return 0;return INF;
}int dfs(int u)
{int t = cal();if(t != INF) return t;if(!u){// alice 搜索最大值 X 使用1表示int res = -INF;for(int i = 0;i < 3;i ++)for(int j = 0;j < 3;j ++)if(!g[i][j]){g[i][j] = 1;res = max(res , dfs(1));g[i][j] = 0;}return res;}else{// bob 搜索最小值 O 使用2表示int res = INF;for(int i = 0;i < 3;i ++)for(int j = 0;j < 3;j ++)if(!g[i][j]){g[i][j] = 2;res = min(res , dfs(0));g[i][j] = 0;}return res;}
}int main()
{int t;cin >> t;while(t --){for(int i = 0;i < 3;i ++)for(int j = 0;j < 3;j ++)cin >> g[i][j];// 0表示alice 1表示bobcout << dfs(0) << endl;}
}

第五題：二次求和

線段樹+前綴和+樹（不會）

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;
const int N = 100010, M = N * 2, MOD = 1e9 + 7;int n, m, L, R;
int w[N];
int h[N], father[N], e[M], ne[M], idx;
int depth[N], fa[N][17];
int path[N], d[N], que[N];
int pos[N], root[N];
bool st[N];
int tr[N];
struct Node
{int d, w, id;bool operator< (const Node& t) const{return d < t.d;}
}q[N], p[N];inline void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}inline int lowbit(int x)
{return x & -x;
}inline void update(int x, int v, int k)
{for (int i = x; i <= k; i += lowbit(i)) tr[i] = (tr[i] + v) % MOD;
}inline int query(int x, int k)
{x = min(x, k);int res = 0;for (int i = x; i > 0; i -= lowbit(i)) res = (res + tr[i]) % MOD;return res;
}void bfs()
{memset(depth, 0x3f, sizeof depth);depth[0] = 0, depth[1] = 1;int hh = 0, tt = 0;que[0] = 1;while (hh <= tt){int t = que[hh ++ ];for (int i = h[t]; ~i; i = ne[i]){int j = e[i];if (depth[j] > depth[t] + 1){depth[j] = depth[t] + 1;que[ ++ tt] = j;fa[j][0] = t;for (int k = 1; k <= 16; k ++ )fa[j][k] = fa[fa[j][k - 1]][k - 1];}}}
}inline int lca(int a, int b)
{if (depth[a] < depth[b]) swap(a, b);for (int k = 16; k >= 0; k -- )if (depth[fa[a][k]] >= depth[b])a = fa[a][k];if (a == b) return a;for (int k = 16; k >= 0; k -- )if (fa[a][k] != fa[b][k]){a = fa[a][k];b = fa[b][k];}return fa[a][0];
}void dfs(int u, int fa)
{d[u] = (d[fa] + path[u]) % MOD;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (j == fa) continue;dfs(j, u);}
}int get_size(int u, int fa)
{if (st[u]) return 0;int res = 1;for (int i = h[u]; ~i; i = ne[i])if (e[i] != fa)res += get_size(e[i], u);return res;
}int get_wc(int u, int fa, int tot, int& wc)
{if (st[u]) return 0;int sum = 1, ms = 0;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (j == fa) continue;int t = get_wc(j, u, tot, wc);ms = max(ms, t);sum += t;}ms = max(ms, tot - sum);if (ms <= tot / 2) wc = u;return sum;
}void get_dist(int u, int fa, int dist, int sum, int& qt)
{if (st[u]) return;q[ ++ qt] = {dist, sum, u};for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (j != fa)get_dist(j, u, dist + 1, (sum + w[j]) % MOD, qt);}
}inline int get(Node a[], int k, int limit, int wu, int& pu)
{sort(a + 1, a + k + 1);static int sum[N];int res = 0;for (int i = 1; i <= k; i ++ ) sum[i] = (sum[i - 1] + a[i].w) % MOD;for (int i = 1, j = k; i < j; i ++ ){while (j > i && a[j].d + a[i].d - 1 > limit) j -- ;if (j > i && a[j].d + a[i].d - 1 <= limit){res = (res + (LL)sum[j] - sum[i] + (LL)(j - i) * a[i].w - (LL)wu * (j - i)) % MOD;pu = (pu + j - i) % MOD;}}return res;
}int dfs_path(int u, int fa, int dist, int maxd)
{if (st[u]) return 0;int res = (query(R + 1 - dist, maxd) - query(L - dist, maxd)) % MOD;if (dist >= L && dist <= R) res = (res + 1) % MOD;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (j != fa)res = (res + dfs_path(j, u, dist + 1, maxd)) % MOD;}path[u] = (path[u] + res) % MOD;return res;
}int calc(int u)
{if (st[u]) return 0;get_wc(u, -1, get_size(u, -1), u);st[u] = true;int res = 0, pt = 0;if (L <= 1 && R >= 1) res = w[u], path[u] = (path[u] + 1) % MOD;int cnt = 0, maxd = 0;for (int i = h[u]; ~i; i = ne[i]){int j = e[i], qt = 0;if (st[j]) continue;get_dist(j, -1, 2, (w[u] + w[j]) % MOD, qt);int pR = 0, pL = 0;res = (res - (LL)(get(q, qt, R, w[u], pR) - get(q, qt, L - 1, w[u], pL))) % MOD;path[u] = (path[u] - (LL)(pR - pL)) % MOD;pos[ ++ cnt] = pt + 1;  // 每一段開頭root[cnt] = j;  // 每一段的根節(jié)點(diǎn)for (int k = 1; k <= qt; k ++ ){if (q[k].d >= L && q[k].d <= R){res = (res + q[k].w) % MOD;path[u] = (path[u] + 1) % MOD;  // 只計(jì)算從u到當(dāng)前點(diǎn)的}p[ ++ pt] = q[k];maxd = max(maxd, q[k].d);}}pos[cnt + 1] = pt + 1;  // 哨兵for (int i = 1; i <= maxd; i ++ ) tr[i] = 0;for (int i = 1; i <= pt; i ++ ) update(p[i].d, 1, maxd);  // 插入樹狀數(shù)組中for (int i = 1; i <= cnt; i ++ ){int l = pos[i], r = pos[i + 1] - 1;for (int j = l; j <= r; j ++ ) update(p[j].d, -1, maxd);  // 將當(dāng)前子樹中的節(jié)點(diǎn)刪掉dfs_path(root[i], u, 2, maxd);for (int j = l; j <= r; j ++ ) update(p[j].d, 1, maxd);  // 將當(dāng)前子樹中的節(jié)點(diǎn)添加回來}int pR = 0, pL = 0;res = (res + (LL)get(p, pt, R, w[u], pR) - get(p, pt, L - 1, w[u], pL)) % MOD;path[u] = (path[u] + (LL)pR - pL) % MOD;for (int i = h[u]; ~i; i = ne[i]) res = (res + calc(e[i])) % MOD;return res;
}int main()
{int T;scanf("%d", &T);while (T -- ){scanf("%d%d%d%d", &n, &m, &L, &R);memset(h, -1, sizeof h), idx = 0;memset(path, 0, sizeof path);for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);for (int i = 2; i <= n; i ++ ){int p;scanf("%d", &p);add(i, p), add(p, i);father[i] = p;}memset(st, 0, sizeof st);int res = calc(1);dfs(1, 0);bfs();while (m -- ){int a, b, c;scanf("%d%d%d", &a, &b, &c);int p = lca(a, b);int sum = (d[a] + (LL)d[b] - d[p] * 2 + path[p]) * c % MOD;res = ((res + sum) % MOD + MOD) % MOD;printf("%d\n", res);}}return 0;
}

?