2024/03/31 周日
填充
【参考代码】
想用暴力，没过
//枚举，未出结果QAQ
#include <bits/stdc++.h>
using namespace std;
string s00 = "00";
string s11 = "11";
int ans = 0;
//m个问号，子串有2^m种，使用dfs
//初步思路：分割子串，直到只有两位
int calculate(string s)
{
int substringCount = 0;
if(s.size() == 2)
{
if(s == s00 || s == s11)
substringCount++;
return substringCount;
}
int mid = s.size() >> 1;
calculate( s.substr(0, mid) );
calculate( s.substr(mid+1, mid+1) );
}
void dfs(string s)
{
if(s.find('?') == -1)
{
ans = max(calculate(s), ans)
return;
}
int index = s.find('?');
for(int i=0;i<=1;i++)
{
s[index] = i;
dfs(s);
}
}
int main()
{
string input;
cin>>input;
dfs(input);
return 0;
}
Accepted贪心，贪心比枚举还要短
#include <bits/stdc++.h>
using namespace std;
int main() //贪心
{
int substringCount = 0;
string s;
cin>>s;
for(int i=0;i<s.size()-1;i++)//防止越界，以倒数第二位作为结束条件
{
if(s[i] == s[i+1] || s[i] == '?' || s[i+1] == '?')
{
substringCount++;
i++; //避免重复计算
}
}
cout << substringCount << endl;
}动态规划
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+1;
int dp[N];
int main() //动态规划
{
string s;
cin>>s;
//三种状态转移方程：
if(s[0] == s[1] || s[0] == '?' || s[1] == '?') //初始化
dp[1] = 1; //dp[0]=0
for(int i=2;i<s.size();i++)
{
dp[i] = dp[i-1]; //当前字符可以和前一个字符拼接，但是不拼接
if(s[i] == s[i-1] || s[i] == '?' || s[i-1] == '?')
//dp[i-2]+1可以和前一个字符拼接，选择拼接
//不拼接和拼接选一个最大值为最优解
dp[i] = max(dp[i-1], dp[i-2]+1); //max(1,1)
}
cout << dp[s.size()-1] << endl;
}奇怪的数
【参考代码】
模拟10%通过
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int main()
{
//模拟10%
int n, m;
long long ans = 1;
cin>>n>>m; //长度为n、连续数位和不大于m
if(n == 0 || m == 0 || m < ceil(n/2))
{
cout << 0 << endl;
return 0;
}
int forCount = 0;
for(int i=2; i <= m - ceil(n/2); i += 2) //天花板，向上取整
{
ans += n; //n位数101010101.....一位加2，其他不变，n种情况
forCount++;
if(forCount == 4)
{
forCount = 0;
n = n-1;
}
if(n == 0)
break;
}
cout << ans % mod << endl;
return 0;
}
看到4维的dp数组，累了，放个别人的题解
#include <iostream>
using namespace std;
int dp[10][10][10][10]; //看到这玩意就不想看了
int N = 998244353;
int main() {
int n, m;
cin >> n >> m;
int res = 0;
//初始化边界
for (int i = 1;i <= 9;i += 2) {
for (int j = 0;j <= 9 && j <= (m - i);j += 2) {
for (int k = 1;k <= 9 && k <= (m - i - j);k += 2) {
for (int t = 0;t <= 9 && t <= (m - i - j - k);t += 2) {
dp[i][j][k][t] = 1;
}
}
}
}
//dp[i][j][k][t] -> p j k t q -> dp[j][k][t][q](将之前的结果存在这里)
//开始动态规划
//q是对应当前的位置的，比如n = 5的时候，q就是第五位，就应该是奇数位可以用i % 2直接得到起始条件，
//再基于q得到上面的t k j p即可
for (int i = 5;i <= n;i++) {
for (int p = i % 2;p <= 9;p += 2) {
for (int j = (i + 1) % 2;j <= 9 && (j <= m - p);j += 2) {
for (int k = i % 2;k <= 9 && (k <= m - p -j); k += 2) {
for (int t = (i + 1) % 2;t <= 9 && t <= (m - p - j -k);t += 2) {
for (int q = i % 2;q <= 9 && q <= (m - p - j - k - t);q += 2) {
//dp[j][k][t][q]是没有被初始化的 我们最开始初始化的是奇偶奇偶 现在是偶奇偶奇
dp[j][k][t][q] += dp[p][j][k][t];
dp[j][k][t][q] %= 998244353;
}
//因此这里还需要归零
dp[p][j][k][t] = 0;
}
}
}
}
}
//因此直接把最后四位累加起来即可
for (int j = (n + 1) % 2;j <= 9 && (j <= m);j += 2) {
for (int k = n % 2;k <= 9 && (k <= m - j); k += 2) {
for (int t = (n + 1) % 2;t <= 9 && t <= (m - j -k);t += 2) {
for (int q = n % 2;q <= 9 && q <= (m - j - k - t);q += 2) {
//dp[j][k][t][q]是没有被初始化的 我们最开始初始化的是奇偶奇偶 现在是偶奇偶奇
res += dp[j][k][t][q];
res %= 998244353;
}
}
}
}
cout << res << endl;
return 0;
}
刷点简单的：
三带一
【参考代码】
打牌，炸弹不算三带一
题解区还有更简单的做法
#include <bits/stdc++.h>
using namespace std;
map<char, int> mp;
int main() //dp写不下去了，写点简单题
{
// map含有clear函数，大大方便了清零效率，也不用另外写一段
int t;
string s;
cin>>t;
while(t--)
{
mp.clear();
cin>>s;
for(int i=0;i<4;i++)
{
mp[s[i]]++;
}
int temp = 0;
for(int i=0;i<4;i++)
temp = max(mp[s[i]], temp);
if(temp == 3)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}数树数
【参考代码】
数学思维题，左孩子结点数是根结点数*2-1。右孩子结点数是根结点数*2
#include <iostream>
using namespace std;
int main()
{
int n, q;
string s;
cin>>n>>q;
for(int i=0;i<q;i++)
{
int number = 1; //记得重置
cin>>s;
for(int j=0;j<s.size();j++)
{
if(s[j] == 'L')
number = number * 2 - 1;
else
number = number * 2;
}
cout << number << endl;
}
return 0;
}奇怪的捐赠
【参考代码】
#include <iostream>
using namespace std;
int f(int x, int money)
{
while(x < money)
{
x *= 7;
}
return x/7;
}
int main() //计算器加程序，1份还是3份是用计算器算的
{
int money = 1e6; //100w
int count = 0, x1=1;
/*
money = money - 1*f(1, money);
money = money - 1*f(1, money);
money = money - 3*f(1, money);
money = money - 3*f(1, money);
money = money - 3*f(1, money);
money = money - 3*f(1, money);
money = money - 1*f(1, money);
money = money - 1*f(1, money);
*/
cout << 16 << endl;
return 0;
}三角回文数
【参考代码】
#include <bits/stdc++.h>
using namespace std;
/*
出现的问题：
1.没有输出结果，范围设置太小（20230514），导致没有搜素到合适
2.输出结果未大于20220514，三角回文数不是末项，而是等差数列的总和求出后，再作回文判断
*/
int main()
{
cout << 35133153 << endl;
int sum = 0;
for(int k=1; ; k++)
{
sum += k; //等差数列 = 三角数，不需要再判断
if(sum > 20220514)
{
string s = to_string(sum);
string tmp = s;
reverse(tmp.begin(), tmp.end());
if(s == tmp)
{
cout << sum << endl;
return 0;
}
}
}
}2024/04/02 周二
子树的大小
【参考代码】
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
while(t--)
{
int n, m, k; //n个结点，m茶树，第k点
cin>>n>>m>>k;
ll ans = 1;
ll leftchild = (k - 1) * m + 2;
ll rightchild = k * m + 1;
while(rightchild <= n)
{
ans += rightchild - leftchild + 1; //加回本身的点
leftchild = (leftchild - 1) * m + 2; //leftchild继续增加
rightchild = rightchild * m + 1; //rightchild继续增加
}
if(leftchild <= n)
{
ans += n - leftchild + 1;
}
cout << ans << endl;
}
return 0;
}阶乘的和
【参考代码】
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 阶乘 1 2 3 4 5 6 7 8 9
int factorial[] = {0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
// 规律：3个2就是6, 4个6（3！）就是24（4！），5个24（4！）就是120（5！）
const int N = 1e5+1;
map<ll, int> factor; //因数
int main()
{
int n;
ll temporary;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>temporary;
factor[temporary]++;
}
for(auto it=factor.begin(); it!=factor.end(); it++)
{
temporary = it->first;
int numbercount = it->second;
if(numbercount % (temporary+1) == 0)
{
factor[temporary+1] += numbercount / (temporary+1);
}
else
{
cout << temporary << endl;
return 0;
}
}
}2024/04/03 周三
蓝桥公园（Floyd算法）
【参考代码】
#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int N = 401;
long long f[N][N];
int n, m, q;
void floyd()
{
for(int k=1; k<=n; k++)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
}
int main()
{
memset(f, 0x3f, sizeof(f));
cin>>n>>m>>q;
for(int i=0; i<m; i++)
{
int u, v;
long long w;
cin>>u>>v>>w;
f[u][v] = f[v][u] = min(w, f[u][v]); //
}
floyd(); //漏了这个：调用函数
//开始输出
int start, end;
for(int i=0; i<q; i++)
{
cin >> start >> end;
if(f[start][end] == INF)
cout << -1 << endl;
else if(start == end)
cout << 0 << endl;
else
cout << f[start][end] << endl;
}
return 0;
}2024/04/04 周四
出差（Bellman-ford算法）
【参考代码】
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 20001; //需要存储双向边，10000*2
struct node
{
int start; //起点
int end; //终点
int RoutineTime; //该路线所需时间
}edge[N];
int LsolationTime[N]; //隔离时间
int ShortDistanceTime[N];
int main()
{
int n, m, u, v, c;
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>LsolationTime[i];
}
for(int i=1; i<=m; i++)
{
cin>>u>>v>>c;
edge[i].start = u;
edge[i].end = v;
edge[i].RoutineTime = c;
edge[m+i].start = v;
edge[m+i].end = u;
edge[m+i].RoutineTime = c;
}
memset(ShortDistanceTime, INF, sizeof(ShortDistanceTime));
ShortDistanceTime[1] = 0; //起点距离为0
for(int operation = 1; operation <= n; operation++) //循环n轮
{
for(int i=1; i<=2*m; i++)
{
u = edge[i].start; //当前点
v = edge[i].end; //邻居
int time = LsolationTime[v]; //邻居点隔离时间
if(v == n) //到达终点
time = 0;
//到邻居所需时间=当前点+路线时间+隔离时间
ShortDistanceTime[v] =
min(ShortDistanceTime[v], ShortDistanceTime[u] + edge[i].RoutineTime + time);
}
}
cout << ShortDistanceTime[n] << endl;
return 0;
}2024/04/05 周五
蓝桥王国（Dijkstra算法）
【参考代码】
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3fLL;
const int N = 3e5+1;
int n, m;
struct edge{
int from;
int to;
ll weight;
edge(int num1, int num2, ll num3) //构造函数，用于给变量赋值。错误点：ll写成int
{
from = num1;
to = num2;
weight = num3;
}
};
vector<edge> e[N];
ll ShortDistance[N];
struct node{
int id; //结点
ll nowdistance; //这个结点到起点的距离
node(int num1, ll num2) //构造函数，用于给变量赋值。错误点：ll写成int
{
id = num1;
nowdistance = num2;
}
bool operator < (const node &a) const
{
return nowdistance > a.nowdistance;
}
};
void dijkstra()
{
bool done[N]; // done[i]=true表示到结点i的最短路径已经找到
for(int i=1;i<=n;i++)
{
ShortDistance[i] = INF; // 对最小距离数组进行初始化
done[i] = false; // 对标记数组进行初始化
}
ShortDistance[1] = 0; // 起点到自己的距离是0
priority_queue<node> q;
q.push(node(1, 0));
while(!q.empty())
{
node dot = q.top();
q.pop();
if(done[dot.id])
continue;
done[dot.id] = true;
for(int i=0; i<e[dot.id].size(); i++)
{
edge neighbor = e[dot.id][i]; //这里的 e[u.id] 是一个存储边信息的向量（vector），它包含了所有从节点 u 出发的边。e[u.id][i] 表示取出向量中的第 i 个元素，即从节点 u 到节点 y.to 的边的信息。
if(done[neighbor.to])
continue;
if(ShortDistance[neighbor.to] > neighbor.weight + dot.nowdistance) //更新距离值
{
ShortDistance[neighbor.to] = neighbor.weight + dot.nowdistance;
q.push(node(neighbor.to, ShortDistance[neighbor.to]));
}
}
}
}
int main()
{
int u, v, w;
cin>>n>>m;
for(int i=1; i<=n; i++)
e[i].clear();
while(m--)
{
cin>>u>>v>>w;
e[u].push_back(edge(u, v, w)); //将边添加到正确的容器中
}
dijkstra();
for(int i=1; i<=n; i++)
{
if(ShortDistance[i] >= INF) //无法到达
cout << -1 << ' ';
else
cout << ShortDistance[i] << ' ';
}
return 0;
}子树的大小
【参考代码】
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
while(t--)
{
ll n, m, k; //n个结点，m茶树，第k点
cin>>n>>m>>k;
ll ans = 1;
ll leftchild = (k - 1) * m + 2;
ll rightchild = k * m + 1;
while(rightchild <= n)
{
ans += rightchild - leftchild + 1; //加回本身的点
leftchild = (leftchild - 1) * m + 2; //leftchild继续增加
rightchild = rightchild * m + 1; //rightchild继续增加
}
if(leftchild <= n)
{
ans += n - leftchild + 1;
}
cout << ans << endl;
}
return 0;
}平均
【参考代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
struct node
{
int number;
int weight;
}a[N];
bool compare(node num1, node num2) //按代价升序排列
{
return num1.weight < num2.weight;
}
int main()
{
int n;
long long value = 0;
int hash[10] = {0}; //0-9出现的次数
cin>>n;
for(int i=0; i<n; i++)
{
cin>>a[i].number>>a[i].weight;
hash[a[i].number]++;
}
sort(a, a+n, compare); //按代价升序排列
for(int i=0; i<n; i++) //从最小代价开始找，不管number，number的出现次数已经存好了
{
if(hash[a[i].number] > n / 10) //题目规定的出现次数，每个数只能出现n/10次
{
value += a[i].weight; //加上这个数的代价
hash[a[i].number]--; //该数出现的次数减一次
}
}
cout << value << endl;
return 0;
}ASC
【参考代码】
#include <iostream>
using namespace std;
int main()
{
cout << 'L'-'A'+'A' << endl;
return 0;
}
不同子串
【参考代码】
这题比较坑的是第二重循环需要从0开始
最终结果：100
set容器，不需要赋值
#include <bits/stdc++.h>
using namespace std;
set<string> s1;
int main()
{
string s = "0100110001010001";
for(int i=0; i<s.size(); i++)
{
for(int j=0; j<s.size(); j++) //需要从0开始，无需担心重复
{
s1.insert( s.substr(i, j) );
}
}
cout << s1.size() << endl;
return 0;
}
map容器，需要赋值
#include <bits/stdc++.h>
using namespace std;
map<string, int> mp;
int main()
{
string s = "0100110001010001";
for(int i=0; i<s.size(); i++)
{
for(int j=0; j<s.size(); j++)
{
mp[s.substr(i, j)] = 1;
}
}
cout << mp.size() << endl;
return 0;
}星期计算
【参考代码】
爆long long，long long范围在
你也可以用__int128
#include <iostream>
using namespace std;
int main()
{
int ans = 6;
long long temporary = 1;
for(int i=0; i<22; i++)
{
temporary *= 20;
temporary %= 7;
}
ans += temporary;
ans %= 7;
cout << ans+7 << endl;
return 0;
}__int128版本：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int ans = 6;
__int128 temporary = 1;
for(int i=0; i<22; i++)
{
temporary *= 20;
}
temporary = temporary % 7;
ans = ans + temporary;
cout << ans << endl;
}