Day 3
A. 黑妹的游戏Ⅰ
题意
给出三个不同的初始数字$a,b,c$，黑妹每次选择两个不同的数字，计算出差的绝对值后如果黑板上没有就写在黑板上。问黑妹最多能添加多少个数字。
思路
考虑到辗转相除法的那种过程（其实我也是突发奇想，严谨证明不会），最后黑板上所有的数字是 $$ ans = \frac{max(a,b,c)}{gcd(a,b,c)} $$ 然后就需要减去黑板上原来的三个数就行。
代码实现
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int t;
long long a,b,c;
long long gcd(long long a,long long b)
{
if(b == 0) return a;
return gcd(b,a%b);
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&a,&b,&c);
long long p = max(max(a,b),c);
long long k = gcd(gcd(a,b),c);
printf("%lld\n",p/k-3);
}
return 0;
}
B. 御坂美琴
题意
有 $n$ 个玩偶堆成一堆。$(1\le n \le 10^{18})$
你可以指定某一有 $x$ 个玩偶的玩偶堆将他分成 $\lfloor \frac{x}{2}\rfloor$ 和 $x-\lfloor \frac{x}{2} \rfloor$ 两堆。
现给定有 $m$ 个数的序列 $a$ ，问能否通过若干次操作使得第 $i$ 堆玩偶数为 $a_i$ 。如果可以输出 misaka 否则输出 ham 。$(1\le m\le 10^5) , (1\le a_i\le 10^{18})$
思路
首先我们可以想到，我们输入序列 $a$ 的时候可以将他累加起来成 $sum$ ，然后考虑最后$sum$ 是否和 $n$ 相同，不同的话肯定是不满足条件的，直接输出ham退出即可。
否则我们就用 $dfs(n)$ 分割这个 n个玩偶的玩偶堆。因为 $n$ 比较大，考虑开一个map映射 $p$ 记录是否已经有为 $i$ 个玩偶的玩偶堆，如果有的话 $p[i] = 1$。如果没有 $p[i] = 0$ 。
然后加一个递归结束的条件，就是当 $dfs(k)$ 的时候 $k == 1$ ，那么就不可再分了，直接返回。
代码实现
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<map>
using namespace std;
#define ll long long
const long long maxn = 1e18+5;
const int maxm = 1e5+5;
ll n,m;
ll a[maxm];
ll sum;
map<ll,bool> mp;
int cmp(ll a,ll b)
{
return a>b;
}
void dfs(ll p)
{
if(mp[p] == 1 || p==1) return ;
else
{
mp[p] = 1;
dfs(p>>1);
dfs(p-(p>>1));
}
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%lld",&a[i]);
sum += a[i];
}
if(sum != n)
{
printf("ham\n");
return 0;
}
// sort(a+1,a+1+m,cmp);
dfs(n);
mp[1] = 1;
for(int i=1;i<=m;i++)
{
if(mp[a[i]] == 0)
{
printf("ham\n");
return 0;
}
}
printf("misaka\n");
return 0;
}
Day 4
A. Distance
题意
给定有 $n$ 个数的序列 $A$ ，第 $i$ 个位置对应的值为 $A_i$ 。$(n\le 10^5 ,A_i \le 10^9)$
定义 $FST$ 距离为 $|i^2 - j^2| + |A_i^2 - A_j^2|$ ，现在 $fst$ 想在序列 $A$ 中找到距离最大的一对元素，他不关心是哪一对，只想要求出最大的距离。
思路
我们分情况讨论一下
- 当 $i > j$ 并且 $A_i > A_j$ ，我们去掉绝对值后 $dis = i^2 + A_i^2 - (j^2 + A_j^2)$
- 当 $i > j$ 并且 $A_i < A_j$ ，我们去掉绝对值后 $ dis = i^2 -A_i^2 -(j^2-A_j^2)$
所以我们只需要在输入的时候维护两个数组，分别为 $p[i] = i^2+A_i^2 ,q[i] = i^2-A_i^2$ ，排序一下，然后在上面两个 $dis$ 中取一个最大值即可。
代码实现
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
#define ll long long
const int maxn = 1e5+5;
int n;
long long a[maxn];
long long f1[maxn];
long long f2[maxn];
int cmp(long long a,long long b)
{
return a>b;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
f1[i] = (long long)i*i + (long long)a[i]*a[i];
f2[i] = (long long)i*i - (long long)a[i]*a[i];
}
sort(f1+1,f1+1+n,cmp);
sort(f2+1,f2+1+n,cmp);
ll p = f1[1] - f1[n];
ll k = f2[1] - f2[n];
if(p > k)
{
printf("%lld",p);
}
else printf("%lld",k);
}
B. 字典序最小的中序遍历
题意
给一个有根二叉树,可以无限次的交换任意节点的左右子树,问最少交换多少次使得该树的中序遍历的字典序最小?
思路
首先这题我上来觉得他就是个贪心题。。不然真的无从下手。
那么字典序最小，只能是左边小于右边，如果不是的话就直接交换就完事了，然后 $ans++$ 即可。
然后最后利用 $dfs$ 进行树的中序遍历即可。看代码还是比较好懂的。
代码实现
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int n,m;
const int maxn = 500005;
int a[maxn],b[maxn];
int ans = 0;
int rev(int p)
{
int l = p ,r = p;
if(a[p]) l = rev(a[p]);
if(b[p]) r = rev(b[p]);
if(l > r)
{
swap(a[p],b[p]);
ans++;
}
return l<r?l:r;
}
void dfs(int p)
{
if(a[p]==0 && b[p] ==0)
{
printf("%d ",p);
return ;
}
if(a[p]) dfs(a[p]);
printf("%d ",p);
if(b[p]) dfs(b[p]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
}
int k = rev(m);
printf("%d\n",ans);
dfs(m);
return 0;
}