头像

我就是废物




离线:36分钟前


活动打卡代码 AcWing 125. 耍杂技的牛

听课前自己先试着敲了一下,貌似比y总那份快5ms

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

const int N=50010;
int n;

struct Cow{
    int w,s;
    bool operator <(const Cow& x)const{
        return (w+s)<(x.w+x.s);
    }
}cow[N];   //牛 结构体,重载了<号,排序时按照(w+s)的大小比较

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&cow[i].w,&cow[i].s);

    sort(cow+1,cow+n+1);  //因为从1开始读入的,所以都加了1

    int res=-2e9,risk=0;  //res保存最终答案,risk表示每头牛的风险值
    for(int i=1;i<=n;i++)
    {
        risk+=cow[i-1].w+cow[i-1].s-cow[i].s; //risk[i]=risk[i-1]+cow[i-1].w+cow[i-1].s-cow[i].s
        res=max(risk,res);  //res取风险值最大的
    }

    printf("%d",res);

    return 0;
}

利用二元组排序的特点,可以不用自己重载<号

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

typedef pair<int,int> PII;

const int N=50010;
int n;
PII cow[N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int w,s;
        scanf("%d%d",&w,&s);
        cow[i].first=w+s;
        cow[i].second=s;
    } //二元组排序时,优先比较first,可以不用结构体再重载<号

    sort(cow+1,cow+n+1);  //因为从1开始读入的,所以都加了1

    int res=-2e9,risk=0;  //res保存最终答案,risk表示每头牛的风险值
    for(int i=1;i<=n;i++)
    {
        risk+=cow[i-1].first-cow[i].second; //risk[i]=risk[i-1]+cow[i-1].w+cow[i-1].s-cow[i].s
        res=max(risk,res);  //res取风险值最大的
    }

    printf("%d",res);

    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1e6+10;
int n;
int a[N];

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);

    sort(a,a+n);

    int res=0;
    for(int i=0;i<n;i++) res+=abs(a[i]-a[n/2]);//n为奇数和偶数都能正确处理

    printf("%d",res);

    return 0;
}


活动打卡代码 AcWing 913. 排队打水

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

typedef long long LL;

const int N=1e5+10;
int n;
int t[N];

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&t[i]);

    sort(t,t+n);

    LL res=0;   //测试样例有较大数,会爆int
    for(int i=n-1;i>=0;i--)
        res+=t[i]*(n-i-1);   //按公式相加即可

    printf("%lld",res);  //记得res是long long 型的,要输出%lld,不然会溢出

    return 0;
}


活动打卡代码 AcWing 148. 合并果子

huffman树, 贪心

#include <iostream>
#include <queue>

using namespace std;

int n;

int main()
{
    scanf("%d",&n);
    priority_queue<int,vector<int>,greater<int>> heap;  //小根堆
    while(n--)
    {
        int a;
        scanf("%d",&a);
        heap.push(a);
    }

    int res=0;
    while(heap.size()>1)
    {
        int a=heap.top();heap.pop();
        int b=heap.top();heap.pop();
        heap.push(a+b);
        res+=a+b;  //累加本次合并所耗费的体力
    }

    printf("%d",res);

    return 0;
}


活动打卡代码 AcWing 907. 区间覆盖

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

const int N=1e5+10;
int s,t,n;   //分别表示:被覆盖区间左端点,右端点; 所给区间数量

struct Range{
    int l,r;

    bool operator <(const Range &x)const{
        return l<x.l;
    }
}range[N];  //结构体表示表示区间[l,r],且重载了<号,按左端点进行比较

int main()
{
    scanf("%d%d%d",&s,&t,&n);
    for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);

    sort(range,range+n);  //按区间左端点大小进行排序

    bool suc=false; int res=0;  //suc作为成功标记,res记录最小区间数量
    for(int i=0;i<n;i++)   //枚举每一个区间
    {
        int r=-2e9;   //哨兵初始为-∞,保证至少能选出一个区间并更新r
        while(i<n && range[i].l<=s)
        {
            r=max(r,range[i].r);
            i++;
        }

        if(r<s) break;  //r没有被更新,说明已经不存在能涵盖s的区间了

        res++;  //更新成功,所需区间数量+1

        if(r>=t)  //若此时右端点已经超过t,说明已经将最初的[s,t]完全涵盖了
        {
            suc=true;
            break;
        }

        s=r;   //若还没有超过t,则将s更新为下一轮需要被涵盖的最右端点
        i--;   //while退出时i多加了一次,需要减去,避免漏掉一个区间
    }

    if(!suc) res=-1;  //通过上述循环,若不成功,则输出-1
    printf("%d",res);

    return 0;
}


活动打卡代码 AcWing 906. 区间分组

用数组会超时,这里用堆。420ms

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int N=1e5+10;
int n;

struct Range{
    int l,r;

    bool operator < (const Range& x) const{
        return l<x.l;
    }
}range[N];   //定义区间[l,r],并且重载<号,按照左端点比较

