[原创]2015年百度之星程序设计大赛 - 初赛(1) 【解题报告】【未完待续】

2017-03-29 20:35:11 Tabris_ 阅读数：1086

博客爬取于2020-06-14 22:41:02
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/68083224

总结一波 ：
还是读题不清，中文题关键部分读错，导致最终GG，
计算几何薄弱，模板匮乏。

超级赛亚ACMer

虽然题目说打完一次k–,但是没有限定顺序 所以这个限制可以忽略不计

然后说正常怎么来,
先从小到大排序一遍,然后每一次遇到与其相等的就升级战斗力.
为了确保我下一次还能升级战斗力,我就变成比当前战斗力+k小的最大的那个战斗力就行了,
然后扫一遍即可,

(当时以为遇到相等的不能赢.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
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
# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;

# define lowbit(x) (x&-x)
# define abs(x) ((x)>0?(x):-(x))

const int N = 10000+7;
LL n,m,k,mx;
LL a[N];
LL mylb(LL x){
    LL l=1,r=n,mid,ans=0;
    while(l<=r){
        mid = (l+r)>>1;
        if(a[mid]<=x)
            l = mid + 1,ans = mid;
        else r = mid - 1;
    }
    return ans ;
}
int main(){
    int _,kcase = 0;
    scanf("%d",&_);
    while(_--){
        a[0]=0;mx = 0;
        scanf("%I64d%I64d%I64d",&n,&m,&k);
        for(int i=1;i<=n;i++){
            scanf("%I64d",&a[i]);
            if(a[i]<=m){
                mx = (mx>a[i])?mx:a[i];
            }
        }
        m = mx;
        sort(a+1,a+n+1);
//        for(int i=1;i<=n;i++)     printf("%I64d%c",a[i],(i==n)?'\n':' ' );

        int sum = 0;
        for(int i=1;i<=n;i++){
            if(m>=a[i]) sum++;
            else break;
            if(a[i]==m&&k) m=a[mylb(m+k)],k--;
//            printf("%I64d%c",m,(i==n)?'\n':' ' );

        }

//        printf("%d\n",sum);
        printf("Case #%d:\n",++kcase);
        if(sum==n) puts("why am I so diao?");
        else       puts("madan!");
    }
    return 0;
}

找连续数

这个题还是很简单的
我们要找一个长度为k的区间使得其中元素升序后连续,
那么也就说明了这个区间是没有重复元素的,
那么确保了区间内没有相同元素的后
其实也就是找这个区间的最大值和最小值的差是不是等于k-1 ,

确定区间有没有相同元素,可以预处理出每个位置的数出现过的在前面的最近位置,

然后计算的时候我们可以枚举右界,
根据预处理相同元素的位置,能够维护左界,
因为元素没有变化,所以最大最小值可以用ST表预处理出来
一次O(n)就能统计了

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
# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;

# define lowbit(x) (x&-x)
# define abs(x) ((x)>0?(x):-(x))

const int N = 100000+7;

LL a[N];
LL mx[N][20],mi[N][20];int mm[N];
int n,m,x;

void initrmq(){
    mm[0]=-1;
    for(int i=1;i<=n;i++){
        mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
        mi[i][0]=mx[i][0]=a[i];
    }
    for(int j=1;j<=mm[n];j++)
        for(int i=1;i+(1<<j)-1<=n;i++){
            mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
        }
}

LL rmqmi(int x,int y){
    int k=mm[y-x+1];
    return min(mi[x][k],mi[y-(1<<k)+1][k]);
}
LL rmqmx(int x,int y){
    int k=mm[y-x+1];
    return max(mx[x][k],mx[y-(1<<k)+1][k]);
}

map<LL,int>mmp;
int pre[N];
int main(){
    mmp.clear();
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        pre[i]=0;
        scanf("%I64d",&a[i]);
        pre[i]=mmp[a[i]];
        mmp[a[i]]=i;
    }

    initrmq();

    puts("Case #1:");
    while(m--){
        scanf("%d",&x);
        int sum = 0,l = 0;
        for(int i=1;i<=n;i++){
            l=max(l,pre[i]);
            if(i-l>=x){
                if(rmqmx(i-x+1,i)-rmqmi(i-x+1,i)+1==1ll*x)
                    sum++;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

序列变换

这个题也很水,

如果直接进行求解 很困难,那么反过来想想,如果知道了一个数 来判断可不可行是不是非常好做了呢,
显然是的 ,
左边的尽量让他小就行了,

我们考虑如果花费为$x\时能满足题意,那么时能满足题意,那么 \big[x,+\infty\big)\ $都是满足的

所以我们可以二分来做就好了

(最开始把所求看成了cost(A,B)=∑i=1nmax(∣Ai−Bi∣)。cost(A,B)=\sum_{i=1}^nmax(|Ai−Bi|)。 mabi

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
# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;

# define lowbit(x) (x&-x)
# define abs(x) ((x)>0?(x):-(x))
const int N = 100000+7;

int a[N],b[N],n;

bool check(int x){
    for(int i=1;i<=n;i++) b[i]=a[i];
    b[1]-=x;
    for(int i=2;i<=n;i++){
        if(b[i-1]+1<=b[i]+x) b[i]=max(b[i-1]+1,b[i]-x);
        else return false;
    }

    for(int i=2;i<=n;i++)
        if(b[i-1]>=b[i]) return false;

//    for(int i=1;i<=n;i++) printf("%d ",b[i]); puts("");

    return true;
}

int main(){
    int _,kcase = 0;
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)   scanf("%d",&a[i]);

        int l=0,r=10000000,mid,ans;
        while(l<=r){
            mid = (r+l)>>1;

//            printf("%d <--\n",mid);
            if(check(mid))
                ans=mid,r=mid-1;
            else l = mid+1;
        }
        printf("Case #%d:\n",++kcase);
        printf("%d\n",ans);
    }
    return 0;
}

KPI

这题就是一个模拟,我这里是离线+二分+树状数组做的时间复杂度是O(nlog⁡22n)O(n\log_2^2{n})

首先离线出来每个数,按照题意的顺序操作,但是每次都是插入到树状数组中,这样我就能用O(log⁡22n)O(\log_2^2{n})的复杂度来处理查询操作了,对于其他操作,我先拿一个数组来存每次的操作元素是谁,那么也可以O(log⁡2n)O(\log_2{n})处理了

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;

# define lowbit(x) (x&-x)
# define abs(x) ((x)>0?(x):-(x))
const int N = 100000+7;

int op[N];
int b[N],c[N],m;
int x,n,k;
char a[20];

int sum[N];
void update(int i,int v){
    for(;i<=m;i+=lowbit(i)) sum[i]+=v;
}
int getSum(int i){
    int ans=0;
    for(;i;i-=lowbit(i)) ans+=sum[i];
    return ans ;
}

int mylb(int x){
    int l=1,r=m,mid,ans;
    while(l<=r){
        mid = (r+l)>>1;
        if(getSum(mid)>=x)
            ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans ;
}

int mybs(int x){
    int l=1,r=m,mid,ans;
    while(l<=r){
        mid = (r+l)>>1;
        if(b[mid]>=x)
            ans = mid,r=mid-1;
        else l=mid+1;
    }
    return ans ;
}

void init(){
    memset(sum,0,sizeof(sum));
    m=0,k=0;
}

int main(){
    int kcase = 0;
    while(~scanf("%d",&n)){
        init();

        for(int i=1;i<=n;i++){
            scanf("%s",a);
            if(a[0]=='i'){
                op[i]=1;
                scanf("%d",&x);
                b[++m]=x;
            }
            else if(a[0]=='q'){
                op[i]=2;
            }
            else if(a[0]=='o'){
                op[i]=(++k)*10+3;
            }
        }

        printf("Case #%d:\n",++kcase);

//        for(int i=1;i<=n;i++){
//            printf("%d <--\n",op[i]);
//        }

        for(int i=1;i<=m;i++) c[i]=b[i];
        sort(b+1,b+m+1);
//        m = unique(b+1,b+m+1)-(b+1);

        int sum = 0,num = 0;
        for(int i=1;i<=n;i++){
            if(op[i]==1){
                sum++;num++;
                update(mybs(c[num]),1);
                continue;
            }
            else if(op[i]==2){
                printf("%d\n",b[mylb(sum/2+1)]);
                continue;
            }
            op[i]/=10;
            update(mybs(c[op[i]]),-1);sum--;
        }
    }
    return 0;
}

三阶魔方

不会玩魔方啊 不会做…(这两点可能惯性并不是很大,)

矩形面积

这题很明显的是要对所有的矩形求凸包,然后求最小面积的矩形覆盖,旋转卡壳可过,

旋转卡壳应用很详细的介绍

贴上模板就行了.

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
# include <map>
# include <set>
# include <vector>
# include <math.h>
# include <string>
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <iostream>
# include <algorithm>
# include <functional>

using namespace std;
const int MAXN=1005;
const double eps=1e-10;
int dcmp(double x){
    if(fabs(x)<eps)return 0;
    if(x>0)return 1;
    return -1;
}                                                   //弄精度
struct Point {
    double x,y;
}p[MAXN];                                           //搞点
double dot(Point a,Point b,Point c){
    double s1=b.x-a.x;
    double t1=b.y-a.y;
    double s2=c.x-a.x;
    double t2=c.y-a.y;
    return s1*s2+t1*t2;
}                                                     //点积
int n,res[MAXN],top;
bool cmp(Point a,Point b){
    if(a.y==b.y)return a.x<b.x;
    return a.y<b.y;
}
bool mult(Point sp,Point ep,Point op){
    return (sp.x-op.x)*(ep.y-op.y)>=(ep.x-op.x)*(sp.y-op.y);
}
void Graham(){
    int len;
    top=1;
    sort(p,p+n,cmp);
    if(n==0)return;res[0]=0;
    if(n==1)return;res[1]=1;
    if(n==2)return;res[2]=2;
    for(int i=2;i<n;i++){
        while(top&&mult(p[i],p[res[top]],p[res[top-1]]))top--;
        res[++top]=i;
    }
    len=top;
    res[++top]=n-2;
    for(int i=n-3;i>=0;i--){
        while(top!=len&&mult(p[i],p[res[top]],p[res[top-1]]))top--;
        res[++top]=i;
    }
}                                                               //求凸包
double dist(Point a,Point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double Cross(Point a,Point b,Point c){
    return (c.x-a.x)*(b.y-a.y) - (b.x-a.x)*(c.y-a.y);
}
double ComGeo(){
    int R=1,U=1,L;
    double ans=99999999999999;
    for(int i=0;i<top;i++){
        while(dcmp(fabs(Cross(p[res[i]],p[res[(i+1)%top]],p[res[(U+1)%top]]))-fabs(Cross(p[res[i]],p[res[(i+1)%top]],p[res[U]])))>=0) U=(U+1)%top;//最上面一点
        while(dcmp(dot(p[res[i]],p[res[(i+1)%top]],p[res[(R+1)%top]])-dot(p[res[i]],p[res[(i+1)%top]],p[res[R]]))>0) R=(R+1)%top;//最右一点
        if(i==0)L=R;
        while(dcmp(dot(p[res[i]],p[res[(i+1)%top]],p[res[(L+1)%top]])-dot(p[res[i]],p[res[(i+1)%top]],p[res[L]]))<=0) L=((L+1)%top)%top;//最左一点
        //旋转卡壳精髓所在
        double d=dist(p[res[i]],p[res[(i+1)%top]])*dist(p[res[i]],p[res[(i+1)%top]]);
        double area=fabs(Cross(p[res[i]],p[res[(i+1)%top]],p[res[U]]))*//求面积
        fabs(dot(p[res[i]],p[res[(i+1)%top]],p[res[R]])-dot(p[res[i]],p[res[(i+1)%top]],p[res[L]]))/d;
        if(area<ans) ans = area;
    }
    return ans;
}                                               //旋转卡壳
int main()
{
    int t;
    scanf("%d",&t);
    int k=1;
    while(t--){
        int m;
        scanf("%d",&m);
        n=0;
        double x;
        for(int i=0;i<m;i++){
            for(int j=1;j<=8;j++){
                scanf("%lf",&x);
                if(j&1)p[n].x=x;
                else p[n++].y=x;
            }
        }
        Graham();
        double ans;
        if(top<3)ans=0;
        else
        ans=ComGeo();
        long long sum=ans+0.5;   //进1法 因为要覆盖上 所以不能四舍五入
        printf("Case #%d:\n%I64d\n",k++,sum);
    }
    return 0;
}