2019暑训第一场训练赛 |（2016-icpc区域赛）部分题解

// 今天下午比赛自闭了，晚上补了题，把AC的部分水题整理一下，记录坑点并吸取教训。

// CF补题链接：http://codeforces.com/gym/101291

A - Alphabet

题目大意：

给定一字符串，问至少需要添加多少字母后，能使该字符串删掉一些字母后成为“abcdefghijklmnopqrstuvwxyz"的序列。

分析及代码：

最长上升子序列（LIS）问题，n的规模不大，直接DP两重循环求解。答案为 26-最长上升子序列的长度。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int main() {

    char str[];

    int dp[];      // dp[i] 以str[i]结尾的最长上升子序列的长度

                      // dp[i] = max(dp[i], dp[k]+1), 0<=k<i, str[k]<str[i]

    int maxLen = ;   // maxLen = max(dp[i]), 0<=i<n

    scanf("%s", str);

    int len = strlen(str);

    for(int i=;i<len;i++) {

        dp[i] = ;

        for(int j=;j<i;j++) {

            if(str[j]<str[i]) {

               dp[i] = max(dp[i], dp[j]+);

            }

        }

        maxLen = max(maxLen, dp[i]);

    }

    printf("%d\n", -maxLen);

    return ;

}

顺便学习了求解最长公共子序列（LCS）与LIS的O(nlogn)算法，其利用了贪心思想和二分搜索。

数组dp表示目前找到的最长序列，不影响dp长度前提下，在原序列中尽可能找到更小的元素来代替现有的最长序列中的元素；如果比最大的元素要大，就添加在dp末尾。

由于数组dp单调，使用二分搜索能将更新的复杂度降低到O(logn)，所以总的复杂度为O(nlogn)。

// 返回最长上升子序列的长度

// 时间复杂度： O(nlogn)

// 来源：https://blog.csdn.net/ltrbless/article/details/81318935

//

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

int main()

{

    char arr[],  dp[];

    scanf("%s", arr);

    int n = strlen(arr);

    /* 求解最长子序列的个数的核心代码 */

    /* ********************************************** */

    int k = ;

    dp[k] = arr[];

    for(int i=;i<n;i++) {

        if(dp[k]<arr[i]) dp[++k] = arr[i];              //如果比最后一个元素大，那么就添加再最后末尾处

        else *(lower_bound(dp, dp+k, arr[i])) = arr[i]; //如果比最后一个元素小，那么就替换该序列第一个比他大的数；

    }

    /* ********************************************** */

    printf("最长子序列的个数为： %d\n", k);

    return ;

}

B - Barbells

题目大意：

分别给你n个杠铃的重量和m个盘子的重量，可以把盘子加到杠铃上，但要两边的重量相同。输出全部能组合的杠铃重量。

分析及代码：

n，m不超过14，直接枚举全部可能，也没什么技巧了。

比赛时候写这题，电脑突然崩溃了，代码都不见了，心态爆炸。。。

直接用DFS算重量的组合，把m当做n作为终止条件，debug没看出来。改用储存全部组合的状态（二进制），懒得去重排序都一股脑往set里放，写了自己都看不懂的代码交上去就过了。

#include<cstdio>

#include<iostream>

#include<vector>

#include<map>

#include<set>

using namespace std;

int n, m;

map<int, int> sums;

vector<int> vec[];

int sum[];

int cnt;

int arr2[], arr[];

set<int> ans;

set<int> ans2;

int main()

{

    cin>>n>>m;

    for(int i=;i<n;i++) {

        scanf("%d", &arr[i]);

    }

    for(int i=;i<m;i++) {

        scanf("%d", &arr2[i]);

    }

    for(int s=;s<(<<m)-;s++) {

        int now = ;

        for(int k=;k<m;k++) {

            if((s>>k)&) {

                now += arr2[k];

            }

        }

        if(sums.find(now)==sums.end()) {

            sums[now] = ++cnt;

            sum[cnt] = now;

            vec[sums[now]].push_back(s);

        }else

            vec[sums[now]].push_back(s);

    }

    ans.insert();

    for(int i=;i<=cnt;i++) {

        if(vec[i].size()>) {

        //    cout<<sum[i]<<':';

            for(int j=;j<vec[i].size();j++) {

                for(int k=j+;k<vec[i].size();k++) {

                    if((vec[i][j] & vec[i][k])==) {

                        ans.insert(*sum[i]);

                    }

                }

            }

        }

    }

    for(set<int>::iterator it=ans.begin();it!=ans.end();it++) {

        for(int i=;i<n;i++) {

            ans2.insert(*it+arr[i]);

        }

    }

    for(set<int>::iterator it=ans2.begin();it!=ans2.end();it++)

    {

        printf("%d\n", *it);

    }

    return ;

}

