每日一水第43弹 2015微软编程之美复赛

比较遗憾地把数组开小了而没有ac,太久没写函数式线段树了。

讲讲BCD吧,A不会做。

B:猜数字

很裸的线段树,可以在线直接函数式线段树来做,简单粗暴。

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
106
107
108
109
110
111
112
113
114
115
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
const int maxn = 400010;  
int ls[maxn*20],rs[maxn*20],sum[maxn*20];  
int T[maxn],tot,rt;  
int num[maxn],san[maxn],n,m;  
void build(int l,int r,int &rt)   
{  
    rt=++tot;  
    sum[rt]=0;  
    if(l==r) return ;  
    int m=l+r>>1;  
    build(l,m,ls[rt]);  
    build(m+1,r,rs[rt]);  
}  
void update(int last,int p,int l,int r,int &rt)  
{  
    rt=++tot;  
    ls[rt]  = ls[last];   rs[rt]  = rs[last];   sum[rt] = sum[last] + 1;  
    if(l==r) return ;  
    int m=l+r>>1;  
    if(p<=m) update(ls[last],p,l,m,ls[rt]);  
    else update(rs[last],p,m+1,r,rs[rt]);  
}  
int query1(int ss,int tt,int l,int r,int k)   //大于的最小
{  
    if(san[r] <= k) {
        return -1;
    }
    if(sum[tt] - sum[ss] == 0) {
        return -1;
    }
    if(l==r)  {
        if(k < san[l]) {
            return l;
        }
        return -1;
    }
    int m=l+r>>1;  
        int ret = -1;
    if(k < san[m]) {
        ret = query1(ls[ss], ls[tt], l, m, k);
    }
    if(ret != -1) return ret;
    return query1(rs[ss], rs[tt], m+1, r, k);
}  
int query2(int ss, int tt, int l, int r, int k) //小于等于的最大
{
    if(san[l] > k) {
        return -1;
    }
    if(sum[tt] - sum[ss] == 0) {
        return -1;
    }
    if(l == r) {
        if(k >= san[l]) {
            return l;
        }
        return -1;
    }
    int m = l+r>>1;
    int ret = -1;
    if(san[m + 1] <= k && sum[rs[tt]] - sum[rs[ss]]) {
        ret = query2(rs[ss], rs[tt], m + 1, r, k);
    }
    if(ret != -1) return ret;
    return query2(ls[ss], ls[tt], l, m, k);
}
 
int ca;
inline void Min(int &x, int y)
{
    if(x == -1 ¦¦ y < x) {
        x = y;
    }
}
void gogogo()  
{  
    int l,r,k;  
    for(int i=1;i<=n;i++)  
    {  
        scanf("%d",&num[i]);  
        san[i]=num[i];  
    }  
    tot=0;  
    sort(san+1,san+n+1);  
    int cnt=unique(san+1,san+n+1)-san-1;  
    build(1,cnt,T[0]);  
    for(int i=1;i<=n;i++) num[i]=lower_bound(san+1,san+cnt+1,num[i])-san;  
    for(int i=1;i<=n;i++)    update(T[i-1],num[i],1,cnt,T[i]);  
    printf("Case #%d:\n", ca++);
    while(m--)  
    {  
        scanf("%d%d%d",&l,&r,&k);  
        int ret = -1;
        int id=query1(T[l-1],T[r],1,cnt,k);  
        if(id != -1) Min( ret , abs(san[id] - k) );
        int id2=query2(T[l-1], T[r],1, cnt, k);
        if(id2 != -1) Min(ret , abs(san[id2] -k));
        printf("%d\n", ret);
    }  
}  
int main()  
{  
    int t;  ca = 1;
    scanf("%d",&t);  
    while(t--)   
    {  
        scanf("%d%d",&n,&m);  
        gogogo();  
    }  
    return 0;  
}

 

 

C:机器人

小冰的N个机器人兄弟排成一列,每个机器人有一个颜色。现在小冰想让同一颜色的机器人聚在一起,即任意两个同颜色的机器人之间没有其他颜色的的机器人。

假设任意相邻的两个机器人可以交换位置,请问最少需要多少次交换?

1 ≤ T ≤ 20

1 ≤ N ≤ 105

小数据

1 ≤ K ≤ 3

大数据

1 ≤ K ≤ 16

考虑最终的序列xxx yyy zzz。。

注意到K很小,考虑状态压缩,dp[mask]表示将mask状态的颜色放到开头的最小代价,枚举一种不在集合里面的颜色假设是j放到末尾,前面已经放好了,没必要再挤到前面去浪费次数

将某一种颜色j全部都放到当前状态的末尾的代价就是

\sum{}pair[k][j]

pair[k][j]表示k颜色在j颜色前面的对数

