头像

Hicode002

hicode




离线:4天前



算法1

(dp) $O(tnm)$
Luogu5662纪念品
题面https://www.luogu.com.cn/problem/P5662
这道题没什么细节
是dp
考虑T=1时
显然一天无论怎么买怎么卖最后的值还是m,输出m
t=2很关键
两天时是完全背包
总体积是m,因为第一天买花费钱数必须不能超过m
单体积为第一天的价格
单价值为第二天-第一天价格,显然当有物品的单价值<0时意味着买卖这个物品会赔钱,所以跳过这个物品,不参与dp
而每个物品可以买无限个
所以是完全背包而非01背包
进行完全背包
最后dp[m]为最大利润
输出m+dp【m】

推广到一般情况
当第i天买第k天卖
由于每天可以无限次买卖
所以相当于第i天买第i+1天卖第i+1天再买,第i+2天再卖
所以2天2天的完全背包
把每次完全背包后的利润加在一起
m也要随之更新
每一次完全背包m都要加上这次的利润
最后输出和

注意:!!dp数组的大小不是纪念品的个数而是总体积大小,所以开到10^4而非100,在这里wa了一次

时间复杂度

完全背包优化后为$O(nm)$
n是物品个数,m是体积(这里m为金币数)
执行t-1次
所以为$O(tnm)$

C++ 代码


#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[10009],a[103][103];
using namespace std;
int main(){
    int t,n,m;
    cin>>t>>n>>m;
    for(int i=1;i<=t;++i){
        for(int j=1;j<=n;++j){
            cin>>a[i][j];
        }
    }
    //int tot=0;
    for(int i=1;i<=t-1;++i){
        memset(dp,0,sizeof dp);
        int v=m;
        for(int j=1;j<=n;++j){
            int vi=a[i][j];
            int wi=a[i+1][j]-a[i][j];
            if(wi<=0)continue;
            for(int z=vi;z<=v;++z){
                dp[z]=max(dp[z],dp[z-vi]+wi);
            }
        }
        m=m+dp[v];

    }
    cout<<m<<endl;
    return 0;
}




算法1

(暴力枚举) $O(玄学)$
Luogu5661公交换乘
题面https://www.luogu.com.cn/problem/P5661
模拟题
注意几点
只有乘地铁才会获得优惠券,优惠券只能用来乘公交车
优惠卷有效期45分钟
使用优惠券除了时间限制还有价格限制,只有当前公交车票价<=优惠券价格才能用
优惠券可以累积---------队列
如果可以使用优惠券则一定使用优惠券,并且优先用最早的合法优惠券,这意味着在优惠券合法的情况下,先用最早获得的
在最早的优惠券不合法的情况下,一定向后找合法的优惠券,如果找不到就代表这次公交车不使用优惠券(去年就栽在这)


所以一个双端deque结构体队列,存时间与价格,坐地铁时入队,统计地铁价格,坐公交时检查队列并出队
不能用普通队列因为queue不能用迭代器
规则:
当公交车时间-队头时间>45时不断出队直到公交车时间-队头时间<=45或队空(如果这次公交车-队头时间都大于45那么后面的公交车-队头时间也大于45,所以这样的优惠券作废)
若队空直接加上此次公交车价格
若队不空,开始检查价格
如果队头价格>=公交车价格就出队并跳过本次循环(使用了优惠券)
否则就用stl的iterator迭代器从队头开始向后遍历整个队列直到找到一个优惠券价格大于等于公交车价格
那么就用stl的erase删除掉这个优惠券(注意erase左闭右开erase(i,i+1)代表删除i)
然后跳过本次循环
如果遍历完队列找不到合法优惠券就直接加上此次公交车价格


最后输出价格和。

时间复杂度

O(n)~O(玄学)

C++ 代码

#include<iostream>
#include<cstdio>
#include<iterator>
#include<deque>
#include<queue>
using namespace std;
struct p{
    int t;//time
    int w;//price

};
deque<p>pro;
int main(){
    int n,tot=0;
    cin>>n;
    for(int i=0;i<n;++i){
        int tran;
        cin>>tran;
        p po;
        cin>>po.w>>po.t ;
        if(tran==0){//sub
            pro.push_back(po);
            tot+=po.w;
        }else{//bus
            while(1){
                if(!pro.empty() ){
                    if(po.t-pro.front().t>45){
                        pro.pop_front() ;
                    }else{
                        break;
                    }
                }else{
                    break;
                }
            }
            if(pro.empty() ){
                tot+=po.w;
                continue;
            }
            if(po.w<=pro.front().w){
                pro.pop_front() ;
                continue;
            }else{
                deque<p> ::iterator to;
                int fl=1;
                for(to=pro.begin() ;to!=pro.end() ;++to){
                    if(po.w >(*to).w){
                        continue;
                    }else{
                        fl=0;
                        pro.erase(to,to+1); 
                        break;
                    }
                }
                if(fl){
                    tot+=po.w;
                }else{
                    continue;
                }
            }


        }
    }
    cout<<tot<<endl;
    return 0;
}