晚上重新用DFS还带剪枝的，重新写了一遍。

dfs(k, left, right)，每层三个分支，不用set<int>而用数组储存中间组合结果，一定要开辟足够的内存空间（3^14），否则就奇怪地WA了（为什么不是运行错误？？？）。

最后也没有用set去排序，复习一下unique函数的用法。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<set>

using namespace std;

int n, m;

int a[], b[], bSum;

//int bbb[20010];     // 单边有2^14种组合，约16000, 会WA

//int bbb[5000000];   // 3^14, AC

set<int> bbb;

int ans[];      // 14*16000

int k;

void dfs(int k, int left, int right) {

    if(k==m+) {

        if(left==right) {

            bbb.insert(left*);

        }

        return;

    }

    if(left>bSum/ || right>bSum/) return;

    dfs(k+, left+b[k], right);

    dfs(k+, left, right+b[k]);

    dfs(k+, left, right);

}

int main()

{

    cin>>n>>m;

    for(int i=;i<=n;i++) {

        scanf("%d", &a[i]);

    }

    for(int i=;i<=m;i++) {

        scanf("%d", &b[i]);

        bSum += b[i];

    }

    dfs(, , );

    for(int i=;i<=n;i++) {

        for(set<int>::iterator it=bbb.begin();it!=bbb.end();it++) {

            ans[++k] = a[i] + *it;

        }

    }

    sort(ans+, ans++k);

    k = unique(ans+, ans++k) - (ans+);

    for(int i=;i<=k;i++) {

        printf("%d\n", ans[i]);

    }

    return ;

}

F - Equality

题目大意：

签到题。

分析及代码：

没有代码。

G - Gravity

题目大意：

似乎是模拟苹果下落？输出最后苹果的状态。

分析及代码：

没想到苹果可能在障碍的下方（题目也没有说明，被样例误导以为苹果都在天上），WA了几次自闭了。

苹果的下落就相当于在垂直方向上苹果‘o'与空气’.'进行排序。

要避免障碍就使用相邻交换排序，相邻只要有苹果在空气上方就互换位置。 冒泡排序的思想？

 #include<iostream>

#include<cstdio>

using namespace std;

char mp[][];

int n, m;

int h[], num[];

int main() {

    cin>>n>>m;

    getchar();

    for(int i=;i<n;i++) {

        scanf("%s", mp[i]);

    }

    for(int j=;j<m;j++) {

        for(int i=;i<n;i++) {

            for(int k=;k<n;k++) {

                if(mp[k-][j]=='o' && mp[k][j]=='.') {

                    mp[k-][j] = '.';

                    mp[k][j] = 'o';

                }

            }

        }

    }

    for(int i=;i<n;i++) puts(mp[i]);

    return ;

}

H - Islands

题目大意：

给你一块卫星地图，L表示陆地，W表示水域，C表示有云挡住。问最少可能有多少块岛。

分析及代码：

本以为还要建图，求联通分量啥的。。。

L与C连起来不影响岛的个数，直接从每块L区域DFS求联通块个数即可。

#include<cstdio>

#include<iostream>

#include<vector>

#include<map>

#include<queue>

#include<set>

using namespace std;

int n, m;

const int dx[] = {, , , -};

const int dy[] = {, -, , };

char mp[][];

bool vis[][];

void dfs(int x, int y) {

    vis[x][y] = ;

    for(int i=;i<;i++) {

        int nx = x + dx[i];

        int ny = y + dy[i];

        if(nx>= && nx<n && ny>= && ny<m && !vis[nx][ny] && mp[nx][ny]!='W') {

            dfs(nx, ny);

        }

    }

}

