偏简单
A 爬山 题目：
（签到）
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> using namespace std ;const int N = 5e5 + 5 ;int a[N], n;int ans;int main () scanf ("%d" , &n); for (int i = 1 ; i <= n; i++){ scanf ("%d" , &a[i]); } for (int i = 1 ; i < n; i++){ ans = max(ans, abs (a[i] - a[i+1 ])); } printf ("%d\n" , ans); return 0 ; }
B 纸片 题目：
T组输入，每组输入l, r。求 l (l +1)(l +2)…(r −1)r ，例如 l =2,r =6, 连在一起后得到 23456，问这个数字是不是9的倍数。
题解：
1 ≤ T ≤ 10000,1 ≤ l ≤ r ≤ 1e12 。
首先一个数字是不是9的倍数，看各位和是不是9的倍数。
打表看了一下1-10000中每个数各位和模9之后的结果就发现了1，2，3……8，9， 0的规律，接下来就只需要看l，r分别对应的模数是多少，然后把对应这段加起来判断和是不是9的倍数即可。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> using namespace std ;const int N = 5e5 + 5 ;int t;long long l, r;int f (long long x) int res = 0 ; while (x){ res += x % 10 ; x /= 10 ; } return res % 9 ; } int main () scanf ("%d" , &t); while (t--){ scanf ("%lld%lld" , &l, &r); int x = f(l), y = f(r); int ans = 0 ; for (int i = x; i <= y + 9 ; i++){ ans += i; } if (ans % 9 == 0 ){ printf ("Y\n" ); } else printf ("N\n" ); } return 0 ; }
C颜色 题目：
现在给定一张 n * M 的网格图，网格中如果当前这个有颜色，那么是一个非零的数字，如果这个点没有颜色，那么为0 ，求只能在上下左右相邻的且都是有颜色的格子上移动的情况下，自己最多能碰到多少种颜色。
1 ≤ n，m ≤ 10000,1 ≤ 颜色编号 ≤ 1e9 。
题解：
离散化颜色编号，最多才1e6种，就很方便可以用数组记录了。
然后就是BFS。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <queue> #define pii pair<int, int> using namespace std ;const int N = 1e3 + 5 ;const int M = 1e6 + 5 ;int n, m, tot, ans;int a[N][N];queue <pii> q;int c[M], vis[N][N], b[M];int dx[] = {1 , -1 , 0 , 0 };int dy[] = {0 , 0 , 1 , -1 };int query (int x) return lower_bound(b, b + ans, x) - b; } int f (int x, int y) vector <int > V; int res = 0 ; q.push(pii(x, y)); while (q.size()){ pii tmp = q.front(); q.pop(); int x = tmp.first, y = tmp.second; int tmp_color = query(a[x][y]); if (c[tmp_color] == 0 ){ res++; c[tmp_color] = 1 ; V.push_back(tmp_color); } for (int i = 0 ; i < 4 ; i++){ int tx = x + dx[i]; int ty = y + dy[i]; if (!vis[tx][ty] && a[tx][ty]){ vis[tx][ty] = 1 ; q.push(pii(tx, ty)); } } } for (int i = 0 ; i < V.size(); i++) c[V[i]] = 0 ; return res; } int main () scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= n; i++){ for (int j = 1 ; j <= m; j++){ scanf ("%d" , &a[i][j]); b[tot++] = a[i][j]; } } sort(b, b + tot); ans = unique(b, b + tot) - b; int Max = 0 ; for (int i = 1 ; i <= n; i++){ for (int j = 1 ; j <= m; j++){ if (!vis[i][j] && a[i][j]){ Max = max(f(i, j), Max); } } } printf ("%d\n" , Max); return 0 ; }
D 图论 题目：
现在给定一棵树，给定树根，每次查a,求出有多少点对 (x,y)（其中 x,y 可以相等）的 LCA 是 a，答案对 10^9+7 取模
题解：
dfs
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define ll long long using namespace std ;const int N = 2e6 + 5 ;const int Mod = 1e9 + 7 ;int head[N], ver[N], Next[N], tot;int n, m, root;ll ans[N], son[N]; void add (int x, int y) ver[++tot] = y; Next[tot] = head[x]; head[x] = tot; } void dfs1 (int x, int pre) son[x] = 1 ; for (int i = head[x]; i; i = Next[i]){ int y = ver[i]; if (y == pre) continue ; dfs1(y, x); son[x] += son[y]; } } void dfs2 (int x, int pre) for (int i = head[x]; i; i = Next[i]){ int y = ver[i]; if (y == pre) continue ; dfs2(y, x); ans[x] += 2 * son[y]; ans[x] %= Mod; ans[x] = ans[x] + son[y] * (son[x] - son[y] - 1 ) % Mod; ans[x] %= Mod; } ans[x] += 1 ; ans[x] %= Mod; } int main () scanf ("%d%d%d" , &n, &m, &root); for (int i = 1 ; i < n; i++){ int x, y; scanf ("%d%d" , &x, &y); add(x, y); add(y, x); } dfs1(root, 0 ); dfs2(root, 0 ); for (int i = 1 ; i <= m; i++){ int x; scanf ("%d" , &x); printf ("%lld\n" , ans[x]); } }
