Codeforces Round #262 (Div. 2)

A

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 100000
#define LL long long
#define INF 0xfffffff
const double eps = 1e-8;
const double pi = acos(-1.0);
const double inf = ~0u>>2;
int n,m;
int main()
{
    int n,m,i,j;
    cin>>n>>m;
    if(m>n)
    cout<<n<<endl;
    else
    {
        int o = 0;
        while(n)
        {
            n--;
            o++;
            if(o%m==0) n++;
        }
        cout<<o<<endl;
    }
    return 0;
}

B

枚举和值

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 100000
#define LL long long
#define INF 0xfffffff
#define M 1000000000
const double eps = 1e-8;
const double pi = acos(-1.0);
const double inf = ~0u>>2;
int o[N];
int judge(LL x)
{
    int ans = 0;
    while(x)
    {
        ans+=x%10;
        x/=10;
    }
    return ans;
}
int main()
{
    int a,b,c,i,j;
    cin>>a>>b>>c;
    int g = 0;
    for(i = 1; i <= 100 ; i++)
    {
        LL k = (LL)b*pow(i*1.0,a)+c;
        if(judge(k)==i&&k>0&&k<M)
        o[++g] = k;
    }
    cout<<g<<endl;
    if(g)
    {


    sort(o+1,o+g+1);
    for(i = 1; i < g ; i ++)
    cout<<o[i]<<" ";
    cout<<o[i]<<endl;
    }
    return 0;
}

C

二分高度，之后用高度减去原有高度，就可以知道每株花被浇了多少水，用线段树维护一下就可以得到最少浇水的次数。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 100010
#define LL long long
#define INF 0xfffffff
#define M 1000200000
const double eps = 1e-8;
const double pi = acos(-1.0);
const double inf = ~0u>>2;
int a[N],o[N];
LL s[N<<2];
int n,m,w;
void build(int l,int r,int w)
{
    s[w] = 0;
    if(l==r)
    {
        s[w] = o[l];
        return ;
    }
    int m = (l+r)>>1;
    build(l,m,w<<1);
    build(m+1,r,w<<1|1);
}
void down(int w,int m)
{
    if(s[w])
    {
        s[w<<1] += s[w];
        s[w<<1|1] += s[w];
        s[w] = 0;
    }
}
void update(int a,int b,int d,int l,int r,int w)
{
    if(a<=l&&b>=r)
    {
        s[w]+=d;
        return ;
    }
    down(w,r-l+1);
    int m = (l+r)>>1;
    if(a<=m) update(a,b,d,l,m,w<<1);
    if(b>m) update(a,b,d,m+1,r,w<<1|1);
}
LL query(int p,int l,int r,int w)
{
    if(l==r)
        return s[w];
    down(w,r-l+1);
    int m = (l+r)>>1;
    if(p<=m) return query(p,l,m,w<<1);
    else return query(p,m+1,r,w<<1|1);
}
int cal(int k)
{
    int i,j;
    for(i = 1; i <= n; i++)
        if(k>a[i]) o[i] = k-a[i];
        else o[i] = 0;
    build(1,n,1);
    LL num = 0;
    for(i = 1; i <= n; i++)
    {
        int pp = query(i,1,n,1);
        
       
        if(pp>0) {update(i,min(n,i+w-1),-pp,1,n,1);num+=pp;} if(num>m) return 0;
    }
    if(num<=m) return 1;
    return 0;
}
int main()
{
    int i,j;
    cin>>n>>m>>w;
    for(i = 1; i <= n; i++)
        scanf("%d",&a[i]);
    int low = 1,high = M,mid;
    int ans = 1;
    while(low<=high)
    {
        mid = (low+high)>>1;
        if(cal(mid)==0)
            high = mid-1;
        else
        {
            low = mid+1;
            ans = max(ans,mid);
        }
    }
    cout<<ans<<endl;
    return 0;
}

D

对于

k=1 ,ans = L。

