Codeforces Global Round 14

入口

思路
题目保证所有数字都不相同，只需要从小到大填数，若正好等于x，记录当前数并填下一个数即可

代码

#include
using namespace std;
const int N=105;
int a[N];
int t,n,x;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>x;
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum+=a[i];
        }
        sort(a+1,a+n+1);
        if(sum==x)
        {
            cout<<"NO"<x||sum=1;i--) cout< 
B. Phoenix and Puzzle 
入口
 
思路
 我们发现一个正方形必能拆成两个大三角形，因此只要能构成三角形，则它的2的幂次倍一定可以构成正方形，1,1+3,1+3+5……可构成三角形，预处理这些三角形数后递归查询即可。
 
代码
 
#include
#define int long long

using namespace std;

const int N=1e6+5;
int sum[N],cnt=0;
bool vis[N];

void init()
{
    for(int i=1;i<=N;i++)
    {
        cnt++;
        sum[i]=sum[i-1]+i*2-1;
        if(sum[i]>1e9) break;
    }
    cnt--;
}
bool flag=false;
void dfs(int x)
{
    if(flag) return ;
    if(sum[lower_bound(sum+1,sum+cnt+1,x)-sum]==x)
    {
        flag=true;
        return ;
    }
    if(x%2==1) return ;
    dfs(x/2);
}
signed main()
{
    int t;
    cin>>t;
    init();
    while(t--)
    {
        int n;
        cin>>n;
        flag=false;
        if(n%2)
        {
            cout<<"NO"< 
C. Phoenix and Towers 
入口
 
思路
 贪心，每次将输入的数加到高度最低的那里，可以保证相差最小
 
代码
 
#include

using namespace std;

typedef pair PII;

priority_queue,greater > heap;
int n,m,x;
int t;
vector res;

int main()
{
    cin>>t;
    while(t--)
    {
        while(heap.size()) heap.pop();
        res.clear();
        cin>>n>>m>>x;
        for(int i=1;i<=m;i++) heap.push({0,i});
        for(int i=1;i<=n;i++)
        {
            int k;
            cin>>k;
            auto tmp=heap.top();
            heap.pop();
            res.push_back(tmp.second);
            tmp.first+=k;
            heap.push(tmp);
        }
        int last=0;
        bool flag=true;
        while(heap.size())
        {
            auto tmp=heap.top();
            heap.pop();
            if(last==0)
            {
                last=tmp.first;
                continue;
            }
            //cout<x)
            {
                flag=false;
                break;
            }
        }
        if(!flag) cout<<"NO"< 
D. Phoenix and Socks 
入口
 
思路
 先将所有能匹配的袜子删去，再将左右重复的袜子删去，最后左右两边的袜子都不能匹配且不重复，假设左有k1，右有k2，最后结果再加上（k1+k2)/2+abs(k1-k2)/2即可
 
代码
 
#include
using namespace std;
const int N=2e5+5;

int n,l,r;
int a[N][2];
int t;
int main()
{
    cin>>t;
    while(t--)
    {
        memset(a,0,sizeof(a));
        cin>>n>>l>>r;
        int k;
        for(int i=1;i<=l;i++)
        {
            cin>>k;
            a[k][0]++;
        }
        for(int i=1;i<=r;i++)
        {
            cin>>k;
            a[k][1]++;
        }
        for(int i=1;i<=n;i++)
        {
            if(a[i][0]&&a[i][1])
            {
                int minx=min(a[i][0],a[i][1]);
                a[i][0]-=minx;
                a[i][1]-=minx;
            }
        }
        int tmp=l-r;
        int res=0;
        for(int i=1;i<=n;i++)
        {
            while(a[i][0]>1&&tmp>0)
            {
                tmp-=2;
                a[i][0]-=2;
                res++;
            }
            while(a[i][1]>1&&tmp<0)
            {
                tmp+=2;
                a[i][1]-=2;
                res++;
            }
        }
        int res1=0,res2=0;
        for(int i=1;i<=n;i++)
        {
            res1+=a[i][0];
            res2+=a[i][1];
        }
        res+=abs(res1-res2)/2+(res1+res2)/2;
        cout<