2024.11.28周四
-
Q1. 1200
给定a,b。构造一数组，满足平均值为a，中位数为b。 -
Q2. 1300
给定4个数字，输出1~5中未出现的数字。 -
A1. 9mins
考虑等差数列，3个元素便能构造出来：4a-3b,b,2b-a。 -
A2. 4mins
数组记录一下即可。 -
A3. 补：假思路：bfs会MLE 还不知道为什么
一个巧妙的做法：考虑每个元素最多贡献一次，某个元素可以为其他元素作通路。
选择某个数可以将数组长度从a->b，处理每个数，建立有向图。从n跑一遍找最大值。
A1.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' //
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
const int mod = 998244353;
const int N = 10 + 5e5;
void _();
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
_();
return 0;
}
// 给定a,b。构造一数组，满足平均值为a，中位数为b。
// 9mins
// 考虑等差数列，3个元素便能构造出来：4a-3b,b,2b-a。
void _()
{
int a, b;
cin >> a >> b;
int x = 4 * a - 3 * b, y = 2 * b - a;
cout << 3 << endl;
cout << x << ' ' << b << ' ' << y << endl;
}
A2.
#include <bits/stdc++.h>
// #define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
_();
return 0;
}
// 给定4个数字，输出1~5中未出现的数字。
// 4mins
// 水题。
void _()
{
int n = 4;
int has[6] = {};
while (n--)
{
int x;
cin >> x;
has[x] = 1;
}
for (int i = 1; i < 6; i++)
if (!has[i])
{
cout << i << endl;
return;
}
}
A3.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
const int mod = 998244353;
const int N = 10 + 5e5;
void _();
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
_();
return 0;
}
// 给定一数组，每次操作你可以选择一个元素a[i](满足a[i]是从右向左数第a[i]个)在数组右边添加i-1个0。问任意操作数组长度的最大值。
// 假思路：bfs会MLE 还不知道为什么
// 一个巧妙的做法：考虑每个元素最多贡献一次，某个元素可以为其他元素作通路。
// 选择某个数可以将数组长度从a->b，处理每个数，建立有向图。从n跑一遍找最大值。
void _()
{
int n;
cin >> n;
map<int, vector<int>> e;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
e[x + i - 1].push_back(x + 2 * i - 2);
// bug2(x + i - 1, x + 2 * i - 2);
}
map<int, bool> vis; // core
// 2.
// int res = n;
// function<void(int)> dfs = [&](int u)
// {
// if (vis[u])
// return;
// vis[u] = 1;
// res = max(res, u);
// for (auto v : e[u])
// dfs(v);
// };
// dfs(n);
// cout << res << endl;
// 1.
function<int(int)> dfs = [&](int u)
{
if (vis[u])
return 0ll;
vis[u] = 1;
int maxw = u;
for (auto v : e[u])
maxw = max(maxw, dfs(v));
return maxw;
};
cout << dfs(n) << endl;
}
// bfs_debug死循环 原理：数是递增的 从而中止循环 bug：增量为0
// void _()
// {
// // srand(time(0));
// int n = 3e5;
// cin >> n;
// vector<int> w(n + 1);
// map<int, bool> in_q;
// map<int, vector<int>> has;
// for (int i = 1; i <= n; i++)
// {
// int x;
// cin >> x;
// // x = rand() % (int)1e12;
// // bug(x);
// w[i] = i - 1;
// if (i > 1)
// has[x - (n + 1 - i)].push_back(i);
// // bug(x - (n + 1 - i));
// }
// int res = 0;
// int cnt = 0;
// auto bfs = [&]()
// {
// queue<int> q;
// for (auto i : has[0])
// {
// q.push(w[i]);
// res = max(res, w[i]);
// in_q[w[i]] = 1;
// }
// int cnt = 0;
// while (q.size())
// {
// // cnt++;
// // if (cnt > 20)
// // break;
// auto x = q.front();
// // bug(x);
// q.pop();
// in_q[x] = 0;
// for (auto i : has[x])
// {
// // bug2(x, i);
// if (!in_q[x + w[i]])
// q.push(x + w[i]);
// res = max(res, x + w[i]);
// }
// }
// };
// bfs();
// res += n;
// cout << res << endl;
// }
// void _()
// {
// int n;
// cin >> n;
// vector<int> w(n + 1);
// map<int, vector<int>> has;
// for (int i = 1; i <= n; i++)
// {
// int x;
// cin >> x;
// w[i] = i - 1;
// has[x - (n + 1 - i)].push_back(i);
// }
// int res = 0;
// function<void(int,int)>dfs=[&](int u,int ans)
// {
// for(auto i:has[u])
// {
// ans+=w[i];
// }
// }
// cout << res << endl;
// }