Codeforces Round #262 (Div. 2)-A,B,C,D_html/css_WEB-ITnose

A. Vasya and Socks

No need to say more about the water question, just violent enumeration and that's it.

#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 and Equation

Needless to say, it’s a simple question, just enumerate s(x) directly, and then get x, Then it is appropriate to deduce s(x) based on x.

I wrote 81 as 72, and I couldn’t help but feel very sad, sad.

#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. Present

Two points for greed. It is also a form of expression of water problems. . . .

Divide the result into two and be greedy to see if the current result can be achieved.

#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

It was so tragic when I wrote this question that it turned out to be the last time I thought I could be wrong. The place is written wrong.

I am very sad.

n=r-l 1;

If n<=20, it is obvious that state compression is OK.

If k<=3.

When k=1, it is obvious to take l.

When k=2, it is obvious that taking two adjacent numbers with only the last bit different, their XOR result is 1.

When k=3, the Take l for a number, and then if the result is 0, calculate the minimum value of the remaining two numbers. If the largest of the two numbers

is not greater than r, then we take these three numbers, otherwise we take two numbers so that the result is 1.

When k>=4:

For the alternation of the following two numbers:

..........0111110                     k-2

.....0111111            -1

.....1000000 k

.....1000001 k 1

Obviously we can see The XOR value of k-2,k-1,k,k 1 is 0.

Because n>20, we can definitely find this kind of k.

#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 220000void dos1(LL l,LL r,LL k){    LL n=r-l+1;    LL st=((LL)1)<<n;    LL ans=0;    LL res=r+100;    LL rst=0;    LL len=0;    for(LL i=1; i<st; i++)    {        ans=0;        len=0;        for(LL j=0; j<n; j++)        {            if(i&(((LL)1)<<j))            {                ans=ans^(j+l);                len++;            }        }        if(len>k)continue;        if(res>ans)        {            res=ans;            rst=i;        }    }    len=0;    for(LL i=0; i<n; i++)    {        if(rst&(((LL)1)<<i))len++;    }    cout<<res<<endl;    cout<<len<<endl;    for(LL i=0; i<n; i++)    {        if(rst&(((LL)1)<<i))        {            len--;            cout<<(i+l);            if(len)cout<<" ";            else cout<<endl;        }    }}LL dos2(LL l,LL r,LL ks){    for(LL i=50; i>=0; i--)    {        if((l&(((LL)1)<<i))!=((r&(((LL)1)<<i))))        {            LL k=((LL)1)<<i;            LL n=(l>>i);            n=(n<<i);            n=n+k;            k=n;            if(k-2>=l&&k+1<=r)            {                return k;            }            else if(k-2<l)return dos2(k,r,ks);            else if(k+1>r)return dos2(l,k-1,ks);        }    }    return 0;}void dos3(LL l,LL r,LL k){    if(k==1)    {        cout<<l<<endl;        cout<<"1"<<endl;        cout<<l<<endl;        return;    }    if(k==2)    {        cout<<"1"<<endl;        cout<<"2"<<endl;        if(l&1)l++;        cout<<l<<" "<<l+1<<endl;        return;    }    LL len=0;    LL n=l;    while(n)    {        len++;        n=n/2;    }    LL a,b;    a=b=0;    int leap=0;    a=b=(((LL)1)<<len);    for(LL i=len; i>=0; i--)    {        if(l&(((LL)1)<<i))        {            if(!leap)b+=(((LL)1)<<i);            else a+=(((LL)1)<<i);            leap++;        }    }    if(b<=r)    {        cout<<"0"<<endl;        cout<<"3"<<endl;        cout<<l<<" "<<a<<" "<<b<<endl;    }    else    {        cout<<"1"<<endl;        cout<<"2"<<endl;        if(l&1)l++;        cout<<l<<" "<<l+1<<endl;    }}int main(){    LL l,r,k;    while(~scanf("%I64d%I64d%I64d",&l,&r,&k))    {        LL n=r-l+1;        if(n<=20)        {            dos1(l,r,k);            continue;        }        if(k<=3)        {            dos3(l,r,k);            continue;        }        LL ans=dos2(l,r,k);        cout<<"0"<<endl;        cout<<"4"<<endl;        for(LL i=ans-2; i<=ans+1; i++)        {            cout<<i;            if(i!=ans+1)cout<<" ";            else cout<<endl;        }    }    return 0;}