2018 Multi-University Training hdu Contest 5

Posted on | In , | Visitors:

嚯嚯嚯！补题！

hdu多校总链接

补题： 4题/12题

  • 置换群
  • 排列组合
  • 计算几何
  • 线段树
  • LIS
  • LDS

B. Beautiful Now

for each permutation of digits, the minimum number of swaps equals to n minus the number of disjoint cycles in the permutation. We can solve the problem by enumerating all the n-permutations. That is, for each permutation, we just check if it can be reached within k swaps (because swapping the same digit is permitted) and then update the answer. Time complexity is expected to be O(n!) while algorithms in time complexity O(n!n) may get TLE verdict (but who knows?). In order to achieve the excepted time complexoty, we may need to maintain some information about chains and cycles effciently during the process of searching and backtracking.

考虑下标的置换，可以发现最少的交换次数等于 n 减去置换中循环的数量，所以可以枚举所有的 n 排列解决此题。 对于每个置换， 只需要检查它是否可以在 k 次交换内实现（因为可以交换相同的位置） 并更新答案。 期望时间复杂度是 O(n!)， O(n!n)的算法有可能会超时（也可能不超时）。 为了实现期望 复杂度可能需要在搜索和回溯过程中高效维护链和环的信息。

看不懂题解的我，被空调吹傻的我……

置换群？排列组合？

一直以为是贪心呢！（想知道数据啊，感觉也可行呐！不过给的时间就可以告诉我，不是的，但苍天啊，大地啊！给个反例吧！）

第二天，博博过了！

嗯，大概就是通过把每种置换方法都列出来，然后通过每种置换变换为目标的串所需要的次数，如果小于k，则是可以的；对于可以的，进行值的比较更新结果！

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
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
const int maxn=9;
char buf[maxn + 2];
int q[maxn+2],num[maxn+2],p[maxn+2];
int low,upp,n,m;
void update(){
    if(num[p[1]]==0) return; //第一位数字不可以是0
    for(int i=1;i<=n;i++) q[i]=p[i]; //q数组内保存全排列后的位置
    int k=0,s=0;
    for(int i=1;i<=n;i++){
        s=s*10+num[p[i]];
        if(q[i]!=i){ //如果当前位数字更改了
            for(int j=i+1;j<=n;j++){
                if(q[j]==i){//找到交换后的位置，进行交换
                    swap(q[i],q[j]);
                    k++;
                    if(k>m) return;
                    break;
                }
            }
        }
    }
    if(k>m) return;//转换了超过k次
    upp=max(upp,s);
    low=min(low,s);
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &low, &m);
        upp = low;
        n = sprintf(buf, "%d", low);
        if(n > maxn) { //1e9，10位数字
            printf("%d %d\n", low, upp);
            continue;
        }
        if(n-1 <= m) {//这里刚开始没怎么想，如果写n<=m则会TLE，这里看到全排列是如此多啊！！！
            sort(buf, buf + n, greater<char>());
            sscanf(buf, "%d", &upp);
            //特殊处理第一位
            for(int i = 1; i < n; ++i)
                if(buf[0] > buf[i] && buf[i] > '0')
                    swap(buf[0], buf[i]);
            //排序
            sort(buf + 1, buf + n);
            sscanf(buf, "%d", &low);
            printf("%d %d\n", low, upp);
            continue;
        }
        
        for(int i=1;i<=n;i++){
            num[i]=buf[i-1]-'0';
        }
        
        for(int i=1;i<=n;i++) p[i]=i;  //每一位数字原来保存在哪里
        do{
            update();
        }while(next_permutation(p+1,p+n+1)) ;//全排列
        printf("%d %d\n",low,upp);
    }
    return 0;
}

E. Everything Has Changed

Note that the cutting areas do not intersect and the different areas do not affect each other. Just enumerate every cutting area intersecting the disk and then count the lengths of their circumferences covered by each other.

注意切割区域两两不相交， 则不同切割区域不会相互影响。 枚举每个与圆盘相交的切割区域， 计算互相被包含的圆周长度即可。

画个图就ok！

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
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
const double PI = acos(-1.0);
const int MAX = 105;
const double EPS = 1e-5;
struct Point {
    double x, y;
    Point(double a = 0, double b = 0) {
        x = a;
        y = b;
    }
};
struct Cycle {
    Point centre;
    double r;
}cycle[MAX];
double dis(Point a, Point b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
int cmp(double a, double b) {
    if (a - b >= EPS)    return 1;
    else if (b - a >= EPS)   return -1;
    return 0;
}
bool check(Cycle a) {//判断是否相交
    double d = dis(a.centre, cycle[0].centre);
    if (cmp(d, cycle[0].r - a.r) >= 0 && cmp(cycle[0].r + a.r, d) >= 0) return true;
    return false;
}
int main() {
    // freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        cycle[0].centre = Point(0, 0);
        int m;
        scanf("%d%lf", &m, &cycle[0].r);
        for (int i = 1; i <= m; ++i) {
            scanf("%lf%lf%lf", &cycle[i].centre.x, &cycle[i].centre.y, &cycle[i].r);
        }
        double angle, d, r, R = cycle[0].r, ans = 2 * PI * R, beta;
        // cout << ans << endl;
        for (int i = 1; i <= m; ++i) {
            if (check(cycle[i])) {
                // cout << i << endl;
                d = dis(cycle[0].centre, cycle[i].centre);
                r = cycle[i].r;
                beta = acos((R * R + d * d - r * r) / (2 * R * d));
                angle = acos((d * d + r * r - R * R) / (2 * d * r));
                ans += 2 * angle * r - 2 * beta * R;
            }
        }
        printf("%.7lf\n", ans);
    }
}

