更好的閱讀體驗(yàn) \color{red}{更好的閱讀體驗(yàn)} 更好的閱讀體驗(yàn)
A. Mocha 上小班啦
原題鏈接
題目大意:
- 一個(gè)數(shù)由互不相同的 n n n 位數(shù)組成。
- 輸出 n n n 位的滿足上述條件的最小整數(shù)(不含前導(dǎo)零)。
- 不存在則輸出 ? 1 -1 ?1。
思想:
- 簽到題。
- 當(dāng)
n <= 10
時(shí),最小的 n n n 位數(shù)的序列為[1, 0, 2, 3, 4, 5, 6, 7, 8 ,9]
。 - 當(dāng)
n > 10
時(shí)不存在可以滿足條件的數(shù)。
代碼:
#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不存在滿足條件的數(shù)
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 的俳句
原題鏈接
題目大意:
- 給定一個(gè)長(zhǎng)度為 n n n 的字符串 S S S。
- 求是否存在長(zhǎng)度為
17
17
17 的子序列滿足:
- S ′ 1 , S ′ 2 , S ′ 3 , S ′ 4 , S ′ 5 S′_1 , S′_2 , S′_3 , S′_4 , S′_5 S′1?,S′2?,S′3?,S′4?,S′5? 為同一個(gè)字符;
- S ′ 6 , S ′ 7 , . . . , S ′ 11 , S ′ 12 S′_6 , S′_7 , . . . , S′_{11}, S′_{12} S′6?,S′7?,...,S′11?,S′12? 為同一個(gè)字符;
- S ′ 13 , S ′ 14 , S ′ 15 , S ′ 16 , S ′ 17 S′_{13}, S′_{14}, S′_{15}, S′_{16}, S′_{17} S′13?,S′14?,S′15?,S′16?,S′17? 為同一個(gè)字符。
- 存在輸出該子序列,不存在則輸出
none
。
思想:
- 簽到題。
- 暴力枚舉 S i S_i Si?,統(tǒng)計(jì)滿足的 S 1 ′ ~ S 5 ′ S'_1 \sim S'_5 S1′?~S5′?,若可以找到滿足的子序列,標(biāo)記該字符后進(jìn)入下一層循環(huán);
- 暴力枚舉 S j S_j Sj?,統(tǒng)計(jì)滿足的 S 6 ′ ~ S 12 ′ S'_6 \sim S'_{12} S6′?~S12′?,若可以找到滿足的子序列,標(biāo)記該字符后進(jìn)入下一層循環(huán);
- 暴力枚舉 S k S_k Sk?,統(tǒng)計(jì)滿足的 S 13 ′ ~ S 17 ′ S'_{13} \sim S'_{17} S13′?~S17′?,若可以找到滿足的子序列,則將上面標(biāo)記的直接輸出即可。
- 當(dāng)
n < 17
時(shí)或者沒有找到存在可以滿足條件的子序列,則輸出none
。 - 由于每一段的子序列很短,最壞的情況是 2 6 3 × 5 2 × 7 = 3 , 075 , 800 26^3 \times 5^2 \times 7 = 3,075,800 263×52×7=3,075,800,實(shí)際上的情況會(huì)遠(yuǎn)小于該時(shí)間復(fù)雜度,所以完全 O K OK 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){ //長(zhǎng)度不夠,不可能找到
cout << "none" << endl;
return ;
}
string s; cin >> s;
int vis1[N] = {0}; //統(tǒng)計(jì)相同的前5個(gè)字符
for(int i = 0; i < s.size(); i ++){
vis1[s[i]] ++;
if(vis1[s[i]] == 5){
char op1 = s[i]; //標(biāo)記前5個(gè)字符
int vis2[N] = {0}; //統(tǒng)計(jì)相同的中間7個(gè)字符
for(int j = i + 1; j < s.size(); j ++){
vis2[s[j]] ++;
if(vis2[s[j]] == 7){
char op2 = s[j]; //標(biāo)記中間7個(gè)字符
int vis3[N] = {0}; //統(tǒng)計(jì)相同的后5個(gè)字符
for(int k = j + 1; k < s.size(); k ++){
vis3[s[k]] ++;
if(vis3[s[k]] == 5){ //找到最后5個(gè)字符,直接輸出
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. 集合之和
原題鏈接
題目大意:
- 對(duì)于兩個(gè)有限的數(shù)集
A
,
B
A,B
A,B,定義
A
+
B
A+B
A+B 為:
- A + B = { x + y ? ∣ ? x ∈ A , y ∈ B } A + B = \{x + y~|~ x \in A, y \in B \} A+B={x+y?∣?x∈A,y∈B}
- 記有限數(shù)集 A A A 的元素個(gè)數(shù)為 ∣ A ∣ |A| ∣A∣。
- 給定 n n n,求滿足 ∣ A + A ∣ = n |A + A| = n ∣A+A∣=n ,且滿足 ? x ∈ A , 0 ≤ x ≤ 5 × 1 0 5 \forall x \in A, 0\le x \le 5\times10^5 ?x∈A,0≤x≤5×105 的數(shù)集 A A A。
- 若存在 A A A 滿足上述條件,輸出內(nèi)含元素的數(shù)量并輸出所含元素(任意解均可),不存在則輸出 ? 1 -1 ?1。
思想:
-
思維,規(guī)律,構(gòu)造。
-
構(gòu)造簡(jiǎn)單數(shù)集 A = { 0 , 1 , 2 , … , k } , ∣ A ∣ = k A = \{0,1,2,\dots,k\}, |A| = k A={0,1,2,…,k},∣A∣=k,則 A + A = { 0 , 1 , 2 , … , 2 k } , ∣ A + A ∣ = 2 k + 1 A + A = \{0,1,2,\dots,2k\},|A+A| = 2k + 1 A+A={0,1,2,…,2k},∣A+A∣=2k+1。
-
通過上述構(gòu)造,顯然當(dāng) n n n 為奇數(shù)時(shí)一定有解,我們只需要構(gòu)造滿足如上規(guī)則的數(shù)集即可。
-
接下來討論 n n n 為偶數(shù)的情況:
- ∣ A ∣ = 2 , ∣ A + A ∣ = 3 |A| = 2, |A+A| = 3 ∣A∣=2,∣A+A∣=3,當(dāng) n = 2 n = 2 n=2 時(shí)無解;
- ∣ A ∣ = 3 , 5 ≤ ∣ A + A ∣ ≤ 6 |A| =3,5\le |A+A|\le 6 ∣A∣=3,5≤∣A+A∣≤6,當(dāng) n = 4 n = 4 n=4 時(shí)無解;
- 其他情況下,構(gòu)造數(shù)集 A = { 0 , 2 , 3 , … , k } A = \{0,2,3,\dots,k\} A={0,2,3,…,k},則 A + A = { 0 , 2 , 3 , … , 2 k } , ∣ A + A ∣ = 2 k A+A =\{0,2,3,\dots,2k\},|A+A| = 2k A+A={0,2,3,…,2k},∣A+A∣=2k。
-
綜上所述,根據(jù) n n n 的奇偶性按照上述規(guī)則構(gòu)造即可。
代碼:
#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){ //奇數(shù)構(gòu)造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{ //偶數(shù)構(gòu)造 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 n n 個(gè) 01 01 01 串以及 q q q 次操作,每次操作會(huì)把第 i i i 個(gè)串的 l ? r l ? r l?r 位替換為和第 j j j 個(gè)串的 l ? r l ? r l?r 位分別進(jìn)行與運(yùn)算的結(jié)果。
- 第 i i i 次操作有概率 p i p_i pi? 成功。
- 詢問最后 n n n 個(gè)串與運(yùn)算得到的串中 1 1 1 的個(gè)數(shù)。
思想:
- 思維題。
- 概率期望套皮,其實(shí)無需處理。
- 只要一列中出現(xiàn)過 0 0 0,由于進(jìn)行的是“與”位運(yùn)算,操作多少次都不會(huì)影響任何一個(gè) 01 01 01 串第 i i i 位的值,結(jié)果一定是 0 0 0。
- 故直接計(jì)算初始 01 01 01 串與操作后的 1 1 1 的個(gè)數(shù)即為答案。
代碼:
#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時(shí)
}
res += cnt;
}
cout << res << endl;
}
int main(){
IOS;
int _ = 1;
while(_ --){
solve();
}
return 0;
}
H. 旋轉(zhuǎn)水管
原題鏈接
題目大意:
- 給定
2
×
m
2 \times m
2×m 的水管圖,水管有
I,L
兩種,且兩種水管均可以旋轉(zhuǎn)。 - 問是否可以通過旋轉(zhuǎn)水管,使得水從 x x x 列流入后從 y y y 列流出。
思想:
-
DFS
搜索。 - 水管出水狀態(tài)和進(jìn)入狀態(tài)相關(guān),故需要記錄上一個(gè)格子流入下一個(gè)格子時(shí)的狀態(tài)。
- 分析狀態(tài)可知:
- 對(duì)于
I
形的水管,流出狀態(tài)和流入狀態(tài)相同。 - 對(duì)于
L
形的水管,當(dāng)流入狀態(tài)是 ↑ \uparrow ↑ 或 ↓ \downarrow ↓ 時(shí),流出時(shí)都有兩種狀態(tài) ← \leftarrow ← 和 → \rightarrow →;當(dāng)流入狀態(tài)是 ← \leftarrow ← 或 → \rightarrow → 時(shí),流出時(shí)都有兩種狀態(tài) ↑ \uparrow ↑ 和 ↓ \downarrow ↓ 。
- 對(duì)于
- 根據(jù)上述分析,我們可以得到相應(yīng)狀態(tài)的偏移量,在搜索時(shí)通過加上該偏移量達(dá)到坐標(biāo)的轉(zhuǎ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, 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){ //越界只有到達(dá)出口的情況合法
flag = 1; //標(biāo)記答案
return ;
}
if(l < 0 || l >= 2 || r < 0 || r >= m) return ; //越界直接返回
if(vis[l][r]) return ; //走過該點(diǎn)返回
vis[l][r] = 1; //標(biāo)記走過
if(l >= 0 && l < 2 && r >= 0 && r < m){
if(mp[l][r] == 'I'){ //進(jìn)入狀態(tài)和流出狀態(tà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){ //從下面或上面流入的狀態(tài)
dfs(l, r + 1, 1);
dfs(l, r - 1, 3);
}
if(st == 1 || st == 3){ //從左邊或右邊流入的狀態(tài)
dfs(l + 1, r, 0);
dfs(l - 1, r, 2);
}
}
}
vis[l][r] = 0; //搜過返回恢復(fù)現(xiàn)場(chǎng)
return ;
}
bool solve(){
cin >> m >> sl >> el;
for(int i = 0; i < 2; i ++) cin >> mp[i];
flag = 0; //多實(shí)例,初始化
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;
}
賽后回顧與總結(jié)
生涯第一次參加 C C P C CCPC CCPC,先貼一張戰(zhàn)績(jī):
銅尾巴是
188
188
188,我們隊(duì)伍
191
191
191 喜提鐵牌 (bushi) 啊吧啊吧。。。
賽程回顧
- 兩個(gè)大三的隊(duì)友還是很給力的,上來就切掉了
A
A
A 題,拿下了一個(gè)漂亮的
AC
。 - 我之后粗略地計(jì)算了一下
E
E
E 題的時(shí)間復(fù)雜度,于是直接三個(gè)循環(huán)暴力切掉了,雖然因?yàn)榻y(tǒng)計(jì)字母數(shù)量的
vis
數(shù)組開小了,白白吃了一發(fā)WA
,為全隊(duì)奠定了打鐵的基礎(chǔ)。 - 然后我發(fā)現(xiàn) H H H 題是個(gè)搜索貌似能行?從此隊(duì)伍少了一個(gè)人。。。
- 隊(duì)友開搞 F F F ,上機(jī)打表,我在紙上手撕 H H H。
- 隊(duì)友開搞
G
G
G ,最后發(fā)現(xiàn)是道沙筆套皮期望的詐騙題,光速寫完不測(cè)樣例直接沖,小
WA
一下就過了,沒有一開始切掉就很可惜。 - 然后
zhgg
開始幫我調(diào)我的沙筆 H H H 題,因?yàn)橛X得BFS
的思路完全沒問題,死磕到底,最后頭暈?zāi)X脹坐標(biāo)都搞混了,剩半小時(shí)重寫一次最后都沒搞出來,直接大寄 (。_。)。 - 最后絕望看榜
200
+
200+
200+ 的名次去掉大星的隊(duì)伍粗略算一下能拿銅尾巴~~(賽后發(fā)現(xiàn)還是太天真)~~,不過維他檸檬茶是真的好喝,
逃。
賽后總結(jié):文章來源:http://www.zghlxwxcb.cn/news/detail-453635.html
- 打鐵的根本的原因還是自己能力太弱小了。
- 其本質(zhì)就是我的懶惰,在本該出成績(jī)的時(shí)期思想上懈怠、行動(dòng)上松懈了。訓(xùn)練量達(dá)不到還妄想著出成績(jī)。
- 這次參賽也明顯感受到了經(jīng)驗(yàn)的不足,兩個(gè)大三的隊(duì)友異常地鎮(zhèn)定和發(fā)揮穩(wěn)定,相較而言,沒有大賽經(jīng)驗(yàn)的我在比賽時(shí)手忙腳亂拖累了團(tuán)隊(duì)。
- 最后是比賽題目的分配和合作,團(tuán)隊(duì)協(xié)同參賽的我們互相沒有磨合好,隊(duì)友在討論時(shí)我獨(dú)自去切沒有把握的題,最后還沒有解出來,也錯(cuò)過了討論和看其他題目的機(jī)會(huì)和時(shí)間。
PS:文章來源地址http://www.zghlxwxcb.cn/news/detail-453635.html
- 今后的計(jì)劃:
- 加訓(xùn);
- 加訓(xùn);
- 還是
TMD
加訓(xùn)。
- 和隊(duì)友抽空多打幾場(chǎng)
VP
,訓(xùn)練團(tuán)隊(duì)合作。 - 臥薪嘗膽,下次 I C P C ICPC ICPC 必將勝利。
到了這里,關(guān)于2022 年 CCPC 河南省賽 (A,E,F,G,H)的文章就介紹完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!