传奇网站模板psd,qt网站开发,app软件开发,网页版微信聊天记录会被监控吗比赛链接#xff1a;AtCoder Beginner Contest 380(A-F)
A - 123233
题意
给出一个数字 N N N#xff0c;问这个数字中是否 1 1 1 恰好出现了 1 1 1 次#xff0c; 2 2 2 恰好出现了 2 2 2 次#xff0c; 3 3 3 恰好出现了 3 3 3 次。
数据范围 100000 ≤ N ≤ 99…比赛链接AtCoder Beginner Contest 380(A-F)
A - 123233
题意
给出一个数字 N N N问这个数字中是否 1 1 1 恰好出现了 1 1 1 次 2 2 2 恰好出现了 2 2 2 次 3 3 3 恰好出现了 3 3 3 次。
数据范围 100000 ≤ N ≤ 999999 100000 \le N \le 999999 100000≤N≤999999
思路
把 N N N 当字符串处理然后直接遍历字符串统计每种数字的数量判断是否符合条件即可
复杂度
时间复杂度 O ( ∣ N ∣ ) O(|N|) O(∣N∣)空间复杂度 O ( ∣ N ∣ ) O(|N|) O(∣N∣)
代码实现
// Problem: A - 123233
// Contest: AtCoder - AtCoder Beginner Contest 380
// URL: https://atcoder.jp/contests/abc380/tasks/abc380_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;#define int long longconst int N 1e6 5;void solve()
{string s;cin s;int cnt[10] { 0 };for (char c : s) {cnt[c - 0];}if (cnt[1] 1 cnt[2] 2 cnt[3] 3)cout Yes;elsecout No;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T 1;// cin T;while (T--) {solve();}
}B - Hurdle Parsing
题意
有一个长度为 n n n 的序列 A A A通过序列 A A A 以如下方式构造出字符串 S S S。 S S S 以 ′ ∣ ′ | ′∣′ 开头。 然后进行 n n n 次操作在第 i i i 次操作时添加 A i A_i Ai 个 ′ − ′ - ′−′ 到 S S S 结尾然后添加 ′ ∣ ′ | ′∣′ 到 S S S 结尾。
现在给出字符串 S S S求出序列 A A A。
数据范围 3 ≤ ∣ S ∣ ≤ 100 n ≥ 1 3\le |S| \le 100n \ge 1 3≤∣S∣≤100n≥1
思路 A i A_i Ai 为 S S S 中第 i i i 个字符 ′ − ′ - ′−′ 的连续段的长度因此可以从左到右遍历 S S S每遇到一个字符 ′ − ′ - ′−′就以该字符为开头向右遍历完其所在的连续段从而得到该连续段的长度。 在遍历完一个连续段后就直接跳到连续段之后的下一个位置遍历这样就可以遍历到所有的连续段并得到对应长度。
复杂度
时间复杂度 O ( ∣ S ∣ ) O(|S|) O(∣S∣)空间复杂度 O ( ∣ S ∣ ) O(|S|) O(∣S∣)
代码实现
// Problem: B - Hurdle Parsing
// Contest: AtCoder - AtCoder Beginner Contest 380
// URL: https://atcoder.jp/contests/abc380/tasks/abc380_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;#define int long longconst int N 1e6 5;void solve()
{string s;cin s;int n s.size();for (int i 0; i n; i) {if (s[i] -) {int j i;while (j n s[j] -)j;cout j - i ;i j - 1;}}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T 1;// cin T;while (T--) {solve();}
}C - Move Segment
题意
给出一个长度为 n n n 的 01 01 01 串 S S S。
定义 ′ 1 − b l o c k ′ 1-block ′1−block′ 为只含 1 1 1 的子串且该子串前后都不存在 1 1 1换句话说若子串对应的区间为 [ l , r ] [l,r] [l,r]则 l 1 l1 l1 或 S l − 1 0 S_{l-1} 0 Sl−10且 r n r n rn 或 S r 1 0 S_{r1} 0 Sr10。 01 01 01 串中保证至少有 k k k 个 ′ 1 − b l o c k ′ 1-block ′1−block′现在要求把第 k k k 个 ′ 1 − b l o c k ′ 1-block ′1−block′ 移动到 第 k − 1 k-1 k−1 个 ′ 1 − b l o c k ′ 1-block ′1−block′ 的后面然后输出修改后的 S S S。
数据范围 1 ≤ n ≤ 5 ∗ 1 0 5 , 2 ≤ k 1 \le n \le 5*10^5,2 \le k 1≤n≤5∗105,2≤k
思路
模拟题从左到右遍历字符串然后记录上一个 ′ 1 − b l o c k ′ 1-block ′1−block′ 的末尾下标 p r e pre pre当遍历到第 k k k 个 ′ 1 − b l o c k ′ 1-block ′1−block′ 时将其移动到 p r e pre pre 接下去的位置即可。
复杂度
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
代码实现
// Problem: C - Move Segment
// Contest: AtCoder - AtCoder Beginner Contest 380
// URL: https://atcoder.jp/contests/abc380/tasks/abc380_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;#define int long longconst int N 1e6 5;int n, k;
string s;void solve()
{cin n k s;int pre -1, cnt 0;for (int i 0; i n; i) {if (s[i] 1) {cnt;int j i;while (j n s[j] 1) {j;}if (cnt k) {int len j - i;for (int i1 1; i1 len; i1) {s[i i1 - 1] 0;}for (int i1 1; i1 len; i1) {s[pre i1] 1;}break;}pre i j - 1;}}cout s;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T 1;// cin T;while (T--) {solve();}
}D - Strange Mirroring
题意
给出一个字符串 S S S对 S S S 进行 1 0 100 10^{100} 10100 次如下操作 新建一个字符串 T T T通过转换 S S S 每个位置的字母的大小写得到。 把 S S S 变成 S T ST ST。
现在进行 q q q 次查询第 i i i 次查询给出一个数字 k i k_i ki问字符串 S S S 第 k i k_i ki 个字母是什么
数据范围 1 ≤ ∣ S ∣ , q ≤ 2 ∗ 1 0 5 , 1 ≤ k i ≤ 1 0 18 1 \le |S|,q \le 2*10^5,1 \le k_i \le 10^{18} 1≤∣S∣,q≤2∗105,1≤ki≤1018
思路
令 n n n 为初始时 S S S 的长度。
不考虑大小写的话第 k i k_i ki 个字母即为 S k i % n 1 S_{k_i \% n 1} Ski%n1。
现在要考虑第 k i k_i ki 个字母的大小写形式。
因为不考虑大小写的情况下每次操作都是把 S S S 变成 S S SS SS所以第 i i i 次操作后 S S S 会翻倍 i i i 次 S S S 的长度为 2 i ∗ n 2^i*n 2i∗n。
令 f ( w , i d ) f(w,id) f(w,id) 为第 i d id id 个位置的字母的大小写是否与初始时 S S S 对应位置的字母的大小写相同 0 0 0 表示相同 1 1 1 表示不同。 同时第 w w w 次操作后恰好包含了第 i d id id 个位置换句话说 w w w 为满足 2 w ∗ n ≥ i d 2^w*n \ge id 2w∗n≥id 的最小值。
在 S S S 中前一半和后一半对应位置的大小写相反具体的说当 S S S 的长度为 2 w ∗ n 2^w*n 2w∗n 时第 i i i 个位置 ( 1 ≤ i ≤ 2 w − 1 ∗ n ) (1 \le i \le 2^{w-1}*n) (1≤i≤2w−1∗n) 与 第 i 2 w − 1 ∗ n i2^{w-1}*n i2w−1∗n 的位置的字母相同大小写相反。
因此若 i d ≤ 2 w − 1 ∗ n id \le 2^{w-1}*n id≤2w−1∗n那么 f ( w , i d ) f ( w − 1 , i d ) f(w,id) f(w-1,id) f(w,id)f(w−1,id)否则 f ( w , i d ) f ( w − 1 , i d − 2 w − 1 ∗ n ) ⊕ 1 f(w,id) f(w-1,id-2^{w-1}*n) \oplus 1 f(w,id)f(w−1,id−2w−1∗n)⊕1。
特别的当 w 0 w0 w0 时表示未操作时的初始串 f ( 0 , i d ) 0 f(0,id)0 f(0,id)0。
因为上一个状态的长度都是当前状态长度的一半所以求解 f ( w , i d ) f(w,id) f(w,id) 的复杂度为 O ( log 2 i d ) O(\log_2id) O(log2id)
复杂度
时间复杂度 O ( q ∗ log 2 k i ) O(q*\log_2 k_i) O(q∗log2ki)空间复杂度 O ( ∣ S ∣ ) O(|S|) O(∣S∣)
代码实现
// Problem: D - Strange Mirroring
// Contest: AtCoder - AtCoder Beginner Contest 380
// URL: https://atcoder.jp/contests/abc380/tasks/abc380_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;#define int long longconst int N 1e6 5;int n, q;
string s;// 代码实现和思路有些不同w传的是倍数思路中传的是指数
int f(int w, int id)
{if (w 1) {return 0;}int len w * n;if (id len / 2) {return f(w / 2, id);} else {return f(w / 2, id - w / 2 * n) ^ 1;}
}void solve()
{cin s q;n s.size();s s;while (q--) {int id;cin id;int p (id - 1) % n 1;char c s[p];for (int i 0; i 63; i) {int w 1ll i;if (w * n id) {int op f(w, id);if (op) {if (islower(c))c toupper(c);elsec tolower(c);}break;}}cout c ;}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T 1;// cin T;while (T--) {solve();}
}E - 1D Bucket Tool
题意
有 n n n 个单元格初始时第 i i i 个单元格的颜色为 i i i第 i i i 个单元格与第 i 1 i1 i1 个单元格相邻。
进行 q q q 次查询查询有两种情况
修改第 x x x 个单元格所在的同色连通块的颜色为 c c c。输出颜色为 c c c 的单元格有多少个。
数据范围 1 ≤ n ≤ 5 ∗ 1 0 5 , 1 ≤ q ≤ 2 ∗ 1 0 5 1 \le n \le 5*10^5,1 \le q \le 2*10^5 1≤n≤5∗105,1≤q≤2∗105
思路
考虑用并查集维护同色连通块并查集上需要维护连通块的单元格数左边界和右边界。
对于操作 1 1 1首先第 x x x 个单元格的颜色的单元格数会减少所在连通块的单元格数然后把颜色 c c c 的单元格数增加所在连通块的单元格数。
如果修改颜色后和左边连通块或者右边连通块颜色相同则合并在一起。
对于操作 2 2 2则直接输出记录的对应颜色单元格数即可。
复杂度
时间复杂度 O ( n q ) O(nq) O(nq)空间复杂度 O ( n ) O(n) O(n)
代码实现
// Problem: E - 1D Bucket Tool
// Contest: AtCoder - AtCoder Beginner Contest 380
// URL: https://atcoder.jp/contests/abc380/tasks/abc380_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;#define int long longconst int N 1e6 5;int n, q;
int p[N], lx[N], rx[N], sz[N], col[N], cnt[N];int find(int x)
{return x p[x] ? x : p[x] find(p[x]);
}void merge(int x, int y)
{x find(x), y find(y);if (x ! y) {p[x] y;lx[y] min(lx[y], lx[x]);rx[y] max(rx[y], rx[x]);sz[y] sz[x];}
}void solve()
{cin n q;for (int i 1; i n; i) {cnt[i] sz[i] 1;p[i] lx[i] rx[i] col[i] i;}while (q--) {int op;cin op;if (op 1) {int x, c;cin x c;x find(x);cnt[col[x]] - sz[x];col[x] c;cnt[c] sz[x];if (lx[x] ! 1) {int fl find(lx[x] - 1);if (col[fl] c) {merge(x, fl);}}if (rx[x] ! n) {int fr find(rx[x] 1);if (col[fr] c) {merge(x, fr);}}} else {int c;cin c;cout cnt[c] \n;}}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T 1;// cin T;while (T--) {solve();}
}F - Exchange Game
题意 T a k a h a s h i Takahashi Takahashi 有 n n n 张卡片 A o k i Aoki Aoki 有 m m m 张卡片初始时桌子上有 L L L 张卡片每张卡片上都有数字。 T a k a h a s h i Takahashi Takahashi 和 A o k i Aoki Aoki 先后出牌 T a k a h a s h i Takahashi Takahashi 先手出牌当前轮到某人出牌时如果无牌可出则输否则可以出一张牌如果当前桌子上有一张比刚出的牌更小的牌则当前的出牌人可以拿起这张牌。
问哪个人必赢
数据范围 n m L ≤ 12 nmL \le 12 nmL≤12牌上的数字为正数不超过 1 0 9 10^9 109
思路
注意到总牌数很少对应的情况数必然不超过 3 n m L 3^{nmL} 3nmL最大为 531 , 441 531,441 531,441因此可以记忆化搜索所有的博弈状态从而确定哪个人必赢。
其中可以加个小剪枝就是如果要在出牌后在桌子上拿牌的话取小于刚出的牌的最大的牌是最优的因为取得的牌越大后面再打出就可能可以再次在桌上取牌从而保持有牌的状态避免失败。
复杂度
时间复杂度 O ( 3 n m L ) O(3^{nmL}) O(3nmL)空间复杂度 O ( 3 n m L ) O(3^{nmL}) O(3nmL)
代码实现
// Problem: F - Exchange Game
// Contest: AtCoder - AtCoder Beginner Contest 380
// URL: https://atcoder.jp/contests/abc380/tasks/abc380_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;#define int long longconst int N 1e6 5;int n, m, k;maparraymultisetint, 3, int f[2];int dfs(arraymultisetint, 3 st, int op)
{if (f[op].count(st))return f[op][st];if (!st[op].size())return f[op][st] 0;for (int x : st[op]) {auto it st[2].lower_bound(x);int y -1;if (st[2].size() it ! st[2].begin()) {y *(--it);}arraymultisetint, 3 ne st;ne[op].erase(ne[op].lower_bound(x));if (y ! -1) {ne[2].erase(ne[2].lower_bound(y));ne[op].insert(y);}ne[2].insert(x);if (!dfs(ne, op ^ 1))return f[op][st] 1;}return f[op][st] 0;
}void solve()
{cin n m k;arraymultisetint, 3 st;for (int i 0; i n; i) {int x;cin x;st[0].insert(x);}for (int i 0; i m; i) {int x;cin x;st[1].insert(x);}for (int i 0; i k; i) {int x;cin x;st[2].insert(x);}int flag dfs(st, 0);cout (flag ? Takahashi : Aoki) \n;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T 1;// cin T;while (T--) {solve();}
}