G. Glad You Came

If there are two operations covering the same interval, we can just keep the maximum one. For each operation(l,r,v),let d be 」log2(r-l+1)」, replace this operation by two operations (l,l+2^d-1,v) and (r-2^d+1,r,v). After that, the length of the interval that each operations covers is a power of 2, which means the lengths are only O(logn) types. The remaining part is just to enumerate operations in length decreasing order and split each operation into two operations of equal length until the length is one. Time complexity is O(m+nlogn) and space complexity is O(nlogn).

如果有两个操作覆盖相同的间隔，我们可以保持最大值。 对于每个操作（l，r，v），令d为对log2（r-l + 1）向下取整，将该操作替换为两个操作（l，l + 2 ^ d-1，v）和（r-2 ^d+ 1，R，v）。 之后，每个操作所覆盖的间隔的长度是2的幂，这意味着长度仅为O（logn）类型。 剩下的部分只是按长度递减顺序枚举操作，并将每个操作分成两个相等长度的操作，直到长度为1。 时间复杂度为O（m + nlogn），空间复杂度为O（nlogn）。

如果有两个操作覆盖相同的区间， 我们可以保留最大的那个。 对于每个操作（l，r，v）， 令 d 等于 对log2（r-l + 1）向下取整， 我们可以用两个操作（l，l + 2 ^ d-1，v）和（r-2 ^d+ 1，R，v）替换此操作。 这样做之后， 每个操作所覆盖的区间长度均为 2 的幂， 这意味着长度仅有 O（logn）种。 剩下的只不过是， 按长度递 减的顺序枚举操作，将每个操作分成两个相等长度的操作，直到区间长度为一。这样做的时间复杂度为O（m + nlogn），空间复杂度为O（nlogn）。

这个，线段树有博博会就够了！emmm……我估计永远都不会线段树了！

H. Hills And Valleys

首先dp应该是很明显的，其次我们应该转换思路，因为这里的n是1e5，肯定会炸；所以我们可以从最长不下降的串入手。这个串如果不重复的话，就有C(2,10)，然后我们通过原串和此串进行匹配；同时我们需要注意的是，这里的是不下降，所以我们需要对此串进行一些改造，这样可以保证原串是重复的。

dp方程我们的设计思路是

$dp[i][j]=max(dp[i-1][j]+(a[i]==b[j]),dp[i][j-1])$

这里表示若是两个值相等，则可以是对于前面的数字匹配或者是对相同数字又多了一个匹配

然后，0 1 2 3 x y y-1 …… x+1 x y+1……9

这样翻转过来，还是最长不下降串；

所以，我们需要在b串的构造的时候多加端点的两个值

注意，题中还需记录翻转端点，第一次遇到左端点的值和最后一次遇到右端点的值的时候，需要更新值

然后我研究了半个小时的东西，然后发现自己没脑子的开数组，开成dp[maxn][maxn]，导致出现了linker command failed with exit code 1 (use -v to see invocation)，看不懂这个东西，然后，开始瞎注释，问题的是，一个数组开那么大没问题，开两个就有问题了，导致我以为是al这个不可以使用名字（因为百度说的……

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
char a[maxn];
int b[15],dp[maxn][15],al[maxn][15],ar[maxn][15];
int l,r,ll,rr,n,ans,m,tmp;
int solve(){
    for(int i=0;i<=9;i++) dp[0][i]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=dp[i-1][j];
            al[i][j]=al[i-1][j];
            ar[i][j]=ar[i-1][j];
            if((int)(a[i]-'0')==b[j]){
                dp[i][j]++;
                if(ll==j&&!al[i][j]) al[i][j]=i;
                if(rr==j) ar[i][j]=i;
            }
            if(j>0&&dp[i][j-1]>dp[i][j]){
                dp[i][j]=dp[i][j-1];
                al[i][j]=al[i][j-1];
                ar[i][j]=ar[i][j-1];
            }
        }
    }
    return dp[n][m];
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d %s",&n,a+1);
        m=0;
        for(int i=0;i<=9;i++) b[++m]=i;
        l=1;r=1;ans=solve();
        for(int i=0;i<=9;i++){
            for(int j=i+1;j<=9;j++){
                m=0;
                for(int k=0;k<=i;k++) b[++m]=k;
                ll=m+1;
                for(int k=j;k>=i;k--) b[++m]=k;
                rr=m;
                for(int k=j;k<=9;k++) b[++m]=k;
                tmp=solve();
                if(ans<tmp&&al[n][m]&&ar[n][m]){
                    ans=tmp;
                    l=al[n][m];
                    r=ar[n][m];
                }
            }
        }
        printf("%d %d %d\n",ans,l,r);
    }
    return 0;
}

碎碎念

2018.08.11晚

嗝，吃多了！

记录一下，若是有长度为n的序列，如果LIS的长度为L的话，那么LDS的长度为（n/L）向下取整

因为我是小金鱼呀！

2018.08.12 早

早上不想起床了，留了一集小葡萄

唔，疲劳期，倦怠期，还有好多题目没有补

中午照样在赖床，羡慕各位聚聚和舍长爸爸

充满无限的活力

2018.08.12 晚

没有报名百度之星，好无聊啊

也不能提交，继续补题啊

好想穿上美美的小裙子，梳上丸子头，出门拍上美美的照片啊！

于是拍了一段小短片，感觉像是一个广告，顺便，马卡龙好评！

郁闷，我又胖了，一定是坐太久了！

感觉我已经进入暴躁期了，喜怒无常，无所事事

给博客增加了置顶的功能！

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