输入输出+暴力模拟入门：魔法之树、染色の树、矩阵、字母加密、玫瑰鸭

秋招实习刷题网站推荐：codefun2000.com，还有题解博客：blog.codefun2000.com/。以下内容都是来自塔子哥的~

输入输出

2023.04.15-春招-第三题-魔法之树

//#include<bits/stdc++.h>
#include<vector>
#include<iostream>using namespace std;typedef long long LL;
const int N = 1001;
LL n, l, r;
vector<int> weight(N);
vector<vector<int>> vec(N);//二维数组
// 图的存储:开一个全局的定长数组，其中每个元素都是一个不定长数组vector<int>
// 开1001 是因为节点下标范围为[1,1000] , 所以需要多开一个
// 你所见到的开1005,1006也是这个原因。至少多开辟一位即可
int result = 0;//传入当前节点 当前节点的父节点 累加的值 的值
void dfs(int u, int root, int pre)
{//获取遍历过路径 二进制 对应的十进制//获得当前权重 pre二进制进一位 相当于十进制*2//1--11  1--1*2+1int cur = pre * 2 + weight[u];cout << "pre = " << pre << "\tweight[u] = " << weight[u] << "\tcur = " << cur;//找到符合的路径if (cur > r) return;else if (cur >= l) result++;//遍历当前层for (auto& num : vec[u]){if (num == root) continue;//跳过父节点 一个父节点不能是权重//for(auto& vv : vec[u]) cout << "vv = " << vv << endl;cout << "\tnum = " << num << endl;dfs(num, u, cur);}
}int main1()
{cin >> n >> l >> r;string str;cin >> str;for (int i = 1; i <= n; i++){weight[i] = str[i-1] - '0';}// 由于是树,所以只需要读n - 1 条边// 由于你无法确认x,y之间谁是父亲节点，所以需要存双向边,// 在dfs的过程中防止返祖即可(返祖会引发死递归!)。// PS:在有一些题目里，他会明确规定谁是父亲,这种情况下就不用存双向边，// 且在dfs的过程中也不用担心返祖的问题.for (int i = 0; i < n - 1; i++){int u, v;cin >> u >> v;vec[u].push_back(v);vec[v].push_back(u);}for (int i = 1; i <= n; i++){//从父节点1开始出发 他没有父节点所以是-1 累加的十进制数是0cout << "i = " << i << endl;dfs(i, -1, 0);}cout << result << endl;//string str = "11010";//vector<vector<int>> nums = { {1,2,3}, {2,4,5 }, {1}, {2}, {2} };/*cout << "n = " << n << "\tl = " << l << "\tr = " << r << endl;cout << "str = " << str << endl;for (int i = 0; i < vec.size(); i++){cout << "i = " << i << "\tvec[i] = " << vec[i][0] << endl;for (int j = i; j < vec[i].size(); j++){cout << "\tvec[i][j] = " << vec[i][j] << endl;}}cout << "done" << endl;*/   system("pause");return 0;
}

2023.04.01-第五题-染色の树

//#include<bits/stdc++.h>
#include <vector>
#include <iostream>
using namespace std;
int n;
vector<vector<int>> edges;
vector<int> color;int dfs(int root) {vector<int> tmp(2);//如果当前层有2个子节点 保存其两个子节点//如果    当前层有0个子节点    该节点的价值为    1//如果    当前层有1个子节点    该节点的价值为    其唯一子节点的价值//如果    当前层有2个子节点    该节点是红色，价值为两个子节点价值和；是绿色，价值为两个子节点价值的异或值if (edges[root].size() == 0) return 1;else if (edges[root].size() == 1) return dfs(edges[root][0]);else {for (int i = 0; i < 2; i++) tmp[i] = dfs(edges[root][i]);//两个子节点的价值 为了计算父节点价值if (color[root - 1] == 1) {return tmp[0] + tmp[1];//父节点是红色}else return tmp[0] ^ tmp[1];//父节点是绿色}
}
int main() {cin >> n;if (n < 1) return 0;if (n == 1) return 1;color.resize(n + 1);edges.resize(n + 1);//4行//cout << edges.size() << endl;//保存     { {}, {2,3}, {}, {} }//过程是   p[i]=1 i从2开始 第2个父节点是1，i++；p[i]=1，i=3，第3个父节点是1int idx = 0;while (idx < n) {int tmp;cin >> tmp;//输入的是父节点edges[tmp].push_back(idx+2);//idx+2才是子节点 注意题目的i是从2开始idx++;}int idx2 = 0;while (idx2 < n) {int tmp;cin >> tmp;color[idx2++] = tmp;}/*for(int i = 0; i < edges[1].size(); i ++)cout << edges[1][i] << " ";*///输入父节点值int res = dfs(1);//cout << res << endl;return 0;
}

