长沙理工集训队-9.11日组队赛

发表于 | 更新于 | 阅读次数：
本文字数： 14k | 阅读时长 ≈ 13 分钟

好久没写博客了，写篇博客放松一下。

外网OJ：http://csustacm.com:4803/

1题我就不写了这题写了也没啥意义。

2.黄金矿工

Description

游戏中有n个宝石，每个宝石有一个价值vi，每次挖出这个宝石需要时间ti。因为有些宝石被另外一个宝石挡住了（两个宝石在同一直线上），一个宝石最多挡住一个宝石，一个宝石最多被一个宝石挡住。要先捡起挡路的宝石，才能捡起该宝石。每个宝石的挡路宝石为fi，如果没有挡路宝石fi = 0，即它自己(题目保证没有环，且不存在)。

游戏的时间限制是t秒，在t秒内你获得最大价值和是多少？

Input

第一行一个整数T，表示接下来有T组数据。（T <= 50）

每组数据格式如下：

第一行两个整数n（1<=n<=200），t（1<=t<=100,000,000）

接下来n行，每行三个整数vi（1<=vi<=50），ti（1<=ti<=1000,000），（0<=fi<=n）

Output

输出获得的最大价值和

Sample Input 1 

1
1 5 10 2 1 0 5 3 1 3 2 0 1 4 3 4 6 4

Sample Output 1

1
11

题意：挖宝石，挖某个宝石前可能有一个宝石，一个宝石也只能阻难一个宝石，挖某个宝石要消耗时间ti获得价值vi，问T=t秒最多可以挖宝石的最大价值。

题解：看了下数据范围，肯定是以价值DP，求价值的最小时间，如果时间小于所给定的时间就可以挖到相应价值。

首先处理下，每个宝石前后最多只有一个，肯定是一条链，把每条链处理一下（假如一条链是1->2->3,那么这条链上就有3个节点分别保存2个值，挖到1，(v1,t1）挖到2，（v1+v2,t1+t2）挖到3,(v1+v2+v3,t1+t2+t3))。最多只有200条链，所以不用担心超时。

每条链保存 两个值，价值和所需要的时间。然后在DP就行了。因为每条链上只能选一个值所以DP肯定要开二维。

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
 #include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
#define debug(x) cout<<"["<<x<<"]"<<endl;

typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
const int maxn=1e3+7;
const int inf=0x3f3f3f3f;

