Chengrui's Blog

0%

发表于 分类于 ， Disqus：

给出剩余时间和想唱的歌，求最多能唱几首和最长时间。

较为简单的01背包问题，在算数目的时候顺便计算时间就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=180*55+678;
int song[55],f[maxn],k[maxn];
int main(){
    int t,tt=0;
    cin>>t;
    while(t--){
        memset(f,0,sizeof(f));
        memset(k,0,sizeof(k));
        memset(song,0,sizeof(song));
        int n,t,cnt=1,len=678;
        cin>>n>>t;
        --t;
        for(int i=0;i<n;++i)
            cin>>song[i];
        for(int i=0;i<n;++i)
            for(int j=t;j>=song[i];--j){
                if(f[j-song[i]]+1>f[j]||(f[j-song[i]]+1==f[j]&&k[j-song[i]]+song[i]>k[j])){
                    f[j]=f[j-song[i]]+1;
                    k[j]=k[j-song[i]]+song[i];
                }
            }
        cnt+=f[t],len+=k[t];
        cout<<"Case "<<++tt<<": "<<cnt<<" "<<len<<endl;
    }
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出一些长方体，求能叠成的最高的顶面长和宽严格递减的塔有多高。

几乎和嵌套矩形的一样，储存每个长方体的面，然后dp搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=100;
int n,cnt,d[maxn],best;
bool g[maxn][maxn];
pair<int,int> k[maxn];
map<pair<int,int>,int> h;
void make_block(int a,int b,int c){
    pair<int,int> t=make_pair(a,b);
    if(h.count(t)) h[t]=max(h[t],c);
    else h[t]=c,k[cnt++]=t;
    t=make_pair(a,c);
    if(h.count(t)) h[t]=max(h[t],b);
    else h[t]=b,k[cnt++]=t;
    t=make_pair(b,c);
    if(h.count(t)) h[t]=max(h[t],a);
    else h[t]=a,k[cnt++]=t;
    return;
}
int dp(int i){
    int& ans=d[i];
    if(ans!=-1) return ans;
    ans=h[k[i]];
    for(int j=0;j<cnt;++j)
        if(g[i][j]) ans=max(ans,dp(j)+h[k[i]]);
    return ans;
}
int main(){
    int t=0;
    while(cin>>n,n){
        cnt=best=0;
        h.clear();
        memset(g,0,sizeof(g));
        memset(d,-1,sizeof(d));
        for(int i=0;i<n;++i){
            int a,b,c;
            cin>>a>>b>>c;
            if(a>b) swap(a,b);
            if(a>c) swap(a,c);
            if(b>c) swap(b,c);
            make_block(a,b,c);
        }
        sort(k,k+cnt,[](const pair<int,int> a,const pair<int,int> b){return a.first==b.first?a.second<b.second:a.first<b.first;});
        for(int i=0;i<cnt;++i)
            for(int j=0;j<cnt;++j)
                g[i][j]=k[i].first>k[j].first&&k[i].second>k[j].second;
        for(int i=0;i<cnt;++i)
            best=max(best,dp(i));
        cout<<"Case "<<++t<<": maximum height = "<<best<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出4堆糖，往容量为5篮子里装任意一个在堆顶的糖，篮子里有相同颜色的就拿走，问最多能拿走几次。

定义四维数组记忆搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=45;
bool bas[25];
int n,piles[4][maxn],k[maxn][maxn][maxn][maxn];
int dp(int a,int b,int c,int d){
    int& best=k[a][b][c][d];
    if(best!=-1) return best;
    if(count(bas,bas+25,true)==5) return best=0;
    if(a==n&&b==n&&c==n&&d==n) return best=0;
    if(a!=n){
        bool& p=bas[piles[0][a]];
        p=!p;
        best=max(best,dp(a+1,b,c,d)+(p?0:1));
        p=!p;
    }
    if(b!=n){
        bool& p=bas[piles[1][b]];
        p=!p;
        best=max(best,dp(a,b+1,c,d)+(p?0:1));
        p=!p;
    }
    if(c!=n){
        bool& p=bas[piles[2][c]];
        p=!p;
        best=max(best,dp(a,b,c+1,d)+(p?0:1));
        p=!p;
    }
    if(d!=n){
        bool& p=bas[piles[3][d]];
        p=!p;
        best=max(best,dp(a,b,c,d+1)+(p?0:1));
        p=!p;
    }
    return best;
}
int main(){
    while(scanf("%d",&n),n){
        memset(k,-1,sizeof(k));
        memset(bas,0,sizeof(bas));
        memset(piles,0,sizeof(piles));
        for(int i=0;i<n;++i)
            for(int j=0;j<4;++j)
                scanf("%d",&piles[j][i]);
        printf("%d\n",dp(0,0,0,0));
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

一个间谍要从第1个车站到第n个车站在T时刻与人接头。她可以灵活地在车站在各列车上穿梭，求在车站等待的最短时间。

书上给出了思路和主程序代码，剩下的就是输入了，用has_train存每个时刻每个车站的状态。每读入一辆车，就模拟至目标时间，储存它经过的站点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=55,maxt=210;
const int INF=1<<30;
int t[maxn],dp[maxt][maxn];
bool has_train[maxt][maxn][2];
int main(){
    int n,T,tt=0;
    while(cin>>n,n){
        memset(has_train,0,sizeof(has_train));
        int m1,m2,d;
        cin>>T;
        for(int i=1;i<n;++i) cin>>t[i];
        cin>>m1;
        while(m1--&&cin>>d)
            for(int i=1;i<n;d+=t[i++])
                if(d<=T) has_train[d][i][0]=true;
        cin>>m2;
        while(m2--&&cin>>d)
            for(int i=n-1;i>0;d+=t[i--])
                if(d<=T) has_train[d][i+1][1]=true;
        for(int i=1;i<n;++i) dp[T][i]=INF;
        dp[T][n]=0;
        for(int i=T-1;i>=0;--i)
            for(int j=1;j<=n;++j){
                dp[i][j]=dp[i+1][j]+1;
                if(j<n&&has_train[i][j][0]&&i+t[j]<=T)
                    dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);
                if(j>1&&has_train[i][j][1]&&i+t[j-1]<=T)
                    dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]);
            }
        cout<<"Case Number "<<++tt<< ": ";
        if(dp[0][1]>=INF) cout<<"impossible\n";
        else cout<<dp[0][1]<<"\n";
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出系统组件的依赖关系，然后给出操作指令。

书上给出了安装和删除的代码，剩下就的没什么难度了。分配id，然后使用id操作。

用到了std::remove，在algorithm头文件里，返回一个迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<string>
#include<map>
#include<sstream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=10000;
int cnt,status[maxn];
string name[maxn];
map<string,int> ids;
vector<int> depend[maxn],depend2[maxn],installed;
int get_id(string s){
    if(ids.count(s)) return ids[s];
    name[cnt]=s;
    return ids[s]=cnt++;
}
bool needed(int item) {
    for(int i=0;i<depend2[item].size();++i)
        if(status[depend2[item][i]]) return true;
    return false;
}
void install(int item,bool toplevel){
    if(!status[item]){
        for(int i=0; i<depend[item].size();i++)
            install(depend[item][i],false);
        cout<<"   Installing "<<name[item]<<'\n';
        status[item]=toplevel?1:2;
        installed.push_back(item);
    }
    return;
}
void remove(int item,bool toplevel){
    if((toplevel||status[item]==2)&&!needed(item)){
        status[item]=0;
        installed.erase(remove(installed.begin(),installed.end(),item),installed.end());
        cout<<"   Removing "<<name[item]<<'\n';
        for(int i=0;i<depend[item].size();++i)
            remove(depend[item][i],false);
    }
}
int main(){
    ios::sync_with_stdio(false);
    string s,cmd;
    while(getline(cin,s)){
        cout<<s<<'\n';
        if(s[0]=='E') break;
        stringstream ss(s);
        ss>>cmd;
        if(cmd[0]=='L'){
            for(int i=0;i<installed.size();++i)
                cout<<"   "<<name[installed[i]]<<'\n';
        }
        else{
            int id1,id2;
            string s1,s2;
            ss>>s1;
            id1=get_id(s1);
            if(cmd[0]=='D'){
                while(ss>>s2){
                    id2=get_id(s2);
                    depend[id1].push_back(id2);
                    depend2[id2].push_back(id1);
                }
            }
            if(cmd[0]=='I'){
                if(status[id1]) cout<<"   "<<s1<<" is already installed.\n";
                else install(id1,true);
            }
            if(cmd[0]=='R'){
                if(!status[id1]) cout<<"   "<<s1<<" is not installed.\n";
                else if(needed(id1)) cout<<"   "<<s1<<" is still needed.\n";
                else remove(id1,true);
            }
        }
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

有n个长度为1的线段，给出n个区间，第i个区间表示第i个线段所在的范围，求所给线段至少有几个间隙。

首先对区间进行排序，然后单次遍历，对每个求相交区间，当无法相交时，即有一个间隙。

这道题rank 1，截图留念：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100010,inf=1<<30;
struct node{
    int l,r;
    bool operator < (const node& x) const {
        return l!=x.l?l<x.l:r<x.r;
    }
} a[maxn];
int main(){
    int n,t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;++i)
            scanf("%d%d",&a[i].l,&a[i].r);
        sort(a,a+n);
        int l=-inf,r=inf,cnt=0;
        for(int i=0;i<n;++i){
            l=max(a[i].l,l+1),r=min(a[i].r,r+1);
            if(r<=l) ++cnt,l=a[i].l,r=a[i].r;
        }
        printf("%d\n",cnt);
    }
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出1到n的一个排列，求最少几次剪切粘贴后使序列升序排列。

加深搜索，枚举剪切的起点和终点，再枚举粘贴的切入点。然后当后继数字不正确的值h满足，d3+h>3maxd时剪枝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<cstring>
const int maxn=9;
int a[maxn],n,maxd;
int h(){//求后继数字不正确的个数。
    int cnt=0;
    for(int i=0;i<n-1;++i)
        if(a[i]+1!=a[i+1]) ++cnt;
    if(a[n-1]!=n) ++cnt;
    return cnt;
}
bool dfs(int d){
    int cnt=h();
    if(d*3+cnt>maxd*3) return false;
    if(!cnt) return true;
    int b[maxn],c[maxn];
    memcpy(b,a,sizeof(a));
    for(int i=0;i<n;++i)//枚举剪切。
        for(int j=i;j<n;++j){
            int cnt1=j-i+1,cnt2=n-cnt1;
            memcpy(c,b,sizeof(int)*(i));
            memcpy(c+i,b+j+1,sizeof(int)*(n-j));
            for(int k=0;k<=cnt2;++k){//枚举粘贴。
                if(i==k) continue;
                memcpy(a,c,sizeof(int)*k);
                memcpy(a+k,b+i,sizeof(int)*cnt1);
                memcpy(a+k+cnt1,c+k,sizeof(int)*(n-cnt1-k));
                if(dfs(d+1)) return true;
            }
        }
    memcpy(a,b,sizeof(a));
    return false;
}
int main(){
    int t=0;
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<n;++i) scanf("%d",&a[i]);
        for(maxd=0;;++maxd)
            if(dfs(0)) break;
        printf("Case %d: %d\n",++t,maxd);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

贪心部分的理论依据：前i个数可以凑出1～sum[i]的所有整数。

证明：

第二类数学归纳，n=1时成立，假设n=k之前所有项都成立，当n=k+1时。sum[k+1]=sum[k]+a[k+1]。只需证明能凑出sum[k]+1~su m[k+1]间的整数即可。设1≤p≤a[k+1]，sum[k]+p=sum[k]+a[k+1]-(a[k+1]-p)。因为1≤a[i]≤i，易得sum[k] ≥k,a[k+1]-p≤k。所以一定可以凑出a[k+1]-p。所以只需从之前凑出sum[k]里面剪掉凑出a[k+1]-p的数就可以凑出sum[k]+p。所以 从1~sum[k+1]都可以凑出。

输入n个数，第i个数ai满足1≤ai≤i。对每个数添加符号，使和值为0。

排序后从最大的数开始贪心就好。这次用了一些c++不常用的特性写的，一开始缺了个头文件CE了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<algorithm>
#include<iterator>
using namespace std;
const int maxn=100010;
struct q{
    int num,id;
    friend ostream& operator << (ostream &out,const q& x){
        cout<<x.num;
        return out;
    }
};
q a[maxn];
int main(){
    int n;
    while(cin>>n){
        long long sum=0;
        for(int i=0;i<n;++i){
            a[i].id=i;
            cin>>a[i].num;
            sum+=a[i].num;
        }
        if(sum&1) {cout<<"No\n";continue;}
        sum>>=1;
        sort(a,a+n,[](q& a,q& b){return a.num>b.num;});
        for(int i=0;i<n;++i){
            if(a[i].num<=sum){
                sum-=a[i].num;
                a[i].num=1;
            }
            else a[i].num=-1;
        }
        sort(a,a+n,[](q& a,q& b){return a.id<b.id;});
        cout<<"Yes\n";
        copy(a,a+n,ostream_iterator<q>(cout," "));
        cout<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出订单需要时间和截止时间，求最多能完成多少，hint给了很详细的提示。

先按照截止日期排序，然后单次遍历，每次当前订单耗时小于之前订单最大值时，用当前订单替换耗时最长的订单，最终得到最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=800010;
struct order{
    int q,d;
    order(int q=0,int d=0):q(q),d(d){};
    bool operator < (const order& x) const {
        if(d!=x.d) return d<x.d;
        return q<x.q;
    }
};
order a[maxn];
priority_queue<int> b;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        while(!b.empty()) b.pop();
        int n,sum=0;
        scanf("%d",&n);
        for(int i=0;i<n;++i)
            scanf("%d%d",&a[i].q,&a[i].d);
        sort(a,a+n);
        for(int i=0;i<n;++i){
            if(sum+a[i].q<=a[i].d){
                sum+=a[i].q;
                b.push(a[i].q);
            }
            else if(!b.empty()&&b.top()>a[i].q){
                sum-=b.top(),b.pop();
                sum+=a[i].q;
                b.push(a[i].q);
            }
        }
        printf("%d\n",(int)b.size());
        if(t) printf("\n");
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

很久之前跳过去了这道题，现在看没什么难度，给出一个树的BFS和DFS的序列，输出这棵树。
用BFS顺序去分离DFS，然后记录每个结点的子结点就好了。这道题不清空vector居然是PE，而不是WA。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=1010;
vector<int> tree[maxn];
int pos[maxn],dfs[maxn],n;
int main(){
    while(~scanf("%d",&n)){
        memset(pos,0,sizeof(pos));
        memset(dfs,0,sizeof(dfs));
        int k,p,q=0;
        for(int i=0;i<n;++i) scanf("%d",&k),pos[k]=i,tree[i].clear();
        scanf("%d",&dfs[0]);
        for(int i=1;i<n;++i){
            scanf("%d",&p);
            while(q&&pos[p]<=pos[dfs[q]]+1) --q;
            tree[dfs[q]-1].push_back(p);
            dfs[++q]=p;
        }
        for(int i=0;i<n;++i){
            printf("%d:",i+1);
            for(int j=0;j<tree[i].size();++j)
                printf(" %d",tree[i][j]);
            printf("\n");
        }
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **