头像

cskaobo


访客:2043

离线:7个月前



cskaobo
8个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

秦淮案灯火阑珊

C++ 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define N 100010
using namespace std;
long long h[N],w[N],stk[N];  //stk栈存储插入栈中直方图高度
                             //w存储每个直方图可扩展的宽度;
int n,top=0;
void work()
{
    memset(stk,0,sizeof(stk));  //清空栈中原有内容
    top=0;  //栈顶指针回0
    int i,wide;
    long long res=0;
    for(i=1;i<=n+1;i++)
    {
        if(stk[top]<h[i]) //新插入的直方图高度比栈顶直方图高
        {
            stk[++top]=h[i];  //直接将直方图插到栈顶之后
            w[top]=1;   //设置当前直方图扩展宽度为1
        }
        else  //新插入的直方图高度与栈顶直方图高度相等或小于栈顶直方图高度
        {
            wide=0;
            while(top>0&&stk[top]>=h[i])  //计算新插入直方图左侧所有高度大于等于新插入直方图的最大扩展面积
            {
               //while循环中的top>0是为了防止数组越界,当循环执行到i==n+1、top==0时,此时
               //stk[0]=0>=h[n+1]=0,因此top--=-1,stk[-1]数组越界就会产生段错误
                res=max(res,stk[top]*(w[top]+wide)*1ll);
                wide+=w[top];
                top--;  //栈中所有高度大于等于h[i]的直方图出栈
            }
            stk[++top]=h[i]; //将第i个直方图插到栈中第1个高于小于它的位置之后
            w[top]=wide+1;  //更新第i个直方图的最大扩展宽度
        }
    }
    cout<<res<<endl;
}

