Codeforces Global Round 14
比赛link-》戳我看题
A. Phoenix and Gold
题意解读
题目连接：https://codeforces.com/contest/1515/problem/A
题目的大概意思就是说给你n个不重复数字，然后给你一个k，让你求是否存在一个排列，使得这个排列的前缀和中不出现k
当时自己竟然没做出来，我当时在想先从最小开始输出还是从最大开始输出，然后交了两发wa了之后我还试了一下随机打乱数组，后来自己的思路就困在了如果遇到前缀和为k的数，先保留，所有数字输出完，在输出这个数，但不知道交上去还是不对。
比赛结束看了题解才知道，直接按照原来的祖烈输出就行了，只要遇到前缀和为k的数字，就交换这个数字和下一个，另外需要注意的就是，只要这n个数字的综合不是k，总有办法避开k的。
代码展示
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
ll sum = 0;
cin>>n>>k;
int a[n+2];
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum += a[i];
}
if(sum == k)
cout<<"NO\n";
else
{
cout<<"YES\n";
for(int i=1;i<=n;i++)
{
if(a[i] == k)
{
swap(a[i],a[i+1]);
}
if(i==1)
{
cout<<a[i];
}
else
{
cout<<" "<<a[i];
}
k -= a[i];
}
cout<<endl;
}
}
return 0;
}
B. Phoenix and Puzzle
题目连接：https://codeforces.com/contest/1515/problem/B
题意理解
题意就是说给你一个边长为等边直角三角形，问n块是否可以组成一个正方形。
由正三角形组成正方形只有两种方法，要么拿直角放中间，要么把直角放在正方形的顶点，内部还可以嵌套一个旋转45度的正方形，把这两种情况画一下，列出来所需要的三角形个数，要么2powr(i,2) == n 要么 4powr(i,2) == n，另外，不需要暴力的从1到n判断，只需要到根号n就可以了。
代码展示
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<cstring>
#include<map>
#include<string>
typedef long long ll;
using namespace std;
const ll maxn = 1e9;
ll powr(int a,int n) {//快速幂
int ans = 1;
while(n) {
if(n&1) {
ans *= a;
} else
a *= a;
n>>=1;
}
return ans;
}
int main() {
int t;
cin>>t;
while(t--) {
ll n;
cin>>n;
int flag1 = 1;
for(int i=1; powr(i,2)<= n; i++) {//只有这两种情况
if(2*powr(i,2) == n || 4*powr(i,2) == n) {
flag1 = 0;//出现一种情况就行
}
}
if(flag1)
cout<<"NO\n";
else
cout<<"YES\n";
}
return 0;
}
C. Phoenix and Towers（贪心）
题意解读
题目连接：https://codeforces.com/contest/1515/problem/C
给n个大于等于1且小于等于x的高度值，将它们分配给m个位置，每个位置的高度为分配的数值之和，要使得m个位置两两之间高度差不超过x。
我没做出来，网上看人家的博客。
解题思路：边输入边输出，每次拿出当前高度最低的位置，然后把当前得到的高度值加在上面。
证明正确性：
每次增加最低位置的高度后，整体状态都符合条件。
假设当前这m个位置符合条件，则最高位置的高度减去最低位置的高度不大于x，当前最低位置和其他任意位置的高度差都大于等于0。
然后给最低位置加上一个大于等于1且小于等于x的高度值，那么有两种情况，一是原来最低位置成了新的最高位置，第二低的位置成了最低位置，显然两者差值不大于x，二是原来最低位置的新值不超过原来最高位置，但是新的最低位置的高度并不小于原来最低位置的高度。两种情况都符合条件。
代码展示
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
int t,n,m,x,h[N],y[N];
struct node{//定义结构体来存储每一个Tower的位置和当前高度
int h,id;
node(int _h = 0,int _id = 0):h(_h),id(_id){}//初始化函数，记住就行了
}p[N];
bool operator > (const node & a,const node & b)//重载>运算符，因为下边用到了优先队列
{
return a.h > b.h;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m>>x;
cout<<"YES\n";
priority_queue<node,vector<node>,greater<node> >pq;//这里按照高度由小到大排，如果默认less就重载小于号，如果默认greater就重载大于号
for(int i=1;i<=m;i++)
pq.push(node(0,i));//初始化所有的Tower的高度是0；
for(int i=1;i<=n;i++)
{
cin>>p[i].h;
node tmp = pq.top();//取出高度最低的tower
pq.pop();
printf("%d%c",tmp.id,i==n? '\n' : ' ');//放在最低的那个Tower上
pq.push(node(tmp.h + p[i].h,tmp.id));//放好后在放回优先队列，他会自动排序的
}
}
return 0;
}
D. Phoenix and Socks
https://codeforces.com/contest/1515/problem/D
题意解读
有n（偶数）只袜子，前l只是左脚的，后r只为右脚的，每个袜子都有一个颜色，需要把所有的袜子成对（每个袜子必须有一个左脚和一个右脚相对应，且颜色相同）
可以通过一些操作来实现，每个操作需要1元
1.给一个袜子换一个颜色
2.给一个左脚的袜子变为右脚的
3.给一个右脚的袜子变为左脚的
求最小代价
题目类型：贪心
解析：
贪心思想，首先，能不花钱就不花钱，看看能不能左右匹配。
设对于左右不同颜色的直接匹配为硬匹配，花费2元。不花钱的处理完了之后，若存在L != R的情况，此时不能直接硬匹配。如果L多，就在1~L中找找，能不能改方向，不改颜色匹配。因为此时硬匹配不但要改颜色而且要改方向，不如先在L中看看能不能同方向匹配，能的话绝对是赚的，每匹配一对，最终少改一次颜色。
最后硬匹配即可。
自己还是写不出来，只会参考别人的代码，然后对照理解（55555~）
代码解析
//这不是我的代码，照着别的博主看的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 202020;
int n,t,l,r,a[N],col[N],cor[N];
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
int finish = 0 , ans = 0;
cin >> n >> l >> r ;
for(int i = 1 ; i <= n ; ++i){
cin >> 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;
}