排位三和四记录

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;
}