int main()

{

    cin>>n>>m;

    getchar();

    for(int i=;i<n;i++) {

        scanf("%s", mp[i]);

    }

    int ans = ;

    for(int i=;i<n;i++) {

        for(int j=;j<m;j++) {

            if(!vis[i][j] && mp[i][j]=='L') {

                dfs(i, j);

                ans++;

            }

        }

    }

    printf("%d\n", ans);

    return ;

}

J - Postman

题目大意：

邮递员在原点，要给分布在x轴上的n个客户送信，每个客户有mi封信件，每次配送最多带k封信。求送完信最少需要多长时间。

分析及代码：

贪心吧。由于走到最远再回到原点会经过更近的点，每次带k封信，送完最远的顺路给次远的，这样优先配送距离最远的信件，送完最远的再送第二远的，依次下去。

注意x正负区间分别计算。

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

int n, k;

struct node {

    int x, m;

    bool operator<(const node &a)const {

        return x<a.x;

    }

}n1[], n2[];

int cnt1, cnt2;

int main()

{

    cin>>n>>k;

    for(int i=;i<n;i++) {

        int x, m;

        scanf("%d %d", &x, &m);

        if(x<) {

            n1[++cnt1].x = -x;

            n1[cnt1].m = m;

        } else {

            n2[++cnt2].x = x;

            n2[cnt2].m = m;

        }

    }

    sort(n1+, n1++cnt1);

    sort(n2+, n2++cnt2);

    ll ans = ;

    for(int i=cnt1;i>=;i--) {

        if(n1[i].m>) {

            int t = (n1[i].m+k-) / k;

            ans += *(ll)n1[i].x* t;

            int left =  t*k - n1[i].m;

            int j = i-;

            while(j>=) {

                if(n1[j].m>=left) {

                    n1[j].m -= left;

                    break;

                }

                else {

                    left -= n1[j].m;

                    n1[j].m = ;

                    j--;

                }

            }

        }

    }

    for(int i=cnt2;i>=;i--) {

        if(n2[i].m>) {

            int t = (n2[i].m+k-) / k;

            ans += *(ll)n2[i].x* t;

            int left =  t*k - n2[i].m;

            int j = i-;

            while(j>=) {

                if(n2[j].m>=left) {

                    n2[j].m -= left;

                    break;

                }

                else {

                    left -= n2[j].m;

                    n2[j].m = ;

                    j--;

                }

            }

        }

    }

    printf("%lld\n", ans);

    return ;

}

K - Six Sides

题目大意：

弱智概率题。。。（卡了半天怪我英语太差没读懂咯O.O）

分析及代码：

结果为：赢局数 / (36 - 平局数)

为什么呢？反正我WA了两次队友告诉我的。

设单次胜的概率为p=win/36，平局概率为q=pin/36

总体赢的概率P为 p + q*p + q*q*p + q*q*q*p + ... = p/(1-q)

所以 P = win / (36 - pin)

#include<iostream>

#include<cstdio>

using namespace std;

int mp[][];

int a[], b[];

int main() {

    for(int i=;i<;i++) cin>>a[i];

    for(int i=;i<;i++) cin>>b[i];

    int win=, p=, lose= ;

    for(int i=;i<;i++) {

        for(int j=;j<;j++) {

            if(a[i]>b[j]) win++;

            else if(a[i]==b[j]) p++;

            else lose++;

        }

    }

    if(win==lose) printf("%.5lf\n", 0.5);

    else printf("%.5lf\n", (win+0.0)/(-p));

    return ;

}

（未完待续。。。）

巴特西

2019暑训第一场训练赛 |（2016-icpc区域赛）部分题解

A - Alphabet

题目大意：

分析及代码：

B - Barbells

题目大意：

分析及代码：

F - Equality

题目大意：

分析及代码：

G - Gravity

题目大意：

分析及代码：

H - Islands

题目大意：

分析及代码：

J - Postman

题目大意：

分析及代码：

K - Six Sides

题目大意：

分析及代码：

最新文章

热门文章