牛客练习赛100题解

#include
#define int long long
#define rep(i, a, b) for(int i=a;ib;--i)
using namespace std;
const int N = 10005;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int a=read(), b=read(), x=read();
	bool flag=false;
	rep(i, 0, x/a+1){
	    rep(j, 0, x/b+1){
	        if(i*a+j*b==x){
	            printf("%lld %lld", i, j);
	            return 0;
	        }
	    }
	}
	if(!flag){
	    put(-1);
	}
	return 0;
}

#include
#define int long long
#define rep(i, a, b) for(int i=a;ib;--i)
using namespace std;
const int N = 200005;
int n;
int arr[N];
string s;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int resx(int flag, int b, int r, char co, char bo){
    int tmp=0, resa=0;
    rep(i, 0, n){
        if (flag){
            if (arr[i]%2==r&&s[i]==co&&tmp){
                resa+=tmp;
                flag=0;
                tmp=arr[i];
            }
            else if(arr[i]%2==b&&s[i]==bo){
                tmp=max(tmp, arr[i]);
            }
            if(i==n-1){
                resa+=tmp;
            }
        }
        else{
            if(arr[i]%2==r&&s[i]==co){
                tmp = max(tmp, arr[i]);
            }
            else if(arr[i]%2==b&&s[i]==bo){
                resa+=tmp;
                flag=1;
                tmp=arr[i];
            }
            if(i==n-1){
                resa+=tmp;
            }
        }
    }
    return resa;
}
signed main(){
    n=read();
    rep(i,  0,  n)
        arr[i]=read();
    cin >> s;
    int res = resx(1, 0, 1, 'R', 'B');
    res = max(resx(1, 1, 0, 'B', 'R'), res);
    res = max(resx(1, 1, 0, 'R', 'B'), res);
    res = max(resx(1, 0, 1, 'B', 'R'), res);
    cout << res;
}

首先我们可以把所有的数位按模3的值分为3类，同一类本质为等价的。由于0不能删除，所以0可以直接忽略。
如果原数模3为x，那么小红也必须删除一个模3为x的数。
接下来相当于小紫先手，小紫必须删一个模3为x的数（x为1或2），之后小红则必须删一个模3为(1-x)的数。

#include
#define int long long
#define rep(i, a, b) for(int i=a;ib;--i)
using namespace std;
const int N = 200005;
int a[N];
int sum=0;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin>>s;
	rep(i, 0, s.size()){
	    // 由于0不能删除，所以0可以直接忽略。
	    if(s[i]-'0'){
	        a[(s[i]-'0')%3]++;    
	    }
	    // 各位数相加和能被3整除,数就能被3整除	
	    sum+=s[i]-'0';
	}
	if(!a[sum%3]){
	    puts("yukari");
	    return 0;
	}
	else{
	    a[sum%3]--;
	    if(a[1]==a[2]&&a[0]){
	        puts("you");
	    }
	    else{
	        puts("yukari");
	    }
	}
	return 0;
}

我们可以先构造一个这样的字符串"rererererere……"，可以发现，在第一个re后面添加xx个d，可以稳定增加 x 个子序列；在第二个re后面添加x个d，可以稳定增加 3x 个子序列……以此类推，在第k个re后面添加x个d，可以稳定增加 k ∗ ( k + 1 ) x 2 frac{k*(k+1)x}{2} 2k∗(k+1)x​
个子序列。用这种方式可以将最终的字符串长度缩短到 n 1 / 3 n^{1/3} n1/3级别，可以证明，当n小于 1 0 14 10^{14} 1014时是一定可以在长度200000以内构造完成的。

#include
#define int long long
#define rep(i, a, b) for(int i=a;ib;--i)
using namespace std;
const int N = 200005;
int a[N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int k=read();
	if(!k){
	    puts("d");
	}
	else{
	    // i*i*i/6
	    int i;
	    for(i=1;i*i*i/6<=k;++i);
	    i--;
	    Rep(j, i, 0){
	        a[j]+=k/(j*(j+1)/2);
	        k%=j*(j+1)/2;
	    }
	    rep(j, 1, i+1){
	        printf("re");
	        while(a[j]--){
	            printf("d");
	        }
	    }
	}
	return 0;
}

珂朵莉树

所谓珂朵莉树，即用set维护区间信息，然后暴力合并区间。
本题保证了数据随机，因此不难发现，很容易产生大量区间满足区间内所有数相等的情况，因此我们可以用set来维护这样的区间信息：[l,r]中所有数为x。
当修改一个区间时，我们可以利用二分找到需要合并的区间，然后将set中的需要合并的区间全部删除。这样最终的平均复杂度是O(nloglogn*k)，其中kk为合并区间时维护区间内因子转移的情况，需要一些技巧来减小常数。

#include
using namespace std;
#define S_IT set::iterator
mapv[20101];
struct segment{
    int l,r;
    mapfac;
    int res;
    segment(int l,int r):l(l),r(r){}
    segment(int l,int r,mapfac,int res):l(l),r(r),fac(fac),res(res){}
    bool operator<(const segment x)const{
        return this->ls;
S_IT split(unsigned int pos)
{
    S_IT it = s.lower_bound(segment(pos,pos));
    if (it != s.end() && it->l == pos)
    return it;
    --it;
    unsigned int l = it->l, r = it->r;
    map fac = it->fac;
    int res=(*it).res;
    s.erase(it);
    s.insert(segment(l, pos - 1,fac,res));
    return s.insert(segment(pos, r, fac,res)).first;
}
const int mod=1e9+7;
int power(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=(long long)res*a%mod;
        b>>=1;
        a=(long long)a*a%mod;
    }
    return res;
}
int assign(int l, int r)
{
    S_IT it2 = split(r + 1), it1 = split(l);
    S_IT it=s.upper_bound(segment(l,r));
    it--;
    mapfac=(*it).fac;
    for (S_IT it = it1; it != it2; ++it){
        for(auto itt:(*it).fac){
            int x=itt.first,y=itt.second;
            if(!fac.count(x))fac[x]=y;
            else{
                fac[x]=max(fac[x],y);
            }
        }
    }
    int res=1;
    for(auto it:fac){
        res=(long long)res*power(it.first,it.second)%mod;
    }
    while(it2!=s.end()&&(*it2).fac==fac)it2++;
    r=(*it2).l-1;
    it=it1;
    it--;
    while((*it).fac==fac)it--;
    it++;
    it1=it;
    l=(*it).l;
    s.erase(it1, it2);
    s.insert(segment(l, r, fac,res));
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int i,j,x,n,q;
    for(i=2;i<=2e4;i++){
        if(v[i].size())continue;
        for(j=i;j<=2e4;j+=i){
            int cnt=0;
            for(int k=i;j%k==0;k*=i,cnt++);
            v[j][i]+=cnt;
        }
    }
    cin>>n>>q;
    for(i=1;i<=n;i++){
        cin>>x;
        segment temp(i,i);
        temp.fac=v[x];
        temp.res=x;
        s.insert(temp);
    }
    segment temp(n+1,n+1);
    s.insert(temp);
    s.insert(segment(0,0));
    while(q--){
        int l,r;
        cin>>l>>r;
        S_IT it=s.upper_bound(segment(l,r));
        it--;
        if((*it).r>r){
            cout<<(*it).res<<'n';
            continue;
        }
        cout<

原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