Codeforces Round #698 (Div. 2)

Aは1つの減少しない配列を与えて、少なくともいくつかの色で染色することを聞いて、各色の中の数を厳格に増加させて明らかに同じ数でなければ、同じ色で染色することができて、そのため最も多く現れる数を記録します

#include 
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll read(){
     ll f=1;ll x=0;char ch=getchar();while(ch>'9'||ch<'0'){
     if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f; }
inline ll quick_pow(ll a,ll b,ll mod) {
     ll ans=1,base=a;while(b){
     if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){
     return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){
     return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){
     return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 998244353;
const ll maxn = 110;
void solve()
{
     
    int a[maxn];
    int n;
    cin >> n;
    int maxx = 0;
    map<int,int> m;
    rep(i,1,n)
    {
     
        scanf("%d", &a[i]);
        m[a[i]]++;
        maxx = max(maxx, m[a[i]]);
    }
    cout << maxx << '
';
    return;
}
int main()
{
     
    int T;
    cin>>T;
    while(T--)
    {
     
        solve();
    }
    return 0;
}

B qは、1つの要素が複数の10進数のdの数の和から構成できるかどうかを尋ねる.1つの数が10 d以上である場合には必ず解があり、任意の数は(d 10+x)+ndからなり、例えばd=7の場合、明らかに70−77が合法である.77に達したとき、70+7に変化することができ、このとき明らかに(70,70+7)+7、すなわち77-84が合法であり、このように推定される.10 d未満の場合、dは減少し続ける.ビット数を0にすることができれば、任意の数に残りの得数を加えることができるので、合法的である.例えば、d=7、num=58である.numがdを4回減らすと,7+7+7+7+30となり,明らかに7+30=37が合法であれば7+7+7+37となる.

#include 
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll read(){
     ll f=1;ll x=0;char ch=getchar();while(ch>'9'||ch<'0'){
     if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f; }
inline ll quick_pow(ll a,ll b,ll mod) {
     ll ans=1,base=a;while(b){
     if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){
     return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){
     return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){
     return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 998244353;
const ll maxn = 1e4+10;

void solve()
{
     
    int q,d;
    cin >> q >> d;
    while(q--)
    {
     
        int tmp;
        cin >> tmp;
        bool flag = false;
        if(tmp >= 10 * d)
            puts("YES");
        else
        {
     
            while(tmp > 0)
            {
     
                if(tmp % 10 == d)
                {
     
                    puts("YES");
                    flag = true;
                    break;
                }
                tmp -= d;
            }
            if(!flag)
                puts("NO");
        }
    }
    return;
}
int main()
{
     
    int T;
    cin>>T;
    while(T--)
    {
     
        solve();
    }
    return 0;
}

Cは配列aからn対の逆数を与え,di=Σ2 nj=|ai−aj|に変化した配列dを与える.d配列から一意のa配列を反転させることができるかどうかを尋ねると、a=−1,1,−3,3 d=8,8,12,12から最初の数1を見ることができる.自身の反対の数は彼に1つの貢献を生むことができて、すなわち2 a 1、第2の数とその反対の数もそれに対して貢献を生むことができます|a 1-a 2|+|a 1-(-a 2)|a 2がa 1より大きいと仮定してもよくて、それでは結果はa 2-a 1+a 2+a 1=2 a 2です.従って、異なる数ajの自己aiへの寄与は2 max(ai,aj)に等しい.したがって,配列を並べ替えて逆数を除いた場合,最大の数の寄与は配列長(nと仮定)にこの数を乗じて2を乗じ,次の大きい数の寄与は(n−1)に次の大きい値を乗じて2を乗じ,最大値を加えて2を乗じたものである.

#include 
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll read(){
     ll f=1;ll x=0;char ch=getchar();while(ch>'9'||ch<'0'){
     if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f; }
inline ll quick_pow(ll a,ll b,ll mod) {
     ll ans=1,base=a;while(b){
     if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){
     return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){
     return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){
     return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 998244353;
const ll maxn = 1e5+10;
ll a[maxn], d[maxn];
void solve()
{
     
    int n;
    cin >> n;
    rep(i, 1, 2*n)
        scanf("%lld", &d[i]);
    sort(d + 1, d + 1 + 2 * n);
    int tot=unique(d+1,d+1+2*n)-d-1;
	if(tot != n) {
     
        puts("NO");
        return;
    }
    ll suf = 0;
    bool flag = true;
    /*for (int i = 1;i <= n;i++)
        {
            cout << d[i] << " ";
        }
    cout << '
';*/
    per(i,n,1)
    {
     
        if((d[i] - suf) % (2*i) ||d[i] <= suf )
        {
     
            flag = false;
            break;
        }
        a[i] = (d[i] - suf) / (2 * i);
        suf += 2 * a[i];
    }
    if(flag)puts("YES");
    else
        puts("NO");
    /*for (int i = 1;i <= n;i++)
        cout << a[i] << " ";
    cout << '
';*/
    return;
}
int main()
{
     
    int T;
    cin>>T;
    while(T--)
    {
     
        solve();
    }
    return 0;
}

Dは2つの数を選んで、1つの2*x-yの数を生んで、1つのkがx+x-yを生んで2つの数を考慮することに相当するかどうかを聞いて、2つの数の差値はきっと2つの数の最大の公因数の倍数であるため、2つの数が転がって減算して彼らの最大の公因数を得ることができます.複数の数は複数の数の最大公因数であり、最小単位はこのn個の数差の最大公因数である.本題には負数が存在するので,いずれかの数を任意に探して検証すればよい.

#include 
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll quick_pow(ll a,ll b,ll mod) {
     ll ans=1,base=a;while(b){
     if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){
     return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){
     return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){
     return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 998244353;
const ll maxn = 1e5 + 10;
void solve()
{
     
    ll n, k;
    cin >> n >> k;
    ll a[n + 2];
    rep(i, 1, n)
    {
     
        cin >> a[i];
    }
    ll factor = a[2]-a[1];
    rep(i,3,n)
    {
     
        factor = __gcd(factor, a[i] - a[i - 1]);
    }
    if((k-a[1])%factor == 0)
        puts("YES");
    else
        puts("NO");
    return;
}
int main()
{
     
    int T;
    cin>>T;
    while(T--)
    {
     
        solve();
    }
    return 0;
}

後続候補