连续偶奇异或是为1的 比如10 11    12 13等 ，而奇偶则是不一定的

k= 2, 如果l%2==0，ans = L^(L+1)=1 ,否则要根据R-L+1的取值决定

k= 4 ，如果L%2=0，ans = L^(L+1)^(L+2)^(L+3)  = 0，否则如果R-L+1>4 也是为偶奇偶奇=0的，若R-L+1=4 就可转化为3的时候做。

k=3 ，有可能为1也有可能为0 ，假设L-R范围内的三个数x,y,z异或为0，x,y,z不同，就设x>y>z，那么x,y已确定，那么就是尽可能让z大，

比如 

x  100110001111   那么y值的第一位一定为1，不然z就为1就不符合假设y>z了，因为y<x，所以之后遇到x为0的位，y，z也是为0的，一旦再遇到一位1，就可以把y置为0，z置为1，再之后z就可以一直为1，而y的变化可以依据x,z而定。

x  100110001111...1

y  100001110000...0

z  000111111111...1

这样z将获得<R的最大值，再与L相比较就可以知道结果了。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 100000
#define LL long long
#define INF 0xfffffff
const double eps = 1e-8;
const double pi = acos(-1.0);
const double inf = ~0u>>2;
LL a[10];
int di[50];
void judge(LL l,LL r)
{
    LL x = r;
    LL i;
    int g = 0;
    while(x)
    {
        di[g++] = x%2;
        x/=2;
    }
    LL y = 0;
    LL z = 0;
    int flag = 0;
    y+=((LL)1<<(g-1));
    for(i = g-2 ; i >= 0 ; i--)
    {
        if(di[i])
        {
            flag = 1;
            z += ((LL)1<<i);
        }
        else if(flag)
        {
            z+=((LL)1<<i);
            y+=((LL)1<<i);
        }
    }
    if(z>=l)
    {
        cout<<"0
";
        cout<<"3
";
        cout<<r<<" "<<y<<" "<<z<<endl;
    }
    else
    {
        cout<<"1
";
        cout<<"2
";
        if(l%2)
        cout<<l+1<<" "<<l+2<<endl;
        else
        cout<<l<<" "<<l+1<<endl;
    }
}
int main()
{
    LL l,r,i,k;
    cin>>l>>r>>k;
    if(r==l)
    {
        cout<<l<<endl;
        cout<<"1
";
        cout<<l<<endl;
        return 0;
    }
    if(l%2==0)
    {
        if(r-l+1==2||k<=2)
        {
            if(k==1)
            {
                cout<<l<<endl;
                cout<<"1
";
                cout<<l<<endl;
            }
            else
            {
                cout<<"1
";
                cout<<"2
";
                cout<<l<<" "<<l+1<<endl;
            }
        }
        else if(r-l+1==3||k==3)
        {
            judge(l,r);
        }
        else
        {
            cout<<"0
";
            cout<<"4
";
            for(i = l  ; i < l + 4 ; i++)
                cout<<i<<" ";
            puts("");
        }
    }
    else
    {
        if(r-l+1==2||k<=2)
        {
            if(k==1||(r-l+1==2&&(l^(l+1))>l))
            {
                cout<<l<<endl;
                cout<<"1
";
                cout<<l<<endl;
            }
            else
            {
                if(r-l+1==2)
                {
                    cout<<(l^(l+1))<<endl;
                    cout<<"2
";
                    cout<<l<<" "<<l+1<<endl;
                }
                else
                {
                    cout<<"1
";
                    cout<<"2
";
                    cout<<l+1<<" "<<l+2<<endl;
                }
            }
        }
        else if(r-l+1==3||k==3)
        {
            judge(l,r);
        }
        else if(r-l+1==4)
        {
            int flag = 0;
            judge(l,r);
        }
        else
        {
            cout<<"0
";
            cout<<"4
";
            for(i = l+1 ; i < l+5 ; i++)
                cout<<i<<" ";
            puts("");
        }

    }
    return 0;
}