欢迎来到
银狐的个人博客

第三届全国大学生算法设计与编程挑战赛个人银首——>金奖

话说每次都是周末一大早吗,前一晚嗨了,第二天就起迟了,本来以为罚时令我与金擦肩而过~

但11月2号下午查重后的获奖名单,检索自己的名字,居然变成了金奖(意外,有点惊喜),看来有同学不小心被查重除名了…

G题如果L在2e5的话,还能用前缀和+dp做,但是如此大的数据范围,一下子整不会了,想了会儿没有啥好办法就直接爬上床补觉了~

某规律题找完规律也不咋会做,很果断地give up~

a[1]=1;a[2]=5;for(int i=3; i<=1000; i++)  a[n]=4*a[n-1]-2*a[n-2]+a[n-3];

目录

A-登神长阶

C-网络流

E-老鹰捉小鸡

H-买装备


A-登神长阶

签到题,注意时间单位啊,退役有好一段时间了,敏感度变差了,本来开A就迟,还因为单位没换算罚时+1(欲哭无泪…别说了,菜狗的锅自己背

#include <bits/stdc++.h>#define ll long longusing namespace std;int main(){ll a=1,b=1,c=1,t;t=read();t/=60;if(t==0) {cout<<"0";return 0; }if(t<=3) {cout<<"1";return 0;}ll ansa=0; for(int i=4; i<=t; i++){ansa = (a%425+b%425+c%425)%425;a=b%425;b=c%425;c=ansa%425;}printf("%lld\\n", ansa%425);return 0;}

C-网络流

这题题意给的挺明确的,没像团队赛一样谜语人(开个玩笑)手要快!

#include <bits/stdc++.h>#define ll long longusing namespace std;int n;int main(){    multiset<int> se;    scanf("%d", &n);    vector<int> a(n);    for(auto &x: a)  scanf("%d", &x), se.insert(x);    int ma = 0;    for(int i=0; i<n; i++)  {        se.erase(se.find(a[i]));        ma = max(ma, *se.begin());        se.insert(a[i]);    }    printf("%d\\n", ma);    return 0;}

E-老鹰捉小鸡

一开始以为是区间dp,结果是背包啊… 只要找到合理的方案数,就一定能找到对应解

#include <bits/stdc++.h>#define ll long longusing namespace std;int main(){    int n; scanf("%d", &n);    vector<int> b(n+1), a(n+1);    for(int i=1; i<=n; i++)        scanf("%d", &b[i]);    for(int i=1; i<=n; i++)        scanf("%d", &a[i]);    vector<int> dp(n + 1);    for(int i=1; i<=n; i++)    {        for (int j=n; j>=b[i]; j--)            dp[j] = max(dp[j], dp[j-b[i]] + a[i]);    }    printf("%d\\n", dp[n]);    return 0;}

H-买装备

啊这…板子题吗,上树剖板子,保过!

#include<bits/stdc++.h>#define ll long longusing namespace std;const int maxn = 4e5+88;struct yz{    ll w,loc;}ok[100010];bool cmp(yz x,yz y){    return x.w<y.w;}bool cmp(string a,string b) { //按字关键词长度升序排序int la=a.size(),lb=b.size();if(la==lb)  return a<b;return  la<lb;}ll read() {    ll x=0,f=1;    char ch=getchar();    while(ch<'0'||ch>'9') {    if(ch=='-')f=-1;    ch=getchar();}    while(ch>='0'&&ch<='9') {    x=x*10+ch-'0';    ch=getchar();}    return x*f;}int check(string a,string b){int len1=a.size(), len2=b.size();if(len1 >= len2) return 0;int f=0;for(int i=0;i<len1;i++)    if(a[i]!=b[i]) {f=1;  break;}return !f;}ll n,m,r,fa[maxn],dep[maxn],son[maxn],size[maxn];ll top[maxn],id[maxn],cnt,w[maxn];struct node {    ll l,r,lz;    ll ma;} a[maxn*4];vector<int>e[maxn];void dfs1(int u,int p) {    dep[u] = dep[p] +1,fa[u]=p;    for(int v:e[u]) {        if(v==p) continue;        dfs1(v,u);        size[u]+=size[v];        if(son[u]==0||size[v]>size[son[u]]) son[u] = v;    }}void dfs2(int u,int p) {    id[u] = ++cnt,w[cnt] =0,top[u] = p;    if(son[u]==0) return ;    else dfs2(son[u],p);    for(int v:e[u]) {        if(v==fa[u]||son[u]==v) continue;        dfs2(v,v);    }}long double aw(long double x1,long double y1,long double x2,long double y2) {    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}long double cv(long double a,long double b,long double c) {    return acos((b*b+c*c-a*a)/(2*b*c));}void push_up(int st) {    a[st].ma = max(a[st*2].ma,a[st*2+1].ma);}void push_down(int  st) {    if(a[st].lz==0) return ;    a[st*2].lz+=a[st].lz,a[st*2+1].lz+=a[st].lz;a[st*2].ma+=a[st].lz;a[st*2+1].ma+=a[st].lz;    a[st].lz=0;}void build(int st,int l,int r) {    a[st].l=l,a[st].r=r,a[st].lz=0;    if(l==r) {        a[st].ma=0;        return ;    }    int mid =(l+r)>>1;    build(st*2,l,mid),build(st*2+1,mid+1,r);    push_up(st);}void update(int st,int l,int r,int ql,int qr,ll num) {    if(ql<=l&&qr>=r) {        a[st].lz+=num;        a[st].ma +=num;        return ;    }    push_down(st);    int mid = (l+r)>>1;    if(ql<=mid) update(st*2,l,mid,ql,qr,num);    if(qr>mid) update(st*2+1,mid+1,r,ql,qr,num);    push_up(st);}double lenth(double x1,double y1,double x2,double y2) {return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}ll  query(int st,int l,int r,int ql,int 第三届全国大学生算法设计与编程挑战赛个人银首——>金奖 第1张图片-银狐博客qr) {    if(ql<=l&&qr>=r) return a[st].ma;    push_down(st);    ll mid = (l+r)>>1,ans=0;    if(ql<=mid) ans=max(ans,query(st*2,l,mid,ql,qr));    if(qr>mid) ans=max(ans,query(st*2+1,mid+1,r,ql,qr));    return ans;}void modify2(ll x,ll z) {    update(1,1,cnt,id[x],id[x]+size[x]-1,z);}ll q2(int x) {    return  query(1,1,cnt,id[x],id[x]+size[x]-1);}int main() {//#define rep(i, a, b) for(int i=(a);i<=(b);++i)//#define dep(i, a, b) for(int i=(a);i>=(b);--i)    n=read(第三届全国大学生算法设计与编程挑战赛个人银首——>金奖 第2张图片-银狐博客);   r = 1;    for(int i=1; i<=n; i++)  size[i]=1;    for(int i=1 ; i<n ; i++) {        int u,v;        u=read(),v=read();        e[u].push_back(v);        e[v].push_back(u);    }    dfs1(r,0);dfs2(r,r);    build(1,1,cnt);    m=read();    for(int i=1 ; i<=m ; i++) {        int op,x,y,z;        op=read();        if(op==1) {            x=read(),z=read();            modify2(x,z);        } else  {            x=read();            printf("%lld\\n",q2(x));        }    }    return 0;}

别想了,下面没啦~

这次银首上升到了金,体验感不错,hhh

下个赛季再见啦~

赞(0) 打赏
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《第三届全国大学生算法设计与编程挑战赛个人银首——>金奖》
文章链接:https://www.yinhu3.com/2266.html
本站资源仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。
如果文章侵犯到你的权益,请查看本站免责声明:《免责声明》

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

愿意请我喝杯矿泉水吗

支付宝扫一扫打赏