新鲜事 原文

Hicode002
1个月前
有人吗? n/ln n=k 已知k怎么求n 近似值即可



Hicode002
10个月前

算法1

(暴力枚举) $O(nk)$

这道题很坑,40分很好做,只要桶排一遍即可,70分只要桶排前挑出符合时间的即可,100分用到stl了,用queue存每个人的时间与国籍,每次找不符合时间的,把它出队,桶内–;
注意:
1.struct存时间和国籍
2.统计的是不符合时间的而不是符合时间的
3.每次以前一次的统计为基础,减去不符合时间的不同国籍数就是这次的不同总人数
4.queue要记得判断是否empty(),不直接调用front(),这样会re,当queue 空时,只需统计这次国籍不同数量即可,不用找之前的。

参考文献

C++ 代码

#include<iostream>//can`t
#include<cstdio>//can`t
#include<cstring>//can`t
#include<string>//can`t
#include<cmath>
#include<fstream>
#include<sstream>
#include<ctime>//can`t
#include<cstdlib>//can`t
#include<cfloat>//can`t
#include<climits>//can`t
#include<iomanip>
#include<stack>//can`t
#include<queue>//can`t
#include<deque>//can`t
#include<map>//can`t
#include<set>//can`t
#include<bitset>//can`t
#include<vector>//can`t
#include<algorithm>//can`t
#define ll long long
#define ui unsigned
#define re register
#define fop(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define fc() fclose(stdin),fclose(stdout)

using namespace std;//can`t

inline void myread(int&x){
    char a,f=1;
    x=0;
    a=getchar();
    if(a>='0'&&a<='9')x=a-48;
    else if(a=='-')f=-1;
    while(1){
        a=getchar();
        if(a>='0'&&a<='9')x=x*10+a-48;
        else {x=x*f;return;
        }
    }
}
inline void mywrite(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)mywrite(x/10);
    putchar(x%10+48);
}
struct people{
    int time,ji;
};
queue<people>port;
int gjs[100007];
void tests(const int& totp){
    cout<<'\n';
    for(re int i=0;i<100007;++i){

        if(gjs[i]!=0)cout<<"test:"<<i<<" geshu:"<<gjs[i]<<' ';
    }
    cout<<endl<<"totp:"<<totp<<"\n";
}
int main(){
    memset(gjs,0,sizeof(gjs));
    int n,totp=0;
    myread(n);
    for(re int i=0;i<n;++i){
        int t,k;
        myread(t),myread(k);
        if(!port.empty() ){

            while(1){
                if(port.empty() ||port.front() .time>t-86400)break;

                else{

                    --gjs[port.front() .ji];
                    if(gjs[port.front() .ji]==0)--totp;
                    port.pop() ;

                }
            }
        }
        for(re int j=0;j<k;++j){
            int x;
            myread(x);
            people lin;
            lin.ji =x;
            lin.time =t;
            port.push(lin);
            if(gjs[x]==0)++totp;
            ++gjs[x];
        //  tests(totp);
        }
        mywrite(totp),putchar('\n');
    }
    return 0;
}





Hicode002
10个月前

样例

in:
5 1 1

out:
1


算法1

(暴力枚举、模拟) $O((n+1)/2)$

这道题很简单,不用找很多规律,太难了,更不要开二维数组(mle),其实只要模拟一下,并且找一个简单规律即可
首先我们发现一个矩阵有固定圈数,偶数时为n/2,奇数时(n+1)/2,整合得(n+1)/2
然后找到发现每一圈的格数为4(t-1)(t为一行的格数)
再发现从最外一圈每向内缩一圈,t就-=2
每一圈只有4个情况:
1.第i行第e列(i为每圈首行)
2.第e行第i列(i为每圈首列)
3.第e行第in列(in为每圈末列)
4.第in行第e列(in为每圈末行)
所以枚举即可

时间复杂度

总共进行2次循环,第一次为圈数$(n+1)/2$,第二次为i,j所在圈数次,所以总时间复杂度约等于2*n,舍掉2得$O(n)$

C++ 代码

