コードフォース #275 div2_html/css_WEB-ITnose

リンク: codeforce #275 div2

A.反例

質問: 左右の区間 [l, r] が与えられた場合、a と b が互いに素であるような区間内の 3 つの数値 a、b、c を見つけます。

b c と互いに素ですが、a と c が互いに素でない場合は、-1 を出力します

分析: 連続する偶奇数列を見つけるだけです

#include<stdio.h>int main(){    __int64 l,r;    scanf("%I64d%I64d",&l,&r);    if(l%2)        l++;    if(r-l<2)        printf("-1\n");    else    printf("%I64d %I64d %I64d",l,l+1,l+2);    return 0;}

B。友達とプレゼント

ヒント: 2 つのシーケンスを作成します。最初のシーケンスには cnt1 の数値が必要であり、x の倍数があってはなりません。

2 番目のシーケンスには cnt2 の数値が必要で、y の倍数があってはなりません。 2 つのシーケンスが同じ数値を持つことはできません。

では、2 つのシーケンス内の最大数値の最小値を見つける必要があります。

分析: m=num - num / x、x の倍数を含まない 1 から num までの数値の数

n=num - num / y、x の倍数を含まない 1 から num までの数値の数x の倍数を含む

num/(x*y) は、x の倍数でもあり y の倍数でもある数値です

つまり、m>=cnt1 および n>=cnt2

2 つのシーケンスが同じものを持つことはできないため数値なので、cnt1 + cnt2

次に、num の最小値を二分探索します

#include<stdio.h>int main(){    __int64 x,y,cnt1,cnt2,m,n;    __int64 l,r,mid;    scanf("%I64d%I64d%I64d%I64d",&cnt1,&cnt2,&x,&y);    l=1;    r=1e12;    while(l<r){        mid=(l+r)/2;        m=mid-mid/x;        n=mid-mid/y;        if(m>=cnt1&&n>=cnt2&&mid-mid/(x*y)>=cnt1+cnt2)            r=mid;        else            l=mid+1;    }    printf("%I64d\n",r);    return 0;}

C.Diverse Permutation

質問: を含む n を見つけます1-n 一連の数値の場合、隣接する 2 つの要素間の差の絶対値の異なる数が k である必要があります

分析: n 個の数値には n-1 個の違いがあり、次のことを確認する必要があります。 k 個の差の絶対値は異なります。

次に、同じ差を持つ n-k-1 個の差が存在します。まず、[1, n-k] の間の n-k 個の数値を順番に出力できます。

次に、最小値と最大値を出力します。

#include<stdio.h>int main(){    int n,k,i,j,num;    scanf("%d%d",&n,&k);    num=n-k-1;    for(i=1;i<=num;i++)        printf("%d ",i);    j=n;    while(num<n){        printf("%d",i++);        if(num!=n)            printf(" ");        num++;        if(num==n)            break;        printf("%d",j--);        if(num!=n)            printf(" ");        num++;    }    return 0;}