假设k是状态里面没有的颜色,因为j颜色移动到了所有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
const int N = 100010;
const long long inf = 1LL<<62;
long long f[1 << 16];
long long a[20][20];
long long s[N];
int two[22];
int Log[1<<20];
int main()
{
    for(int i = 0; i < 20; i++) two[i] = 1<<i;
    Log[1] = 0;
    for(int i = 1; i < 20; i++) Log[1<<i] = i;
    int t, n, k, ca = 1;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &k);
        memset(s, 0, sizeof(s));
        memset(a, 0, sizeof(a));
        int x;
        for(int i = 0; i < n; i++) {
            scanf("%d", &x);
            x--;
            for(int j = 0; j < k; j++) {
                a[j][x] += s[j];
            }
            s[x]++;
        }
        f[0] = 0;
        int full = two[k] - 1;
        for(int i = 1; i < two[k]; i++) {
            f[i] = inf;
            for(int jj = i; jj ; jj -= jj&-jj)  { //枚举一个子状态 f[i ^ (1 << j)],把j颜色放到末尾
                int j = Log[jj&-jj];
                int sum = 0;
                for(int kk = ~i & full; kk; kk -= kk&-kk) {//枚举每种不在状态里面的颜色
                    int k = Log[kk & -kk];
                    sum += a[k][j];//j颜色跨过了这些颜色,所以要加上这个代价。
                }
                f[i] = min(f[i], f[i ^ (1 << j)] + sum);
        }
        }
        printf("Case #%d: %lld\n",ca++, f[two[k] - 1]);
    }
    return 0;
}

 

 

D城市和魔法塔

 

原题啊。

做法就是一条边对应一个cost,最后求一个最小代价的环。

另外在凸包外面的点肯定没办法包围了。

update:

原来的代码忘了判断凸包小于三个点的时候的情况了,囧。

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<cstdio>
#include<cstring>
#include<algorithm>
#define op operator
const int inf = 1000000000;
const int MAX = 210;
int N, M, G, P;
struct PT {
        int x, y;
        PT() {}
        PT(int x, int y) :
                x(x), y(y) {
                }
        void in() {
                scanf("%d%d", &x, &y);
        }
        void print() {
                printf("x=%d y=%d\n", x, y);
        }
} guard[110], mine[110] , p[220];
bool op <(const PT& p1, const PT& p2) {
        return p1.y < p2.y ¦¦ (p1.y == p2.y && p1.x < p2.x);
}
bool op ==(const PT& p1, const PT& p2) {
        return p1.x == p2.x && p1.y == p2.y;
}
PT op+(const PT& p1, const PT& p2) {
        return PT(p1.x + p2.x, p1.y + p2.y);
}
PT op-(const PT& p1, const PT& p2) {
        return PT(p1.x - p2.x, p1.y - p2.y);
}
int op*(const PT& p1, const PT& p2) {
        return p1.x*p2.y - p1.y*p2.x;
}
int cross(PT a, PT b, PT c) {
        return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
inline void Min(int &x, int y) {
        if (y < x)
                x = y;
}
int dis[MAX][MAX], mp[MAX][MAX];
bool vis[MAX]; //标记某个金矿是否在凸包外面
void input() {
        scanf("%d%d%d%d", &N, &M, &G, &P);
        for (int i = 0; i < N; i++) {
                guard[i].in();
                p[i] = guard[i];
        }
        for (int i = 0; i < M; i++) {
                mine[i].in();
        }
}
void convex(PT *p, int &n) {
        if(n < 3) {
                return ;
        }
        std::sort(p, p + n);
        std::copy(p, p + n - 1, p + n);
        std::reverse(p + n, p + 2 * n - 1);
        int m = 0, top = 0;
        for(int i = 0; i < 2 * n - 1; i++) {
                while(top >= m + 2 && ((p[top - 1] - p[top - 2]) * (p[i] - p[top - 2])) <= 0) {
                        top --;
                }
                p[top++] = p[i];
                if(i == n - 1) {
                        m = top - 1;
                }
        }
        n = top - 1;
}
int inside_convex(PT q,int n,PT* p){
        for(int i = 0; i < n ; i++) {
                if(cross(p[i],p[i+1],q) < 0) return 0;
        }
        return 1;
}
int gao(int a, int b) {
        for (int i = 0; i < M; i++) if(!vis[i]){
                if (cross(guard[a], guard[b], mine[i]) < 0)
                        return inf;
        }
        return 2*P;
}
void solve(int ca) {
        int n = N;
        convex(p,n);
        int outside = 0;
        memset(vis,false,sizeof(vis));
        for(int i = 0; i < M; i++) if(!inside_convex(mine[i],n,p)) {
                vis[i] = true;
                outside ++;
        }
        for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                        mp[i][j] = inf;
                }
        }
        for(int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++)  if (i != j) {
                        mp[i][j] = gao(i, j);
                }
        }
        int ans = inf;
        for (int k = 0; k < N; k++) {
                for (int i = 0; i < N; i++) {
                        for (int j = 0; j < N; j++) {
                                mp[i][j] = std::min(mp[i][j],mp[i][k]+mp[k][j]);
                        }
                }
        }
        if(outside == M ¦¦ n < 3) ans = G * M;
        else {
                ans = inf;
                for(int i = 0; i < N; i++) ans = std::min(ans,mp[i][i]);
                ans /= 2;
                ans += outside * G ;
        }
        printf("Case #%d: %d\n",ca++,ans);
}
int main() {
        //  freopen("small.in", "r", stdin);
        //  freopen("cmp.out","w", stdout);
        int t, ca = 1;
        scanf("%d", &t);
        while (t--) {
                input();
                solve(ca++);
        }
        return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注