int main()
{
    scanf("%d",&n);

    for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);

    sort(range,range+n);  //将区间按左端点排序

    priority_queue<int,vector<int>,greater<int>> cnt;  //小根堆,记录分组情况
    cnt.push(range[0].r);  //先将将第一个区间插入(后面就不需要判空了)
    for(int i=1;i<n;i++)  //r[0]已经插入了,从i开始
    {
        int x=cnt.top();  //x为最小的右端点

        if(x<range[i].l) cnt.pop(),cnt.push(range[i].r);//说明当前区间可以加入x所在分组中,将最小的右端点更新为range[i].r
        else cnt.push(range[i].r);  //否则,说明需要建立新的分组,当前右端点即新分组的右端点
    }

    printf("%d",cnt.size());  //可见堆中右端点的个数即分组的数量

    return 0;
}

题解区作者:未来重要。 这份280ms

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100100;

int n;
int b[2 * N], idx;

int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n ; i ++)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        b[idx ++] = l * 2;//标记左端点为偶数。
        b[idx ++] = r * 2 + 1;// 标记右端点为奇数。
    }

    sort(b, b + idx);

    int res = 1, t = 0;
    for(int i = 0; i < idx ; i ++)
    {
        if(b[i] % 2 == 0) t ++;
        else t --;
        res = max(res, t);
    }
    printf("%d",res);
    return 0;
}



好家伙,默写了一遍上一题

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

const int N=1e5+10;
int n;

struct Range{
    int l,r;

    bool operator < (const Range &x)const{
        return r<x.r;
    }
}range[N];

int main()
{
    scanf("%d",&n);

    for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);

    sort(range,range+n);

    int res=0,ed=-2e9;
    for(int i=0;i<n;i++)
        if(range[i].l>ed)
        {
            ed=range[i].r;
            res++;
        }

    printf("%d",res);

    return 0;
}


活动打卡代码 AcWing 905. 区间选点

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

const int N=1e5+10;
int n;

struct Range{
  int l,r;

  bool operator < (const Range &x)const{
      return r<x.r;
  }
}range[N];   //定义结构体表示区间[l,r],并且重载了<号,按区间的右端点比较

int main()
{
    scanf("%d",&n);

    for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);

    sort(range,range+n);  //按区间右端点,进行排序

    int res=0,ed=-2e9;   //res保存选点的个数;ed表示每次选择的点,初始为-∞
    for(int i=0;i<n;i++)
        if(ed<range[i].l)   //if true,说明当前的ed已经不属于下个区间了,需要再选择一个点
        {
            ed=range[i].r;  //每次新选择的点都为当前区间的右端点
            res++;    //每选择一个点,记录的点数加1
        }

    printf("%d",res);   //返回答案

    return 0;
}


活动打卡代码 AcWing 338. 计数问题

