寒假集训思维训练1题解

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

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

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

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

#include<bits/stdc++.h>
using namespace std;
int main() {int t;cin>>t;for(int i=1;i<=t;i++) {int n,a,b,c;cin>>n>>a>>b>>c;if(a>=n) {a=n;}if(b>=n) {b=n;}if(c>2*n-a-b){c=2*n-a-b;}cout<<a+b+c<<endl;
}return 0;
}

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

#include<bits/stdc++.h>
using namespace std;
#define N 200005
long long t,vis[N],cnt,n,a[N];
int main(){cin>>t;while(t--){memset(vis,0,sizeof(vis)),cnt=0;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){if(vis[a[i]]==1) cnt++;else{vis[a[i]]=1;cout<<a[i]<<" ";}}for(int i=1;i<=n;i++){if(vis[i]!=1) cout<<i<<" ";}}
}

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
输入字符矩阵，从最后一行开始枚举，依次输出每个#所在哪一列

#include<bits/stdc++.h>
using namespace std;
char A[510][510];
int main() {int t,n;cin>>t;for(int i=1;i<=t;i++){cin>>n;for(int j=1;j<=n;j++){for(int k=1;k<=4;k++){cin>>A[j][k];}}for(int j=n;j>=1;j--){for(int k=1;k<=4;k++){if(A[j][k]=='#'){cout<<k<<' ';}}}cout<<endl;}return 0;
}

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$结束

#include<bits/stdc++.h>
using namespace std;
int main(){int t;cin>>t;while(t--){int x,y,k;cin>>x>>y>>k;int needx=x/k+(x%k!=0);int needy=y/k+(y%k!=0);int ans;if(needy>=needx){ans=needy*2;}else{ans=needx*2-1;}cout<<ans<<'\n';}return 0;
}

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