总算又能安心刷题了
A. Nastia and Nearly Good Numbers
题意:
给定A、B,要求找出三个数 x,y,z。满足条件:
- x + y = z
- 其中有两个数只能整除A,有一个可以整除A*B
- x,y,z 各不相同
思路:
显然,z是最大的,让z整除A*B就行了 。
那么令 x = A*(B-1) , y = A , z = A*B 就行了。
这个时候,可以发现,B不能等于1,同时当B等于2的时候,x 和 y 相等。那么可以令 x = 3A ,y = A ,z = 4A。
Code:
#include <bits/stdc++.h>
#define int long long
const int inf = 1e18;
using namespace std;
const int N = 1e6+7;
int t = 1,n,m;
int a[N];
signed main(){
int t;
cin>>t;
while(t--){
cin>>n>>m;
if(m == 1){
cout<<"NO"<<endl;
}else{
cout<<"YES"<<endl;
if(m != 2)
cout<<n*(m-1)<<" "<<n<<" "<<n*m<<endl;
else{
cout<<n*(3)<<" "<<n<<" "<<n*4<<endl;
}
}
}
}
B. Nastia and a Good Array
题意:
给定一个数组,给定一种操作,可以选择两个位置上的数,给他们重新赋值,要求保持 赋值后 两个数的最小值 等于 原来的最小值。要把数组变成相邻位置全部互质,问如何操作。
思路:
众所周知, gcd(x,x+1) = 1,也就是相邻两数是互质的。那么只需要找到数组中的一个最小值。然后有了这个最小值,就可以把数组变成一个 从最小值的位置往两边递增的数组,且增量为1。也就是
x+2 , x+1 , x , x+1 , x+2 , x+3
Code:
#include <bits/stdc++.h>
#define int long long
const int inf = 1e18;
using namespace std;
const int N = 1e6+7;
int t = 1,n,m;
int a[N];
signed main(){
int t;
cin>>t;
while(t--){
cin>>n;
for(int i = 0 ; i < n ; i ++) cin>>a[i];
if(n == 1){
cout<<0<<endl;
}else{
int maxi = 0;
int minn = 2e9;
for(int i = 0 ; i < n ; i ++){
if(a[i] < minn){
minn = a[i];
maxi = i;
}
}
cout<<n-1<<endl;
int now = minn;
for(int i = maxi ; i < n-1 ; i ++){
cout<<maxi+1<<" "<<i+2<<" "<<a[maxi] <<" "<< ++ now <<endl;
}
now = minn;
for(int i = maxi ; i > 0 ; i --){
cout<<maxi+1<<" "<<i<<" "<<a[maxi] <<" "<< ++ now<<endl;
}
}
}
}
C. Nastia and a Hidden Permutation
题意:
给定一个未知的排列,即数组元素为 1 - n。
有两种询问( 1 <= x <= n-1)。
- max( min(x,pi) , min(x+1,pj) )
- min( max(x,pi) , max(x+1,pj) )
要求在 ⌊ 3 ⋅ n 2 \frac{3⋅n}{2} 23⋅n⌋+30 次 询问之内, 还原这个排列。
思路:
先观察一下这两种操作。
对于第二种操作。如果知道 pj = n。那么问题就解决了。
只需要询问 min( max(1,pi) , max(2,n) ) 就知道pi是多少了。因为右边永远是 n,而左边 永远是pi,而外面 又是min,那么查询的结果就是 pi。
于是问题变成了,如何用 n/2 次操作找到 pj = n。
对于第一种操作,如果取x = n-1,那么就变成了max( min(n-1,pi) , min(n,pj) ) 由于里面取的是min。如果这两个数 都小于 n-1,那么这样查,查出来的就是 max(pi,pj),由此每次可以排除两个小于n-1 的数。那么对于 n-1,和 n。不管 n或者n-1在左边,那么查询结果都是 n-1。即 max( min(n-1,n-1) , min(n,pj) ) , max( min(n-1,n) , min(n,pj) ) 结果都是 n-1。那么这时候,只要再查询一次,把 pi, pj 交换位置,变成 max( min(n-1,pj) , min(n,pi) ) 如果 pi 是 n,这时候就能查出来了。
因为是两个数两个数一查,也就是 n/2 次 + 一两次。
还有一个小细节就是当 n为奇数时。如果 前面 n-1 个都没查到n。那么最后一个就是n了。
Code:
#include <bits/stdc++.h>
#define int long long
const int inf = 1e18;
using namespace std;
const int N = 1e6+7;
int t = 1,n,m;
int a[N];
int ask(int op,int i,int j,int x){
cout<<"? "<<op<<" "<<i<<" "<<j<<" "<<x<<endl;
cout.flush();
cin>>x;
return x;
}
int ans(){
cout<<"! ";
for(int i = 1 ; i <= n ; i ++){
cout<<a[i]<<" ";
}
cout<<endl;
cout.flush();
}
signed main(){
int t;
cin>>t;
while(t--){
cin>>n;
int flag = 0;
for(int i = 1 ; i <= n-1 ; i += 2){
int minn = ask(1,i,i+1,n-1);
if(minn == n){
a[i+1] = n;
for(int j = 1 ; j <= i ; j ++){
a[j] = ask(2,j,i+1,1);
}
for(int j = i+2 ; j <= n ; j ++){
a[j] = ask(2,j,i+1,1);
}
flag = 1;
break;
}else if(minn == n-1){
minn = ask(1,i+1,i,n-1);
if(minn == n){
a[i] = n;
flag = 1;
for(int j = 1 ; j < i ; j ++){
a[j] = ask(2,j,i,1);
}
for(int j = i+1 ; j <= n ; j ++){
a[j] = ask(2,j,i,1);
}
break;
}else{
a[i] = n-1;
}
}
}
if(!flag){
a[n] = n;
int i = n;
for(int j = 1 ; j < i ; j ++){
a[j] = ask(2,j,i,1);
}
}
ans();
}
}