头像

溜溜odd




离线:8天前


最近来访(19)
用户头像
aaaa不了c
用户头像
小镇错题家
用户头像
@装睡的人
用户头像
小飞龙
用户头像
HAMMER_XIAO
用户头像
LaoT
用户头像
BitterSweet
用户头像
挑战关注所有大佬
用户头像
空釉璃
用户头像
空位

活动打卡代码 AcWing 3492. 负载均衡

溜溜odd
2个月前

greater是小根堆

优先队列的使用

#include<iostream>
#include<queue>

using namespace std;

typedef pair<int,pair<int,int> >  tii;
const int N=200010;

int n,m;
int v[N];
priority_queue<tii,vector<tii>,greater<tii> >  tree;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++)  cin>>v[i];

    int a,b,c,d;
    while(m--)
    {
        cin>>a>>b>>c>>d;

        while(tree.size() && tree.top().first <= a)
        {
            v[tree.top().second.second] += tree.top().second.first;
            tree.pop();
        }

        if(v[b] < d)  cout<<-1<<endl;
        else
        {
            tree.push({a+c,{d,b}});
            v[b]-=d;
            cout<<v[b]<<endl;
        }

    }

    return 0;
}


活动打卡代码 AcWing 3491. 完全平方数

溜溜odd
2个月前
#include<iostream>
#include<map>

using namespace std;

typedef long long ll;
ll n,x=1;

int main()
{
    cin>>n;


    i 也要定ll  这种题直接都ll得了

    for(ll i=2;i*i<n;i++)
    {
        ll s=0;
        while(n%i==0)
        {
            s++;
            n/=i;
        }
        if(s%2) x*=i; 
    }
    if(n>2)  x*=n;

    cout<<x<<endl;

    return 0;
}


活动打卡代码 AcWing 3490. 小平方

溜溜odd
2个月前
#include<iostream>

using namespace std;

int n,res;

int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        if((i*i%n)<<1 < n)  res++;
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 4441. 谎牛计数

溜溜odd
2个月前
#include<iostream>
#include<algorithm>

using namespace std;

const int N=1010;
int l[N],r[N];
int n,ll,rr;
int res;

bool cmp(int a,int b)
{
    return a>b;
}

int main()
{
    cin>>n;
    res=n;
    while(n--)
    {
        char ch;
        int pos;
        cin>>ch>>pos;
        // if(ch=='G')
        // {
        //     l[ll]=pos;
        //     ll++;
        // }
        // else
        // {
        //     r[rr]=pos;
        //     rr++;
        // }


        switch (ch)
        {
            case 'G':
                l[ll]=pos;
                ll++;
                break;
            case 'L':
                r[rr]=pos;
                rr++;
                break;
        }


    }
    n=ll+rr;

    sort(l,l+ll,cmp);
    sort(r,r+rr);

    for(int i=0;i<ll;i++)
    {
        for(int j=0;j<rr;j++)
        {
            if(r[j]>=l[i])
            {
                res=min(res,i+j);
                break;
            }
        }
    }
    res=min(res,ll);
    res=min(res,rr);
    这值得注意

    cout<<res<<endl;


    return 0;
}



溜溜odd
3个月前
#include<iostream>
#include<cstring>

using namespace std;

const int N=12,M=1<<12;
int n,m;
long long f[N][M];//第n列 为m
bool st[M];

int main()
{
    while(cin>>n>>m,n||m)
    {
        //处理0~2^n-1 哪些数合法
        //memset(st,true,sizeof st);
        for(int i=0;i< 1<<n;i++)
        {
            bool valid=true;
            int cnt=0;
            for(int j=0;j<n;j++)
            {
                if(i>>j&1)
                {
                    if(cnt&1)
                    {
                        valid=false;
                        break;
                    }
                }
                else
                {
                    cnt++;
                }
            }
            if(cnt&1) valid=false;
            st[i]=valid;
        }


        //

        memset(f,0,sizeof f);
        f[0][0]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=0;j< 1<<n;j++)
            {
                for(int k=0;k< 1<<n;k++)
                {
                    if( (j&k)==0 && st[k|j])
                        f[i][j]+=f[i-1][k];
                }
            }
        }


        cout<<f[m][0]<<endl;


    }

    return 0;
}



活动打卡代码 AcWing 4405. 统计子矩阵

溜溜odd
3个月前

i j 行
l r列
(图片倒过来)

核心在双指针

115313_9c85b174b9-无标题.png

#include<iostream>

using namespace std;

