Codeforces ラウンド #262 (ディビジョン 2)-A、B、C、D_html/css_WEB-ITnose

A. Vasya と靴下

水の問題についてはこれ以上言う必要はありません。ただ乱暴に列挙して終わりです。

#include <iostream>#include<stdio.h>#include<stdlib.h>#include<time.h>#include<vector>#include<algorithm>#include<string.h>using namespace std;#define LL __int64int main(){    int n,k;    while(~scanf("%d%d",&n,&k))    {        int m=n;        int ans=n;        int yu=0;        while(m)        {            m=m+yu;            yu=m%k;            m=m/k;            ans+=m;        }        cout<<ans<<endl;    }    return 0;}

B. Little Dima と方程式

言うまでもなく、これは水の問題です。s(x) を直接列挙し、x を取得し、x に基づいて s(x) を推定するのは適切ですか。

81を72と書いたとき、とても悲しくて悲しくて仕方がありませんでした

#include <iostream>#include<stdio.h>#include<stdlib.h>#include<time.h>#include<vector>#include<algorithm>#include<string.h>using namespace std;#define LL __int64#define INF 1000000000vector<int>vec;LL pows(LL x,LL y){    LL ans=1;    while(y--)ans=ans*x;    return ans;}int dus(LL x){    int ans=0;    while(x)    {        ans=ans+x%10;        x=x/10;    }    return ans;}int main(){    int n,k;    int a,b,c;    while(~scanf("%d%d%d",&a,&b,&c))    {        LL ans=0;        vec.clear();        for(int i=1;i<=81;i++)        {            ans=(LL)b;            ans=ans*pows(i,a);            ans=ans+(LL)c;            if(ans>=INF)break;            if(ans<=0)continue;            if(dus(ans)==i)vec.push_back(ans);        }        cout<<vec.size()<<endl;        sort(vec.begin(),vec.end());        for(int i=0;i<vec.size();i++)        {            printf("%d",vec[i]);            if(i!=vec.size()-1)printf(" ");            else puts("");        }    }    return 0;}

C.プレゼント

2点+欲張り。それは水問題の表現形式でもあります。 。 。 。

結果を2つに分けて、今の結果が達成できるか貪欲に見てみましょう。

#include <iostream>#include<stdio.h>#include<stdlib.h>#include<time.h>#include<vector>#include<algorithm>#include<string.h>using namespace std;#define LL __int64#define INF 1000000000#define maxn 220000LL a[maxn];LL b[maxn];LL flag[maxn];LL n,w;LL qiu(LL x){    memset(flag,0,sizeof(flag));    for(LL i=1;i<=n;i++)    {        b[i]=x-a[i];    }    LL ch=0;    LL ans=0;    for(LL i=1;i<=n;i++)    {        ch-=flag[i];        b[i]-=ch;        if(b[i]<0)b[i]=0;        flag[i+w]+=b[i];        ch+=b[i];        ans+=b[i];    }    return ans;}int main(){    LL m;    while(~scanf("%I64d%I64d%I64d",&n,&m,&w))    {        for(LL i=1;i<=n;i++)scanf("%I64d",&a[i]);        LL l=0;        LL r=1e9;        r=r*2;        LL mid=(l+r)/2;        while(l<r)        {            if(qiu(mid)>m)r=mid;            else l=mid+1;            mid=(l+r)/2;        }        mid--;        cout<<mid<<endl;    }    return 0;}

D. Little Victor and Set

この質問を書いたときはとても悲劇的でしたが、最も間違っている可能性が低いと思われる場所で間違って書いてしまいました。

とても悲しいです。

n=r-l+1;

n<=20 であれば、状態圧縮がOKであることは明らかです。

If k<=3.

k=1 の場合、l を取るのは明らかです。

k=2 の場合、隣接する 2 つの数値が取られ、最後の桁のみが異なる場合、それらの XOR 結果は 1 になることは明らかです。

k=3 の場合、最初の数値は l として取られ、次の場合結果は 0 になり、残りの 2 つの数値の最小値が計算されます。 2 つの数値の最大の

が r より大きくない場合は、これら 3 つの数値を取得し、そうでない場合は、結果が 1 になるように 2 つの数値を取得します。

k>=4 の場合:

次の交互の場合2 つの数値:

....0111110

.... ......1000001 k+1

明らかに、k-2,k-1,k,k+1 の XOR 値であることがわかります。は0です。

n>20 なので、この種の k は確実に見つかります。 ❤️