头像

溜溜odd




离线:7天前


最近来访(17)
用户头像
AllKilledDreamer
用户头像
Acwing_gyq
用户头像
装睡的人ᝰ
用户头像
小飞龙
用户头像
HAMMER_XIAO
用户头像
LaoT
用户头像
BitterSweet
用户头像
挑战关注所有大佬
用户头像
空釉璃
用户头像
空位

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

#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
14天前
#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
15天前

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
15天前
#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
20天前
#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
1个月前

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

#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
1个月前

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

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

}













活动打卡代码 AcWing 1207. 大臣的旅费

溜溜odd
1个月前
#include<iostream>
#include<vector>

using namespace std;

const int N=100010;
int n;
int dist[N];
struct edge
{
    int son;
    int dist;
};
vector<edge> h[N];

void dfs(int u,int f,int f_u)
{
    dist[u]=dist[f]+f_u;

    for(int i=0;i<h[u].size();i++)
    {
        if(h[u][i].son!=f)
        { 
            dfs(h[u][i].son,u,h[u][i].dist);
        }
    }

}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        h[a].push_back({b,c});
        h[b].push_back({a,c});
    } 

    //算1 到所有点的距离 

    dfs(1,0,0);
    int u,res=0;
    for(int i=1;i<=n;i++)
    {
        if(dist[i]>res) 
        {
            res=dist[i];
            u=i;
        }
    }

    dfs(u,0,0);
    res=0;
    for(int i=1;i<=n;i++)
        res=max(res,dist[i]);

    long long ans=0,one=1;
    ans=10*res+res*(one+res)/2; 

    cout<<ans<<endl;
    return 0;

}






活动打卡代码 AcWing 1096. 地牢大师

溜溜odd
1个月前

bfs

#include<iostream>
#include<cstring>
using namespace std;

const int N=110;
int l,r,c;
char g[N][N][N];
int d[N][N][N];
int dx[7]={0,1,-1,0,0,0,0};
int dy[7]={0,0,0,1,-1,0,0};
int dz[7]={0,0,0,0,0,1,-1};

struct pii
{
    int x;
    int y;
    int z;
} q[N*N*N];

int bfs(int x,int y,int z)
{
    memset(d,-1,sizeof d);
    int tt=0,hh=0;
    d[x][y][z]=0;
    q[0]={x,y,z};

    while(hh<=tt)
    {
        pii t=q[hh++];
        for(int i=1;i<=6;i++)
        {
            int xx=t.x+dx[i];
            int yy=t.y+dy[i];
            int zz=t.z+dz[i];
            if(xx>=1 && xx<=l && yy>=1 && yy<=r &&
                zz>=1 && zz<=c && d[xx][yy][zz]==-1 &&
                g[xx][yy][zz]!='#')
            {
                d[xx][yy][zz]=d[t.x][t.y][t.z]+1;
                if(g[xx][yy][zz]=='E')  return d[xx][yy][zz];
                q[++tt]={xx,yy,zz};
            }
        }
    }
    return -1;
}

int main()
{
    while(cin>>l>>r>>c)
    {
        if(l*r*c==0)  return 0;

        int x,y,z;
        for(int i=1;i<=l;i++)
        {
            for(int j=1;j<=r;j++)
            {
                for(int k=1;k<=c;k++)
                {
                    cin>>g[i][j][k];
                    if(g[i][j][k]=='S') 
                        x=i,y=j,z=k;
                }
            }
        }
        int res=bfs(x,y,z);
        if(res==-1)  cout<<"Trapped!"<<endl;
        else  cout<<"Escaped in "<<res
                    <<" minute(s)."<<endl;
    }

    return 0;
}












溜溜odd
1个月前

放累加和的地方 直接用long long 就得了

都要记得更新状态

#include<iostream>

using namespace std;

const int N=100010;
int n;
long long ms=-1e18,res;
int a[N];

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

    cin>>n;


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

    int len=1;
    for(int i=1; i<=n ; i+=len,len*=2 )
    {
        long long temp=0;
        for(int j=i; j<i+len && j<=n ;j++)
        {
            temp+=a[j];
        }
        //cout<<len<<endl;
        if(temp>ms)
        {
            ms=temp;
            res=len;
        }
        //cout<<len<<"  "<<temp<<endl;
    }

    int ans=1;
    while(res!=1)
    {
        ans++;
        res/=2;
    }

    cout<<ans;

}