→🔗←

第一次AK铜组进银啊qwq

耗时 $3h \ 30min$

Leaders

贪心。能想到的话其实代码很短。

我们可以把选择的两个领导分为两种情况：

1. 有一个领导可以管理自己所有种类的牛，且另外一个领导可以管理这个领导。

2. 两个领导都可以管理各自种类的牛。

把这个想出来代码也就自然好写了。

我们可以先把两种种类第一次和最后一次出现的牛出现的位置找出来。

之后我们可以看到，如果这头牛能管控的牛可以当领导（那么这个被管控的领导管控的牛必须包括所有和自己种类一样的牛。），如果满足，那么就形成一对。

如果两头牛都可以管控所有和自己种类一样的牛，那么也是一对。

#include<bits/stdc++.h>
#define int long long
using namespace std; 
const int N=1e5+10;
int a[N];
signed main() 
{ 
    int n;
    cin>>n;
    string st;
    cin>>st;
    st=' '+st;
    int g=0,h=0,G=0,H=0;
    for(int i=1;i<st.size();i++){
        if(st[i]=='G'&&!g)g=i;
        else if(st[i]=='H'&&!h)h=i;
    }
    for(int i=st.size()-1;i>=1;i--){
        if(st[i]=='G'&&!G)G=i;
        else if(st[i]=='H'&&!H)H=i;
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    char ch;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(st[i]=='G'){
            if(a[i]>=h&&i<=h&&a[h]>=H)ans++;
        }
        if(st[i]=='H'){
            if(a[i]>=g&&i<=g&&a[g]>=G)ans++;
        }
    }
    /*
    为了防止抄题解，代码里可能会有废话/ww
    管控另外一个领导的定义如下：这个牛所管理的范围可以包含另外一种牛第一次出现的位置。
    管理包括所有和自己种类一样的牛的定义如下：这个牛所管理的范围可以包含和自己种类一样的牛最后一次出现的位置。
    */
    if(a[g]>=G&&a[h]>=H)ans++;
    cout<<ans;
}

Cownditioning II

前置芝士：枚举子集

是的，我们分为取和不取的情况考虑然后取最小值就行了。

这里用二进制模拟，其实很多方法都可以实现。

可以先把每个单位的牛棚所要的温度加上，如果最后减的话每个单位都比 0 小，那么我们就取最小值。

由于 $m$ 的范围非常小，所以 是可以过去的。

#include<bits/sdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],f[N],x[N],n,m;
struct node{
    int l,r,x,t;
}s[N];
string bin(int n,int m)
{
    int x[101],t=0,s=m;
    while(n!=0){
        x[t]=n%2;
        t++;
        n=n/2;
    }
    string st="";
    while(t<s){
        s--;
        st+='0';
    }
    for(int i=t-1;i>=0;i--)st+=char(x[i]+48);
    return st;
}
int main()
{
    cin>>n>>m;
    int L=INT_MAX,R=0;
    for(int i=1;i<=n;i++){
        int l,r,c;
        cin>>l>>r>>c;
        a[l]+=c;
        a[r+1]-=c;
        L=min(L,l);//左边界
        R=max(R,r);//有边界
    }
    //多余的区域是不需要管的。
    for(int i=L;i<=R;i++)f[i]=f[i-1]+a[i];//差分求每一的单位所需减少的温度。
    //for(int i=L;i<=R;i++)cout<<f[i]<<' ';
    for(int i=1;i<=m;i++)cin>>s[i].l>>s[i].r>>s[i].x>>s[i].t;
    int mi=INT_MAX;
    for(int i=0;i<=pow(2,m)-1;i++){
        for(int j=L;j<=R;j++)x[j]=f[j];
        string st=bin(i,m);
        int ans=0;
        for(int j=0;j<st.size();j++){
            if(st[j]=='1'){
                for(int k=s[j+1].l;k<=s[j+1].r;k++)x[k]-=s[j+1].x;
                ans+=s[j+1].t;
            }
        }
        bool ok=1;
        //for(int j=L;j<=R;j++)cout<<x[j]<<' ';
        //puts("");
        for(int j=L;j<=R;j++)
            if(x[j]>0){
                ok=0;
                break;
            }
        if(ok)mi=min(mi,ans);
    }
    cout<<mi;
}

Moo Operations

首先字符串至少要有 3 位，没有直接输出 -1。

我们三位三位模拟取最小值，只要中间是 O ，都可以变成 MOO。

操作次数如下：

1. MOO：0次。
2. MOM：1次。
3. OOO：1次。
4. OOM：2次。

最终取最小值加上总长度 -3 即可。因为最终只能保留 3 位。如果 $mi$ 仍是初始值，那么输出 -1。

#include<bits/sdc++.h>
using namespace std;

