C. Great Sequence

原题描述

题意理解

我们可以从数组中任选两个数x,y，满足x*p=y即可。如果一个数组中所有的数都可以组成这个关系，则称为好数组。现题目给出数组元素与p，你可以在数组中添加任意元素，至少添加多少个元素能使题目所给数组符合要求。

说明：当p=4时，1，4，4，16是一个好数组，因为a[2]=p*a[1]，a[4]=p*a[3]。可组成两个数对(1,4),(4,16)。注意的是，每个数对中的数必须是不同位置的数。

题解

对于数组a，我们找到所有满足x*p=y的数对，然后剩下k个元素没有匹配，添加k个元素与之配对即可。

在寻找数对之前，我们可以通过排序，使数组元素单调，这样我们只需要两个指针各遍历一次数组即可。一个指针用来寻找x，一个指针用来寻找y。从大到小遍历，对于a[i]，如果a[i]能被p整除，则移动j，只要j>1且a[j]>a[i]/p，就递减j，如果递减到刚刚小于等于a[i]则停止。再移动i到下一个y。i，j均在循环体外定义，故复杂度为O(n)。值得注意的是，一个数不能使用两次，所以用一个数组标记一下使用过的数字，遇到则不取。

复杂度为O(nlogn)（由排序决定）。

AC代码

/*@_krito*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LM LLONG_MAX
#define IM INT_MAX
#define int long long
#define _for(i,a,b) for(int i=a;i<=b;i++)
const int N = 2e5+10;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
}
int a[N];
bool vis[N];
signed main(){int t;t=read();while(t--){memset(vis , 0 , sizeof vis);int n,x;n=read();x=read();_for(i,1,n) a[i]=read();sort(a+1,a+1+n);int ans=n;int j=n;for(int i=n;i>=1;i--){if(vis[i]) continue;if(a[i]%x==0){int temp=a[i]/x;while(j>=1&&(vis[j]||a[j]>temp)){j-=1;}if(j>=1&&!vis[j]&&a[j]==temp){vis[i]=1;vis[j]=1;ans-=2;}}}printf("%d\n",ans);}
}

B. Power Walking

原题描述

题解

随着k递增，我们每次移出去一个不重复的元素，这样对于k个分组，其和仍与只有一个分组时一致，直到没有不重复元素可以移出去时，只能移出重复元素，这时对于k个分组，其和为移出去的重复元素个数加上初始数组元素种类。所以本题关键在于初始数组中的元素种类。故使用set，将输入都塞入set，最后读一下set的大小，然后当i<s.size()时输出s.size()，当i>s.size()时，每次迭代使答案加1即可。

AC代码

/*@_krito*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LM LLONG_MAX
#define IM INT_MAX
#define _for(i,a,b) for(int i=a;i<=b;i++)inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
}
int main(){int t;t=read();while(t--){set<int> s;int n;n=read();_for(i,1,n){int temp;temp=read();s.insert(temp);}int x=s.size();_for(i,1,n){if(i<=x){cout<<x;}if(i>x){cout<<++x;}cout<<" ";}cout<<endl;}
}