创意活动策划网站,上海网站开发工程师,平面设计线上培训机构推荐,梧州网站优化公司A.Problemsolving Log(计数)
题意#xff1a;
有 26 26 26个问题 A ∼ Z A \sim Z A∼Z#xff0c;分别需要尝试 1 ∼ 26 1 \sim 26 1∼26次才能通过。
给出一个字符串#xff0c;里面包含的每个字母代表着这道题目的一次尝试#xff0c;问#xff1a;总共通过了多少题…A.Problemsolving Log(计数)
题意
有 26 26 26个问题 A ∼ Z A \sim Z A∼Z分别需要尝试 1 ∼ 26 1 \sim 26 1∼26次才能通过。
给出一个字符串里面包含的每个字母代表着这道题目的一次尝试问总共通过了多少题目。
分析
使用数组记录每个字母的出现次数如果 A A A出现了一次 B B B出现了两次…就代表该题目通过了记录过题数量即可。
代码
#include bits/stdc.husing namespace std;
const int N 100005;int vis[30];void solve() {memset(vis, 0, sizeof (vis));int n;string s;cin n s;for (int i 0; i n; i) {vis[s[i] - A];}int ans 0;for (int i 0; i 25; i) {if (vis[i] i) ans;}cout ans endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}B.Preparing for the Contest构造
题意
给出一个难度序列序列中 a [ i ] a [ i − 1 ] a[i] a[i - 1] a[i]a[i−1]的个数为该序列的难度系数求长度为 n n n且难度系数为 k k k的序列。
分析
首先让序列为增序即 1 , 2 , . . . , n 1, 2, ..., n 1,2,...,n然后除最后 k k k个元素外将前面部分翻转变为 n − k , n − k − 1 , . . . , 1 , n − k 1 , . . . , n n - k, n - k - 1, ..., 1, n - k 1, ..., n n−k,n−k−1,...,1,n−k1,...,n。
此时前面的 n − k ∼ 1 n- k \sim 1 n−k∼1均为降序不会产生难度系数后面的 k 1 k 1 k1个元素(包含前面部分结尾的1)为升序会产生 k k k个难度系数满足题目要求。
代码
#include bits/stdc.husing namespace std;
const int N 100005;void solve() {int n, k;cin n k;for (int i n - k; i 1; i--) {cout i ;}for (int i n - k 1; i n; i) {cout i ;}cout endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}C.Quests枚举
题意
有 n n n个关卡你只能从前往后进行闯关通过上一关才能进入下一关第一次通过第 i i i个关卡时可以获得 a i a_i ai点积分之后再次通过第 i i i个关卡时可以获得 b i b_i bi点积分问如果能闯关 k k k次最多能获得多少积分。
分析
不难发现最多只会在一个关卡进行多次通过那么只需要枚举最后到达的关卡并记录过程中遇到过的关卡的 b i b_i bi中的最大值 m a x b i max_{b_{i}} maxbi那么到达第 i i i关的最大积分为 a 1 a 2 . . . a i ( k − i ) × m a x b i , i ≤ k a_1 a_2 ... a_i (k - i) \times max_{b_{i}},i \le k a1a2...ai(k−i)×maxbi,i≤k。
代码
#include bits/stdc.husing namespace std;
const int N 2e5 5e2;int a[N], b[N];void solve() {int n, k;cin n k;for (int i 1; i n; i) {cin a[i];}for (int i 1; i n; i) {cin b[i];}int ans 0, tmp 0, maxn 0;for (int i 1; i n; i) {tmp a[i];maxn max(maxn, b[i]);if (k i) {ans max(ans, tmp max(0, k - i) * maxn);}}cout ans endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}D.Three Activities枚举
题意
在 n n n天里每天有三种活动 滑雪 看电影 玩游戏
在第 i i i天有 a i a_i ai人会参加活动 1 1 1有 b i b_i bi人会参加活动 2 2 2有 c i c_i ci人会参加活动 3 3 3。
每个活动只能进行一次且每天只能完成一个活动问最多能召集多少个朋友完成所有活动。
分析
不难想到每个活动只有人数最多的三天会被选择仅记录每个活动人数最多的三天枚举所有的方案记录可行的方案中人数最大的即可。
代码
#include bits/stdc.husing namespace std;
const int N 2e5 5e2;struct Node{int val, id;bool operator (const Node o) const {return val o.val;}
};Node a[N], b[N], c[N];void solve() {int n;cin n;for (int i 1; i n; i) {cin a[i].val;a[i].id i;}for (int i 1; i n; i) {cin b[i].val;b[i].id i;}for (int i 1; i n; i) {cin c[i].val;c[i].id i;}sort(a 1, a n 1);sort(b 1, b n 1);sort(c 1, c n 1);int ans 0;for (int i 1; i 3; i) {for (int j 1; j 3; j) {for (int k 1; k 3; k) {if (a[i].id b[j].id || b[j].id c[k].id || a[i].id c[k].id) continue;ans max(ans, a[i].val b[j].val c[k].val);}}}cout ans endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}E.Game with Marbles贪心
题意
两个人进行石子游戏每个人均拥有 n n n种不同的石子且每种石子的数量不同但两人的石子种类相同当轮到某人操作时他可以选择手上的一种石子丢掉其中一颗石子并让对手丢掉相同颜色的全部石子只有对手手上还有这种颜色的石子时才能进行。
游戏结束时先手手上剩下的石子数量减去后手手上剩余的石子数量就是最后的得分。
先手希望结束时得分尽可能高后手希望得分尽可能低而两人都极为聪明每次操作均会选择最优策略问最后的得分是多少
分析
对于Easy Version由于石子数量较小 ( n ≤ 6 ) (n \le 6) (n≤6)那么可以对两人的操作进行模拟来得到答案。
对于Hard Version考虑贪心通过模拟后可以发现实际上每个人操作时会选择剩下的石子中 a i b i a_i b_i aibi最大的颜色 i i i进行操作因为哪怕自己这种颜色的石子很少但也可以消除对手最多的石子。
因此使用结构体存储先后手的石子数量对两者拥有的石子数量总和从大到小进行排序然后从前往后模拟操作即可。
代码
#include bits/stdc.husing namespace std;
typedef long long LL;
const int N 2e5 5e2;struct Node{int a, b;bool operator (const Node o) const {return a b o.a o.b;}
};Node g[N];void solve() {int n;cin n;for (int i 1; i n; i) {cin g[i].a;}for (int i 1; i n; i) {cin g[i].b;}sort(g 1, g n 1);LL ans 0;for (int i 1; i n; i) {if (i 1) {ans g[i].a - 1;} else {ans - g[i].b - 1;}}cout ans endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}F.Programming Competition树形DP
题意
有一个公司需要选择若干个人两两组队参与比赛且选择的两个人中不能存在上下级关系直接和间接均不行问最多可以组成多少只队伍
分析
实际上公司的上下级关系就是一个树形的关系对于上下级关系只要两个节点不在同一棵子树上那么可以任意进行组队。
因此当某个节点的子树数量大于 1 1 1时使用 s u m sum sum表示所有子树节点之和 m a x n maxn maxn表示最大子树中节点数量 m a x c maxc maxc表示最大子树中已经匹配的队伍数有以下两种情况 最大的子树中节点数量 m a x n maxn maxn减去以及可以完成匹配的人数后小于等于其他子树中的节点数量总和 s u m − m a x n sum - maxn sum−maxn即 m a x n − m a x c × 2 ≤ s u m − m a x n maxn - maxc \times 2 \le sum - maxn maxn−maxc×2≤sum−maxn此时能组成的队伍数为 ⌊ s u m 2 ⌋ \lfloor \frac{sum}{2} \rfloor ⌊2sum⌋ 否则此时能组成的队伍数为已经匹配的人数加上其他子树中所有节点数量即 m a x c s u m − m a x n maxc sum - maxn maxcsum−maxn。
如果子树数量等于 1 1 1那么只能直接继承子树的状态。
代码
#include bits/stdc.husing namespace std;
typedef long long LL;
const int N 2e5 5e2;vectorint G[N];
int n, sz[N], dp[N];//节点总数子树大小子树能组成的队伍数void dfs(int root) {sz[root] 1;dp[root] 0;int len G[root].size();int maxn 0, maxc 0, sum 0;for (int i 0; i len; i) {int v G[root][i];dfs(v);sz[root] sz[v];dp[root] max(dp[root], dp[v]);if (maxn sz[v]) {maxn sz[v];maxc dp[v];}sum sz[v];}if (len 1) return;if (sum - maxn maxn - maxc * 2) {dp[root] sum / 2;} else {dp[root] sum - maxn maxc;}
}void solve() {cin n;for (int i 1; i n; i) {G[i].clear();}for (int i 2; i n; i) {int u;cin u;G[u].push_back(i);}dfs(1);cout dp[1] endl;
}int main() {int Case;cin Case;while (Case--) {solve();}return 0;
}G.Light Bulbs线段树优化建图强连通分量
题意
本题两个版本不同之处在于数据范围。
有 2 n 2n 2n个灯泡排成一排。每个灯泡都有从 1 1 1到 n n n的颜色每种颜色正好有两个灯泡。
最初所有的灯泡都是关掉的。选择一组灯泡 S S S按任意顺序执行任意次数以下操作:
选择两个颜色相同的灯泡 i i i和 j j j且其中一个是亮着的打开另一个灯泡;选择三个灯泡 i , j , k i,j,k i,j,k要求灯泡 i i i和 k k k都是亮着且颜色相同灯泡 j j j在它们之间即 i j k i j k ijk打开灯泡 j j j。
题目希望选择一组灯泡 S S S通过执行上述操作确保所有灯泡都是打开的。
计算两个数字:
最初可以选择的最小灯泡数量即一组灯泡 S S S包含的最小数目。最小灯泡数量对应的的方案数结果对998244353取模。
分析
对于简单版本假设最坏情况下整个区间都变成一个环。例如 [ 1 , 2 , 1 , 2 ] [1,2,1,2] [1,2,1,2]点 1 1 1可以到点 2 2 2点 2 2 2可以到点 1 1 1构成环。如果是 [ 1 , 2 , 2 , 1 ] [1,2,2,1] [1,2,2,1]点 1 1 1可以到点 2 2 2但是点 2 2 2不能到 1 1 1。把环缩成点后就变成了经典的拓扑排序问题。最小数目就是这个拓扑排序入度为 0 0 0的点方案数就是入度为 0 0 0的点相乘即可。
困难版本的思路如下
首先可以发现同种颜色的点我们只会取一个,然后发现如果我们取了某种对应位置为 [ l , r ] [l,r] [l,r]的点,那么我们同时也取了 [ l 1 , r − 1 ] [l1,r−1] [l1,r−1]之间的所有点。
如果取了颜色 a a a后颜色 b b b也能自动被取连一条从 a a a指向 b b b的边。
对这样的图跑强连通分量只需要操作所有入度为 0 0 0的点即可假设一个入度为 0 0 0的强连通分量里有 x x x种颜色那么有 2 x 2x 2x种取法用乘法原理统计答案即可。
直接暴力连边复杂度 O ( n 2 ) O(n^2) O(n2)这样只能做 e a s y easy easy版本。
对于 h a r d hard hard版本使用线段树优化建图用线段树实现对一个区间内的所有点连边然后再跑强连通分量即可。但是此时需要操作就不一定是入度为 0 0 0的强连通分量了因为有可能入度为 0 0 0的是线段树上的点组成的强连通分量。
此时可以按照拓扑序跑一遍 D P DP DP找到所有没有任何颜色进入线段树上的点可以进入的强连通分量再统计答案即可。时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)空间复杂度为 O ( n ) O(n) O(n)。
代码
#includebits/stdc.h
using namespace std;
typedef long long LL;
const int MAXN4e55;
const int MOD998244353;struct S1{vectorvectorintg,scc;vectorintdfn,low,stk,id;vectorboolins;int ts,n;S1(const vectorvectorint g) : g(g){n (int)g.size();dfn.assign(n, 0);low.assign(n, 0);id.assign(n, -1);ins.assign(n, false);stk.reserve(n);ts 0;build();}void tarjan(int u){dfn[u] low[u] ts;stk.push_back(u);ins[u] 1;for(auto j : g[u]){if (!dfn[j]){tarjan(j);low[u] min(low[u], low[j]);}else if (ins[j]) low[u] min(low[u], dfn[j]);}if (dfn[u] low[u]){int scc_cnt scc.size();scc.push_back({});int y;do{y stk.back();stk.pop_back();id[y] scc_cnt;ins[y] 0;scc.back().push_back(y);}while(y ! u);}}void build(){for(int i 0; i n; i){if (!dfn[i]){tarjan(i);}}}
};vectorvectorint g;
int a[MAXN];
int n;void build(int u, int l, int r){if (l r){g[u].push_back(8 * n a[r]);return;}int mid (l r) / 2;g[u].push_back(2 * u);g[u].push_back(2 * u 1);build(2 * u, l, mid); build(2 * u 1, mid 1, r);
}void modify(int u, int l, int r, int L, int R, int x){if (l R || r L) return;if (l L r R){g[x].push_back(u);return;}int mid (l r) / 2;modify(2 * u, l, mid, L, R, x);modify(2 * u 1, mid 1, r, L, R, x);
}int main(){int T;cin T;while(T--){cin n;vectorarrayint, 2 pos(n 1);for(int i 1; i 2 * n; i){cin a[i];if (pos[a[i]][0] 0){pos[a[i]][0] i;}else{pos[a[i]][1] i;}}g.assign(9 * n 1, {});build(1, 1, 2 * n);for(int i 1; i n; i){auto [l, r] pos[i];if (l 1 r - 1){modify(1, 1, 2 * n, l 1, r - 1, 8 * n i);}}S1 s1(g);const int m s1.scc.size();vectorint c(m);for(int i 0; i m; i){int s 0;for(auto x : s1.scc[i]){s (x 8 * n);}c[i] s;}int cnt 0,sum 1;vectorintbad(m);for(int i m - 1; i 0; i--){if (!bad[i] c[i] 0){cnt 1;sum 2LL * sum * c[i] % MOD;}bad[i] | (c[i] 0);for(auto x : s1.scc[i]){for(auto j : g[x]){if (s1.id[j] ! i){bad[s1.id[j]] | bad[i];}}}}coutcnt sumendl;}return 0;
}学习交流
以下为学习交流QQ群群号 546235402每周题解完成后都会转发到群中大家可以加群一起交流做题思路分享做题技巧欢迎大家的加入。