signed main()
{
    int t;
    cin>>t;
    while(t--){
        int mi=0x3f3f3f3f;
        string st;
        cin>>st;
        if(st.size()<3){
            puts("-1");
            continue;
        }
        for(int i=0;i<st.size()-2;i++){
            string str=st.substr(i,3);
            if(str=="MOO")mi=min(mi,0);
            else if(str=="MOM")mi=min(mi,1);
            else if(str=="OOO")mi=min(mi,1);
            else if(str=="OOM")mi=min(mi,2);
        }
        if(mi==0x3f3f3f3f)puts("-1");
        else cout<<mi+st.size()-3<<'\n';
    }
}

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main() 
{
    string st;
    int n,ans=0;
    cin>>st>>n;
    ans=st.size();
    while(ans<n){
        int t=ans;
        while(n>t)t*=2;
        t/=2;
        n-=t;
        n--;
        if(!n)n=t;
    }
    cout<<st[n-1];
}

算法1

树状数组，因为每次都会把区间反转，那么我们可以把这个区间 +1。
由于之前所有数的值都是 0，所以如果是奇数就是 1，偶数就是 0。

参考文献

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[500001],t[500001];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))t[i]+=c;
}
int ask(int x)
{
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i))ans+=t[i];
    return (ans&1?1:0);
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)a[i]=0,add(i,a[i]-a[i-1]);
    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){
            int l,r;
            cin>>l>>r;
            add(l,1);
            add(r+1,-1);
        }
        else{
            int x;
            cin>>x;
            cout<<ask(x)<<'\n';
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,id;
}a[100001];
bool cmp(node a,node b)
{
    if(a.x==b.x)return a.id<b.id;
    return a.x<b.x;
}
int main() 
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x,a[i].id=i;
    sort(a+1,a+1+n,cmp);
    int ma=0;
    for(int i=1;i<=n;i++)
        ma=max(ma,a[i].id-i);
    cout<<ma+1;
}

算法1

把每一位上的数算出来判断输出即可。

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    while(n++){
        int t1,t2,t3,t4;
        t1=n/1000;
        t2=n%1000/100;
        t3=n%1000%100/10;
        t4=n%1000%100%10;
        if(t1!=t2&&t1!=t3&&t1!=t4&&t2!=t3&&t2!=t4&&t3!=t4){
            cout<<n;
            return 0;
        }
    }
}

算法1

生成树板子，排序由大到小，距离取两数异或即可。

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int M=5000001;
LL f[M],a[M],n,m,ans=0,cnt=0;
struct node{
    int u,v,w;
}e[M];
bool cmp(node a,node b)
{
    return a.w>b.w;
}
int find(int x)
{
    if(x==f[x])return x;
    f[x]=find(f[x]);
    return f[x];
}
int main()
{
    cin>>n;
    for(int i=0;i<=n;i++)f[i]=i;
    for(int i=1;i<=n;i++)cin>>a[i];
    int c=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            c++;
            e[c]={i,j,(a[i]^a[j])};     
        }
    sort(e+1,e+1+c,cmp);
    for(int i=1;i<=c;i++){
        if(find(e[i].u)!=find(e[i].v)){
            f[find(e[i].v)]=find(e[i].u);
            ans+=e[i].w;
            cnt++;
            if(cnt==n-1)break;
        }
    }
    cout<<ans;
}

算法1

生成树板子，没有太大区别，把距离算出来就行了。

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int M=5000001;
LL f[M],a[M],b[M],n,m,ans=0,cnt=0;
struct node{
    int u,v,w;
}e[M];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int find(int x)
{
    if(x==f[x])return x;
    f[x]=find(f[x]);
    return f[x];
}
double dis(int x1,int y1,int x2,int y2)
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<=n;i++)f[i]=i;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    int c=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            if(m<=dis(a[i],b[i],a[j],b[j])){
                c++;
                e[c]={i,j,dis(a[i],b[i],a[j],b[j])};
            }
        }
    sort(e+1,e+1+c,cmp);
    for(int i=1;i<=c;i++){
        if(find(e[i].u)!=find(e[i].v)){
            f[find(e[i].v)]=find(e[i].u);
            ans+=e[i].w;
            cnt++;
            if(cnt==n-1)break;
        }
    }
    cout<<(cnt==n-1?ans:-1);
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int M=5000001;
LL f[M],a[M],b[M],n,m,ans=0,cnt=0;
struct node{
    int u,v,w;
}e[M];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int find(int x)
{
    if(x==f[x])return x;
    f[x]=find(f[x]);
    return f[x];
}
double dis(int x1,int y1,int x2,int y2)
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<=n;i++)f[i]=i;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    int c=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            if(m<=dis(a[i],b[i],a[j],b[j])){
                c++;
                e[c]={i,j,dis(a[i],b[i],a[j],b[j])};
            }
        }
    sort(e+1,e+1+c,cmp);
    for(int i=1;i<=c;i++){
        if(find(e[i].u)!=find(e[i].v)){
            f[find(e[i].v)]=find(e[i].u);
            ans+=e[i].w;
            cnt++;
            if(cnt==n-1)break;
        }
    }
    cout<<(cnt==n-1?ans:-1);
}