四川省住房和城乡建设厅网站无法进入,wordpress cosy,10个产品设计成功案例,福州网站建设H5前言
最近碰到一个专门制作大厂真题模拟题的网站 codefun2000#xff0c;最近一直在上面刷题。今天来进行2023.04.15携程研发岗笔试#xff0c;整理了一下自己的思路和代码。
比赛地址
A. 找到you
题意#xff1a;
给定一个仅包含小写字母的 n n n\times n nn 的矩阵…前言
最近碰到一个专门制作大厂真题模拟题的网站 codefun2000最近一直在上面刷题。今天来进行2023.04.15携程研发岗笔试整理了一下自己的思路和代码。
比赛地址
A. 找到you
题意
给定一个仅包含小写字母的 n × n n\times n n×n 的矩阵问这个矩阵中所有 2 × 2 2\times 2 2×2 的矩阵中同时包含 y、o 和 u 三个字符的子矩阵数量。
数据范围 1 ≤ n , m ≤ 1000 1\leq n, m\leq 1000 1≤n,m≤1000
题解
暴力枚举每个 2 × 2 2\times 2 2×2 子矩阵对于每个子矩阵判断其之中是否同时存在 y、o 和 u 三个字符即可共需要枚举 ( n − 1 ) × ( m − 1 ) (n - 1) \times (m - 1) (n−1)×(m−1) 个子矩阵。
时间复杂度分析 O ( n m ) O(nm) O(nm)
#include bits/stdc.h
using namespace std;const int N 1010;
char s[N][N];
int n, m;bool check(int i, int j) {int val 0;for (int x 0; x 2; x)for (int y 0; y 2; y) {if (s[i x][y j] y) val | 1 0;if (s[i x][y j] o) val | 1 1;if (s[i x][y j] u) val | 1 2;}return val 7;
}int main()
{scanf(%d%d, n, m);;for (int i 1; i n; i) scanf(%s, s[i] 1);int ans 0;for (int i 1; i 1 n; i)for (int j 1; j 1 m; j) {if (check(i, j)) ans 1;}printf(%d\n, ans);return 0;
}B. 最小公倍数
题意 T T T 组数据每组数据给定一个 n n n现在问在 a b n a b n abn 的情况下使得 l c m ( a , b ) lcm(a, b) lcm(a,b) 最大的 a a a 和 b b b 是多少
数据范围 1 ≤ T ≤ 1 0 5 , 2 ≤ n ≤ 1 0 13 1\leq T\leq 10^5, 2\leq n\leq 10^{13} 1≤T≤105,2≤n≤1013
题解 T T T 组数据而 T T T 最大为 1 0 5 10^5 105 则每组数据至多要在 O ( log n ) O(\log n) O(logn) 的时间解决因为这个题需要求 l c m lcm lcm这个求解的复杂度是 O ( log n ) O(\log n) O(logn) 的 所以判断的操作得在 O ( 1 ) O(1) O(1) 时间复杂度内。
下面我们都认为 a ≤ b a \leq b a≤b 当两个数 a a a 和 b b b 满足 a 1 b a 1 b a1b 那么此时 a a a 和 b b b 互质 l c m ( a , b ) a × b lcm(a, b) a \times b lcm(a,b)a×b。
考虑奇数将其拆分成 a ⌊ n 2 ⌋ , b ⌈ n 2 ⌉ a \lfloor\frac{n}{2}\rfloor, b \lceil\frac{n}{2}\rceil a⌊2n⌋,b⌈2n⌉有 a 1 b a 1 b a1b故此时最大的 l c m ( a , b ) lcm(a, b) lcm(a,b) 就是 a ⌊ n 2 ⌋ , b ⌈ n 2 ⌉ a \lfloor\frac{n}{2}\rfloor, b \lceil\frac{n}{2}\rceil a⌊2n⌋,b⌈2n⌉。 考虑偶数将其拆分成 a n 2 , b n 2 a \frac{n}{2}, b \frac{n}{2} a2n,b2n 的 l c m ( a , b ) n 2 lcm(a, b) \frac{n}{2} lcm(a,b)2n。
因为 n n n 是偶数所以拆分出必然是要么 a a a 和 b b b 均为偶数要么 a a a 和 b b b 均为奇数。 这里有一个结论对于正数 a , b , n a,b,n a,b,n如果有 a b n a b n abn且 a a a 和 b b b 均为奇数则 g c d ( a , b ) 1 gcd(a,b)1 gcd(a,b)1 。
当 n 2 n2 n2只有一种拆分法 a 1 , b 1 a1,b1 a1,b1。
当 n 2 n2 n2对于拆分 a 1 , b n − 1 l c m ( 1 , n − 1 ) l c m ( n 2 , n 2 ) a1,bn-1lcm(1,n-1)lcm(\frac{n}{2},\frac{n}{2}) a1,bn−1lcm(1,n−1)lcm(2n,2n)所以 a n 2 , b n 2 a\frac{n}{2},b\frac{n}{2} a2n,b2n这个拆分必然不如其他任意一个拆分。
此外下面的讨论都只针对大于 2 2 2 的偶数。
所以对于一个数 n n n我们至多只需要考虑 2 2 2 个位置因为其他位置都不如这些位置中的任意一个
当 n 2 \frac{n}{2} 2n 为奇数 a n 2 − 1 , b n 2 1 , l c m ( a , b ) a × b g c d ( a , b ) ( n 2 − 1 ) × ( n 2 1 ) 2 a \frac{n}{2} - 1, b \frac{n}{2} 1, lcm(a,b)\frac{a \times b}{gcd(a,b)}\frac{(\frac{n}{2} - 1)\times (\frac{n}{2} 1)}{2} a2n−1,b2n1,lcm(a,b)gcd(a,b)a×b2(2n−1)×(2n1)因为 b − a 2 b-a2 b−a2且 a a a 和 b b b 都是偶数故 g c d ( a , b ) 2 gcd(a,b)2 gcd(a,b)2 a n 2 − 2 , b n 2 2 , l c m ( a , b ) a × b g c d ( a , b ) ( n 2 − 2 ) × ( n 2 2 ) 1 a \frac{n}{2} - 2, b \frac{n}{2} 2,lcm(a,b)\frac{a \times b}{gcd(a,b)}\frac{(\frac{n}{2} - 2)\times (\frac{n}{2} 2)}{1} a2n−2,b2n2,lcm(a,b)gcd(a,b)a×b1(2n−2)×(2n2)因为 b − a 4 b-a4 b−a4故公约数只能为 1 , 2 , 4 1,2,4 1,2,4且 a a a 和 b b b 都是奇数故最大公约数只能为 1 1 1。
当 n 2 \frac{n}{2} 2n 为偶数 a n 2 − 1 , b n 2 1 , l c m ( a , b ) a × b g c d ( a , b ) ( n 2 − 1 ) × ( n 2 1 ) 1 a \frac{n}{2} - 1, b \frac{n}{2} 1, lcm(a,b)\frac{a \times b}{gcd(a,b)}\frac{(\frac{n}{2} - 1)\times (\frac{n}{2} 1)}{1} a2n−1,b2n1,lcm(a,b)gcd(a,b)a×b1(2n−1)×(2n1)因为 b − a 2 b-a2 b−a2故公约数只能为 1 , 2 1, 2 1,2且 a a a 和 b b b 都是奇数故 g c d ( a , b ) 1 gcd(a,b)1 gcd(a,b)1 a n 2 − 2 , b n 2 2 , l c m ( a , b ) a × b g c d ( a , b ) ( n 2 − 2 ) × ( n 2 2 ) g c d ( a , b ) ≥ 2 a \frac{n}{2} - 2, b \frac{n}{2} 2,lcm(a,b)\frac{a \times b}{gcd(a,b)}\frac{(\frac{n}{2} - 2)\times (\frac{n}{2} 2)}{gcd(a,b)\geq2} a2n−2,b2n2,lcm(a,b)gcd(a,b)a×bgcd(a,b)≥2(2n−2)×(2n2)因为 b − a 4 b-a4 b−a4故公约数只能为 1 , 2 , 4 1,2,4 1,2,4且 a a a 和 b b b 都是偶数故最大公约数至少为 2 2 2。
上面已经说明了对于本题中的 a b n abn abn a × b ( a − 1 ) × ( b 1 ) a × b a − b − 1 a \times b (a - 1) \times (b 1) a \times b a - b - 1 a×b(a−1)×(b1)a×ba−b−1 因为 a − b − 1 0 a - b - 1 0 a−b−10故 a × b ( a − 1 ) × ( b 1 ) a \times b (a - 1) \times (b 1) a×b(a−1)×(b1)。
当 n 2 \frac{n}{2} 2n 为奇数 l c m ( n 2 − 1 , n 2 1 ) − l c m ( n 2 − 2 , n 2 2 ) ( n 2 8 − 1 2 ) − ( n 2 4 − 4 ) 28 − n 2 8 lcm(\frac{n}{2}-1,\frac{n}{2}1)-lcm(\frac{n}{2}-2,\frac{n}{2}2)(\frac{n^2}{8}-\frac{1}{2})-(\frac{n^2}{4}-4)\frac{28-n^2}{8} lcm(2n−1,2n1)−lcm(2n−2,2n2)(8n2−21)−(4n2−4)828−n2因为 n 2 \frac{n}{2} 2n 为奇数且 n 2 n2 n2故 n ≥ 6 n\geq6 n≥6故 28 − n 2 8 0 \frac{28-n^2}{8}0 828−n20故 l c m ( n 2 − 2 , n 2 2 ) l c m ( n 2 − 1 , n 2 1 ) lcm(\frac{n}{2}-2,\frac{n}{2}2)lcm(\frac{n}{2}-1,\frac{n}{2}1) lcm(2n−2,2n2)lcm(2n−1,2n1)
当 n 2 \frac{n}{2} 2n 为偶数 l c m ( n 2 − 1 , n 2 1 ) l c m ( n 2 − 2 , n 2 2 ) lcm(\frac{n}{2}-1,\frac{n}{2}1)lcm(\frac{n}{2}-2,\frac{n}{2}2) lcm(2n−1,2n1)lcm(2n−2,2n2)
总结
当 n n n 为奇数 a ⌊ n 2 ⌋ , b ⌈ n 2 ⌉ a \lfloor\frac{n}{2}\rfloor, b \lceil\frac{n}{2}\rceil a⌊2n⌋,b⌈2n⌉
当 n n n 为偶数
当 n 2 n 2 n2 a 1 , b 1 a1,b1 a1,b1当 n 2 \frac{n}{2} 2n 为奇数 a n 2 − 2 , b n 2 2 a \frac{n}{2} - 2, b \frac{n}{2} 2 a2n−2,b2n2当 n 2 \frac{n}{2} 2n 为偶数 a n 2 − 1 , b n 2 1 a \frac{n}{2} - 1, b \frac{n}{2} 1 a2n−1,b2n1
代码
#include bits/stdc.h
using namespace std;typedef long long ll;void solve() {ll n; scanf(%lld, n);if (n 1) {printf(%lld %lld\n, n / 2, n - n / 2);} else {if (n 2) puts(1 1\n);if ((n / 2) 1) {printf(%lld %lld\n, n / 2 - 2, n / 2 2);} else {printf(%lld %lld\n, n / 2 - 1, n / 2 1);}}}int main()
{int T;scanf(%d, T);while (T--) {solve();}return 0;
}C.魔法之树
题意
给定一个 n n n 个点的树问这棵树上任意一条简单路径有起点和终点这条路径上的点构成的二进制字符串对应的十进制数在 [ l , r ] [l, r] [l,r] 范围内的简单路径数。这里的简单路径长度至少为 1 1 1 即自己到自己不算在内
数据范围 1 ≤ n ≤ 1000 , 1 ≤ l ≤ r ≤ 1 0 14 1\leq n\leq 1000, 1\leq l\leq r\leq {10^{14}} 1≤n≤1000,1≤l≤r≤1014
题解 枚举以每个点作为起点遍历完所有的其他 n − 1 n-1 n−1 个点为终点当遇到值大于 r r r 则后面的点作为终点的简单路径构成的二进制字符串对应的十进制数都必然大于 r r r 了不会再可能成为答案了。这里必须要及时判断一方面可以剪枝另一方面是为了避免爆 long long。
时间复杂度 O ( n 2 ) O(n^2) O(n2)
代码
#include bits/stdc.h
using namespace std;typedef long long ll;const int N 1010;
vectorint g[N];
int n;
ll l, r;
char s[N];
int ans;void dfs(int cur, int u, int fa, ll val) {val val * 2 (s[u] - 0);if (val r) return ;if (val l u ! cur) ans 1;for (int v: g[u]) {if (v fa) continue ;dfs(cur, v, u, val);}
}void solve() {scanf(%d%lld%lld, n, l, r);scanf(%s, s 1);for (int i 1; i n; i) {int a, b;scanf(%d%d, a, b);g[a].push_back(b);g[b].push_back(a);}ans 0;for (int i 1; i n; i) {dfs(i, i, 0, 0);}printf(%d\n, ans);
}int main()
{int T 1;
// scanf(%d, T);while (T--) {solve();}return 0;
}D.01串的回文子串
题意
给定 n n n 个数 a i a_i ai当 i i i 为奇数表示生成 a i a_i ai 个 1当 i i i 为偶数表示生成 a i a_i ai 个 0。即生成一个长度为 ∑ i 1 n a i \sum\limits_{i1}^n a_i i1∑nai 的序列 s s s s [ 1 , a 1 ] 1 , s [ a 1 1 , a 2 ] 0 , s [ a 2 1 , a 3 ] 1 , s [ a 3 1 , a 4 ] 0 , . . . s[1, a_1]1,s[a_11,a_2]0,s[a_21,a_3]1,s[a_31,a_4]0,... s[1,a1]1,s[a11,a2]0,s[a21,a3]1,s[a31,a4]0,... 。问这个序列中有多少个回文子串。答案对 1 0 9 7 10^97 1097 取模
数据范围 1 ≤ n ≤ 1000 , 1 ≤ a i ≤ 1 0 9 1\leq n\leq 1000,1\leq a_i\leq 10^9 1≤n≤1000,1≤ai≤109
题解
可以将看成序列看成分为 n n n 块每块内部都是连续的 0 0 0 或 1 1 1。
考虑每块内部可以生成多少回文子串一块内部有 x x x 个数以第 i i i 个数结尾的回文子串数量为 i i i 即 ∑ i 1 x i x × ( x 1 ) 2 \sum\limits_{i1}^xi\frac{x\times (x1)}{2} i1∑xi2x×(x1)
再考虑包含第 i i i 块的回文子串数量。那么以第 i i i 块为回文子串中心向左右扩展。当且仅当左右两个数都相同会多生成一个回文子串。这个什么时候截止呢假设我们当前 a [ i − 1 ] a [ i 1 ] , a [ i − 2 ] a [ i 2 ] , . . . a [ i − p ] a [ i p ] a[i-1]a[i1],a[i-2]a[i2],...a[i-p]a[ip] a[i−1]a[i1],a[i−2]a[i2],...a[i−p]a[ip]但是 a [ i − p − 1 ] ≠ a [ i p 1 ] a[i-p-1]\neq a[ip1] a[i−p−1]a[ip1]则生成的回文子串数为 m i n ( a [ i − p − 1 ] , a [ i p 1 ] ) ∑ j 1 p a [ j ] min(a[i-p-1],a[ip1])\sum\limits_{j1}^p a[j] min(a[i−p−1],a[ip1])j1∑pa[j]
时间复杂度 O ( n 2 ) O(n^2) O(n2)
代码
#include bits/stdc.h
using namespace std;const int N 1010;
const int mod 1e9 7;long long a[N];
int n;void solve() {long long ans 0;scanf(%d, n);for (int i 1; i n; i) {scanf(%lld, a[i]);ans (ans a[i] * (a[i] 1) / 2) % mod;}for (int i 2; i n; i) {int L i - 1, R i 1;while (L 1 R n) {ans (ans min(a[L], a[R])) % mod;if (a[L] a[R]) L - 1, R 1;else break;}}printf(%lld\n, ans);
}int main()
{int T 1;
// scanf(%d, T);while (T--) {solve();}return 0;
}
