CF1515
A:CF1515A Phoenix and Gold
因为所有数并不相同，所以这个题解决起来很简单，如果前缀和 \(ans=x\) 时，交换前后两个数位置就行了，其他的正常输出。
#include<bits/stdc++.h>
using namespace std;
int T,n,x;
const int N=1e2+5;
int a[N];
int main(){
cin>>T;
while(T--){
cin>>n>>x; int ans=0,flag=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),ans+=a[i];
if(ans==x){puts("NO"); continue;}
puts("YES"); ans=0;
for(int i=1;i<=n;i++){
ans+=a[i];
if(ans==x){
swap(a[i],a[i+1]);
printf("%d %d ",a[i],a[i+1]); ans+=a[i];
i++; continue;
}
printf("%d ",a[i]);
}
puts("");
}
// system("pause");
return 0;
}
B:CF1515B Phoenix and Puzzle
考虑一下怎么可以构成一个正方形：当两个或者四个相同等腰直角三角形可以组成。
而且这两种组合方法不能同时用。
因此必须 \(\frac{n}{2}\) 或 \(\frac{n}{4}\) 是完全平方数才行。
判断一下即可。
#include<bits/stdc++.h>
using namespace std;
int T,n;
bool check(int x){
if(sqrt(x)*sqrt(x)==x) return 1;
return 0;
}
int main(){
cin>>T;
while(T--){
cin>>n;
if(check(n/2)||check(n/4)) puts("YES");
else puts("NO");
}
return 0;
}
C:CF1515C Phoenix and Towers
贪心问题，我们遍历 \(n\) 个数字, 每次把当前这个数字放到总和最小的组里即可.
因为我们最后要求任意两组之前的差值尽可能的小, 相当于让 \(m\) 组数尽可能的平均. 我们贪心去做即可(从大到小一个一个放).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N=1e5+10;
int res[N],n,m,k,T;
int main()
{
cin>>T;
while(T--){
priority_queue<PII, vector<PII>, greater<>>q;//放里面西巴
scanf("%d %d %d", &n, &m, &k);
for(int i=1;i<=m;i++) q.push({0,i}); //第二维是组数的下标
for(int i=1,x;i<=n;i++){
scanf("%d", &x);
auto op=q.top(); q.pop();
op.first+=x; res[i]=op.second;
q.push(op);
}
puts("YES");
for(int i=1;i<=n;i++) printf("%d ",res[i]); puts("");
}
// system("pause");
return 0;
}
D:CF1515D Phoenix and Socks
依然是贪心。
对于所有能匹配的情况，我们肯定能匹配就匹配。(大废话)
设对于左右不同颜色的直接匹配为硬匹配，花费 \(2\) 元。
不花钱的处理完了之后，若存在 \(L != R\) 的情况，此时不能直接硬匹配。
如果 \(L\) 多，就在 \([1,L]\) 中找找，能不能改方向，不改颜色匹配。
因为此时硬匹配不但要改颜色而且要改方向，不如先在L中看看能不能同方向匹配，能的话绝对是赚的，每匹配一对，最终少改一次颜色.
最后剩下的只能硬匹配了
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,T,l,r,a[N],col[N],cor[N];
int main(){
cin>>T;
while(T--){
int finish=0,ans=0;
cin>>n>>l>>r;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
if(i<=l) col[a[i]]++;
else cor[a[i]]++;
}
int nl=l,nr=r;
for(int i=1;i<=l;++i){//处理左右匹配
if(col[a[i]]&&cor[a[i]]){
col[a[i]]--; cor[a[i]]--;
nl--; nr--;
}
}
if(nl>=nr){
for(int i=1;i<=l;++i)//处理左匹配
if(col[a[i]]>=2&&nl>nr){
col[a[i]]-=2;
nl-=2; ans++;
}
ans+=(nl-nr)/2+(nl+nr)/2;
}
else {//处理右匹配
for(int i=l+1;i<=n;++i)
if(cor[a[i]]>=2&&nr>nl){
cor[a[i]]-=2;
nr-=2; ans++;
}
ans+=(nr-nl)/2+(nr+nl)/2;
}
cout<<ans<<endl ;
for(int i=1;i<=n;++i) col[i]=cor[i]=0;
}
return 0;
}