Solution 1: 笨办法，直接模拟
#include<bits/stdc++.h>
using namespace std;
map<char, int> mp{{'A', 10}, {'B', 11}, {'C', 12}, {'D', 13}, {'E', 14}, {'F', 15}};
int main(){
string s;
while(cin >> s){
int n = (int)s.size();
int sum = 0;
for(int i = 2; i < n; i++){
char c = s[i];
if(c - '0' <= 9) sum += (c - '0');
else sum += mp[c];
if(i != n - 1) sum *= 16;
}
cout << sum << endl;
}
return 0;
}Solution 2: 直接转换读取形式（非常好用👍）
#include<bits/stdc++.h>
using namespace std;
// 十进制：dec
// 十六进制：hex
// 八进制：oct
int main(){
int a;
while(cin >> hex >> a){
cout << a << endl;
}
return 0;
}
Solution 1: 双指针简单解决
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* ReverseList(ListNode* head) {
// write code here
ListNode* tmp;
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur != nullptr){
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};跳台阶(DP秒了)
HJ35 蛇形矩阵(找出规律模拟即可)
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
int num = 1;
vector<vector<int>> v(n);
for (int i = 0; i < n; i++) {
for (int j = i; j >= 0; j--) {
v[j].push_back(num++);
}
}
for (int i = 0; i < n; i++) {
for (auto x : v[i]) {
cout << x << " ";
}
cout << endl;
}
}
return 0;
}HJ96 表示数字(主要还是模拟)
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
while(cin >> s){
int flag = 0; // 判断是否是连续数字
string ans = "";
for(int i = 0; i < s.size(); i++){
if(s[i] >= '0' && s[i] <= '9'){
if(flag == 0){
ans.push_back('*');
flag = 1;
}
ans.push_back(s[i]);
if(i == s.size() - 1) ans.push_back('*');
}
else {
if(flag == 1){
ans.push_back('*');
flag = 0;
}
ans.push_back(s[i]);
}
}
cout << ans << endl;
}
}HJ51 输出单向链表中倒数第k个结点（模拟即可，IDE上面操作链表还有点不熟悉）
#include<bits/stdc++.h>
using namespace std;
struct ListNode{
int val;
ListNode* next;
ListNode():val(0), next(nullptr){};
ListNode(int x): val(x), next(nullptr){};
ListNode(int x, ListNode* next): val(x), next(next){};
};
int main(){
int n;
while(cin >> n){
ListNode* cur = nullptr;
ListNode* head = nullptr;
for(int i = 0; i < n; i++){
int k; cin >> k;
if(i == 0) {
head = new ListNode(k);
cur = head;
} else {
cur->next = new ListNode(k);
cur = cur->next;
}
}
int num; cin >> num;
ListNode* slow = head;
ListNode* fast = head;
while(fast != nullptr && num--) fast = fast->next;
while(fast != nullptr){
slow = slow->next;
fast = fast->next;
}
if(slow != nullptr) cout << slow->val << endl;
else cout << "No such node." << endl;
}
return 0;
}
[编程题]迷宫问题(难点在于回溯找到一条完整路径)
Solution 1: #BFS
#include<bits/stdc++.h>
using namespace std;
int n, m;
int maze[10][10];
bool visited[10][10];
vector<pair<int, int>> path;
bool dfs(int x, int y){
if(x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == 1 || visited[x][y]) return false;
visited[x][y] = true;
path.push_back({x, y});
if(x == n - 1 && y == m - 1) return true;
if(dfs(x + 1, y) || dfs(x, y + 1) || dfs(x - 1, y) || dfs(x, y - 1)) return true;
path.pop_back();
return false;
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++) cin >> maze[i][j];
}
memset(visited, 0, sizeof(visited));
dfs(0, 0);
for(auto x : path){
cout << "(" << x.first << "," << x.second << ")" << endl;
}
return 0;
}Solution 2: #DFS
#include<bits/stdc++.h>
using namespace std;
int n, m;
int maze[10][10];
bool visited[10][10];
pair<int ,int> pre[10][10];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void print_path(pair<int, int> cur){
stack<pair<int, int>> s;
while(cur != make_pair(0,0)){
s.push(cur);
cur = pre[cur.first][cur.second];
}
s.push({0, 0});
while(!s.empty()){
auto [x, y] = s.top();
s.pop();
cout << "(" << x << "," << y << ")" << endl;
}
}
void bfs(){
queue<pair<int, int>> q;
q.push({0, 0});
visited[0][0] = true;
while(!q.empty()){
auto [x, y] = q.front();
q.pop();
if(x == n - 1 && y == m - 1){
print_path({x, y});
return;
}
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && maze[nx][ny] == 0) {
visited[nx][ny] = true;
pre[nx][ny] = {x, y};
q.push({nx, ny});
}
}
}
cout << "No path" << endl;
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> maze[i][j];
memset(visited, 0, sizeof(visited));
bfs();
return 0;
}
Solution 1: Brute Force，我还第一时间没有想到这个方法……
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
while(cin >> s){
map<char, int> mp;
for(char c : s) mp[c]++;
for(int i = (int)s.size(); i > 0; i--){
for(auto it : mp){
if(it.second == i) cout << it.first;
}
}
}
return 0;
}Solution 2: 重构sort
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<char, int>& a, pair<char, int>& b){
if(a.second == b.second) return a.first < b.first;
else return a.second > b.second;
}
int main(){
string s;
while(cin >> s){
map<char, int> mp;
for(char c : s) mp[c]++;
// 这里要把mp复制到vec然后进行sort
vector<pair<char, int>> vec(mp.begin(), mp.end());
sort(vec.begin(), vec.end(), cmp);
for(auto p : vec) cout << p.first << " ";
cout << endl;
}
return 0;
}
Solution 1: 力扣原题，贪心过去
#include<bits/stdc++.h>
using namespace std;
bool cmp(const pair<int, int>& a, const pair<int, int>& b){
if(a.first == b.first) return a.second < b.second;
return a.first < b.first;
}
int main(){
int x, y;
char c;
vector<pair<int, int>> vec;
while(cin >> x >> c >> y){
vec.push_back({x, y});
}
sort(vec.begin(), vec.end(), cmp);
int end = vec[0].second;
vector<pair<int, int>> ans;
ans.push_back(vec[0]);
for(int i = 1; i < vec.size(); i++){
if(vec[i].first > end){
ans.push_back(vec[i]);
}
else{
end = max(ans.back().second, vec[i].second);
ans.back().second = end;
}
}
for(auto p : ans){
cout << p.first << "," << p.second << " ";
}
return 0;
}MGJ8 链表合并(这里的字符串流的读取很重要，不知道istringstream会非常麻烦……)
#include<bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(): val(0), next(nullptr) {}
ListNode(int x): val(x), next(nullptr) {}
ListNode(int x, ListNode* next): val(x), next(next) {}
};
int main() {
string s;
string t;
getline(cin, s);
getline(cin, t);
vector<int> v1;
vector<int> v2;
istringstream iss(s);
istringstream itt(t);
int num;
while (iss >> num) {
v1.push_back(num);
}
while (itt >> num) {
v2.push_back(num);
}
ListNode* head1 = new ListNode(v1[0]);
ListNode* head2 = new ListNode(v2[0]);
ListNode* tmp;
ListNode* cur1 = head1;
ListNode* cur2 = head2;
for (int i = 1; i < v1.size(); i++) {
tmp = new ListNode(v1[i]);
cur1->next = tmp;
cur1 = cur1->next;
}
for (int j = 1; j < v2.size(); j++) {
tmp = new ListNode(v2[j]);
cur2->next = tmp;
cur2 = cur2->next;
}
cur1 = head1;
cur2 = head2;
ListNode* dummyhead = new ListNode;
if (cur1->val <= cur2->val) dummyhead->next = cur1;
else dummyhead->next = cur2;
ListNode* cur = dummyhead;
while (cur1 != nullptr && cur2 != nullptr) {
if (cur1->val <= cur2->val) {
cur->next = cur1;
cur = cur->next;
cur1 = cur1->next;
} else {
cur->next = cur2;
cur = cur->next;
cur2 = cur2->next;
}
}
if (cur1) cur->next = cur1;
if (cur2) cur->next = cur2;
cur = dummyhead->next;
while (cur != nullptr) {
cout << cur->val << " ";
cur = cur->next;
}
return 0;
}XM10 爬楼梯（DP直接秒了, 难点在模拟大整数相加）
#include<bits/stdc++.h>
using namespace std;
vector<string> a(105);
int n;
string add(string s1, string s2){
reverse(s1.begin(), s1.end());
reverse(s2.begin(), s2.end());
int n = (int)s1.size();
int m = (int)s2.size();
string s3 = "";
int i = 0;
int j = 0;
int carry = 0;
int num = 0;
while(i < n || j < m || carry){
num = carry;
if(i < n){
num += (s1[i] - '0');
i++;
}
if(j < m){
num += (s2[j] - '0');
j++;
}
carry = num / 10;
num %= 10;
s3 += to_string(num);
}
reverse(s3.begin(), s3.end());
return s3;
}
int main(){
cin >> n;
a[1] = "1";
a[2] = "2";
for(int i = 3; i <= n; i++){
a[i] = add(a[i - 1], a[i - 2]);
}
cout << a[n] << endl;
return 0;
}Solution 1: 二分设置一个精度 0.01
#include<bits/stdc++.h>
using namespace std;
double cal(double val){
bool isPositive = val > 0;
val = abs(val);
double left = 0.0f;
double right = 0.0f;
double mid = 0.0f;
if(val > 1.0){
left = 1.0f;
right = val;
}
else {
left = val;
right = 1.0;
}
mid = (left + right) * 0.5f;
while(abs(val - mid * mid * mid) >= 0.01){
if(mid * mid * mid < val){
left = mid;
mid = (left + right) * 0.5f;
}
else{
right = mid;
mid = (left + right) * 0.5f;
}
}
return isPositive ? mid : -1.0 * mid;
}
int main(){
double val;
cin >> val;
printf("%.1lf", cal(val));
}Solution：#DFS，这里建图直接用临接表，然后暴力跑一遍临接表。
#include<bits/stdc++.h>
using namespace std;
int sum = 0;
const int N = 1e5 + 10;
vector<int> v[N];
void DFS(int x, int pre, int w){
for(int i = 0; i < v[x].size(); i++){
if(v[x][i] != pre){
DFS(v[x][i], x, w + 1);
}
}
sum = max(sum, w); // sum记录跑完图最大的路径长度
}
int main(){
int n,x,y;
cin>>n;
for(int i=1;i<=n-1;i++){
cin>>x>>y;
v[x].push_back(y); // 临接表
v[y].push_back(x);
}
DFS(1, -1, 0);
cout<<2*(n-1)-sum<<endl;
return 0;
}HJ22 汽水瓶（确定数学公式，简单循环下去♻️）
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
if (n == 0) break;
if (n <= 1) cout << 0 << endl;
int sum = n / 3;
int left = n - sum * 3 + sum;
while (left >= 2) {
if (left == 2) {
sum += 1;
left = 0;
} else {
sum += left / 3;
left = left % 3 + left / 3;
}
}
cout << sum << endl;
}
return 0;
}
HJ3 明明的随机数（排序去重，老套路了）
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin >> n){
vector<int> vec(n, 0);
for(int i = 0; i < n; i++){
cin >> vec[i];
}
sort(vec.begin(), vec.end());
auto last = unique(vec.begin(), vec.end());
vec.erase(last, vec.end());
for(auto x : vec){
cout << x << endl;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
for(int i = 0; i < s.size(); i += 8){
if(i + 8 < s.size()){
string t = s.substr(i, 8);
cout << t << endl;
}
else{
string tt = s.substr(i);
for(int i = tt.size(); i < 8; i++){
tt.push_back('0');
}
cout << tt << endl;
}
}
return 0;
}HJ6 质数因子（暴力枚举）
#include<bits/stdc++.h>
using namespace std;
int main(){
long n;
cin >> n;
for(long i = 2; i <= sqrt(n); i++){
while(n % i == 0){
cout << i << " ";
n /= i;
}
}
if(n - 1) cout << n << " ";
return 0;
}HJ7 取近似值(考察C++中向零取整)
HJ8 合并表记录(考察STL容器)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin >> n){
map<int, int> mp;
int index;
int num;
while(n--){
cin >> index >> num;
auto it = mp.find(index);
if(it != mp.end()){
it->second += num;
}
else mp.insert({index, num});
}
for(auto it : mp){
cout << it.first << " " << it.second << endl;
}
}
return 0;
}
// 64 位输出请用 printf("%lld")Solution 1: 数学方法一个一个mod下来
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int ans = 0;
unordered_map<int, int> mp;
while(n % 10){
int num = n % 10;
n /= 10;
if(mp.find(num) == mp.end()){
mp.insert({num, 1});
ans = (ans * 10) + num;
}
}
cout << ans << endl;
return 0;
}
Solution 2: 用string的库函数
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
string s = to_string(n);
reverse(s.begin(), s.end());
string result;
for(char c : s){
if(result.size() == 0 && c == '0') continue;
else if(result.find(c) == string::npos){
result.push_back(c);
}
}
cout << result << endl;
return 0;
}
HJ10 字符个数统计(set去重轻松解决)
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
set<int> st;
for(auto c : s){
st.insert(c);
}
cout << st.size() << endl;
return 0;
}#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
vector<string> vec;
while(cin >> s){
vec.push_back(s);
}
reverse(vec.begin(), vec.end());
for(auto x : vec){
cout << x << " ";
}
return 0;
}
// 64 位输出请用 printf("%lld")#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<string> v;
string word;
while(n--){
cin >> word;
v.push_back(word);
}
sort(v.begin(), v.end());
for(auto x : v){
cout << x << endl;
}
return 0;
}
// 64 位输出请用 printf("%lld")Solution 1: 不断除下去（模拟）
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
int sum = 0;
cin >> n;
while(n){
if(n % 2 != 0) sum++;
n /= 2;
}
cout << sum << endl;
return 0;
}
// 64 位输出请用 printf("%lld")Solution 2: 内置函数bitset
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
bitset<32> b(n);
cout << b.count() << endl; // 输出置1的位数
return 0;
}HJ21 简单密码(暴力映射……)
#include<bits/stdc++.h>
using namespace std;
int main() {
string s;
string a = {"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"}; //非必要的参照字典
string b = {"bcdefghijklmnopqrstuvwxyza222333444555666777788899990123456789"};
cin >> s;
for (int i = 0; i < s.length(); i++) {
cout << b[a.find(s[i])];
}
}HJ23 删除字符串中出现次数最少的字符(哈希大法)
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
unordered_map<char, int> mp;
for(char c : s){
mp[c]++;
}
int count = INT_MAX;
for(auto it : mp){
count = min(count, it.second);
}
string ans = "";
for(char c : s){
if(mp[c] == count) continue;
ans.push_back(c);
}
cout << ans << endl;
return 0;
}
// 64 位输出请用 printf("%lld")#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
getline(cin, s);
for(int i = 0; i < s.size(); i++){
if(!isalpha(s[i])) s[i] = ' ';
}
for(int i = s.size() - 1; i >= 0; i--){
if(s[i] == ' '){
cout << s.substr(i + 1) << " ";
s.erase(i);
}
if(i == 0) cout << s << endl;
}
return 0;
}
// 64 位输出请用 printf("%lld")#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
getline(cin , s);
sort(s.begin(), s.end());
cout << s << endl;
return 0;
}
// 64 位输出请用 printf("%lld")#include<bits/stdc++.h>
using namespace std;
bool isValid(int n){
if(n <= 1) return false;
if(n == 2 || n == 3) return true;
for(int i = 2; i <= sqrt(n); i++){
if(n % i == 0) return false;
}
return true;
}
int main(){
int n;
cin >> n;
vector<int> vec;
vec.push_back(2);
vec.push_back(3);
for(int i = 4; i <= n; i++){
if(isValid(i)) vec.push_back(i);
}
int gap = INT_MAX;
int index1 = -1;
int index2 = -2;
for(int i = 0; i < vec.size(); i++){
for(int j = i; j < vec.size(); j++){
if(vec[i] + vec[j] == n){
gap = min(gap, abs(vec[i] - vec[j]));
index1 = i;
index2 = j;
}
}
}
cout << vec[index1] << endl;
cout << vec[index2] << endl;
return 0;
}#include<bits/stdc++.h>
using namespace std;
int num = 0;
void solve(int n, int m){
if(n < m) m = n;
if(n == 1 || n == 0 || m == 1){
num++;
return;
}
for(int i = 1; i <= m; i++) solve(n - i, i);
return;
}
int main(){
int n, m;
cin >> n >> m;
solve(n, m);
cout << num << endl;
return 0;
}
// 64 位输出请用 printf("%lld")#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
if(b == 0) return a;
else return gcd(b, a%b);
}
int main(){
int a, b;
cin >> a >> b;
cout << a / gcd(a, b) * b << endl;
return 0;
}#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n){
if(n <= 1) return false;
for(int i = 2; i <= sqrt(n); i++){
if(n % i == 0) return false;
}
return true;
}
int main(){
int n;
cin >> n;
int a = -1, b = -1;
for(int i = 2; i <= sqrt(n); i++){
if(isPrime(i)){
if(n % i == 0){
if(isPrime(n / i)){
a = i, b = n / i;
break;
}
}
}
}
cout << a << " " << b << endl;
return 0;
}#include<bits/stdc++.h>
using namespace std;
void calculate(string &str, char type, bool isSharp){
size_t pos = 0;
while((pos = str.find(type)) != string::npos){
size_t left = pos;
size_t right = pos;
while(left > 0 && isdigit(str[left - 1])) --left;
while(right < str.size() - 1 && isdigit(str[right + 1])) ++right;
int x = stoi(str.substr(left, pos - left));
int y = stoi(str.substr(pos + 1, right - pos));
int result = isSharp ? 4 * x + 3 * y + 2 : 2 * x + y + 3;
str.replace(left, right - left + 1, to_string(result));
}
}
int main(){
string str;
cin >> str;
calculate(str, '#', true);
calculate(str, '$', false);
cout << str << endl;
return 0;
}#include<bits/stdc++.h>
using namespace std;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
struct Cell{
int x, y, score;
// score大的优先级更高，所以更先出优先队列
bool operator < (const Cell& other) const{
return score < other.score;
}
};
int solve(vector<vector<int>>& maze){
int R = maze.size(), C = maze[0].size();
priority_queue<Cell> pq;
vector<vector<bool>> visited(R, vector<bool>(C, false));
pq.push({0, 0, maze[0][0]});
visited[0][0] = true;
while(!pq.empty()){
Cell cur = pq.top();
pq.pop();
int x = cur.x, y = cur.y, score = cur.score;
if(x == R - 1 && y == C - 1){
return score;
}
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < R && ny >= 0 && ny < C && !visited[nx][ny]){
visited[nx][ny] = true;
pq.push({nx, ny, min(score, maze[nx][ny])});
}
}
}
return -1;
}
int main(){
int R, C;
cin >> R >> C;
vector<vector<int>> maze(R, vector<int>(C));
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++){
cin >> maze[i][j];
}
}
cout << solve(maze) << endl;
return 0;
}#include<bits/stdc++.h>
using namespace std;
int main(){
string w;
int n;
cin >> w >> n;
string tmp;
bool ans = true;
for(int i = 0; i < n; i++){
cin >> tmp;
if(tmp.find(w) == 0) cout << tmp << endl, ans = false;
}
if(ans) cout << -1 << endl;
return 0;
}#include<bits/stdc++.h>
using namespace std;
int ans = 0;
void dfs(int k, int score, int N, int S){
if(k > N) return;
if(k == N && score == S) {
ans++;
return;
}
dfs(k + 1, score * 2, N, S);
dfs(k + 1, score - (k + 1), N, S);
}
int main(){
int N, S;
cin >> N >> S;
dfs(0, 10, N, S);
cout << ans << endl;
return 0;
}