按照yls思路的一份代码(好像和dp没啥关系

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


/*获取数组中l位到r位的数字,例如数组中是nums={4,3,7,5,1,2,6,4},其中低位在保存在前
实际上保存的是整数46217543,如果我们要获取其中的最高三位462,则get_num(nums,7,5)
此时会返回整数462*/
int get_num(vector<int> nums,int l,int r)
{
    int res=0;
    for(int i=l;i>=r;i--)
        res=res*10+nums[i];
    return res;
}

int pow10(int x)  //求10^x
{
    int res=1;
    while(x--)
        res*=10;
    return res;
}

int count(int n,int x)  //返回整数1~n中,数字x出现的次数
{
    if(!n) return 0;  //若n==0,由定义次数为0

    vector<int> nums;  //将数字n保存在数组nums中(低位在前,高位在后)
    while(n)
    {
        nums.push_back(n%10);
        n/=10;
    }
    n=nums.size();  //将n保存为原始数字n的位数

    int res=0;  //记录整数1~n中,数字x出现的次数
    for(int i=n-1-!x;i>=0;i--)  //枚举x在每一位的情况,且当x=0时,i从第二高位开始
    {
        if(i<n-1)   //1:x左边的高位小于的原数高位的情况(i<n-1,保证x不是在最高位)
        {
            res+=get_num(nums,n-1,i+1)*pow10(i);  //高位的情况(x左边)*低位的情况(x右边)
            if(!x) res-=pow10(i);  //特判当x==0时,高位实际上少一种全选0的情况,应该是[ get_num(nums,n-1,i+1) -1]*pow10(i)
        }
        if(x<nums[i]) res+=pow10(i);  //2.1:x左边的高位相等,且x小于i位置的数
        else if(x==nums[i]) res+=get_num(nums,i-1,0)+1; //2.2:x左边的高位相等,且x等于i位置的数,记得+1
    }
    return res;  //所有情况都已经处理完毕,返回结果即可
}

int main()
{
    int a,b;
    while(cin >> a >> b,a||b)  //当a和b都为0时退出循环
    {
        if(a>b) swap(a,b);  //保证a<b

        for(int i=0;i<10;i++)  //枚举0~9每个数字
            printf("%d ",count(b,i)-count(a-1,i));  //前缀和思想
        puts("");
    }

    return 0;
}

题解区大佬代码

#include <iostream>
#include <vector>

using namespace std;

int base[10];
int f[10][10];
int g[10][10];

void init()
{
    base[0] = 1;
    for(int i = 1 ; i <= 9 ; i++) base[i] = base[i-1]*10;

    //从00……0 - 99……9 的各位数字有多少个,其中i为数字个数(包含前导零)
    for(int i = 0 ; i <= 9 ; i++) f[1][i] = 1;
    for(int i = 2 ; i <= 9 ; i++)
        for(int j = 0 ; j <= 9 ; j++)
            f[i][j] = f[i-1][j]*10 + base[i-1];

    //从1 - 99……9 的各位数字有多少个,其中i为数字个数(不包含前导零)
    for(int i = 1 ; i <= 9 ; i++) g[1][i] = 1;//循环从1开始
    for(int i = 2 ; i <= 9 ; i++) {
        g[i][0] = g[i-1][0] + f[i-1][0]*9;
        for(int j = 1 ; j <= 9 ; j++)
            g[i][j] = g[i-1][j] + f[i-1][j]*9 + base[i-1];
    }
}

vector<int> dp(int n)
{
    vector<int> ans(10,0); //记录答案
    if(n<=0) return ans; //边界条件

    vector<int> nums;
    while(n) nums.push_back(n%10), n/=10;

    vector<int> last(10,0); //记录前缀中各个数字个数

    //统计1 - 99……9(n-1个9)里面各个数字有多少个
    for(int i = 0 ; i <= 9 ; i++) ans[i] = g[nums.size()-1][i];
    //统计大于10……0(n-1个0) 的树里各个数字有多少个
    for(int i = nums.size()-1 ; i >=0 ; i--) {
        //循环变量i可以表示剩下的数字有多少个
        int x = nums[i];
        for(int j = i==nums.size()-1 ; j < x ; j++) { //第一次循环不能有0
            //前缀部分
            for(int k = 0 ; k <= 9 ; k++)
                ans[k] += last[k] * base[i];
            //当前位置部分
            ans[j] += base[i];
            //后缀部分
            for(int k = 0 ; k <= 9 ; k++)
                ans[k] += f[i][k];
        }
        //更新前缀计数器
        last[x] ++;

        //统计叶子节点(这个数本身)
        if(!i) for(int k = 0 ; k <= 9 ; k++) ans[k] += last[k];
    }
    return ans;
}

vector<int> ask(int a, int b)
{
    auto x = dp(b);
    auto y = dp(a-1);
    vector<int> ans;
    for(int i = 0 ; i <= 9 ; i++) ans.push_back(x[i]-y[i]);
    return ans;
}

void print(vector<int> ans)
{
    for(auto x:ans) printf("%d ",x);
    puts("");
}

bool check(int x)
{
    auto t = ask(x,x);
    vector<int> cnt(10,0);
    while(x) cnt[x%10]++,x/=10;
    for(int i = 0 ; i <= 9 ; i++)
        if(cnt[i] != t[i])
            return false;
    return true;
}

int main()
{
    init();

    //这里是一个DEBUG函数
    // for(int i = 1 ; i <= 1000000 ; i*=10) {
    //     if(!check(i))
    //         printf("ERROR:%d\n",i);
    // }

    int a,b;
    while(cin >> a >> b, a||b) {
        if(a>b) swap(a,b);
        auto t = ask(a,b);
        print(t);
    }

    return 0;
}

作者:aleihentai
链接:https://www.acwing.com/solution/content/4934/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


活动打卡代码 AcWing 901. 滑雪

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

const int N=310;

int n,m;
int h[N][N];  //保存每个点的高度
int f[N][N];  //f[i][j]表示:以点(i,j)为起点开始滑,的最长滑雪长度
int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};  //上下左右下个方向

int dp(int x,int y)   //递归计算f[x][y],并且保存可以由(x,y)走到的点 的f值
{
    int &v=f[x][y];   //v相当于f[x][y]的代号,可以简化代码
    if(v!=-1) return v;  //说明f[x][y]已经计算过了,直接返回f[x][y]的值

    v=1;  //否则,f[x][y]至少是1,即四个方向都不能走的情况
    for(int i=0;i<4;i++)  //枚举四个方向
    {
        int a=x+dx[i],b=y+dy[i];   //(a,b)为下一个方向的点
        if(1<=a && a<=n && 1<=b && b<=m && h[a][b]<h[x][y])  //仍在矩阵内,且高度严格小于(x,y)处的
            v=max(v,dp(a,b)+1);  //(x,y)到(a,b)有一步距离
    }
    return v;  //此时已经计算并保存了f[x][y],返回即可
}

int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&h[i][j]);

    int res=0;  //保存最大长度
    memset(f,-1,sizeof f);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            res=max(res,dp(i,j));   //计算每个点为起点时的f值,保存最大者在res中

    printf("%d",res);

    return 0;
}