#include<iostream>//can`t
#include<cstdio>//can`t
#include<cstring>//can`t
#include<string>//can`t
#include<cmath>
#include<fstream>
#include<sstream>
#include<ctime>//can`t
#include<cstdlib>//can`t
#include<cfloat>//can`t
#include<climits>//can`t
#include<iomanip>
#include<stack>//can`t
#include<queue>//can`t
#include<deque>//can`t
#include<map>//can`t
#include<set>//can`t
#include<bitset>//can`t
#include<vector>//can`t
#include<algorithm>//can`t
#define ll long long
#define ui unsigned
#define re register
#define fop(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define fc() fclose(stdin),fclose(stdout)

using namespace std;//can`t

inline void myread(int&x){
    char a,f=1;
    x=0;
    a=getchar();
    if(a>='0'&&a<='9')x=a-48;
    else if(a=='-')f=-1;
    while(1){
        a=getchar();
        if(a>='0'&&a<='9')x=x*10+a-48;
        else {x=x*f;return;
        }
    }
}
inline void mywrite(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)mywrite(x/10);
    putchar(x%10+48);
}
int main(){
    #ifdef DEBUG
    fop(matrix);
    #endif
    int n,x,y,fl=-1,fl1=-1,fl2=-1;
    cin>>n>>x>>y;
    int q=(n+1)/2;
    for(re int i=1,j=n;i<=q;++i,--j){
        if(x==i&&y>=i&&y<=j){
            fl=i;
            fl1=j;
            fl2=1;
            break;
        }else if(y==j&&x>=i&&x<=j){
            fl=i;
            fl1=j;
            fl2=3;
            break;
        }else if(x==j&&y>=i&&y<=j){
            fl=i;
            fl1=j;
            fl2=4;
            break;
        }else if(y==i&&x>=i&&x<=j){
            fl=i;
            fl1=j;
            fl2=2;
            break;
        }
    }
    int ans=0;
    for(re int i=1,j=n;i<fl;++i,j-=2){
        ans+=4*j-4;

    }

    if(fl2==1){
        cout<<ans+1+(y-fl);
    }else if(fl2==3){
        int r=ans+1+(fl1-fl);
        cout<<x-fl+r;
    }else if(fl2==4){
        int rs=ans+1+(fl1-fl);
        int rss=rs+fl1-fl;
        cout<<rss+(fl1-y);
    }else if(fl2==2){
        int ra=ans+1+(fl1-fl);
        int raa=ra+fl1-fl;
        int raaa=raa+fl1-fl;
        cout<<fl1-x+raaa;
    }

    fc();
    return 0;
}//hicode002所有,禁止抄袭





Hicode002
11个月前

题目描述

样例



算法1

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

水题不水啊

坑点:
1.爆$int$,开$long long$
2.注意暴力时不要枚举一次就重新计算气势值,这样会超时

时间复杂度

