本文最后更新于 839 天前,其中的信息可能已经有所发展或是发生改变。
原题链接
题目大意:
- 一个数由互不相同的 n 位数组成。
- 输出 n 位的满足上述条件的最小整数(不含前导零)。
- 不存在则输出 −1。
思想:
- 签到题。
- 当
n <= 10
时,最小的 n 位数的序列为 [1, 0, 2, 3, 4, 5, 6, 7, 8 ,9]
。
- 当
n > 10
时不存在可以满足条件的数。
代码:
| #include <iostream> |
| #include <cstring> |
| #include <cstdio> |
| #include <algorithm> |
| #include <cmath> |
| #include <sstream> |
| #include <vector> |
| #include <queue> |
| #include <stack> |
| #include <map> |
| #include <set> |
| #include <unordered_map> |
| #include <unordered_set> |
| |
| using namespace std; |
| |
| #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) |
| #define re register |
| #define fi first |
| #define se second |
| #define endl '\n' |
| |
| typedef long long LL; |
| typedef pair<int, int> PII; |
| typedef pair<LL, LL> PLL; |
| |
| const int N = 1e6 + 3; |
| const int INF = 0x3f3f3f3f, mod = 1e9 + 7; |
| const double eps = 1e-6, PI = acos(-1); |
| |
| int a[] = {1, 0, 2, 3, 4, 5, 6, 7, 8, 9}; |
| |
| void solve(){ |
| |
| int n; cin >> n; |
| if(n > 10) cout << -1 << endl; |
| else{ |
| for(int i = 0 ; i < n; i ++) cout << a[i]; |
| } |
| |
| return ; |
| |
| } |
| |
| int main(){ |
| |
| IOS; |
| |
| int _ = 1; |
| |
| |
| |
| while(_ --){ |
| solve(); |
| } |
| |
| return 0; |
| |
| } |
原题链接
题目大意:
- 给定一个长度为 n 的字符串 S。
- 求是否存在长度为 17 的子序列满足:
- S′1,S′2,S′3,S′4,S′5 为同一个字符;
- S′6,S′7,...,S′11,S′12 为同一个字符;
- S′13,S′14,S′15,S′16,S′17 为同一个字符。
- 存在输出该子序列,不存在则输出
none
。
思想:
- 签到题。
- 暴力枚举 Si,统计满足的 S1′∼S5′,若可以找到满足的子序列,标记该字符后进入下一层循环;
- 暴力枚举 Sj,统计满足的 S6′∼S12′,若可以找到满足的子序列,标记该字符后进入下一层循环;
- 暴力枚举 Sk,统计满足的 S13′∼S17′,若可以找到满足的子序列,则将上面标记的直接输出即可。
- 当
n < 17
时或者没有找到存在可以满足条件的子序列,则输出 none
。
- 由于每一段的子序列很短,最坏的情况是 263×52×7=3,075,800,实际上的情况会远小于该时间复杂度,所以完全 OK。
代码:
| #include <iostream> |
| #include <cstring> |
| #include <cstdio> |
| #include <algorithm> |
| #include <cmath> |
| #include <sstream> |
| #include <vector> |
| #include <queue> |
| #include <stack> |
| #include <map> |
| #include <set> |
| #include <unordered_map> |
| #include <unordered_set> |
| |
| using namespace std; |
| |
| #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) |
| #define re register |
| #define fi first |
| #define se second |
| #define endl '\n' |
| |
| typedef long long LL; |
| typedef pair<int, int> PII; |
| typedef pair<LL, LL> PLL; |
| |
| const int N = 200; |
| const int INF = 0x3f3f3f3f, mod = 1e9 + 7; |
| const double eps = 1e-6, PI = acos(-1); |
| |
| void solve(){ |
| |
| int n; cin >> n; |
| if(n < 17){ |
| cout << "none" << endl; |
| return ; |
| } |
| |
| string s; cin >> s; |
| int vis1[N] = {0}; |
| for(int i = 0; i < s.size(); i ++){ |
| vis1[s[i]] ++; |
| if(vis1[s[i]] == 5){ |
| char op1 = s[i]; |
| int vis2[N] = {0}; |
| for(int j = i + 1; j < s.size(); j ++){ |
| vis2[s[j]] ++; |
| if(vis2[s[j]] == 7){ |
| char op2 = s[j]; |
| int vis3[N] = {0}; |
| for(int k = j + 1; k < s.size(); k ++){ |
| vis3[s[k]] ++; |
| if(vis3[s[k]] == 5){ |
| for(int u = 0; u < 5; u ++) cout << op1; |
| for(int u = 0; u < 7; u ++) cout << op2; |
| for(int u = 0; u < 5; u ++) cout << s[k]; |
| return ; |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| cout << "none" << endl; |
| return ; |
| |
| } |
| |
| int main(){ |
| |
| IOS; |
| |
| int _ = 1; |
| |
| |
| |
| while(_ --){ |
| solve(); |
| } |
| |
| return 0; |
| |
| } |
原题链接
题目大意:
- 对于两个有限的数集 A,B,定义 A+B 为:
- A+B=x+y ∣ x∈A,y∈B
- 记有限数集 A 的元素个数为 ∣A∣。
- 给定 n,求满足 ∣A+A∣=n ,且满足 ∀x∈A,0≤x≤5×105 的数集 A。
- 若存在 A 满足上述条件,输出内含元素的数量并输出所含元素(任意解均可),不存在则输出 −1。
思想:
-
思维,规律,构造。
-
构造简单数集 A=0,1,2,…,k,∣A∣=k,则 A+A=0,1,2,…,2k,∣A+A∣=2k+1。
-
通过上述构造,显然当 n 为奇数时一定有解,我们只需要构造满足如上规则的数集即可。
-
接下来讨论 n 为偶数的情况:
- ∣A∣=2,∣A+A∣=3,当 n=2 时无解;
- ∣A∣=3,5≤∣A+A∣≤6,当 n=4 时无解;
- 其他情况下,构造数集 A=0,2,3,…,k,则 A+A=0,2,3,…,2k,∣A+A∣=2k。
-
综上所述,根据 n 的奇偶性按照上述规则构造即可。
代码:
| #include <iostream> |
| #include <cstring> |
| #include <cstdio> |
| #include <algorithm> |
| #include <cmath> |
| #include <sstream> |
| #include <vector> |
| #include <queue> |
| #include <stack> |
| #include <map> |
| #include <set> |
| #include <unordered_map> |
| #include <unordered_set> |
| |
| using namespace std; |
| |
| #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) |
| #define re register |
| #define fi first |
| #define se second |
| #define endl '\n' |
| |
| typedef long long LL; |
| typedef pair<int, string> PII; |
| typedef pair<LL, LL> PLL; |
| |
| const int N = 1e6 + 3; |
| const int INF = 0x3f3f3f3f, mod = 1e9 + 7; |
| const double eps = 1e-6, PI = acos(-1); |
| |
| int n; |
| |
| void solve(){ |
| |
| cin >> n; |
| |
| if(n == 2 || n == 4){ |
| cout << -1 << endl; |
| return ; |
| } |
| |
| if(n % 2 != 0){ |
| cout << (n - 1) / 2 + 1 << endl; |
| for(int i = 0; i <= (n - 1) / 2; i ++) cout << i << ' '; |
| } |
| else{ |
| cout << n / 2 << endl; |
| cout << 0 << ' '; |
| for(int i = 2; i <= n / 2; i ++) cout << i << ' '; |
| } |
| |
| } |
| |
| int main(){ |
| |
| IOS; |
| |
| int _ = 1; |
| |
| while(_ --){ |
| solve(); |
| } |
| |
| return 0; |
| |
| } |
原题链接
题目大意:
- 给定 n 个 01 串以及 q 次操作,每次操作会把第 i 个串的 l−r 位替换为和第 j 个串的 l−r 位分别进行与运算的结果。
- 第 i 次操作有概率 pi 成功。
- 询问最后 n 个串与运算得到的串中 1 的个数。
思想:
- 思维题。
- 概率期望套皮,其实无需处理。
- 只要一列中出现过 0,由于进行的是“与”位运算,操作多少次都不会影响任何一个 01 串第 i 位的值,结果一定是 0。
- 故直接计算初始 01 串与操作后的 1 的个数即为答案。
代码:
| #include <iostream> |
| #include <cstring> |
| #include <cstdio> |
| #include <algorithm> |
| #include <cmath> |
| #include <sstream> |
| #include <vector> |
| #include <queue> |
| #include <stack> |
| #include <map> |
| #include <set> |
| #include <unordered_map> |
| #include <unordered_set> |
| |
| using namespace std; |
| |
| #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) |
| #define re register |
| #define fi first |
| #define se second |
| #define endl '\n' |
| |
| typedef long long LL; |
| typedef pair<int, string> PII; |
| typedef pair<LL, LL> PLL; |
| |
| const int INF = 0x3f3f3f3f, mod = 1e9 + 7; |
| const double eps = 1e-6, PI = acos(-1); |
| |
| const int N = 1010; |
| |
| char a[N][4 * N]; |
| |
| int n, m; |
| |
| void solve(){ |
| |
| int res = 0; |
| cin >> n >> m; |
| for(int i = 0; i < n; i ++) cin >> a[i]; |
| |
| int q; cin >> q; |
| while(q --){ |
| for(int i = 0; i < 5; i ++){ |
| int op; cin >> op; |
| } |
| } |
| |
| for(int i = 0; i < m; i ++){ |
| int cnt = 1; |
| for(int j = 0; j < n; j ++){ |
| if(a[j][i] == '0') cnt = 0; |
| } |
| res += cnt; |
| } |
| |
| cout << res << endl; |
| |
| } |
| |
| int main(){ |
| |
| IOS; |
| |
| int _ = 1; |
| |
| while(_ --){ |
| solve(); |
| } |
| |
| return 0; |
| |
| } |
原题链接
题目大意:
- 给定 2×m 的水管图,水管有
I,L
两种,且两种水管均可以旋转。
- 问是否可以通过旋转水管,使得水从 x 列流入后从 y 列流出。
思想:
DFS
搜索。
- 水管出水状态和进入状态相关,故需要记录上一个格子流入下一个格子时的状态。
- 分析状态可知:
- 对于
I
形的水管,流出状态和流入状态相同。
- 对于
L
形的水管,当流入状态是 ↑ 或 ↓ 时,流出时都有两种状态 ← 和 →;当流入状态是 ← 或 → 时,流出时都有两种状态 ↑ 和 ↓ 。
- 根据上述分析,我们可以得到相应状态的偏移量,在搜索时通过加上该偏移量达到坐标的转移。
代码:
| #include <iostream> |
| #include <cstring> |
| #include <cstdio> |
| #include <algorithm> |
| #include <cmath> |
| #include <sstream> |
| #include <vector> |
| #include <queue> |
| #include <stack> |
| #include <map> |
| #include <set> |
| #include <unordered_map> |
| #include <unordered_set> |
| |
| using namespace std; |
| |
| #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) |
| #define re register |
| #define fi first |
| #define se second |
| #define endl '\n' |
| |
| typedef long long LL; |
| typedef pair<int, int> PII; |
| typedef pair<LL, LL> PLL; |
| |
| const int N = 1e6 + 10; |
| const int INF = 0x3f3f3f3f, mod = 1e9 + 7; |
| const double eps = 1e-6, PI = acos(-1); |
| |
| char mp[2][N]; |
| bool vis[2][N]; |
| |
| int m, sl, el; |
| |
| bool flag = 0; |
| |
| void dfs(int l, int r, int st){ |
| |
| if(flag == 1) return ; |
| |
| if(l == 2 && r == el - 1){ |
| flag = 1; |
| return ; |
| } |
| |
| if(l < 0 || l >= 2 || r < 0 || r >= m) return ; |
| |
| if(vis[l][r]) return ; |
| |
| vis[l][r] = 1; |
| |
| if(l >= 0 && l < 2 && r >= 0 && r < m){ |
| if(mp[l][r] == 'I'){ |
| if(st == 0) dfs(l + 1, r, 0); |
| if(st == 1) dfs(l, r + 1, 1); |
| if(st == 2) dfs(l - 1, r, 2); |
| if(st == 3) dfs(l, r - 1, 3); |
| } |
| else{ |
| if(st == 0 || st == 2){ |
| dfs(l, r + 1, 1); |
| dfs(l, r - 1, 3); |
| } |
| if(st == 1 || st == 3){ |
| dfs(l + 1, r, 0); |
| dfs(l - 1, r, 2); |
| } |
| } |
| } |
| |
| vis[l][r] = 0; |
| |
| return ; |
| } |
| |
| bool solve(){ |
| cin >> m >> sl >> el; |
| for(int i = 0; i < 2; i ++) cin >> mp[i]; |
| |
| flag = 0; |
| for(int i = 0; i < 2; i ++){ |
| for(int j = 0; j <= m; j ++) vis[i][j] = 0; |
| } |
| |
| dfs(0, sl - 1, 0); |
| |
| return flag; |
| |
| } |
| |
| int main(){ |
| |
| IOS; |
| |
| int _ = 1; |
| |
| cin >> _; |
| |
| while(_ --){ |
| if(solve()) cout << "YES" << endl; |
| else cout << "NO" << endl; |
| } |
| |
| return 0; |
| |
| } |
生涯第一次参加 CCPC,先贴一张战绩:
铜尾巴是 188,我们队伍 191 喜提铁牌 (bushi) 啊吧啊吧。。。
赛程回顾
- 两个大三的队友还是很给力的,上来就切掉了 A 题,拿下了一个漂亮的
AC
。
- 我之后粗略地计算了一下 E 题的时间复杂度,于是直接三个循环暴力切掉了,虽然因为统计字母数量的
vis
数组开小了,白白吃了一发 WA
,为全队奠定了打铁的基础。
- 然后我发现 H 题是个搜索貌似能行?从此队伍少了一个人。。。
- 队友开搞 F ,上机打表,我在纸上手撕 H。
- 队友开搞 G ,最后发现是道沙笔套皮期望的诈骗题,光速写完不测样例直接冲,小
WA
一下就过了,没有一开始切掉就很可惜。
- 然后 zhgg 开始帮我调我的沙笔 H 题,因为觉得 BFS 的思路完全没问题,死磕到底,最后头晕脑胀坐标都搞混了,剩半小时重写一次最后都没搞出来,直接大寄 (。_。)。
- 最后绝望看榜 200+ 的名次去掉打星的队伍粗略算一下能拿铜尾巴
(赛后发现还是太天真),不过维他柠檬茶是真的好喝,逃。
赛后总结:
- 打铁的根本的原因还是自己能力太弱小了。
- 其本质就是我的懒惰,在本该出成绩的时期思想上懈怠、行动上松懈了。训练量达不到还妄想着出成绩。
- 这次参赛也明显感受到了经验的不足,两个大三的队友异常地镇定和发挥稳定,相较而言,没有大赛经验的我在比赛时手忙脚乱拖累了团队。
- 最后是比赛题目的分配和合作,团队协同参赛的我们互相没有磨合好,队友在讨论时我独自去切没有把握的题,最后还没有解出来,也错过了讨论和看其他题目的机会和时间。
PS:
- 今后的计划:
- 和队友抽空多打几场
VP
,训练团队合作。
- 卧薪尝胆,下次 ICPC 必将胜利。
评论