2016 百度之星复赛 round 3

发表于 |

只能贴部分题解了，因为太弱了。其它题不会，也不怎么感兴趣。

弱渣需要继续努力。

hdu 5714 拍照 题目

大致题意：有一些船在河里以相同的速度水平行驶（有的向左，有的向右），一个人在河边视角90度，问此人在何时何处能看到最多的船。

显然，我们可以把向左的船看作静止的。如果只看静止的船，那么这个问题就变成了最多区间交问题。排序处理一下就行了。不好表达，看代码自然明了。对于向右的船，如果在静止情况最优解的左边，那么会算入最终答案，否则不会。

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
//#pragma comment(linker,"/STACK:10240000,10240000") // C++ only
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
using namespace std;
typedef long long LL;
#if ( ( _WIN32 || __WIN32__ ) && __cplusplus < 201103L)
#define lld "%I64d"
#else
#define lld "%lld"
#endif
template<typename T>
void upmax(T &a,T b){ if(a<b) a=b;}
//typedef __int128 ll; // for g++
//const int INF =  0x3f3f3f3f;
//1e9+7,1e9+9,1e18+3,1e18+9 are prime
//479<<21|1=1004535809,17<<27|1=2281701377 and g=3
/*------ Welcome to my blog: http://dna049.com ------*/
const int N = 2e4+4;
int val[2];
struct Node{
    int p,add,type;
    bool operator<(const Node& A)const{
        return p==A.p?add>A.add:p<A.p;
    }
}a[N],*s;
int main(){
//    #define dna049 1
#ifdef dna049
    freopen("/Users/dna049/Desktop/AC/in","r",stdin);
    LL time = clock();
#endif
    //    freopen("/Users/dna049/Desktop/AC/out","w",stdout);
    int T;
    scanf("%d",&T);
    for(int Case = 1; Case <= T; ++Case){
        printf("Case #%d:\n",Case);
        s = a;
        int n,x,y,z,d;
        scanf("%d",&n);
        for(int i=0;i<n;++i){
            scanf("%d%d%d%d",&x,&y,&z,&d);
            x+=z;y-=z;
            if(x<y) continue;
            *(s++) = (Node){x,-1,d!=1};
            *(s++) = (Node){y,1,d!=1};
        }
        sort(a,s);
        int ans = 0, tmax = 0;
        val[0]=val[1]=0;
        for(Node *cur=a; cur<s; ++cur){
            val[cur->type]+=cur->add;
            upmax(tmax,val[0]);
            upmax(ans,tmax+val[1]);
        }
        printf("%d\n",ans);
    }
#ifdef dna049
    printf("time: %f\n",1.0*(clock()-time)/CLOCKS_PER_SEC);
#endif
    return 0;
}

以上代码参考 wwt15
代码优势：用指针迭代，以及 (Node){p,add,type} 的写法值得学习。

hdu 5715 XOR 游戏 题目

大致题意：给你一个长为 $n$ 的数组 $a$，把它分成 $M$ 段，且每段的长度不超过 $L$。求使得所有分段方式中每一段异或和的最小值最大的值。

显然，我们预处理出前缀和 $s$，那么问题就变成了，在 $s$ 中取 $M$ 个数，它们相隔不超过 $L$, 使得相邻数之间的异或和的最小值最大。
二分答案，每次监测答案能否达到，用 $f[i][j] = 1$ 表示以 $j$ 结尾，取 $i$ 个数，相邻数之间的异或和的最小值大于当前答案。显然我们需要确定的是 $f[M][n]$ 是否为 1。

