网站制作建设公司哪家好,app需要网站有哪些,wordpress选不了中文,大理网站建设沛宣A.Cover in Water
题意#xff1a;
有一个 1 n 1 \times n 1n的水池#xff0c;里面有些格子可以加水#xff0c;有些格子是被堵上的#xff0c;你可以进行以下两种操作#xff1a; 1.往一个空的格子里加水 2.移除一个有水的格子中的水#xff0c;并将这些水添加到另…A.Cover in Water
题意
有一个 1 × n 1 \times n 1×n的水池里面有些格子可以加水有些格子是被堵上的你可以进行以下两种操作 1.往一个空的格子里加水 2.移除一个有水的格子中的水并将这些水添加到另一个格子中
且如果两个有水的格子中间都是空格子那么水将覆盖中间所有的空格子。
问最少进行多少次操作1才能使所有空格子中均有水。
分析
不难发现只要出现一段长度大于2的连续空格子那么就可以在这段格子两端各使用一次操作1然后这段格子中间就全部被水覆盖了且无论怎么使用操作2由于两端均有水取完之后格子也不会变空可以无限取即一定只需要两次操作1.
如果没有任意一段连续的空格子长度大于2那么只能对每个格子使用一次操作1才能使所有格子都包含水此时的操作1使用次数就是空格子的个数。
代码
#include bits/stdc.h
using namespace std;void solve() {int n;string s;cin n s;int ans 0, cnt 0;for (int i 0; i n; i) {if (s[i] .) {cnt;if (cnt 2) {cout 2 endl;return;}} else {ans cnt;cnt 0;}}ans cnt;//不要忘了加上最后一段cout ans endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}B.Laura and Operations
题意
给出 a a a个 1 1 1 b b b个 2 2 2 c c c个 3 3 3每次可以选择 1 ∼ 3 1 \sim 3 1∼3中的两个不同数字消除这两个数字并产生一个新的数字这个产生的数字与消除的两个数字均不同问有没有方法可以使最后只剩下 1 , 2 , 3 1, 2, 3 1,2,3中的一种能否剩下 1 , 2 , 3 1, 2, 3 1,2,3的可能性单独输出
分析
首先如果想要剩下的全部都是 1 1 1,那么就需要先将 2 2 2和 3 3 3的数量变为相同的再通过一直消除 2 2 2和 3 3 3使得只剩下 1 1 1。
那么要怎么让 2 2 2和 3 3 3数量相同呢
可以先消除 1 1 1和出现较多的数不难发现如果此时没有 1 1 1是无法完成消除操作的此时无解。
而每次消除 1 1 1和出现较多的数字每次进行消除可以使较大出现次数和较小出现次数之间的差减少2(不用担心1是否不够用通过消除 2 2 2和 3 3 3可以再获得 1 1 1)那么如果这两个数的出现次数差为奇数是无法将这两个数完全消除的此时也是无解。
结论只要另外两个数的差为偶数且满足以下两个要求之一就可以完成消除操作 想要留下的数字出现次数不为0 需要消除的两个数字出现次数已经相同
代码
#include bits/stdc.h
using namespace std;void solve() {int a, b, c;cin a b c;if (abs(b - c) % 2 0 (min(c, b) ! 0 || a ! 0)) {cout 1;} else {cout 0;}if (abs(a - c) % 2 0 (min(a, c) ! 0 || b ! 0)) {cout 1;} else {cout 0;}if (abs(a - b) % 2 0 (min(a, b) ! 0 || c ! 0)) {cout 1;} else {cout 0;}cout endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}C.Anji’s Binary Tree
题意
有一棵二叉树树上每个节点均写着ULR中的一个字符这三个字符的含义如下 U当你走到这个节点你需要向这个节点的父节点移动 L当你走到这个节点你需要向这个节点的左孩子移动 R当你走到这个节点你需要向这个节点的右孩子移动
问你最少需要修改多少次节点上的字符能使你从根节点出法到达叶节点。
分析 当前节点为U想要向叶节点移动遇到U就需要修改此时不需要考虑节点被修改成了什么。 当前节点为L此时往左子树走不需修改次数往右子树走需一次修改次数记录两者中的较小值 当前节点为R此时往右子树走不需修改次数往左子树走需一次修改次数记录两者中的较小值
从根节点开始搜索到达叶节点返回记录最小的修改次数即可。
代码
#include bits/stdc.h
using namespace std;
#define INF 0x3f3f3f3fint n, L[300005], R[300005];
string s;int dfs(int x) {if (x 0) return INF;//走到空节点了返回极大值if (L[x] 0 R[x] 0) return 0;//走到叶节点返回0if (s[x - 1] U) {return min(dfs(L[x]), dfs(R[x])) 1;} else if (s[x - 1] L) {return min(dfs(L[x]), dfs(R[x]) 1);} else {return min(dfs(L[x]) 1, dfs(R[x]));}
}void solve() {cin n s;for (int i 1; i n; i) cin L[i] R[i];cout dfs(1) endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}D.Small GCD
题意
给出一个包含 n n n个元素的数组和一个函数 f ( a , b , c ) g c d ( a , b ) f(a, b, c) gcd(a, b) f(a,b,c)gcd(a,b)其中 a b c a b c abc。
求 ∑ i 1 n ∑ j i 1 n ∑ k j 1 n f ( a i , a j , a k ) \sum\limits_{i 1}^{n}\sum\limits_{j i 1}^{n}\sum\limits_{k j 1}^{n}f(a_i, a_j, a_k) i1∑nji1∑nkj1∑nf(ai,aj,ak)。
分析
由于每轮取得三个数实际上只有两个较小数字会对答案产生影响因此可以先对输入的元素进行排序。
然后使用两层for循环对 a i , a j a_i,a_j ai,aj进行枚举此时的 g c d ( a i , a j ) gcd(a_i, a_j) gcd(ai,aj)的答案对于任意一个 k k k都是成立的即 a i , a j a_i,a_j ai,aj对答案产生的贡献为 g c d ( a i , a j ) × ( n − j ) gcd(a_i, a_j) \times (n - j) gcd(ai,aj)×(n−j)。
但是此时的时间复杂度为 O ( n 2 ) O(n^2) O(n2)是无法通过本题的因此需要对算法进行优化
优化
先考虑所有因数对答案的贡献那么只需一层for循环遍历到 a j a_j aj时如果 a j a_j aj的因数 b b b在前面出现过那么这个因数对答案的贡献就是在前面出现的次数(包含该因数的 a i a_i ai个数)乘上后面的数字个数即 c n t [ b ] × ( n − i ) cnt[b] \times (n - i) cnt[b]×(n−i)。
而对于因数分解的时间复杂度是比较慢的需要先对 1 0 5 10^5 105以内的数预处理所有因子。
求完所有因子产生的贡献后需要考虑实际上求出的贡献计算了很多重复的情况如因子为 2 2 2的贡献中包含了所有 2 2 2的倍数的贡献。需要将这些重复计算的贡献减去。
此时可以从后往前对因子进行遍历每次先将所有由倍数产生的贡献减去然后计算当前因子产生的贡献即当前因子的出现次数乘上因子的值。
代码
#include bits/stdc.h
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;const int N 1e5 5e2;int n, a[N];
ll sum[N], cnt[N];vectorint fact[N];void init() {for (int i 1; i N; i) {for (int j i; j N; j i) {fact[j].push_back(i);//预处理因子}}
}void solve() {cin n;for (int i 1; i n; i) cin a[i];sort(a 1, a n 1);for (int i 1; i n; i) {int len fact[a[i]].size();for (int j 0; j len; j) {sum[fact[a[i]][j]] cnt[fact[a[i]][j]] * (n - i);cnt[fact[a[i]][j]];}}ll ans 0;for (int i a[n]; i 1; i--) {for (int j i i; j N; j i) {sum[i] - sum[j];}ans sum[i] * i;}cout ans endl;
}int main() {init();int Case;cin Case;while (Case--) {//初始化memset(sum, 0, sizeof (sum));memset(cnt, 0, sizeof (cnt));solve();}return 0;
}E.Transitive Graph
更新中…
以下学习交流QQ群群号 546235402大家可以加群一起交流做题思路分享做题技巧欢迎大家的加入。
