天梯集训+代码打卡笔记整理

1.着色问题

        直接标注哪些行和列是被标注过的，安全格子的数量就是未标注的行*列

#include <bits/stdc++.h>
using namespace std;const int N = 1e5+10;
int hang[N],lie[N];int main(){int n,m;cin>>n>>m;int q;cin>>q;while(q--){int x,y;cin>>x>>y;if(x==0){if(hang[y]==0){hang[y] = 1;n--;}}else{if(lie[y]==0){lie[y] = 1;m--;}}}cout<<m*n<<endl;return 0;
}

2.插松枝

        当涉及队列的相关操作的时候需要判断队列是否为空，否则会导致段错误。

deque<int>dq;    # 双端队列
dq.push_back(t); # 尾插
dq.pop_back();   # 尾元素出队
dp.pop_front();  # 头元素出队
dq.empty();      # 判断队列是否为空

3.老板的作息表

vector<pair<string, string>>vec # 存储题目的两个字符串
vec.push_back({a,b});           # 在容器尾部插入元素
sort(vec.begin(), vec.end());   # 升序排序，第一个元素相同时，按照第二个元素升序排序

#include <bits/stdc++.h>
using namespace std;int main(){int n;cin>>n;vector<pair<string,string>>s;for(int i=1;i<=n;i++){string a,b,c;cin>>a>>b>>c;s.push_back({a,c});}sort(s.begin(), s.end());string re = "-1";for(auto t:s){if(re=="-1"){re = t.second;if(t.first!="00:00:00"){cout<<"00:00:00 - "<<t.first<<endl;}}else{if(re!=t.first){cout<<re<<" - "<<t.first<<endl;}re = t.second;}}if(re!="23:59:59"){cout<<re<<" - "<<"23:59:59";}return 0;
}

4.在主串s中查找字串t

string t = "123";
string s = "123321";
s.find(t, 0)!=string::npos; # !=说明找到字串了

5.从字符串数据流中读取整数

string s = "12 7";
istringstream iss(s);    # 将字符串转化为数据流
int L,T;
iss>>L>>T;               # 从数据流中读出整数 L=12 T=7

6.字符大小写转化

#include <bits/stdc++.h>
using namespace std;int main(){char a = 'A';char c = a+32; // 'a'cout<<c<<endl;char b = 'z';char d = b-32;cout<<d<<endl; // 'Z'
}

7.记忆数字

#include <bits/stdc++.h>
using namespace std;int main(){string s;getline(cin, s);int len = 0;for(char c:s){if(isalpha(c)){    # 是否是字符len++;}else if(len){cout<<len%10;len = 0;}}if(len){cout<<len%10;}return 0;
}

8.猜单词

#include <bits/stdc++.h>
using namespace std;struct Node {string s;int a, b;
};int main() {vector<Node> vec(5);for (auto &[s, a, b] : vec) {cin >> s >> a >> b;}auto check = [&](const string &t) {bool res = true;set<char> ss(t.begin(), t.end());    # 对t的每个字符插入到set中for (auto &[s, a, b] : vec) {int x = 0, y = 0;for (int i = 0; i < 3; i++) {x += ss.count(s[i]);y += s[i] == t[i];}res &= x == a && y == b;}return res;};vector<string> ans;for (char i = 'A'; i <= 'Z'; i++) {for (char j = 'A'; j <= 'Z'; j++) {for (char k = 'A'; k <= 'Z'; k++) {string t = {i, j, k};if (check(t)) {ans.push_back(t);}}}}cout << ans.size() << '\n';for (auto &x : ans) {cout << x << '\n';}return 0;
}

9.寻宝图

               从每个位置进行搜索，找到以这个位置扩散出去的岛屿，则岛屿数量加1，并将遍历过的地方都置为已经遍历过，遍历过程中判断是否有宝藏

#include <bits/stdc++.h>
using namespace std;const int N = 1e5+7;
vector<int>a[N];
vector<int>whe[N];
bool flag;
int n,m;
int dx[] = {-1,0,1,0};
int dy[] = {0,-1,0,1};void dfs(int i,int j){whe[i][j] = 1;if(a[i][j]>1){flag = true;}for(int t=0;t<=3;t++){int xx = i+dx[t];int yy = j+dy[t];if(xx>=0&xx<n&&yy>=0&&yy<m){if(whe[xx][yy]==1||a[xx][yy]==0){continue;}else{dfs(xx,yy);}}}
}int main(){cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){char c;cin>>c;a[i].push_back(c-'0');whe[i].push_back(0);}}int sum=0, count = 0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(whe[i][j]==0&&a[i][j]>0){sum++;flag = false;dfs(i,j);if(flag){count++;}}}}cout<<sum<<" "<<count<<endl;return 0;
}

