头像

垫底抽風

$$\color{red}{\texttt{Legendary Grandmaster ღꦿ࿐}}$$




在线 


最近来访(14852)
用户头像
萱华
用户头像
luyh
用户头像
1234abcd
用户头像
Easons.
用户头像
chaos_47
用户头像
zeta_y
用户头像
say774
用户头像
ikun拿命打算法
用户头像
顽童
用户头像
爱上AC
用户头像
MrYFX
用户头像
Jetstream_Sam
用户头像
Ethanyyc
用户头像
清风qwq
用户头像
小桐努力变强
用户头像
wuyizhou
用户头像
Fine1
用户头像
双林
用户头像
做事要有遗逝感
用户头像
啦啦啦啦啦啦啦啦


垫底抽風
6小时前

→🔗←

第一次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';
    }
}


新鲜事 原文

垫底抽風
22小时前
三个半小时AK USACO Cu Ag 200分不到哈哈哈哈哈


活动打卡代码 AcWing 1799. 奶牛密码

#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';
        }
    }
}



活动打卡代码 AcWing 1722. 排序

#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);
}



活动打卡代码 AcWing 1918. 灌溉田地

#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);
}