寒假集训思维训练1题解

今日榜单，再接再厉。
每天晚上都要去补题，今天不做，明天就越欠越多

A - Easy Problem
比较简单，可以用数学公式来算，也可以循环枚举$b$,因为$n-b$得到的$a$要求为正整数，所以枚举$b$从$1$开始到$n-1$结束，得到的$a$就是正整数，答案$n-1$

B - Normal Problem
生活中的一种现象，透过玻璃去看贴纸的另一面形状，实际上是一种逆序图形翻转，同学们可以自己在草稿纸上写ABC，然后从反面观察一下

C - Hard Problem
先讨论第一行的猴子能不能都满足，如果不能都满足那么只能让$M$个猴子坐，再讨论第二行能不能都满足，剩下的位置拿去分给第三类猴子，直到没有猴子了或者没位置了

D - Harder Problem
题意要读懂，意思是给定$A$数组，问能不能构造出一个$B$数组，$B$数组的元素值范围是$[1N]$ ，问能不能在$B[1--i]$这段里面，满足$A[i]$是众数。这是属于构造题，构造题同学们要思考的特殊一点，往往构造题的方法比较特殊，有规律。
我们可以考虑构造一个$N$的排列，因为每个数字只出现一次，所以所有的数字都是众数，然后按A数组的元素顺序，去输出这个排列就行了。即先输出A数组中有的元素，再输出其余的元素来凑长度

E - Insane Problem

数据范围比较大，首先Kⁿ 指的是$n$个K相乘，题目的式子可以变形一下 $y=x\ast k$ⁿ
那么L₂ <= y <= R₂ 变为 L₂ <= x* Kⁿ <= R₂ 令左右两边区间同时除以Kⁿ 可以得到一个$X$的 区间范围，

综合原本题目给定的$X$范围 ，两个范围重合的部分就是题目的解。
又因为$n$不确定，所以同学们要自己去枚举$n$ 然后去算区间交集

参考代码如下

#include<bits/stdc++.h>

using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long int  k,l1,r1,l2,r2;
        cin>>k>>l1>>r1>>l2>>r2;
        long long int  kn=1,ans=0;
        for(int n=0;r2/kn>=l1;n++)  //枚举n   
        {	// x的范围 [l1,r1]  以及  [l2/kn , r2/kn]  两个区间不相交  就没必要再枚举了 
            ans+=max(0ll,min(r2/kn,r1)-max((l2-1)/kn+1,l1)+1ll); // 计算区间交   
            kn*=k;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

F - Minimize!
太简单了自己做

G - osu!mania
输入字符矩阵，从最后一行开始枚举，依次输出每个#所在哪一列

H - The Legend of Freya the Frog
思考，只考虑一个轴方向的跳跃，那么达到目标$x$ , $y$ 最少要多少步 ?
很明显是利用$x$整除$k$ ，这样子能最快到达$x$ 但是由于题目每跳跃一次，方向就要改变一次，所以说最快到达目标$x$ ，目标$y$的时间可能不一样，所以先到的，需要等待。
我们考虑一个问题，假设最快跳跃到$x$需要$needx$步，最快跳跃到$y$需要$needy$步，由于跳一次要换方向，一开始从x轴开始跳，我们可以视“跳一次x，跳一次y” 为一组 ，每一组需要两步操作
那么最终得看，哪个方向最晚才能达到目标。如果x轴方向是较晚到达的，即y方向比较早到达，以后y方向的跳跃都是原地跳。那么一共需要跳$needx\ast 2-1$ 次操作才能到达$(x,y)$ ；如果是y方向较晚到达，那么需要$needy\ast 2$次操作，因为以$y$结束

I - Satyam and Counting
坐标点的$y$轴比较特殊，所以考虑一下有几种类型的三角形，去枚举坐标点就行了

#include <bits/stdc++.h>
using namespace std;
int cnt[2][300010];
int main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        memset(cnt,0,sizeof(cnt)); // 把cnt数组清零 
        for(int i=1;i<=n;i++){
            int x,y;
            cin>>x>>y;
            cnt[y][x]++;
        }
        long long int ans=0;
        for(int i=0;i<=n;i++){  //枚举x 坐标  
            if(cnt[0][i]&&cnt[1][i]){
                ans+=n-2;
            }//如果竖着的  有两个点，那么它与其他的N-2个点都可以构成直角三角形   
            if(i+2<=n){
                if(cnt[0][i]&&cnt[0][i+2]&&cnt[1][i+1]){
                    ans++;
                }
                if(cnt[1][i]&&cnt[1][i+2]&&cnt[0][i+1]){
                    ans++;
                }
            }
        }
        cout<<ans<<endl;
    }

    return 0;
}