本文最后更新于 691 天前,其中的信息可能已经有所发展或是发生改变。
A. Mocha 上小班啦
题目大意:
- 一个数由互不相同的 $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; //大于10不存在满足条件的数
else{
for(int i = 0 ; i < n; i ++) cout << a[i]; //注意交换1和0的顺序
}
return ;
}
int main(){
IOS;
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}
E. Serval 的俳句
题目大意:
- 给定一个长度为 $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
。
思想:
- 签到题。
- 暴力枚举 $S_i$,统计满足的 $S'_1 \sim S'_5$,若可以找到满足的子序列,标记该字符后进入下一层循环;
- 暴力枚举 $S_j$,统计满足的 S'_6 \sim S'_{12},若可以找到满足的子序列,标记该字符后进入下一层循环;
- 暴力枚举 S_k,统计满足的 S'_{13} \sim S'_{17},若可以找到满足的子序列,则将上面标记的直接输出即可。
- 当
n < 17
时或者没有找到存在可以满足条件的子序列,则输出none
。 - 由于每一段的子序列很短,最坏的情况是 $26^3 \times 5^2 \times 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}; //统计相同的前5个字符
for(int i = 0; i < s.size(); i ++){
vis1[s[i]] ++;
if(vis1[s[i]] == 5){
char op1 = s[i]; //标记前5个字符
int vis2[N] = {0}; //统计相同的中间7个字符
for(int j = i + 1; j < s.size(); j ++){
vis2[s[j]] ++;
if(vis2[s[j]] == 7){
char op2 = s[j]; //标记中间7个字符
int vis3[N] = {0}; //统计相同的后5个字符
for(int k = j + 1; k < s.size(); k ++){
vis3[s[k]] ++;
if(vis3[s[k]] == 5){ //找到最后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;
// cin >> _;
while(_ --){
solve();
}
return 0;
}
F. 集合之和
题目大意:
- 对于两个有限的数集 $A,B$,定义 $A+B$ 为:
- $A + B = {x + y~|~ x \in A, y \in B }$
- 记有限数集 $A$ 的元素个数为 $|A|$。
- 给定 $n$,求满足 $|A + A| = n$ ,且满足 $\forall x \in A, 0\le x \le 5\times10^5$ 的数集 $A$。
- 若存在 $A$ 满足上述条件,输出内含元素的数量并输出所含元素(任意解均可),不存在则输出 $-1$。
思想:
-
思维,规律,构造。
-
构造简单数集 $A = {0,1,2,\dots,k}, |A| = k$,则 $A + A = {0,1,2,\dots,2k},|A+A| = 2k + 1$。
-
通过上述构造,显然当 $n$ 为奇数时一定有解,我们只需要构造满足如上规则的数集即可。
-
接下来讨论 $n$ 为偶数的情况:
- $|A| = 2, |A+A| = 3$,当 $n = 2$ 时无解;
- $|A| =3,5\le |A+A|\le 6$,当 $n = 4$ 时无解;
- 其他情况下,构造数集 $A = {0,2,3,\dots,k}$,则 $A+A ={0,2,3,\dots,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){ //奇数构造0, 1, 2, 3,...,(n - 1) / 2
cout << (n - 1) / 2 + 1 << endl;
for(int i = 0; i <= (n - 1) / 2; i ++) cout << i << ' ';
}
else{ //偶数构造 0, 2, 3,..., n / 2
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;
}
G. Mocha 上大班啦
题目大意:
- 给定 $n$ 个 $01$ 串以及 $q$ 次操作,每次操作会把第 $i$ 个串的 $l − r$ 位替换为和第 $j$ 个串的 $l − r$ 位分别进行与运算的结果。
- 第 $i$ 次操作有概率 $p_i$ 成功。
- 询问最后 $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; //存在某一列为0时
}
res += cnt;
}
cout << res << endl;
}
int main(){
IOS;
int _ = 1;
while(_ --){
solve();
}
return 0;
}
H. 旋转水管
题目大意:
- 给定 $2 \times m$ 的水管图,水管有
I,L
两种,且两种水管均可以旋转。 - 问是否可以通过旋转水管,使得水从 $x$ 列流入后从 $y$ 列流出。
思想:
DFS
搜索。- 水管出水状态和进入状态相关,故需要记录上一个格子流入下一个格子时的状态。
- 分析状态可知:
- 对于
I
形的水管,流出状态和流入状态相同。 - 对于
L
形的水管,当流入状态是 $\uparrow$ 或 $\downarrow$ 时,流出时都有两种状态 $\leftarrow$ 和 $\rightarrow$;当流入状态是 $\leftarrow$ 或 $\rightarrow$ 时,流出时都有两种状态 $\uparrow$ 和 $\downarrow$ 。
- 对于
- 根据上述分析,我们可以得到相应状态的偏移量,在搜索时通过加上该偏移量达到坐标的转移。
代码:
#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:
- 今后的计划:
- 加训;
- 加训;
- 还是
TMD
加训。
- 和队友抽空多打几场
VP
,训练团队合作。 - 卧薪尝胆,下次 $ICPC$ 必将胜利。
评论