显然 $f[0][0] = 1$，$f[i][j]=1$ 当且仅当 $\exists k, 1 \leq k \leq L$ 使得 $f[i-1][j-k]=1, s[j] \oplus s[j-k] \geq now$。
因此我们直接 $dp$ 就行，但是直接做会超时，因此用数字字典树 Trie 来优化。
即求 $f[i][j]$ 时，把 $f[i][j-k]=1,\; 1 \leq k \leq L$ 的那些 $s[k]$ 丢入到字典树中，那么只要查看字典树中是否存在与 $s[j]$ 异或不小于当前答案的数即可。 

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
//#pragma comment(linker,"/STACK:10240000,10240000") // C++ only
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
using namespace std;
typedef long long LL;
#if ( ( _WIN32 || __WIN32__ ) && __cplusplus < 201103L)
#define lld "%I64d"
#else
#define lld "%lld"
#endif
template<typename T>
void upmax(T &a,T b){ if(a<b) a=b;}
//typedef __int128 ll; // for g++
//const int INF =  0x3f3f3f3f;
//1e9+7,1e9+9,1e18+3,1e18+9 are prime
//479<<21|1=1004535809,17<<27|1=2281701377 and g=3
/*------ Welcome to my blog: http://dna049.com ------*/
struct Trie{
    Trie *nt[2];
    int cnt;
    Trie() { nt[0] = nt[1] = NULL; cnt = 0; }
};
const int Maxb = 31;
void insert(Trie* root, int x, int add){
    root->cnt += add;
    for(int i=Maxb-1;i>=0;--i){
        if(root->nt[(x>>i)&1]==NULL)  root->nt[(x>>i)&1] = new Trie();
        root = root->nt[(x>>i)&1];
        root->cnt += add;
    }
}
void clear(Trie *root){
    if(root->nt[0] != NULL) clear(root->nt[0]);
    if(root->nt[1] != NULL) clear(root->nt[1]);
    delete root;
}
int getans(Trie* root,int x,int k){
    int ans = 0;
    for(int i=Maxb-1;i>=0;--i){
        Trie* t = root->nt[((x>>i)^1)&1];
        root = root->nt[((k^x)>>i)&1];
        if(!((k>>i)&1) && t != NULL)   ans += t->cnt;
        if(root == NULL)    break;
    }
    if(root != NULL)    ans += root->cnt;
    return ans;
}
const int N = 1e4+4;
const int M = 11;
int a[N],n,m,L,now;
bool f[M][N];
bool check(Trie *root){
    memset(f,0,sizeof(f));
    f[0][0] = 1;
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            if(f[i-1][j-1]) insert(root,a[j-1],1);
            if(j>L&&f[i-1][j-L-1])  insert(root,a[j-L-1],-1);
            f[i][j] = getans(root,a[j],now) != 0;
        }
        for(int j=1;j<=L;++j){ // L <= n
            if(f[i-1][n-j]) insert(root, a[n-j], -1);
        }
    }
    return f[m][n];
}
int main(){
//        #define dna049 1
#ifdef dna049
    freopen("/Users/dna049/Desktop/AC/in","r",stdin);
    LL time = clock();
#endif
    //    freopen("/Users/dna049/Desktop/AC/out","w",stdout);
    int T;
    scanf("%d",&T);
    for(int cc = 1; cc <= T; ++cc){
        printf("Case #%d:\n",cc);
        scanf("%d%d%d",&n,&m,&L);
        int tmax = 0;
        for(int i=1;i<=n;++i){
            scanf("%d",a+i);
            upmax(tmax,a[i]);
            a[i]^=a[i-1];
        }
        Trie* root = new Trie();
        for(int i=0;i<=n;++i)   insert(root, a[i], 0);
        int l=0,r=1;
        while(r<tmax)   r<<=1;
        r+=r-1;
        while(l<=r){
            now = (l+r)>>1;
            if(check(root)) l=now+1;
            else        r=now-1;
        }
        printf("%d\n",r);
        clear(root);
    }
#ifdef dna049
    printf("time: %f\n",1.0*(clock()-time)/CLOCKS_PER_SEC);
#endif
    return 0;
}

hdu 5717 矩阵方程的解 题目

此题就是求解线性方程组

$$ (x_1,x_2, \cdots, x_n) A = (1,0,\cdots,0) $$
其中 $A = (a_{ij})_{n \times n}, \quad a_{ij} = [i \mid j]$

题目问，第 $k$ 个 $d$ 在 $x = (x_1,x_2, \cdots, x_n)$ 中 的位置。

由我的博文：两类反演公式及其矩阵形式 知，矩阵 $A$ 的转置本质上就是 Mobius 反演的矩阵形式，因此 $A$ 的逆矩阵 $B = (b_{ij})_{n \times n} $

$$ b_{ij} = \left \lbrace \begin{array}{cc} \mu (\frac{i}{j}), & j|i \\
0, & else. \end{array} \right. $$

而 $x$ 其实就是 $B$ 的第一行，因此 $x_i = \mu(i)$。因为题目保证了有答案，因此 $d$ 只可能是 $-1,0,1$。

