A. Strange Partition
題意：給出大小為n一個數組a ，能進行多次操作 将ai+aj合并合并後數組減短 得到數組b 給出一個x 問
最大是多少
思路:這裡是用的向上取整 很好想如果全部合在一起那麼最多是sum/x+1而如果全部拆開是那麼可能是sum/x+n這裡我們直接枚舉即可 記得開longlong
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,k;
scanf("%d%d",&n,&k);
long long sum=0,ans1=0,ans2=0;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
ans1+=(x+k-1)/k;
sum+=x;
}
printf("%lld %lld\n",(sum+k-1)/k,ans1);
}
}
B. Strange List
題意：您已将長度為n的數組a和整數x賦予了一個全新的機器人。機械手的操作如下：疊代數組的元素，讓目前元素為q。如果q可被x整除，則機械手會将x個這樣的整數q/x 添加到數組的末尾，然後移至下一個元素。請注意，新添加的元素可以稍後由機器人處理。否則，如果q不能被x整除，則機器人将關閉問這個關閉時所有的值加起來是多少
思路：總個數為1e5 我們直接從前往後枚舉即可tot[]數組表示x的個數
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int a[N*25];
int tot[N*25];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,k;
scanf("%d%d",&n,&k);
long long sum=0,ans1=0,ans2=0,cnt=n;
long long ans=0,flag=1;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&a[i]);
tot[i]=1;
}
int i=1;
while(i<=cnt){
ans+=a[i]*tot[i];
if(flag){
if(a[i]%k){
flag=0;
}
else{
tot[++cnt]=tot[i]*k;
a[cnt]=a[i]/k;
}
}
i++;
}
cout<<ans<<endl;
}
return 0;
}
C. Strange Birthday Party
題意:n個朋友參加聚會 送他們禮物或者錢 禮物必須滿足
錢必須等于Ck
然後禮物的價格滿足升序
思路：貪心排個序就好啦
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
typedef long long LL;
int a[N];
int c[N];
bool cmp(int x,int y){
return x>y;
}
bool st[N];
int main(){
int T;
cin>>T;
while(T--){
int n,k;
memset(st,0,sizeof st);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=k;i++){
scanf("%d",&c[i]);
}
LL ans=0;
int cnt=1;
for(int i=1;i<=n;i++){
if(cnt<=k&&c[cnt]<=c[a[i]])
ans+=c[cnt++];
else ans+=c[a[i]];
}
cout<<ans<<endl;
}
}
D. Strange Definition
題意：
思路:x和y滿足有關時他們相乘必然是一個完全平方數 我們進行質因數分解如果一個質因子p為偶數次方那麼我們取p的0次方 （因為p的偶數次方為完全平方數我們把它約掉）如果為奇數次方那麼我們取p的1次方
這時候在處理完後x和y如果他們能成為相關 那麼這2個數一定相等 在w=0時ans就是相等的數的個數的最大值
在w>1時 如果相等的數總個數為偶數即為偶數個1相加為偶數 如果為奇數那麼為奇數個奇數相加仍然為奇數 再進行多次操作後答案不會改變 是以ans隻有2種情況 而奇數一直不變 是以在w>1的時候 ans取w=0時候的ans 與所有偶數個數的 的最大值
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int primes[N],cnt,a[N];
bool st[N];
void init(){
int n=N-1;
for(int i=2;i<=n;i++){
if(!st[i])primes[++cnt]=i;
for(int j=1;primes[j]<=n/i;j++){
st[primes[j]*i]=1;
if(i%primes[j]==0)break;
}
}
}
int main(){
int T;
init();
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
for(int j=1;primes[j]<=a[i]/primes[j];j++){
if(a[i]%primes[j]==0){
int cnt1=0;
while(a[i]%primes[j]==0)a[i]/=primes[j],cnt1++;
if(cnt1&1)a[i]*=primes[j];
}
}
}
sort(a+1,a+1+n);
int ans1=0,ans2=0,pre=0;
a[n+1]=0;
for(int i=1;i<=n;i++){
if(a[i]!=a[i+1]){
ans1=max(ans1,i-pre);
if(a[i]==1)ans2+=i-pre;
else if(!(i-pre&1))ans2+=i-pre;//偶數個奇數相乘等于偶數
pre=i;
}
}
int q;
ans2=max(ans2,ans1);
scanf("%d",&q);
while(q--){
LL w;
scanf("%lld",&w);
if(w==0)printf("%d\n",ans1);
else printf("%d\n",ans2);
}
}
}