int n, m, tot;
int son[maxn];
int in[maxn], v[maxn], t[maxn], vis[maxn];
vector<P> ar[maxn];
int dp[205][10005];
void dfs(int u,int val,int tim) {  //用DFS，一条链
    vis[u] = 1;
    ar[tot].push_back(make_pair(val+v[u],tim+t[u]));
    if(son[u] == 0)return;
    dfs(son[u],val+v[u],tim+t[u]);
}
int main() {
    int tim;
    scanf("%d", &tim);
    while(tim--) {
        scanf("%d%d", &n, &m);
        int sum = 0;
        for(int i = 0; i <= n; ++i) {
            son[i]=vis[i]=0;
            ar[i].clear();
        }
        for(int i = 1, u; i <= n; ++i) {
            scanf("%d%d%d", &v[i], &t[i], &u);
            sum += v[i];
            //if(u == 0)continue;
            son[u] = i;
        }
        tot = 0;
        for(int i = 1; i <= n; ++i) {
            if(vis[i] == 0) {//如果这个节点没有父亲，就说明这有一条链。
                dfs(i, 0, 0);
                tot++;
            }
        }
        memset(dp, 0x3f, sizeof(dp));        
        for(int i = 0; i < tot; ++i) {    。
            ar[i].push_back(make_pair(0, 0));//每个链肯定可以一个都不挖，所以0 ，0要加进去。
            sort(ar[i].begin(),ar[i].end());
        }
        int sz = ar[0].size();
        for(int i = 0; i < sz; ++i) {//dp初始化
            dp[0][ar[0][i].fi] = ar[0][i].se;
        }
        for(int i = 1; i < tot; ++i) {
            sz = ar[i].size();
            for(int j = 0; j < sz; ++j) {
                for(int k = sum; k >= ar[i][j].fi; --k) {
                    dp[i][k] = min(dp[i-1][k-ar[i][j].fi]+ar[i][j].se,dp[i][k]);
                }
            }
        }
        int ans = 0;
        for(int i = sum; i >= 0; --i) {
            if(dp[tot-1][i]<=m) {  //找第一个小于等于给定时间的价值
                ans = i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

3.精灵王国

Description

小J离开了神秘群岛之后，来到了繁华的精灵王国。

精灵王国中有n个城市，现在已知第 i 个城市和第 i + 1个城市之间有一条长度为d[i]的双向道路。（特别的，第n个城市和第1个城市之间有一条长度为d[n]的双向道路）。

随着经济的发展，精灵王国的城市之间建立了m条地铁，第i条地铁可以从城市u[i]前往v[i]，也可以从v[i]前往u[i]，同时地铁的长度为w[i]。

现在小J在各个城市之间旅游，小J想知道从城市x前往城市y旅游需要花费多长的时间？

Input

第一行为2个整数n、m。

第二行为n个正整数d[i]。

接下来m行每行三个正整数u[i]、v[i]、w[i]。

第m+3行为一个正整数Q，表示询问次数。

接下来Q行每行两个正整数x、y，表示一次从城市x到城市y的旅行。

数据范围：1<=n,q<=1e5,1<=m<=30,1<=u[i],v[i],x,y<=n,1<=d[i],w[i]<=1e9;

Output

输出Q行每行一个正整数表示该次旅行的最短时间。

Sample Input 1 

1
4 1 1 2 3 6 1 3 2 5 1 2 1 4 1 3 2 3 4 3

Sample Output 1

1
1 5 2 2 3

看起来挺难的，其实是到原题。。，把数据范围改了一下，见牛客第二场挑战赛。

看起来很难，实际上简单的一匹，只有30条铁路，直接把有铁路的60个点直接全部跑一次最短路，然后问两个点之间的最短距离，要么坐了地铁，那么就是到60个点中的一个最短路加上从这个有铁路的点到另一个点的最短路，要么就是不做地铁，不做地铁一个前缀和就行了。

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
 #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;

int n,m;
int d[maxn];
LL dp[maxn];
vector<int> v;
bool u[maxn];
struct edge {
    int to,next;
    LL w;
} eg[maxn*3];
int tot,head[maxn];
void add(int u,int v,int w) {
    eg[tot].to=v;
    eg[tot].w=w;
    eg[tot].next=head[u];
    head[u]=tot++;
}
LL dis[65][maxn];
int main() {
    scanf("%d%d",&n,&m);
    mem(head,-1);
    for(int i =  1; i <= n ; i ++) {
        scanf("%d",&d[i]);
        dp[i]=dp[i-1]+d[i];
        if(i==n) {
            add(1,n,d[i]);
            add(n,1,d[i]);
        } else {
            add(i,i+1,d[i]);
            add(i+1,i,d[i]);
        }
    }
    while(m--) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(u[a]==0) {
            v.push_back(a);
            u[a]=1;
        }
        if(u[b]==0) {
            v.push_back(b);
            u[b]=1;
        }
        add(a,b,c);
        add(b,a,c);
    }
    mem(dis,inf);
    priority_queue<P,vector<P>,greater<P> > q;
    for(int i = 0 ; i < v.size(); i ++) {
        dis[i][v[i]]=0;
        q.push(P(0,v[i]));
        while(q.size()) {
            int u = q.top().second;
            q.pop();
            for(int j = head[u]; j!=-1; j=eg[j].next) {
                edge &e=eg[j];
                if(dis[i][e.to]>dis[i][u]+e.w) {
                    dis[i][e.to]=dis[i][u]+e.w;
                    q.push(P(dis[i][e.to],e.to));
                }
            }
        }
    }
    int Q;
    scanf("%d",&Q);
    while(Q--) {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a>b)swap(a,b);
        LL ans=min(dp[b-1]-dp[a-1],dp[n]-(dp[b-1]-dp[a-1]));
        for(int i =0 ; i <v.size(); i++) {
//                    debug(dis[i][a]+dis[i][b]);
            ans=min(ans,dis[i][a]+dis[i][b]);
        }
        printf("%lld\n",ans);
    }

    return 0;
}

5.zzq的数学教室2

Description

zzq想保研，他的成绩单上有一排非递减顺序的成绩，面试时老师想知道他数学成绩的位置，zzq知道他的数学成绩是x分，他要找到第一个出现x的位置。

他想运用二分查找算法， 代码如下：

image.png

显然L就是最终的位置。

可是现在他的成绩全被lcy学姐打乱了（随机把数字乱放）。

他想知道最后找到的位置仍然是原来的位置的概率， 请你帮帮他。

概率是在模1e9 + 7意义下的， 即 p / q = p * inv(q) 。inv(q)是q在模1e9 + 7 意义下的逆元。

Input

输入第一行一个正整数N。

第二行N个正整数a[i]，代表的是原来的成绩单，呈非递减顺序。

第三行一个数字x，代表他的数学成绩。

1 <= N <= 1e5

1 <= a[i] <= 1e9

x保证是某一个a[i]。

Output

输出一个整数代表概率。

Sample Input 1 

1
8 1 1 1 3 7 9 9 10 1

Sample Output 1

1
1

Sample Input 2 

1
3 1 2 2 2

Sample Output 2

1
333333336

Hint

对于第二个样例，lcy学姐可能打乱成这3种等概率的情况：

1 2 2

2 1 2

2 2 1

其中只有第一种会结果正确。

概率是1 / 3。

题解：水题，直接把小于x的个数，a，和大于x的个数算出来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
 #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;

int l,r;
LL pow(LL x,LL n) {
    LL ans=1;
    while(n) {
        if(n&1)ans=ans*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return ans;
}
int n,x;
int a[maxn];
int main() {
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i ++) {
        scanf("%d",&a[i]);
    }
    scanf("%d",&x);
    LL mx=0,mi=0;
    for(int i = 1; i<=n; i++) {
        if(a[i]>=x) {
            mx++;//大于等于x的个数
        } else {
            mi++;//小于等于x的个数
        }
    }
    int l=1,r=n;
    LL ans=1;
    while(l<=r) {
        int mid=(l+r)/2;
        if(a[mid]>=x) {
            ans=ans*mx%mod*pow(mi+mx,mod-2)%mod;//需要一个选一个大于等于x的数，选到的概率是(mx/(mi+mx));
            mx--;
            r=mid-1;
        } else {
            ans=ans*mi%mod*pow(mi+mx,mod-2)%mod;//同上。
            mi--;
            l=mid+1;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

6.zzq的数学教室

Description

众所周知，摸鱼是qwb的一大爱好。即使是在zzq的数学课上，qwb也是在疯狂摸鱼。这被眼尖的zzq发现了，所以zzq决定考考摸鱼的qwb，如果qwb答不出来，他的平时分自然就归零了。

现在zzq把数字1~n从左至右排成一排（第i个数的值为i），接下来进行m轮操作，每次操作描述如下：将奇数位置的数字取出形成序列A，将偶数位置的数字取出形成序列B，将A序列拼接在B序列之后，构成新的序列。

现在问题来了：进行m次操作后，第k个位置的数字是多少呢？

Input

第一行，输入2个正整数n,q

接下来q行，每行2个整数m和k，表示zzq想知道在m次操作之后第k个位置上的数是多少。

数据范围：

n<=5000

q<=1e6

m<=1e6

k<=n;

Output

输出q行，每行输出第k个位置的数字。

Sample Input 1 

1
5 2 1 2 2 3

Sample Output 1

1
4 2

水题

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
 #include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"["<<x<<"]"<<endl;

typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
const int maxn=5e3+7;
const int inf=0x3f3f3f3f;

int n,q;
int ar[maxn], br[maxn];
int ans[maxn][maxn];
int main(){
    while(~scanf("%d%d", &n, &q)){
        for(int i = 1; i <= n; ++i){
            ar[i] = ans[0][i] = i;
        }
        int tot, tim = 1;
        do{
            tot = 1;
            for(int i = 2; i <= n; i += 2){
                ans[tim][tot] = ans[tim-1][i];
                //printf("%d ", ans[tim][tot]);
                tot++;
            }
            for(int i = 1; i <= n; i += 2){
                ans[tim][tot] = ans[tim-1][i];
                //printf("%d ", ans[tim][tot]);
                tot++;
            }
            int flag = 0;
            for(int i = 1; i <= n; ++i){
                if(ans[tim][i] != ar[i])flag = 1;
            }
            if(flag == 0)break;
            tim ++;
        }while(1);
        //printf("*%d\n",tim);
        int m, k;
        while(q--){
            scanf("%d%d", &m, &k);
            m %= tim;
            if(m == 0)m = tim;
            printf("%d\n", ans[m][k]);
        }
    }
    return 0;
}

7.玩游戏

Description

dr喜欢玩游戏，现在有n个游戏，每个游戏时间为[Li,Ri)，现在问题是，找出最长的一段游戏时间，使得该时间段被至少k个游戏完全覆盖(这k个区间要每一个都要完全覆盖你选出来的这个区间）。

Input

多组输入

第一行n,k(1<=n,k<1e6)

接下来n行，每行两个数l,r(1<=l<r<=1e9)

Output

输出这个区间的长度

Sample Input 1 

1
3 2 1 5 1 4 1 3

Sample Output 1

1
3

贪心就好，每次从最先结束的一个线段开始选，然后找最小的k小于当前线段结束点的起点，然后满足条件的区间就是当前区间的终点减去k个起始点中最大值。找完这个线段的终点后把这个区间删掉，然后依次类推下去知道找完所有的线段。本来每次找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
 #include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"["<<x<<"]"<<endl;

typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
const int maxn=1e6+7;
const int inf=0x3f3f3f3f;
struct th {
    int st,en,id;
    bool operator <(const th a)const {
        if(en==a.en) {
            return st<a.st;
        } else return en<a.en;
    }
} a[maxn];
bool u[maxn];
priority_queue<P,vector<P>,greater<P> >q;
int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m)) {
        for(int i=0; i<n; i++) {
            scanf("%d%d",&a[i].st,&a[i].en);
            a[i].id=i;
            q.push(P(a[i].st,i));
        }
        sort(a,a+n);
        int cnt=0,ans=0,L=0;
        memset(u,0,sizeof(u));
        for(int i =0; i<n; i++) {
            if(!u[a[i].id])cnt++;
            u[a[i].id]=1;
            L=a[i].st;    //本来这是要找最大值的，但是数据有点水，直接就过去了。。。
            while(cnt<m&&q.size()) {
                if(u[q.top().second]==1) {
                    q.pop();
                    continue;
                } else if(q.top().first>=a[i].en) {
                    break;
                } else {
                    cnt++;
                    u[q.top().second]=1;
                    L=max(L,q.top().first);
                    q.pop();
                }
            }
            if(cnt==m) {
                ans=max(ans,a[i].en-L);
            }
            cnt--;
        }
        while(q.size())q.pop();
        printf("%d\n",ans);
    }
    return 0;
}

9.签到题

Description

“素数就是因子只包含1和它本身的数”zzq如是说道。

现在zzq的数学课下课了，他发现qwb在他的课摸鱼，于是要出一个题考qwb：N！的素因子有多少个？

如果qwb做不出来就要被py交易！但是qwb完全不知道zzq上课讲了什么，于是向从来不摸鱼的你求助了（划重点：这是简单题）。

Input

第一行输入一个整数T（T \leq 10T≤10），表示有T组数据。

每组数据输入站一行，输入一个整数N（N \leq 10^5N≤105）

Output

对于每组数据，输出N!有多少个素因子

Sample Input 1 

1
2 1 4

Sample Output 1

1
0 4

如题目。

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
 #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;

const int maxn=1e5+7;
const int inf=0x3f3f3f3f;

int prim[maxn], p[maxn], pcnt;
int sum[maxn];
int main() {
    int t;
    prim[0]=1;
    prim[1]=1;
    pcnt = 0;
    for(int i =2; i < maxn; i++) {
        if(!prim[i]) p[pcnt++] = i;
        for(int j = 0; j < pcnt&&i*p[j]<maxn; ++j) {
            prim[i*p[j]] = 1;
            if(i%p[j] == 0)break;
        }
    }
    sum[0] = 0;
    sum[1] = 0;
    sum[2] = 1;
    for(int i = 3; i < maxn; ++i) {
        int tmp = i,cnt = 0;
        if(prim[i] == 0) {
            sum[i]=sum[i-1]+1;
            continue;
        }
        for(int j = 0; j < pcnt; ++j) {
            while(tmp % p[j] == 0) {
                tmp /= p[j];
                cnt++;
            }
            if(tmp == 1)break;
        }
        if(tmp!=1)cnt++;
        sum[i] = sum[i-1] + cnt;
    }
    int n;
    scanf("%d",&t);
    while(t--) {
        scanf("%d", &n);
        printf("%d\n", sum[n]);
    }
    return 0;
}