typedef long long ll;
const int N=510;
int n,m,k;
int g[N][N];

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
            g[i][j]+=g[i-1][j];
        }

    ll ans=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            for(ll l=1,r=1,sum=0;r<=m;r++)
            {
                sum+=g[j][r]-g[i-1][r];
                while(sum>k)
                {
                    sum-=g[j][l]-g[i-1][l];
                    l++;
                }
                ans+=r-l+1;
            }
        }
    }

    cout<<ans<<endl;

    return 0;
}


活动打卡代码 AcWing 4404. X 进制减法

溜溜odd
3个月前
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;
const int N=100010,mod=1000000007;
int n;
ll a[N],b[N];
ll jin[N],jin1[N];

int main()
{

    cin>>n;
    int n1,n2;

    cin>>n1;
    for(int i=0;i<n1;i++)  cin>>a[i];

    cin>>n2;
    for(int i=0;i<n2;i++)  cin>>b[i];

    int nmax=max(n1,n2);

    reverse(a,a+n1);
    reverse(b,b+n2);

    ll one=1,two=2;
    for(int i=1;i<=nmax;i++)
    {
        jin[i]=max(two,max(a[i-1],b[i-1])+one);
    }

    jin1[1]=1;
    for(int i=2;i<=nmax;i++)
    {
        jin1[i]=jin[i-1]*jin1[i-1]%mod;
    }

    ll aa=0,bb=0;
    //算 a的十进制表示
    for(int i=1;i<=n1;i++)
    {
        aa%=mod;
        aa+=a[i-1]*jin1[i]%mod;
    }

    for(int i=1;i<=n2;i++)
    {
        bb%=mod;
        bb+=b[i-1]*jin1[i]%mod;
    }

    cout<<(aa-bb+mod)%mod<<endl;


    return 0;
}











活动打卡代码 AcWing 4402. 刷题统计

溜溜odd
3个月前
#include<iostream>

using namespace std;

typedef long long ll;
ll a,b,n;
ll week;

int main()
{
    cin>>a>>b>>n;

    week=5*a+2*b;
    ll ans=n/week;
    ll res=n%week;
    ll sum;
    sum=ans*7;
    ll weeks[]={a,a,a,a,a,b,b};
    for(ll i=0; ;i++)
    {
        if(res<=0)
        {
            cout<<sum<<endl;
            return 0;
        }

        res-=weeks[i];
        sum++;

    }












    return 0;
}


活动打卡代码 AcWing 1226. 包子凑数

溜溜odd
4个月前

还不错的一种写法 可以解决一部分完全背包问题 一些数 可以组成哪些数

#include<iostream>

using namespace std;

const int N=110,M=10010;
int n;
int a[N],s[M];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)  cin>>a[i],s[a[i]]=1;

    for(int i=1;i<=n;i++)
    {
        for(int j=a[i];j<=10000;j++)
        {
            if(s[j-a[i]])  s[j]=1;
        }
    }

    int res=0;
    for(int i=1;i<=10000;i++)
    {
        if(!s[i])  res++;
    }

    if(res<5000)  cout<<res;
    else cout<<"INF";

}








活动打卡代码 AcWing 1235. 付账问题

溜溜odd
4个月前

主要是精度问题 和 输出格式问题

#include<iostream>
#include<cmath> 
#include<cstdio>
using namespace std;

typedef long long ll;
const int N=500010;
long double n,s;
long double a[N];
long double b[N];
bool st[N];

int main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    long double c=s/n;
    long double avg=c;
    int m=0;//剩钱的人数  
    for(int i=1;i<=n;i++)
    {
        if(a[i]>c)  
        {
            a[i]-=c;
            s-=c;
            b[i]=c;
            st[i]=1;
            m++;
        }
        else  
        {
            s-=a[i];
            b[i]=a[i];
            a[i]=0;
            //st[i]=0;
        }
    }
    while(s>0)
    {
        c=s/m;  //没人花这么多 
        m=0;//这次剩钱的人数 
        for(int i=1;i<=n;i++)
        {
            //cout<<s<<endl;
            //cout<<c<<endl;
            if(st[i])
            {
                //cout<<i<<"有钱"<<endl; 
                if(a[i]>c) 
                {
                    a[i]-=c;
                    s-=c;
                    b[i]+=c;
                    st[i]=1;
                    m++;
                } 
                else
                {
                    //cout<<i<<"not enough"<<endl;
                    s-=a[i];
                    b[i]+=a[i];
                    a[i]=0;
                    st[i]=0;
                }  
            }
        }
    }
    long double res=0;

    for(int i=1;i<=n;i++)
    {
        res=res+( b[i]-avg)*( b[i]-avg);
    }

    res=sqrt(res/n);
    printf("%.4Lf\n",res);

}