Codeforces Round #641 (Div. 2)

ここはBCDの問題を補って、今度はやはりあまりに野菜で、ただaは2題だけあって、Dはまた間違っていて、cは少しもできません
トランスファゲート
B題

B題wa三発は惨めで、この時間は比較的ゆとりがあるので、いろいろな方法があって、最終的には基本的にDP

です.

本来考えていたのは、それぞれの数を分解して彼の因子を求め、因子を操作する

である.

または直接DPは、現在の数値の倍数を直接操作する

である.

ここでピットを比較したのはdist[i]=1で,もともと1にのみ初期値を付与していたが,

の様子を思い浮かべた.

a[1]=10,a[2]=1,a[3]=2,a[4]=3,ここでは出力2,2,4が該当するが,いずれも初期値1を付与しなければ出力は1のみであるため,この場所はピットである,

に注意が必要である.
コード:

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 100010;

int a[N], dist[N];



int main(){
    
    int t;
    scanf("%d",&t);
    while(t--){

        memset(dist,0,sizeof dist);
        int n;
        scanf("%d",&n);

        for (int i = 1; i <= n; i++){
            scanf("%d",&a[i]);
            dist[i] = 1;
        }

        for (int i = 1; i <= n; i++){ //     
            int x = i;
            for (int j = 1; x * j <= n; j ++){
                if (a[j * i] > a[i]) dist[i*j] = max(dist[i*j] ,dist[i] + 1);
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i++){
            res = max(res,dist[i]);
        }
        printf("%d
",res);
    }
}

C問題の解題構想:

C問題は少し複雑で、自分で長い間考えてやっと1つの複雑なやり方を理解して、あのlcmはまたgcdの読めないで、まだ

を理解していません

まず質因子分解の構想

について述べる.

まず我々が得た数は他質因子をres=p 1^k 1*p 2^k 2...

に分解する

次にp 1^k 1を例に挙げ、以下をp^k

に簡略化する.

p^kに対して、p^kは彼らのgcdから得たので、彼らが共有している

です.

そのため、私たちは彼らの数ごとに質量因子を分解し、vectorに

保存します.

それから私たちは1~200000から、この範囲(入力データ範囲が1~200000のため)、私たちは順番に彼が値があるかどうかを判断します>=n-1

はなぜn−1なのか.n−1の数以上の質量因子が存在する限り、lcmの最後のgcdは現在の値

に存在することができるからである.

数がnであれば、私は2番目に小さい位置を選んだ.2,4,8彼らのlcmのgcdは4に違いない.彼らは最も少ない2つの指数に拘束されているからだ.これは自分で

を理解している.
次に、

の数がn-1である場合、最小値をとることができる.これは、1ビットが欠けているため、最小値の影響を受ける

である.

そして彼らが乗算すれば

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;

vector<long long> ans[N];

ll mod_mult(ll a,ll b){  //   a*b
    ll res = 0;
    ll exp = a;
    while(b){
        if (b&1){
            res += exp;
            
        }
        exp<<=1;
        
        b>>=1;
    }
    return res;
}


ll mod_exp(ll a,ll b){
    ll res = 1;
    ll exp = a ;
    while(b){
        if (b & 1) res = mod_mult(res,exp);
        exp = mod_mult(exp,exp);
        b>>=1;
    }
    return res;
}

ll pow_(ll a, ll b){
    for (int i = 1; i<= b; i++){
        a = a * a;
    }
    return a;
}
int main(){
    int n;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++){
        int x;
        scanf("%d",&x);
        for (int j = 2; j * j <= x; j ++){
            if (x % j == 0){
                int cnt = 0;
                while(x % j == 0){
                    cnt++;
                    x /= j;
                }
                ans[j].push_back(cnt);
            }
            
        }
        if (x != 1) ans[x].push_back(1);
    }


    ll res = 1;
    for (long long i = 1; i <= 200000; i++){
        if (ans[i].size() >= n - 1){
            sort(ans[i].begin(),ans[i].end());
            if (ans[i].size() == n) res *= mod_exp(i,ans[i][1]);
            else res *= mod_exp(i,ans[i][0]);
        }
    }

    printf("%lld
",res);
    return 0;
}

D問題の解題構想:

D問題はC問題に比べて理解しやすいが、状況が少ないため、最初は

を誤って理解した.

ここでl-rの中位数を探すと、この中位数は値の中位数であり、下付きではない(問題を理解し間違えた)

である.

だからまずこの中にkがあるかどうかを判断して、もし存在するならば半分成功して、もし存在しないならば、もちろん“no”

です

次に、2つの条件が、2つの連続する>=kの値が存在するか否かを判断する.なぜなら、存在する場合、彼はすべての値を>=kに変更することができ、そして、もともとkが存在する場合、k

に変更することができるからである.

もう1つは、3つの連続する値のうち、2つの値>=kが存在するかどうかであり、3つの値のうち少なくとも2つの値>=kが存在するかどうか(これは最初の中位数の理解が間違っていた場所である)を探し、この2つの条件が結合すると「yes」になり、そうでなければ「no」になる.

コード:

#include 
#include 
#include 

using namespace std;

const int N = 100010;

int a[N];

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n, k;
        scanf("%d%d",&n,&k);
        int f = 0;
        for (int i = 1; i <= n; i++){
            scanf("%d",&a[i]);
            if (a[i] == k) f = 1;
        }
        if (n == 1){
            if (a[1] == k) puts("yes");
            else puts("no");
            continue;
        }
        int ff = 0;
        for (int i = 1; i <= n; i++){
            if (a[i] >= k){
                if (i != n){
                    if (a[i + 1] >= k) ff = 1;
                }
                if (i < n - 1){
                    if (a[i + 2] >= k) ff = 1;  
                }
            }
        }
        if (f && ff){
            puts("yes");
        }
        else{
            puts("no");
        }
    }
    return 0;
}