牛客寒假算法基础集训营5

发表于 更新于 分类于
本文字数： 7.6k 阅读时长 ≈ 7 分钟

A.炫酷双截棍

题目描述：

小希现在手里有一个连着的两块木条，长度分别为$ l_1,l_2 $，木条之间有一个无摩擦的连接点，木条之间可以相互转动，小希将其称之为双截棍。
现在小希把长为 $ l_1 $ 的木条的一端放在原点 $ (0,0) $，任意转动这两根木条，小希想知道，是否有可能通过一种转动方式使得双截棍的另一端到达指定点呢?
如果不能，请输出所有能到达的点中离目标点最近的距离。

输入描述：

第一行输入一个两个正整数 $ l_1,l_2 $，表示木条长度。第二行输入一个正整数T，表示询问次数。随后T行，每行两个实数 $ x_i,y_i $ 表示目标点的坐标。
$ l_1,l_2 \leq 1000 $
$ T \leq 1000 $
$ |x|,|y| \leq 10000 $

输出描述：

对于每次询问，如果可以到达，输出0，如果无法到达，给出所有能到达的点中离目标点最近的距离。你的答案将被认为是正确的，如果相对误差不大于 $ 10^{-6} $。

输入

1
2
3
4
5
23 13
3
15 1
40 0
0 0

输出

1
2
3
0.00000000
4.00000000
10.00000000

思路：

签道题！有2点需要注意：①不同类型的数据使用不同类型的绝对值函数；②两个浮点数相等的判定方法：若其差的绝对值小于某个精度，则默认相等。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const double precision = 1e-6;
int T, l1, l2, minus_a, plus_a; double x, y, z;
int main() {
    while(~scanf("%d%d", &l1, &l2)) {
        minus_a = abs(l1 - l2), plus_a = l1 + l2; //整数用abs()函数
        scanf("%d", &T);
        while(T--) {
            scanf("%lf%lf", &x, &y);
            x = fabs(x), y = fabs(y); //浮点数用fabs()函数
            z = sqrt(x * x + y * y);
            if((minus_a < z || fabs(z - minus_a) < precision) && (z < plus_a || fabs(plus_a - z) < precision)) printf("%.8f\n", 0.0); //如果两个实数相等，则其差的绝对值小于某个精度
            else printf("%.8f\n", min(fabs(z - minus_a), fabs(z - plus_a)));
        }
    }
    return 0;
}

D.炫酷路途

题目描述：

小希现在要从寝室赶到机房，路途可以按距离分为N段，第i个和i+1个是直接相连的，只需要一秒钟就可以相互到达。
炫酷的是，从第i个到第 $ i+2^p $ 个也是直接相连的（其中p为任意非负整数），只需要一秒钟就可以相互到达。
更炫酷的是，有K个传送法阵使得某些u,v之间也是直接相连的，只需要一秒钟就可以相互到达，当然，由于设备故障，可能会有一些u=v的情况发生。
现在小希为了赶路，她需要在最短的时间里从寝室(编号为1)到达机房(编号为N)，她不希望到达这N个部分以外的地方（不能到达位置N+1），也不能走到比自己当前位置编号小的地方（比如从5走到3是非法的）。
她想知道最短的时间是多少。

输入描述:

第一行输入两个整数N,K，表示路途的段数和传送法阵的数量。
从第二行开始K行，每行两个整数 $ a_i,b_i $ 表示两个位置之间相连。
$ 2 \leq N \leq 1000000000 $
$ 0 \leq K \leq 15 $

输出描述:

输出一个整数，表示从寝室到机房最短的时间是多少秒。

输入

1
2
3
4
5
6
7
12 2
1 5
6 6

17 2
2 5
8 9

输出

1
2
3
3

1

思路：

补这道题新学了不少东西：①C++STL中的unique函数，注意，一般是先排序，再去重，其返回值是一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。②用lowbit(int x)函数求一个整数x的二进制中’1’的个数（x & -x：求x的二进制中最低位1表示的10进制数）。因为从第i个到第 $ i+2^p $ 个也是直接相连的（其中p为任意非负整数），所以把两个点之间的距离 $ \sum_{p = 1}^k 2^p $ 转换成二进制，二进制中有k个1说明要走k步。③G++编译环境中，__builtin_popcount(unsigned int x)可以 $ O(1)$ 计算x的二进制中’1’的个数。题解：将所有额外连边的点再加上起点终点构成一张单独的有向图，然后计算这些点两两间的距离并求起点到终点最短路即可。

