建设网站准备资料,张雪峰谈工业设计专业,郑州大型网站建设电话,建设网站虚拟主机第一题#xff1a;跳一跳 近来#xff0c;跳一跳这款小游戏风靡全国#xff0c;受到不少玩家的喜爱。 简化后的跳一跳规则如下#xff1a;玩家每次从当前方块跳到下一个方块#xff0c;如果没有跳到下一个方块上则游戏结束。 如果跳到了方块上#xff0c;但没有跳到方块的…第一题跳一跳 近来跳一跳这款小游戏风靡全国受到不少玩家的喜爱。 简化后的跳一跳规则如下玩家每次从当前方块跳到下一个方块如果没有跳到下一个方块上则游戏结束。 如果跳到了方块上但没有跳到方块的中心则获得 1 分跳到方块中心时若上一次的得分为 1 分或这是本局游戏的第一次跳跃则此次得分为 2 分否则此次得分比上一次得分多两分即连续跳到方块中心时总得分将 2468…。 现在给出一个人跳一跳的全过程请你求出他本局游戏的得分按照题目描述的规则。 输入格式 输入包含多个数字用空格分隔每个数字都是 120 之一1 表示此次跳跃跳到了方块上但是没有跳到中心2 表示此次跳跃跳到了方块上并且跳到了方块中心0 表示此次跳跃没有跳到方块上此时游戏结束。 输出格式 输出一个整数为本局游戏的得分在本题的规则下。 数据范围 对于所有评测用例输入的数字不超过 30 个保证 0 正好出现一次且为最后一个数字。 输入样例 1 1 2 2 2 1 1 2 2 0输出样例 22 解题思路
直接模拟
#includeiostreamusing 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;
}
第二题碰撞的小球 数轴上有一条长度为 LL 为偶数)的线段左端点在原点右端点在坐标 L 处。 有 n 个不计体积的小球在线段上开始时所有的小球都处在偶数坐标上速度方向向右速度大小为 1 单位长度每秒。 当小球到达线段的端点左端点或右端点的时候会立即向相反的方向移动速度大小仍然为原来大小。 当两个小球撞到一起的时候两个小球会分别向与自己原来移动的方向相反的方向以原来的速度大小继续移动。 现在告诉你线段的长度 L小球数量 n 以及 n 个小球的初始位置请你计算 t 秒之后各个小球的位置。 提示 因为所有小球的初始位置都为偶数而且线段的长度为偶数可以证明不会有三个小球同时相撞小球到达线段端点以及小球之间的碰撞时刻均为整数。 同时也可以证明两个小球发生碰撞的位置一定是整数但不一定是偶数。 输入格式 输入的第一行包含三个整数 n,L,t用空格分隔分别表示小球的个数、线段长度和你需要计算 t 秒之后小球的位置。 第二行包含 n 个整数 a1,a2,…,an用空格分隔表示初始时刻 n 个小球的位置。 输出格式 输出一行包含 n 个整数用空格分隔第 i 个整数代表初始时刻位于 ai 的小球在 t 秒之后的位置。 数据范围 对于所有评测用例1≤n≤1001≤t≤1002≤L≤10000aiL。L 为偶数。 保证所有小球的初始位置互不相同且均为偶数。 输入样例1 3 10 5
4 6 8输出样例1 7 9 9样例1解释 初始时三个小球的位置分别为 4,6,8。 一秒后三个小球的位置分别为 5,7,9。 两秒后第三个小球碰到墙壁速度反向三个小球位置分别为 6,8,10。 三秒后第二个小球与第三个小球在位置 9 发生碰撞速度反向注意碰撞位置不一定为偶数三个小球位置分别为 7,9,9。 四秒后第一个小球与第二个小球在位置8发生碰撞速度反向第三个小球碰到墙壁速度反向三个小球位置分别为 8,8,10。 五秒后三个小球的位置分别为 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 解题思路
使用结构体存储小球当前的状态 1 表示向右 -1表示向左
第一种情况到边界的时候将方向置反即可
第二种情况正常运动时 1下一秒的时候没有遇到球当前位置加上方向信息 2下一秒的时候遇到球的时候将两个球反向
#includeiostream
#includecstringusing 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映射 题目略 解题思路
其中三个重要的函数
1get_number函数获取字符串中的数字并且返回该数的字符串
2get函数将每一条URL映射解析 如果匹配那么返回一个vector存储的是对应URL请求的解析后的结果 如果不匹配 那么返回一个空的vector
3work函数尽心处理每一条URL请求
#include iostream
#include cstring
#include algorithm
#include vectorusing 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;}// 去掉前导0int k 0;while (k 1 res.size() res[k] 0) k ;return res.substr(k);
}vectorstring get(string path, string str)
{vectorstring 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 正在玩井字棋游戏。 井字棋游戏的规则很简单两人轮流往 3×3 的棋盘中放棋子Alice 放的是 XBob 放的是 OAlice执先。 当同一种棋子占据一行、一列或一条对角线的三个格子时游戏结束该种棋子的持有者获胜。 当棋盘被填满的时候游戏结束双方平手。 Alice 设计了一种对棋局评分的方法 对于 Alice 已经获胜的局面评估得分为(棋盘上的空格子数1)对于 Bob 已经获胜的局面评估得分为 -(棋盘上的空格子数1)对于平局的局面评估得分为 0 例如上图中的局面Alice 已经获胜同时棋盘上有 2 个空格所以局面得分为 213。 由于 Alice 并不喜欢计算所以他请教擅长编程的你如果两人都以最优策略行棋那么当前局面的最终得分会是多少 输入格式 输入的第一行包含一个正整数 T表示数据的组数。 每组数据输入有 3 行每行有 3 个整数用空格分隔分别表示棋盘每个格子的状态。0 表示格子为空1 表示格子中为X2 表示格子中为 O。保证不会出现其他状态。 保证输入的局面合法。(即保证输入的局面可以通过行棋到达且保证没有双方同时获胜的情况) 保证输入的局面轮到 Alice 行棋。 输出格式 对于每组数据输出一行一个整数表示当前局面的得分。 数据范围 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样例解释 第一组数据 Alice 将棋子放在左下角(或右下角)后可以到达问题描述中的局面得分为 3。 3 为 Alice 行棋后能到达的局面中得分的最大值。 第二组数据 Bob 已经获胜(如图)此局面得分为 −(31)−4。 第三组数据 井字棋中若双方都采用最优策略游戏平局最终得分为 0。 解题思路
其中有三个函数
1dfs函数求最终的得分使用深度优先搜索进行遍历每一种情况
2cal函数计算每一个状态时的空格的数量
3check函数对于一个人判断是否是一个获胜的情况
#includeiostreamusing 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;// 计算空格的数量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 algorithmusing 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; // 每一段的根节点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; // 只计算从u到当前点的}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); // 插入树状数组中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); // 将当前子树中的节点删掉dfs_path(root[i], u, 2, maxd);for (int j l; j r; j ) update(p[j].d, 1, maxd); // 将当前子树中的节点添加回来}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;
}