由我的博文：数论函数的 Dirichlet 积 知

  1. $M(n)=\sum_{i=1}^n \mu(i)$ 有计算公式
    $$ \sum_{i=1} ^n M(\lfloor \frac{n}{i} \rfloor) = 1 $$
  2. $Q(n)=\sum_{i=1}^n |\mu(i)|$ 有计算公式
    $$ Q(n) = \sum_{d^2 \leq x} \mu(d) \lfloor \frac{x}{d^2} \rfloor $$

那么 $n$ 以内的，使得

  1. $\mu(m)=-1$ 个数： $\frac{Q(n)-M(n)}{2}$
  2. $\mu(m)=0$ 的个数： $n-Q(n)$
  3. $\mu(m)=1$ 的个数： $\frac{Q(n)+M(n)}{2}$

最终我们进行 “二分查找” 答案。当时 TLE 就是因为本渣用的是最普通的二分查找，导致过多计算最后爆炸。这里应该启发式的思考，以后写二分查找一定要对问题的性质进行思考，启发式查找进而减少迭代步数。

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
//#pragma comment(linker,"/STACK:10240000,10240000") // C++ only
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
using namespace std;
typedef long long LL;
template<typename T>
void upmax(T &a,T b){ if(a<b) a=b;}
//typedef __int128 ll; // for g++
//const int INF =  0x3f3f3f3f;
//1e9+7,1e9+9,1e18+3,1e18+9 are prime
//479<<21|1=1004535809,17<<27|1=2281701377 and g=3
#if ( ( _WIN32 || __WIN32__ ) && __cplusplus < 201103L)
#define lld "%I64d"
#else
#define lld "%lld"
#endif
/*------ Welcome to my blog: http://dna049.com ------*/
const int N = 1.3e7+7;
bool ip[N];
int mu[N],p[N],sumu[N];
void init_mu(){
    mu[1]=1;ip[2]=true;p[0]=2;
    for(int i=1;i<N;i+=2)   ip[i]=true;
    for(int i = 3,cnt = 1;i<N;i+=2){
        if(ip[i]){
            p[cnt++] = i;
            mu[i] = -1;
        }
        for(int j = 1,t;j<cnt&&(t= i * p[j])<N;++j){
            ip[t] = false;
            if(i % p[j] == 0)   break;
            mu[t] = -mu[i];
        }
    }
    for(int i=2;i<N;i+=4)   mu[i]=-mu[i>>1];
    for(int i=1;i<N;++i)    sumu[i]=sumu[i-1]+mu[i];
}
map<LL,LL> mp;
LL M(LL n){
    if(n<N) return sumu[n];
    map<LL,LL>::iterator it = mp.find(n);
    if(it!=mp.end())    return it->second;
    LL r=1;
    for(LL i=2,j;i<=n;i=j+1){
        j=n/(n/i);
        r-=(j-i+1)*M(n/i);
    }
    mp.insert(pair<LL,LL>(n,r));
    return r;
}
LL Q(LL n){
    LL r=0;
    for(LL i=1,t;(t=i*i)<=n;++i){
        r+=mu[i]*(n/t);
    }
    return r;
}
LL f(int d, LL n){
    if(d == 0)  return n-Q(n);
    if(d == -1) return (Q(n)-M(n))>>1;
    if(d == 1)  return (Q(n)+M(n))>>1;
    return 0;
}
LL getans(int d, LL k){
    LL l = 0, r = 5*k+100,m,t;
    LL wl = 0, wr = f(d,r);
    while(l+1<r){
        m = 1.0*(k-wl)/(wr-wl)*(r-l)+l;
        m = min(max(m,l+1),r-1);
        t = f(d,m);
        if(t<k) l=m,wl=t;
        else    r=m,wr=t;
    }
    return r;
}
int main(){
//#define dna049 1
#ifdef dna049
    freopen("/Users/dna049/Desktop/AC/in","r",stdin);
    LL time = clock();
#endif
//    freopen("/Users/dna049/Desktop/AC/out","w",stdout);
    init_mu();
    int T,d;
    scanf("%d",&T);
    while(T--){
        LL k;
        scanf("%d" lld,&d,&k);
        printf(lld "\n",getans(d,k));
    }
#ifdef dna049
    printf("time: %f\n",1.0*(clock()-time)/CLOCKS_PER_SEC);
#endif
    return 0;
}

欢迎批评指正