头像

hutianshuo




离线:10小时前


活动打卡代码 AcWing 1015. 摘花生

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

struct points {//定义采集点的结构体
    int x, y, num;// x y 坐标,以及花生数
};

bool comp(points a, points b) {//将采集点按花生数的多少进行排序
    return (a.num > b.num);
}

int walk(points a, points b) {//两采集点间的距离
    return (abs(a.x - b.x) + abs(a.y - b.y));
}

int main() {
    int T; cin >> T;
    points p[2502];//花生园
    int h, l, steps;//行数,列数,步数
    int numbers;//花生数目

    while (T--) {
        cin >> h >> l >> steps;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < l; j++) {
                cin >> p[i*l + j + 1].num;
                p[i*l + j + 1].x = i + 1;
                p[i*l + j + 1].y = j + 1;
            }
        }

        sort(p + 1, p + h * l + 1, comp);//按花生数目,从大到小排序采集点
        p[0].x = 0; p[0].y = p[1].y;//起点
        p[h*l + 1].x = 0; p[h*l + 1].y = p[h*l].y;//终点(可能提前结束)
        numbers = 0;

        int tem = steps - walk(p[0], p[1]) - 1;//走到第一个采集点后剩余步数
        for (int i = 1; i <= h * l; i++) {
            if (p[i].num == 0)break;//之后的采集点没花生,跳过
            if (tem < p[i].x) {//回不到路边
                numbers = 0;
                break;
            }
            else if (tem < p[i + 1].x + 1 + walk(p[i], p[i + 1])) {//下一采集点回不到路边
                numbers += p[i].num;
                break;
            }
            else {//下一采集点能回到路边,去往下一采集点
                numbers += p[i].num;
                tem -= (walk(p[i], p[i + 1]) + 1);
            }
        }
        cout << numbers << endl;
    }
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 420. 火星人

#include <bits/stdc++.h>
using namespace std;
int n,m,a[10001];
void laugh_at_c_pascal()
{
    cout<<"The OIers of C++ can use STL!!!\n;
}
int main()
{
    int i;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    while (m--) next_permutation(a+1,a+n+1);//全排列求下一组情况
    for (i=1;i<n;i++) printf("%d ",a[i]);
    printf("%d",&a[n]);
    //laugh_at_c_pascal();//嘲笑c语言和pascal语言
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 482. 合唱队形

#include<bits/stdc++.h>
using namespace std;
int n,a[110],f[110][2],MAX;//f[i][1]表示上升子序列的个数,f[i][2]表示下降子序列的个数
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        int mx=0;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])
            {
                mx=max(mx,f[j][1]);//求上升子序列的最大值,也就是第一部分可以留下的最大人数
            }
        }
        f[i][1]=mx+1;
    }
    for(int i=n;i>=1;i--)
    {
        int mx=0;
        for(int j=n;j>i;j--)
        {
            if(a[j]<a[i])
            {
                mx=max(mx,f[j][2]);
            }
        }
        f[i][2]=mx+1;
        MAX=max(MAX,f[i][1]+f[i][2]-1);//f[i][1]+f[i][2]-1表示当a[i]最高点时留下的人数,这里减一,因为上升和下降的个数都包括了最高点,所以减去一个
    }
    cout<<n-MAX<<endl;
    return 0;
 } 

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1603. 整数集合划分

#include <iostream>
#include <algorithm>
using namespace std;
int arr[100005];
int sum[100005];
int main(void)
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    sort(arr+1, arr + n + 1);//排序
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + arr[i];//利用前缀和方便求出两个区间的和
    }
    //如果为奇数,就划分不出两个数量一样的区间,输出1。答案为后n-n+1个数的和与前n-1个数的和的差值
    if (n % 2)cout << 1 << ' ' << sum[n] - 2*sum[(n - 1) / 2];
     //如果为偶数,可以划分出两个数量一样的区间,输出0。答案为后n-/2个数的和与前n、2个数的和的差值
    else cout << 0 << ' ' << sum[n] - 2*sum[n / 2];
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1353. 滑雪场设计

#include<iostream>
using namespace std;
const int N = 10e4 + 10;
int g[N] = {0};
int main(){
    int n,ans = 0x7f7f7f7f;
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> g[i];
    for(int l = 0 ; l <= 100 -17; l++){
        int temp = 0;
        for(int i = 0 ; i < n ; i++){
            // 比当前的低
            if(g[i] < l)
                temp += (l - g[i]) * (l - g[i]);
            // 比当前高17的还高
            if(g[i] > l + 17)
                temp += (l + 17 -g[i]) * (l + 17 -g[i]);
        }
        ans = min(temp,ans);
    }
    cout<<ans;
    return 0; 
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 426. 开心的金明

#include<iostream>
#include<algorithm>
using namespace std;
int w[30],v[30],f[50000];//w数组为重要度,v数组为money,f是用来dp的数组
int n,m;//n是总物品个数,m是总钱数
int main()
{
    cin>>m>>n;//输入
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
        w[i]*=v[i];//w数组在这里意义变为总收获(重要度*money)
    }
       //01背包(参照第二类模板“一维数组优化”)
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)//注意从m开始
        {
            if(j>=v[i])
            {
                f[j]=max(f[j],f[j-v[i]]+w[i]);//dp
            }
        }
    }
    cout<<f[m]<<endl;//背包大小为m时最大值
    return 0;
} 
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



hutianshuo
1个月前

`

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
int n,sum[500001],a[500001],m;
void pushup(int id)
{
sum[id]=sum[id<<1]+sum[id<<1|1];
}
void build(int id,int l,int r)
{
if(l==r)
{
sum[id]=a[l];
return;
}
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
pushup(id);
}
void update(int id,int l,int r,int x,int v)
{
if(l==r)
{
sum[id]+=v;
}
int mid=(l+r)>>1;
if(x>=mid)
{
update(id<<1,l,mid,x,v);
}
else
{
update(id<<1|1,mid+1,r,x,v);
}
pushup(id);
}
int query(int id,int l,int r,int x,int y)
{
if(x>=l&&y<=r)
{
return sum[id];
}
int ans=0;
int mid=(l+r)>>1;
if(x<=mid)
{
ans+=query(id<<1,l,mid,x,y);
}
if(y>mid)
{
ans+=query(id<<1|1,mid+1,r,x,y);
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i)
{
scanf(“%d”,&a[i]);
}
build(1,1,n);
int op;
for(int i=1;i<=m;i
)
{
scanf(“%d”,&op);
if(op==1)
{
int x,y;
if(x>y)swap(x,y);
printf(“%d”,query(1,1,n,x,y));
}
else
{
int x,v;
scanf(“%d %d”,&x,&v);
update(1,1,n,x,v);
}
}
}
`