A
B
C
题目给你一个结论 最少需要min((odd,even)个结点可以把一棵树的全部边连起来 要求你输出两颗树
一棵树结论是正确的 另外一棵结论是正确的 正确结论的树很好造 主要是错误的树
题目给了你提示 提供了一个八个结点的错误的树 然后我们慢慢推发现只要N>=6就存在错误的树(把提供的树的左边两个结点删掉)
结点大于6就全部放在4号结点下
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
const double EPS = 1.0e-4;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
map<string, ll> mp;
string str[];
queue<int> que;
int main()
{
int n;
cin >> n;
if (n < )
{
cout << - << endl;
}
else
{
if (n % )
{
cout << << " " << << endl;
cout << << " " << << endl;
cout << << " " << << endl;
cout << << " " << << endl;
cout << << " " << << endl;
cout << << " " << n << endl;
for (int i = ; i <= n - ; i++)
{
if (i % )
{
cout << << " " << i << endl;
}
else
{
cout << << " " << i << endl;
}
}
}
else
{
cout << << " " << << endl;
cout << << " " << << endl;
cout << << " " << << endl;
cout << << " " << << endl;
cout << << " " << << endl;
for (int i = ; i <= n; i++)
{
if (i % )
{
cout << << " " << i << endl;
}
else
{
cout << << " " << i << endl;
}
}
}
}
for (int i = ; i <= n - ; i++)
{
cout << i << " " << i + << endl;
}
}
D
玄学暴力题
给你一个数列 要求你给出字典序最小的但不小于给定数列的目标数列 要求目标数列内两两互质
假设我们要求出这个数列可能要求的最大的数 质数的数量级是x/logx 所以 x/logx-1e4>1e5 大概可以求出x在2e6差不多
然后把2-2e6的每个数都存到一个set里面这个set存的是当前所有可插入原数组的数 同时把每个数的质因数都存到一个vector里面
然后输入原有的数组 每次输入一个数就在set里去除掉他的质因数的倍数(包括它本身) 这样这个set里面的每个数就都是当前合法插入数
如果需要插入的数比原数列的大 就可以直接输出set.begin()
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
const double EPS = 1.0e-4;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
bool prime[];
vector<int> beishu[];
bool eras[];
set<int> num;
bool pre = true;
int main()
{
int n;
cin >> n;
for (int i = ; i <= ; i++)
{
num.insert(i);
if (prime[i])
{
continue;
}
//cout<<i<<endl;
for (int j = i; j <= ; j += i)
{
prime[j] = true;
beishu[j].pb(i);
}
}
//TS;
int now;
int aim;
for (int i = ; i <= n; i++)
{
scanf("%d", &now);
if (pre)
{
aim = *num.lower_bound(now);
if (aim > now)
{
pre = false;
}
}
else
{
aim = *num.begin();
}
cout << aim << " ";
for (int j : beishu[aim])
{
for (int k = j; k < ; k += j)
{
if (!eras[k])
{
num.erase(k);
eras[k] = true;
}
}
}
}
return ;
}
E
找规律或者OEIS
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
const double EPS = 1.0e-4;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
ll dp[];
ll dfs(ll x)
{
if (x <= )
{
return dp[x];
}
if (x % )
{
return 2LL * dfs(x / ) + x / + ;
}
else
{
return 2LL * dfs(x / ) + x / ;
}
}
int main()
{
ll n;
cin >> n;
ll anser;
dp[] = ;
for (int i = ; i <= ; i++)
{
dp[i * ] = * dp[i] + i;
dp[i * + ] = * dp[i] + i + ;
}
//cout << dp[n - 1] << endl;
// for(int i=1;i<=10;i++)
// cout<<dp[i]<<endl;
cout << dfs(n - ) << endl;
return ;
}