10.吉老师的回归

#include <bits/stdc++.h>
using namespace std;int main(){int n,m;cin>>n>>m;cin.ignore();int flag = 0;m++;                    # m++是因为当做到最后一道题的时候是能AK的，若不+1会误判for(int i=1;i<=n;i++){string s;getline(cin, s);if(s.find("qiandao")!=string::npos||s.find("easy")!=string::npos){continue;}m--;if(m==0){flag = 1;cout<<s<<endl;}}if(flag==0){cout<<"Wo AK le"<<endl;}return 0;
}

11.乘法口诀表

        直接枚举从1到n，当项数多于n的时候break即可

#include <bits/stdc++.h>
using namespace std;const int N = 1e4+7;
int a[N];int main(){int a1,a2,n;cin>>a1>>a2>>n;a[1] = a1;a[2] = a2;int count = 2;for(int i=1;i<=n;i++){int re = a[i]*a[i+1];if(re<=9){count++;a[count] = re;}else{count++;a[count] = re/10;count++;a[count] = re%10;}if(count>=n){break;}}for(int i=1;i<=n;i++){cout<<a[i]<<(i==n?"":" ");}return 0;
}

12.深入虎穴

                深度搜索，需要注意的是，入口是入度为0的门

#include <bits/stdc++.h>
using namespace std;const int N = 1e5+7;
int whe[N];         # 记录某个门是否被遍历过
int dis[N];         # 记录到每个门的距离
int du[N];          # 记录每个门的入度
vector<int>a[N];    # 记录每个门的邻接门void dfs(int i){whe[i] = 1;for(int t=0;t<a[i].size();t++){if(whe[a[i][t]]==0){dis[a[i][t]] = dis[i]+1;dfs(a[i][t]);}else{continue;}}
}int main(){int n;cin>>n;for(int i=1;i<=n;i++){int k;cin>>k;for(int j=1;j<=k;j++){int x;cin>>x;du[x]++;a[i].push_back(x);}}for(int i=1;i<=n;i++){if(du[i]==0){dfs(i);}}int distance = -1;int index = -1;for(int i=1;i<=n;i++){if(dis[i]>distance){distance = dis[i];index = i;}}cout<<index<<endl;return 0;
}

13.倒数第N个字符

            26进制，其中n刚开始要--，因为最后一个字符算倒一字符

#include <bits/stdc++.h>
using namespace std;int main(){int l,n;cin>>l>>n;string re = "";n--;for(int i=1;i<=l;i++){re += 'z';}for(int i=l-1;i>=0;i--){re[i] -= n%26;n /= 26;}cout<<re<<endl;return 0;
}

14.福到了

        对每一行的数据当作字符串来处理，先将每行reverse，再将总体reverse即可得到reverse 的结果，vector容器当作数组使用的时候要初始化

#include <bits/stdc++.h>
using namespace std;int main(){char c;int n;cin>>c>>n;cin.ignore();vector<string>be(n+1),af(n+1);for(int i=1;i<=n;i++){string t;getline(cin, t);af[i] = t;be[i] = t;reverse(af[i].begin(), af[i].end());}reverse(af.begin()+1, af.end());if(af==be){cout<<"bu yong dao le"<<endl;}for(int i=1;i<=n;i++){for(int j=0;j<n;j++){if(af[i][j]!=' '){cout<<c;}else{cout<<' ';}}cout<<endl;}return 0;
}

持续更新中~