取模模板

//#include<bits/stdc++.h>
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;// -----取模操作模板----- 建议使用long long 实例化，最稳
template <typename T>
class Mod {
public:T add(T x, T y, T mod) {x %= mod;y %= mod;T res = (x + y) % mod;return res;}T sub(T x, T y, T mod) {x %= mod;y %= mod;T res = (x - y + mod) % mod;return res;}T mul(T x, T y, T mod) {x %= mod;y %= mod;T res = x * y % mod;return res;}T div(T x, T y, T mod) {x %= mod;y %= mod;T inv = fastPow(y, mod - 2, mod);T res = mul(x, inv, mod);return res;}
private:T fastPow(T a, T b, T mod) {T ans = 1, base = a;while (b) {if (b & 1) ans = mul(ans, base, mod);base = mul(base, base, mod);b >>= 1;}return ans;}
};
// -----取模操作模板 end-----
int main3() {int n;Mod<long long> t;cin >> n;for (int i = 1; i <= n; i++) {int op;long long x, y;cin >> op >> x >> y;if (op == 1) {cout << t.add(x, y, mod) << endl;}else if (op == 2) {cout << t.sub(x, y, mod) << endl;}else if (op == 3) {cout << t.mul(x, y, mod) << endl;}else {cout << t.div(x, y, mod) << endl;}}
}

暴力模拟入门

矩阵

#include<bits/stdc++.h>
using namespace std;
int n;
const int mod = 1e9 + 7;
typedef long long LL;template <typename T>
class MOD
{
public:T mul(T a, T b, T mod){a %= mod;b %= mod;T res = (a * b) % mod;return res;}T fastPow(T a, T b, T mod){T res = 1, base = a;while(b){if((b & 1) == 1)mul(base, res, mod);//res *= a;mul(base, base, mod);//a *= a;b >>= 1;}return res;}
};long long fast_pow(int a, int b)
{long long res = 1, temp = a;while(b){if((b & 1) == 1)res *= temp;temp *= temp;b >>= 1;}return res;
}int main()
{cin >> n;LL num = 0, result = 0;//num = n * (n-1) / 2;for(LL i=1; i<=n-1; i++)num += i;//cout << num << endl;//MOD<LL> mymod;//result = mymod.fastPow(2, num, mod);result = fast_pow(2, num);cout << result << endl;return 0;
}

字母加密

第一次写的时候没有考虑范围超出的时候

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;string instr;
int main()
{cin >> instr;int len = instr.length();vector<int> a(len + 1);a[0] = 1, a[1] = 2, a[2] = 4;for (int i = 3; i < len + 1; i++){a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 26;//while (a[i] > 26) a[i] -= 26;//cout << a[i] << "  ";}string result;for (int i = 0; i < len; i++){char temp = (instr[i] - 'a' + a[i]) % 26 + 'a';//cout << instr[i] - 'a' + a[i] << "  " << instr[i] + a[i] << "  ";//cout << (instr[i] - 'a' + a[i]) % 26<< "  " << temp << endl;result += temp;}cout << result << endl;return 0;
}

玫瑰鸭

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
LL a, b, c;int main()
{cin >> a >> b >> c;//LL a = 8;//LL b = 4;//LL c = 2;if (a > b) swap(a, b);//保证a是小的那个LL temp = b - a;//差值if (c - temp >= 0)//c比差值大 c补给a{//用c把差值补给a，让a = ba += temp;c -= temp;//如果c还有剩下 取c的一半，例如4 8 8a += c / 2;}else a += c;return a / 2;
}