int main()
{
    int i;
    while(cin>>n,n)
    {
        for(i=1;i<=n;i++)
        {
            cin>>h[i];
        }
        //cout<<"数组:";
        /*for(i=1;i<=n+1;i++)
        {
            cout<<h[i]<<' ';
        }
        cout<<endl;*/
        h[n+1]=0;
        work();
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



cskaobo
8个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 2010
typedef pair<int,int> PII;
PII row[N],col[N];
int ans[N];
int main()
{
    int i,m,n,k,l,d,x1,x2,y1,y2,cnt;
    cin>>m>>n>>k>>l>>d;
    for(i=1;i<=m;i++)
    {
        row[i].second=i;  //初始化横向分隔线
    }

    for(i=1;i<=n;i++)
    {
        col[i].second=i;  //初始化纵向分隔线
    }

    while(d--)
    {
        cin>>x1>>y1>>x2>>y2;
        if(abs(x1-x2)==1)
        {
            row[min(x1,x2)].first++;  //统计一条横向分隔线能分隔多少对说话的同学
        }
        if(abs(y1-y2)==1)
        {
            col[min(y1,y2)].first++;  //统计一条纵向分隔线能分隔多少对说话的同学
        }
    }

    sort(row+1,row+m+1);  //按横向分隔线能够分隔的同学对数从小到大排序
    sort(col+1,col+n+1);  //按纵向分隔线能够分隔的同学对数从小到大排序

    cnt=0;
    for(i=m;i>m-k;i--)  //取出k条最优横向分隔线
    {
        ans[cnt++]=row[i].second;
    }
    sort(ans,ans+cnt);  //按照横向分隔线的标号从小到大排序
    for(i=0;i<cnt;i++)
    {
        cout<<ans[i];
        if(i<cnt-1)
        {
            cout<<' ';
        }
    }
    cout<<endl;

    cnt=0;
    for(i=n;i>n-l;i--)  //取出l条最优纵向分隔线
    {
        ans[cnt++]=col[i].second;
    }
    sort(ans,ans+cnt);  //按照纵向分隔线的标号从小到大排序
    for(i=0;i<cnt;i++)
    {
        cout<<ans[i];
        if(i<cnt-1)
        {
            cout<<' ';
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



cskaobo
9个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <stdio.h>
#include <iostream>
#include <map>
#include <algorithm>
#define N 10010
using namespace std;
long d[N]; //初始差分数列为0,表示所有牛的身高没有差距,等于最高的牛h

int main()
{
    int n,p,m,i,a,b;
    long h;
    cin>>n>>p>>h>>m; //n:牛的数量,m:能相互看到的牛的对数,h最高的牛的高度,p:最高的牛的位次
    map<pair<int,int>,bool> exist;  //保存某两头牛相互看见的关系是否存在
    for(i=1;i<=m;i++)
    {
        cin>>a>>b;  //a保存a,b序号中的最小值,b保存a,b序号中的最大值
        if(a>b)
        {
            swap(a,b);
        }
        if(exist[{a,b}])  //如果a,b两头牛互相能看到的关系存在,则此次输入无效
        {
            continue;
        }
        //初始差分序列为
        d[a+1]--;  //a,b两头牛能互相看见,表示[a,b]区间内牛的身高至少比a和b矮1
        d[b]++;
        exist[{a,b}]=true;  //标记a,b两头牛的关系已输入
    }

    for(i=1;i<=n;i++) //差分序列的前缀和序列表示每头牛比最高的牛矮多少
    {
        d[i]+=d[i-1];
        cout<<d[i]+h<<endl;
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



cskaobo
9个月前

题目描述

blablabla

样例

#include <stdio.h>
#include <iostream>
#include <algorithm>
#define N 100010
using namespace std;
long a[N]; //原序列,下标从1开始
long b[N]; //差分序列,下标从1开始

int main()
{
    int i,n;
    long pos=0,neg=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    b[1]=a[1];
    for(i=2;i<=n;i++)
    {
        b[i]=a[i]-a[i-1];
    }
    b[n+1]=0; //初始a[n+1]=a[n]

    //要想使a[i]转化成常数列,实际上就是使b1=a1,b2~bn=0,bn+1是什么无所谓
    for(i=2;i<=n;i++)
    {
        if(b[i]>0)  
        {
            pos+=b[i];  //计算差分序列b2~bn中正数的和
        }
        else
        {
            neg+=b[i];  //计算差分序列中b2~bn中非正数的和,结果要加绝对值
        }
    }
    neg=abs(neg);
    //pos和neg中的小者就是bi和bj一正一负配对时-1+1操作的数量
    //剩余的|pos-neg|就是落单的差分序列中的正数或负数bk,这些差分序列剩余的正数或负数bk可以通过与差分序列中b1或
    //bn+1进行+1-1操作使bk逐步变到0,而这些bk如果与b1配对进行+1-1的操作则会影响常数列的初值a1,从而影响最终
    //的常数列。所以常数列的最多可能有|p-q|+1种(算上前面min(neg,pos)次不影响常数列初值的操作),最少可能有
    //1种,就是差分序列中剩余的bk都与bn+1配对进行+1-1的操作
    cout<<max(pos,neg)<<endl;
    cout<<abs(pos-neg)+1<<endl;

}


算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



cskaobo
9个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define N 1010
typedef pair<int,int> PII;
PII info[N];


vector<int> mul(vector<int> a,int b) //大整数*小整数的乘法
{
    int i,carry;
    vector<int> ret;
    carry=0;
    for(i=0;i<a.size();i++)
    {
        ret.push_back((a[i]*b+carry)%10);
        carry=(a[i]*b+carry)/10;
    }

    while(carry!=0)
    {
        ret.push_back(carry%10);
        carry=carry/10;
    }
    return ret;
}

vector<int> divide(vector<int> a,int b) //大整数/小整数的除法
{
    int re=0,i,t;
    vector<int> ret;
    bool tag=false;  //判断是否非最高位0
    for(i=a.size()-1;i>=0;i--)  //从高位到低位遍历被除数的每一位
    {
        re=re*10+a[i];
        t=re/b;
        if(t!=0||tag==true)
        {
            tag=true;
            ret.push_back(t);
        }
        re=re%b;
    }

    reverse(ret.begin(),ret.end());  //反转商的高位和低位,使商从低位开始存储
    return ret;
}

vector<int> maxvalue(vector<int> a,vector<int> b)
{
    int i;
    if(a.size()>b.size())
    {
        return a;
    }
    else if(a.size()<b.size())
    {
        return b;
    }
    else
    {
        /*if(vector<int>(a.rbegin(),a.rend())>vector<int>(b.rbegin(),b.rend())) //如果a、b的位数相等则从高位到低位比较数字的每一位
        {
            return a;
        }
        return b;*/
        for(i=a.size()-1;i>=0;)
        {
            if(a[i]>b[i])
            {
                return a;
            }
            else if(a[i]<b[i])
            {
                return b;
            }
            else
            {
                i--;
            }
        }
        return a; //如果a和b的每一位都相等,则a==b此时返回a、b均可
    }
}
int main()
{
    vector<int> product(1,1);
    vector<int> res(1,0);
    int n,i,l,r;
    cin>>n;
    for(i=0;i<=n;i++)
    {
        cin>>l>>r;
        info[i].first=l*r;
        info[i].second=l;
    }
    sort(info+1,info+n+1); //按照first从小到大排序
    for(i=0;i<=n;i++)
    {
        if(i!=0)
        {
            res=maxvalue(res,divide(product,info[i].first/info[i].second));
        }
        product=mul(product,info[i].second);  //累乘
    }

    for(i=res.size()-1;i>=0;i--)  //从高位到低位输出最大值的结果
    {
        cout<<res[i];
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

blablabla



cskaobo
10个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;
PII section[110];

bool cmp(PII a,PII b)
{
    return a.first<b.first;
}

int main()
{
    int L,M,i,l,r,curl,curr;
    long sum=0;
    cin>>L>>M;
    for(i=0;i<M;i++)
    {
        cin>>l>>r;
        section[i].first=l;
        section[i].second=r;
    }

    sort(section,section+M,cmp);  //按照区间左端点从小到大排序
    curl=section[0].first;
    curr=section[0].second;
    for(i=1;i<M;i++)
    {
        if(section[i].first<=curr)  //区间有交集,更新区间左右端点
        {
            //curl=min(curl,section[i].first);
            curr=max(curr,section[i].second);

        }
        else
        {
            sum+=curr-curl+1; //计算之前并集的长度
            curl=section[i].first;
            curr=section[i].second;
        }
    }


        sum+=curr-curl+1;

    cout<<L+1-sum;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

blablabla



cskaobo
10个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

#include <stdio.h>
#include <iostream>
using namespace std;
#define N 50
int a[N][N];

int main()
{
    int i,j,num,n;
    cin>>n;

    a[0][n/2]=1;
    i=0;
    j=n/2;
    for(num=2;num<=n*n;num++)
    {
        if((i==0&&j==n-1)||a[(i-1+n)%n][(j+1)%n]!=0)
        {
            i=(i+1)%n;
        }
        else
        {
            i=(i-1+n)%n;
            j=(j+1)%n;
        }
        a[i][j]=num;
    }

    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
}



cskaobo
10个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 310
struct score
{
    int num;
    int chin;
    int math;
    int english;

    bool operator<(struct score const &sc)const
    {
        if(chin+math+english==sc.chin+sc.math+sc.english)
        {
            if(chin==sc.chin)
            {
                return num<sc.num;
            }
            else
            {
                return chin>sc.chin;
            }
        }
        return chin+math+english>sc.chin+sc.math+sc.english;
    }
}scores[N];

int main()
{
    int i,n,a,b,c;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a>>b>>c;
        scores[i].num=i+1;
        scores[i].chin=a;
        scores[i].math=b;
        scores[i].english=c;
    }
    sort(scores,scores+n);
    for(i=0;i<5;i++)
    {
        cout<<scores[i].num<<' '<<scores[i].chin+scores[i].math+scores[i].english<<endl;
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

blablabla



cskaobo
10个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

双指针算法,一轮for循环解决问题
时间复杂度分析:blablabla

C++ 代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 30010
int a[N];
int main()
{
    int i,w,n,j,count=0;
    cin>>w>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    for(i=0,j=n-1;i<j;)
    {
        if(a[i]+a[j]>w)
        {
            count++;
            j--;
        }
        else
        {
            count++;
            i++;
            j--;
        }
    }
    if(i==j)
    {
        count++;
    }
    cout<<count;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

blablabla



cskaobo
10个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 200010
typedef pair<long,long> PLL;
PLL kuangshi[N];
PLL section[N];
long long sum[N]; //保存矿石总价值的前缀和数组
long cnt[N];  //保存满足重量要求的矿石总数量的数组

long long getY(long W,long n,long m)
{
    int i;
    long long Y=0;
    for(i=1;i<=n;i++)
    {
        if(kuangshi[i].first>=W)
        {
            sum[i]=sum[i-1]+kuangshi[i].second;
            cnt[i]=cnt[i-1]+1;
        }
        else
        {
            sum[i]=sum[i-1];
            cnt[i]=cnt[i-1];
        }
    }
    for(i=1;i<=m;i++) //求不同W值时的前缀和
    {
        Y+=(sum[section[i].second]-sum[section[i].first-1])*(cnt[section[i].second]-cnt[section[i].first-1]);
    }
    return Y;
}

int main()
{
    long n,m,l,r,w,v,W,i,j,ans,mid;
    long long S;
    cin>>n>>m>>S;
    for(i=1;i<=n;i++)
    {
        cin>>w>>v;
        kuangshi[i].first=w;
        kuangshi[i].second=v;
    }

    for(i=1;i<=m;i++)
    {
        cin>>l>>r;
        section[i].first=l;
        section[i].second=r;
    }
    l=0;
    r=1e6+1;
    while(l<r) //二分出get(W)大于等于S的最小的Y
    {
        mid=(l+r+1)/2;
        if(getY(mid,n,m)>=S)  //Y增大,W减小
        {
            l=mid;
        }
        else  //Y增大,W减小
        {
            r=mid-1;
        }
    }
    ans=min(abs(getY(l,n,m)-S),abs(getY(l+1,n,m)-S));
    cout<<ans;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

blablabla