AC代码：

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
#pragma GCC optimize (3) //吸氧
#pragma GCC target ("popcnt") //加速
/**===========__builtin_xxx()函数的头文件================**/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m, a[20], b[20], dist[32];
vector<int> vec;
int count_bits(int x) { //求x的二进制数中'1'的个数
    int cnt = 0;
    for(int i = x; i > 0; i -= i & -i) cnt++;
    return cnt;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    while(cin >> n >> m) {
        vec.clear(); memset(dist, 0x3f, sizeof(dist));
        vec.push_back(1), vec.push_back(n);
        for(int i = 0; i < m; ++i) {
            cin >> a[i] >> b[i];
            if(a[i] > b[i]) swap(a[i], b[i]); //保证从小的编号到大的编号
            vec.push_back(a[i]), vec.push_back(b[i]);
        }
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        //先排序，再去重
        dist[0] = 0; //起点到自身的距离为0
        for(size_t i = 0; i < vec.size(); ++i) {
            for(size_t j = i + 1; j < vec.size(); ++j) {
                for(int k = 0; k < m; ++k)
                    if(vec[i] == a[k] && vec[j] == b[k]) dist[j] = min(dist[j], dist[i] + 1); //若有传送法阵，则尝试着更新最短时间
                dist[j] = min(dist[j] , dist[i] + __builtin_popcount(vec[j] - vec[i])); //操作的时间复杂度是0(1)
                //dist[j] = min(dist[j] , dist[i] + count_bits(vec[j] - vec[i])); //操作的时间复杂度是O(logn)
            }
        }
        cout << dist[vec.size() - 1] << endl;
    }
    return 0;
}

E.炫酷划线

题目描述：

平面上有一个圆，圆环上按顺时针顺序分布着从1到n，一共n个点。
现在无聊的小希开始按某种顺序对其在圆内两两连线，小希尽量避免让两条线碰撞，可是有的时候，这显然避免不了。
现在你知道小希划线的顺序是什么，请你判断小希在最优情况下，什么时候会被迫使得线相交，输出最早的时刻（是第几条线）。

输入描述：

数据第一行一个整数T，表示数据组数。
每组数据第一行输入两个整数N,M，代表点的个数和游戏进行的轮数。
随后M行，每行两个整数 $ a_i,b_i $，表示两个点之间连线。
数据保证每个点最多被连线一次。
$ T \leq 10 $
$ 1 \leq N,M \leq 100000 $
$ 1 \leq ai,bi \leq 100000 $

输出描述:

对于每组数据，一行。
如果中途某一条线开始无法避免相交，则输出当轮轮数。
否则，输出-1。

输入

1
2
3
4
5
6
7
8
9
2
10 4
5 3
1 9
2 6
7 10
4 2
1 2
3 4

输出

1
2
4
-1

思路：

题意转化为：读入一些区间，输出直到有区间交叉的第一个轮数。做法：用树状数组维护，每连一条线，给其所在区间打上不同标记，然后对区间左端点和右端点进行求和，（重点判断依据）若左端点的和等于右端点的和，说明区间中没有其他线段加入，即没有交叉区间，否则就输出当轮轮数。涨知识了！

