秋招实习刷题网站推荐：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+1
int 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 累加的十进制数是0
cout << "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个父节点是1
int 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 = b
a += temp;
c -= temp;
//如果c还有剩下 取c的一半，例如4 8 8
a += c / 2;
}
else a += c;
return a / 2;
}
