"字节跳动杯"2018中国大学生程序设计竞赛-女生专场题解（非官方）_"字节跳动杯\"2018中国大学生程序设计竞赛-女生专场 [cloned]"

A - 口算训练

题意：
给定一个数列 { a n } \{a_n\} {an​} ，问 $d\mid \prod _{i=l}^r{a}_i$ 是否成立，其中 $d,l,r$ 都是给定正整数。

题解见队友博客，点击查看。

B - 缺失的数据范围

题意：
求满足 $n^a\lceil {\log }_{2}n{\rceil }^b⩽k$ 的整数 $n$ 的最大值，其中 $a,b⩽10,10^6⩽k⩽10^{18}$ 是给定正整数。

题解见队友博客，点击查看。

D - 奢侈的旅行

题意：
给定一个有 $m$ 条边的 $n$ 顶有向图，其中任意一条从 $u_i$ 到 $v_i$ 的边具有两个相关值 $a_i,b_i$ 。现欲从顶点 $1$ 走到顶点 $n$ ，每次经过一条边 $e_i$ 的时候都要判断 $\text{cost}={\log }_2\frac{\text{level}+a_i}{\text{level}}⩾b_i$ 是否成立，成立才能通行。其中 $\text{level}$ 的初始值为 $1$ ，且每经过一条边 $e_i$ 都要增长 $a_i$ 。
问是否存在从结点 $1$ 到结点 $n$ 的最短路径，如果存在，求最小总 $\text{cost}$ 。

解法：
包装过的单源最短路径问题。

我们可以将到达结点 $i$ 时的 $\text{level}{\mid }_i$ 写成 $1+\sum _{j\in G_{\pi ,i}}{a}_j$ ，其中 $G_{\pi ,i}$ 表示顶点 $i$ 在最短路径上的前驱子图。若记结点 $i$ 在最短路径上的后继结点为 $i^{\prime }$ ，则总的 $\text{cost}$ 就可以写为
∑ i log ⁡ 2 1 + ∑ j ∈ G π , i a j + a i 1 + ∑ j ∈ G π , i a j = log ⁡ 2 ( ∏ i 1 + ∑ j ∈ G π , i ′ a j 1 + ∑ j ∈ G π , i a j ) = log ⁡ 2 ( 1 + ∑ j ∈ G π , n a j ) = log ⁡ 2 ( level ∣ n )

$$\begin{aligned} &\sum_i\log_2\frac{1+\sum\limits_{j\in G_{\pi,i}} a_j+a_i}{1+\sum\limits_{j\in G_{\pi,i}} a_j}\\ =&\log_2\left(\prod_i\frac{1+\sum\limits_{j\in G_{\pi,i'}} a_j}{1+\sum\limits_{j\in G_{\pi,i}} a_j}\right)\\ =&\log_2\left(1+\sum\limits_{j\in G_{\pi,n}} a_j\right)\\ =&\log_2(\text{level}\mid_{n})\end{aligned}$$ ===​i∑​log2​1+j∈Gπ,i​∑​aj​1+j∈Gπ,i​∑​aj​+ai​​log2​⎝⎜⎛​i∏​1+j∈Gπ,i​∑​aj​1+j∈Gπ,i′​∑​aj​​⎠⎟⎞​log2​⎝⎛​1+j∈Gπ,n​∑​aj​⎠⎞​log2​(level∣n​)​

因此，只要求解以结点 $1$ 为起点，以各边的 $a_i$ 值为边权的单源最短路径即可。

值得注意的是，松弛过程中要记得判断当前边是否可取。

另外，在判断的时候还可以将式子两边乘方变为整数与 $2$ 的次幂之间的比较，以提高精度。

参考代码：

#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>

typedef long long ll;
const ll INF=1e18;
const int MAXN=1e5+10;
int n,m;
struct qnode{
    int v;
    ll c;
    qnode(int v=0,ll c=0):v(v),c(c){}
    bool operator<(const qnode &oth)const{
        return c>oth.c;
    }
};
struct Edge{
    int v,a,b;
};
std::vector<Edge> G[MAXN];
ll dist[MAXN];
bool check(ll c,int a,int b){
    return (1+a/c)>=((ll)1<<b);
}
std::priority_queue<qnode> pq;
void dijkstra(){
    dist[1]=1;
    pq.push(qnode(1,1));
    qnode tmp;
    while (!pq.empty()){
        tmp=pq.top();pq.pop();
        int u=tmp.v;
        ll c=tmp.c;
        if (dist[u]<c) continue;
        for (int i=0;i<G[u].size();++i){
            int v=G[u][i].v;
            int cost=G[u][i].a;
            int b=G[u][i].b;
            if (check(c,cost,b)&&dist[v]>c+cost){
                dist[v]=c+cost;
                pq.push(qnode(v,dist[v]));
            }
        }
    }
}
void init(){
    while (!pq.empty()) pq.pop();
    for (int i=1;i<=n;++i)
        G[i].clear();
    for (int i=1;i<=n;++i)
        dist[i]=INF;
}
int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%d%d",&n,&m);
        init();
        for (int i=0;i<m;++i){
            int u,v,a,b;
            scanf("%d%d%d%d",&u,&v,&a,&b);
            G[u].push_back((Edge){v,a,b});
        }
        dijkstra();
        ll res=dist[n];
        if (res==INF) res=-1;
        else res=floor(log2(res));
        printf("%lld\n",res);
    }
    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

F - 赛题分析

题意：
给定两组数，求分别的最小值。

解法：
签到题， $O(n)$ 算法求最值即可。

参考代码：

#include <cstdio>
const int INF=0x3f3f3f3f;
int main(){
    int t;
    scanf("%d",&t);
    for (int x=1;x<=t;++x){
        int n,m;
        scanf("%d%d",&n,&m);
        int y=INF,z=INF;
        for (int i=0;i<n;++i){
            int a;
            scanf("%d",&a);
            if (a<y) y=a;
        }
        for (int i=0;i<m;++i){
            int b;
            scanf("%d",&b);
            if (b<z) z=b;
        }
        printf("Problem %d:\n",x+1000);
        printf("Shortest judge solution: %d bytes.\n",y);
        if (z!=INF)
            printf("Shortest team solution: %d bytes.\n",z);
        else printf("Shortest team solution: N/A bytes.\n");
    }
    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

H - SA-IS后缀数组

题意：

给定一个字符串，请你比较该字符串每个相邻后缀的字典序大小。

题解见队友博客，点击查看。

K - CCPC直播

题意：
给定参赛选手的测评信息，请你按照一定要求做成直播面板。

解法：
格式化输出问题，照做即可。

参考代码：

#include <cstdio>
char s[20],t[20];
int main(){
	int T;
	scanf("%d",&T);
	while (T--){
		int rank,prob;
		scanf("%d %s %d %s",&rank,s,&prob,t);
		printf("%3d|%-16s|%d|[",rank,s,prob);
		if (t[0]=='F') printf("    AC*   ");
		else if(t[0]=='R'&&t[1]=='u'){
			int p;
			scanf("%d",&p);
			for (int i=0;i<p;i++)
                printf("X");
			for (int i=p;i<10;i++)
                printf(" ");
		}
		else printf("    %-3s   ",t);
		puts("]");
	}
	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