AC代码：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100005;
int T; LL n, m, a, b, tree[maxn]; bool flag;
inline LL read(){
    LL x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
void add(LL x, LL v) {
    for(LL i = x; i <= n; i += i & -i) tree[i] += v;
}
LL query(LL x) {
    LL res = 0LL;
    for(LL i = x; i > 0; i -= i & -i) res += tree[i];
    return res;
}
int main() {
    while(~scanf("%d", &T)) {
        while(T--) {
            memset(tree, 0, sizeof(tree));
            n = read(), m = read(); flag = false;
            for(LL i = 1; i <= m; ++i) {
                a = read(), b = read();
                if(flag) continue;
                if(a > b) swap(a, b);
                add(a, i), add(b + 1, -i); //打标记，赋予不同值，这样才能区分是否有交叉区间
                //cout << query(a) << ' ' << query(b) << endl;
                if(query(a) != query(b)) { //若左端点值不等于右端点值，说明肯定有交叉区间
                    flag = true;
                    printf("%lld\n", i);
                }
            }
            if(!flag) printf("-1\n");
        }
    }
    return 0;
}

G.炫酷数字

题目描述：

小希希望你构造一个最小的正整数，使得其有n个因子。

输入描述：

第一行一个整数T表示数据组数
每组数据第一行输入一个正整数n，表示其因子数。
$ n \leq 1000000 $
$ T \leq 1000000 $

输出描述：

输出一行一个整数，表示你构造出的这个数。注意：你需要保证你构造的数 $ \leq 10^6 $，如果在这个范围里面无法构造出一个正整数满足条件，请输出-1。

输入

1
2
3
2
4
5

输出

1
2
6
16

思路：

做这题时第一反应就是约数个数定理，然后胡思乱想（未果，期间还尝试着用dfs写，但感觉情况很复杂），不知如何构造这个最小正整数……赛后看了题解恍然大悟QWQ，只需通过埃氏筛法 $ O(nlog^{log^n}) $ 统计 $ 1 \sim 10^6 $ 中每个数的因子个数，然后标记一下具有 $ 1 \sim 10^6 $ 个因子对应的最小正整数即可QWQ。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+1;
int T, n, ans[maxn], cnt[maxn];
int main() {
    memset(cnt, 0, sizeof(cnt));
    memset(ans, -1, sizeof(ans));
    for(int i = 1; i < maxn; ++i) {
        for(int j = i; j < maxn; j += i)
            cnt[j]++; //累加j的因子个数
        if(ans[cnt[i]] == -1) ans[cnt[i]] = i; //具有n个因子的最小正整数
    }
    while(~scanf("%d", &T)) {
        while(T--) {
            scanf("%d", &n);
            printf("%d\n", ans[n]);
        }
    }
    return 0;
}

I.炫酷镜子

题目描述：

小希拿到了一个镜子块，镜子块可以视为一个N x M的方格图，里面每个格子仅可能安装\或者/的镜子,会反射90°光线，也可能没有安装镜子，使用.代替。
但她看不清楚里面的镜子构造是怎样的。
你是这块镜子块的主人，所以你想计算这块镜子块（从输入的上方往下射入光线）从左到右每一格射入依次分别会从最下面的哪一格子射出，如果无法射出，输出-1。

输入描述:

第一行输入两个整数N,M。随后的N行，每行M个字符。
$ 1 \leq N,M \leq 500 $.

输出描述:

输出M行整数，依次为从第i个格子从上往下射入时从下面的哪里射出，如果光线不会从下面射出，则输出-1。

输入

1
2
3
4
3 3
...
...
\.\

输出

1
2
3
3
2
-1

说明

第一列遇到镜子两次反弹通过第三列射出。
第二列直接射出。
第三列因为镜子反弹后向右边射出。

思路：

简单的dfs！一开始以为会陷入死胡同，即构成四角，就用一个vis数组标记已访问过的，然后一直WA……实际上并不会构成四角，入射到的镜子可能再次入射到，且光线一定会射出边界，所以当光线射出边界时直接判断即可。
注意：因为’\’是转义字符，所以判断一个字符是否为反斜杆，应为’\‘。

AC代码：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 505;
int n, m, flag; //bool vis[maxn][maxn];
char mp[maxn][maxn];
void dfs(int x, int y, int c_x, int c_y) { //c_x，c_y 对应四种状态：上下左右
    if(flag == -1 || flag == 1) return;
    if(x == -1 || y == -1 || y == m ) {flag = -1; printf("-1\n"); return;}
    if(x == n) {flag = 1; printf("%d\n", y + 1); return;}
    //if(vis[x][y]) return; //无需标记是否已访问，因为光线肯定不会陷入死胡同，并且一定射出边界
    //vis[x][y] = true;
    if(mp[x][y] == '.') dfs(x + c_x, y + c_y, c_x, c_y);
    else if(mp[x][y] == '/') {
        if(c_x == 1 && c_y == 0) dfs(x, y - 1, 0, -1); //下--->左
        else if(c_x == -1 && c_y == 0) dfs(x, y + 1, 0, 1); //上--->右
        else if(c_x == 0 && c_y == 1) dfs(x - 1, y, -1, 0); //右--->上
        else dfs(x + 1, y, 1, 0); //左--->下
    }
    else { // mp[x][y] = '\\'
        if(c_x == 1 && c_y == 0) dfs(x, y + 1, 0, 1); //下--->右
        else if(c_x == -1 && c_y == 0) dfs(x, y - 1, 0, -1); //上--->左
        else if(c_x == 0 && c_y == 1) dfs(x + 1, y, 1, 0); //右--->下
        else dfs(x - 1, y, -1, 0); //左--->上
    }
}
int main() {
    while(~scanf("%d %d", &n, &m)) {
        for(int i = 0; i < n; ++i) scanf("%s", mp[i]);
        for(int j = 0; j < m; ++j) {
            flag = 0;
            //memset(vis, false, sizeof(vis));
            dfs(0, j, 1, 0);
            if(flag == 0) printf("-1\n");
        }
    }
    return 0;
}

J.炫酷数学

题目描述

小希最近想知道一个东西，就是A+B=A|B(其中|为按位或)的二元组有多少个。
当然，直接做这个式子对小希来说太难了，所以小希改变了一些条件，她仅想知道其中 $ A,B < N $ 的情况，其中N为2的幂次。
当然，(A=1,B=0)和(A=0,B=1)被认为是不同的二元组。

输入描述:

第一行输入一个非负整数M。
$ N=2M,M \leq 100 $，即2的M次为N。

输出描述:

一个整数ans，对998244353取模。

输入

1
2
3
0

71

输出

1
2
3
1

588378066

思路：

签道题！打表找规律：$ 3^m $。python大法好，简单粗暴！

AC代码：

1
print(pow(3,int(input()),998244353))
0%