$O(N)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define ll long long
#define re register
ll a[N];//num of bing
int main(){
    ll n,m,p1,s1,s2,ls=0,hs=0;
    scanf("%lld",&n);
    for(re ll i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    scanf("%lld%lld%lld%lld",&m,&p1,&s1,&s2);
    a[p1]+=s1;
    for(re ll i=1;i<m;++i){
        ls+=a[i]*(m-i);
    }
    for(re ll i=m+1;i<=n;++i){
        hs+=a[i]*(i-m);
    }
    long long mini=0,minn=LLONG_MAX;

    for(re ll i=1;i<=n;++i){
          if(i<m){
            if(abs(ls+s2*(m-i)-hs)<minn){
                minn=abs(ls+s2*(m-i)-hs);
                mini=i;
            }
          }
          if(i==m){
            if(abs(ls-hs)<minn){//不要写成加号
                minn=abs(ls-hs);//不要写成加号
                mini=i;
              }
          }
          if(i>m){
            if(abs(hs+s2*(i-m)-ls)<minn){
                minn=abs(hs+s2*(i-m)-ls);
                mini=i;
              }
          }
    }
    cout<<mini<<endl;
    return 0;
} 



活动打卡代码 AcWing 419. FBI树

Hicode002
11个月前
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<algorithm>
/*#include<cmath>
#include<cmath>
#include<cmath>
#include<cmath>
#include<cmath>
#include<cmath>
&*/
#define ll long long
#define re register
#define un unsigned
#define fop(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define fc() fclose(stdin),fclose(stdout)
using namespace std;
void ser(int n,string str){
    if(n>0){
        ser(n-1,str.substr(0,1<<(n-1)));
        ser(n-1,str.substr(1<<(n-1)));

    }
    int zer=0,one=0;
    for(re int i=0;i<str.size();++i){
        if(str[i]=='0')++zer;
        else ++one;
    }
    if(zer&&one)printf("F");
    else if(zer)printf("B");
    else printf("I");
}
int main(){
    string str;
    int n;
    cin>>n;
    cin>>str;

    ser(n,str);

    return 0;

}



活动打卡代码 AcWing 417. 不高兴的津津

Hicode002
11个月前

条件:
1.a[i]+b[i]>8
2. a[i]+b[i]最大时的i值
3.相同时i小的在前面

#include<iostream>
#include<cstdio>
#include<cmath>
/*#include<cmath>
#include<cmath>
#include<cmath>
#include<cmath>
#include<cmath>
#include<cmath>
&*/
#define ll long long
#define re register
#define un unsigned
#define fop(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define fc() fclose(stdin),fclose(stdout)
using namespace std;
int main(){
    int a[10],b[10];
    for(re int i=1;i<=7;++i){
        scanf("%d%d",&a[i],&b[i]);
    }
    int maxn=-1,maxk=0;
    for(re int i=1;i<=7;++i){
        if(a[i]+b[i]>maxn&&a[i]+b[i]>8){
            maxn=a[i]+b[i];
            maxk=i;
        }
    }
printf("%d\n",maxk);
    return 0;

}




Hicode002
2019-09-14 10:41

题目描述

blablabla

样例

blablabla

算法1

非正解,使用随机化贪心,骗80–90分,这是没学dp的最好解决此种问题方法-------------

(暴力枚举) $O(懒得算)$
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cctype>
#include<cfloat>
#include<climits>
#include<iomanip>
#include<sstream>
#include<fstream>
#include<cstdlib>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<vector>
#include<ctime>

using namespace std;
struct bag{
    int v,w;
    double i;
    inline void autoi(){
        scanf("%d%d",&v,&w);
        i=1.0*w/v;
    }

}a[3000];
inline bool cmp(bag x ,bag y){
    return x.i >y.i ;
}
inline void mr(bag b[],int n){
    sort(b,b+n,cmp);
    for(int i=0;i<10;++i){
        swap(b[rand()%n],b[rand()%n]);
    }
}
inline int work(bag b[],int n,int v){
    int totalv=v,totalw=0;
    for(int i=0;i<n;++i){
        totalv-=b[i].v;
        if(totalv<0)break;
        else totalw+=b[i].w;
    }
    return totalw;
}
int main(){
    srand(time(0));
    int n,v;
    scanf("%d%d",&n,&v);
    for(int i=0;i<n;++i){
        a[i].autoi();
    }
    int max=-1;
    for(int i=0;i<209999;++i){
        mr(a,n);
        int c=work(a,n,v);
        if(c>max)max=c;
    }
    printf("%d\n",max);

    //cout<<rand()<<" "<<rand()<<endl;
}
/*
30 300
11 19
52 149
7 16
82 116
5 3
84 125
10 25
37 60
35 51
31 53
44 48
89 244
46 60
54 159
28 41
29 80
100 267
13 8
41 21
62 168
24 63
89 133
15 45
2 1
37 107
48 24
93 248
99 85
72 209
60 173
*/
//output 867


#### 时间复杂度

#### 参考文献

#### C++ 代码

blablabla


----------

### 算法2
##### (暴力枚举)  $O(n^2)$

blablabla

#### 时间复杂度

#### 参考文献


#### C++ 代码

blablabla
```




Hicode002
2019-09-14 10:40

题目描述

blablabla

样例

blablabla

算法1

非正解,使用随机化贪心,骗80–90分,这是没学dp的最好解决此种问题方法-------------

(暴力枚举) $O(懒得算)$

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
struct bag{
int v,w;
double i;
inline void autoi(){
scanf(“%d%d”,&v,&w);
i=1.0*w/v;
}

}a[3000];
inline bool cmp(bag x ,bag y){
return x.i >y.i ;
}
inline void mr(bag b[],int n){
sort(b,b+n,cmp);
for(int i=0;i<10;++i){
swap(b[rand()%n],b[rand()%n]);
}
}
inline int work(bag b[],int n,int v){
int totalv=v,totalw=0;
for(int i=0;i[HTML_REMOVED]max)max=c;
}
printf(“%d\n”,max);

//cout<<rand()<<" "<<rand()<<endl;

}
/
30 300
11 19
52 149
7 16
82 116
5 3
84 125
10 25
37 60
35 51
31 53
44 48
89 244
46 60
54 159
28 41
29 80
100 267
13 8
41 21
62 168
24 63
89 133
15 45
2 1
37 107
48 24
93 248
99 85
72 209
60 173
/
//output 867

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla