A. Nezzar and Colorful Balls

题意:

给你一个非递减的序列,求最少可以组成多少个严格上升子序列

思路:

严格上升子序列的数量显然由所给序列中出现次数最多的数字决定,出现的次数即为答案

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
#include<map>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, a[N];
map<int,int>mp;
void solve(){
    mp.clear();
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i], mp[a[i]]++;
    int mx=0;
    for(auto x:mp) mx=mymax(mx,x.second);
    cout<<mx<<endl;
    return ;
}
signed main(){
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

B. Nezzar and Lucky Number

题意:

Nezzar在1,…,9最喜欢的数字是d。 如果d在其十进制表示形式中至少出现一次,他会称其为幸运数字。
给定q整数a1,a2,…,aq对于每个1≤i≤q,Nezzar想知道ai是否可以等于多个(一个或多个)幸运数字的总和 。

思路:

对于大于10d的数字,很明显可以拆分成两个幸运数字相加,而对于小于10d的数字,可以拆分成n10+md(n和m为待定系数)

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, d;
void solve(){
    cin>>n>>d;
    int x;
    for(int i=1; i<=n; i++){
        cin>>x;
        int flag=0;
        if(x>=10*d) {cout<<"YES"<<endl; continue;}
        for(int j=1; j<=9; j++){
            if((j*d)%10==x%10){
                if(j*d==x || x-j*d>=10) cout<<"YES"<<endl;
                else    cout<<"NO"<<endl;
                flag=1;
                break;
            }
        }
        if(!flag) cout<<"NO"<<endl;
    }
    return ;
}
signed main(){
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

C. Nezzar and Symmetric Array

题意:

很久以前有一个长度为2*n序列a,其中每个数都有其相反数,后求得每个数与其他数的差值的绝对值之和的序列d,让你根据序列d求是否可能求得相应的序列a

思路:

首先需要知道一个性质:
一个数字与一对互为相反数的数字的距离为绝对值最大的两倍
例如:-3 -2 -1 0 1 2 3
-3到±2的距离为6,为3的两倍
-2到±3的距离为6,为3的两倍...

所以很显然,序列d中最大的值为n个序列a中最大值两倍
也就是说amax=(dmax/2)/n
同理下一个数为次大值除以2减去最大值除以n-1,以此类推
对于每个求出来的a,判断是否为正整数即可
对于输入的序列d,需要判断值是否全为偶数并且成对出现

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
#include<map>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n;
ll d[N];
map<ll,int>mp;
void solve(){
    mp.clear();
    cin>>n;
    int flag=1;
    for(int i=1; i<=2*n; i++){
        cin>>d[i];
        if(d[i]&1) flag=0;
        mp[d[i]]++;
    }
    if(!flag) {cout<<"NO"<<endl; return ;}
    for(auto x:mp) if(x.second!=2) {cout<<"NO"<<endl; return ;}
    sort(d+1,d+1+2*n);
    ll mx=0;
    for(int i=2*n; i>=2; i-=2){
        if(d[i]/2 -mx<=0 || (d[i]/2 -mx)*2%i!=0)
            {cout<<"NO"<<endl; return ;}
        mx+=(d[i]/2-mx)*2/i;
    }
    cout<<"YES"<<endl;
    return ;
}
signed main(){
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}



平平无奇的大学在读本科生