2019百度之星初赛三 1001最短路1（异或）

旧城等待， 2023-08-17 15:41 107阅读 0赞

# 最短路一 #

题目链接：[http://bestcoder.hdu.edu.cn/contests/contest\_showproblem.php?cid=863&pid=1001][http_bestcoder.hdu.edu.cn_contests_contest_showproblem.php_cid_863_pid_1001]

题目：

有一张 nnn 个点的完全无向图，点的标号是 1...n1...n1...n，其中边 (i,j)(i,j)(i,j) 的长度是 i xor jixorji xor j，现在你需要求出点 111 到点 nnn 的最短路的长度。

Input

第一行一个正整数 TTT 表示数据组数 1≤T≤1001\\leq T\\leq 1001≤T≤100

对于每组数据：第一行一个正整数 nnn 表示点数 (2≤n≤105)(2\\leq n\\leq 10^5)(2≤n≤105)

Output

输出 TTT 行，每行一个整数表示点 111 到点 nnn 的最短路

Sample Input

1
    3

Sample Output

2
    思路：可以将10以内的所有i,j打个表，求出i，j的异或值，然后手推几个例子就发现1到n的直接异或值是最短的，通过其他路径的都比1到n的权值长

#include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    #include<math.h>
    #include<map>
    using namespace std;
    const int maxn=1e6+7;
    int main()
    {
        int n,T,m;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            m=(1^n);
            printf("%d\n",m);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11404650.html

[http_bestcoder.hdu.edu.cn_contests_contest_showproblem.php_cid_863_pid_1001]: http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=863&pid=1001

发表评论取消回复

表情：

评论列表（有 0 条评论，107人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019 年百度之星·程序设计大赛 - 初赛四 1006 Totori's Switching Game

题意：判断在一个图（可能有重边,但是没有自环）中是否存在k个生成树，且它们的边互不相同。分析：水题，统计一下每个节点的度，k就是所有节点的最小度。代码：...

亦凉/ 2024年04月17日 06:00/ 0 赞/ 54 阅读

相关 HDU 6675 度度熊与排列【2019百度之星初赛二1002】

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6675 度度熊与排列 **Time Limit: 2000...

- 日理万妓/ 2024年04月17日 05:39/ 0 赞/ 69 阅读

相关 2019百度之星初赛三 1001最短路1（异或）

最短路一题目链接：[http://bestcoder.hdu.edu.cn/contests/contest\_showproblem.php?cid=863&pid=

旧城等待，/ 2023年08月17日 15:41/ 0 赞/ 108 阅读

相关 2019百度之星初赛二 1001 度度熊与数字（因子问题）

1001 度度熊与数字题目链接：[http://bestcoder.hdu.edu.cn/contests/contest\_showproblem.php?cid=8

柔情只为你懂/ 2023年08月17日 15:41/ 0 赞/ 102 阅读

相关 2019百度之星初赛一1001Polynomial（数学的函数收敛）

Polynomial 题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6668][http_acm.hdu.edu.cn_

素颜马尾好姑娘i/ 2023年08月17日 15:41/ 0 赞/ 26 阅读

相关【题目记录】——2021 年百度之星·程序设计大赛 - 初赛二

文章目录 1001 签到数学模拟 1002 随机题意思维 1003 魔怔图论欧拉回路 1004 净化数学，思维题目地址 [2

心已赠人/ 2022年09月04日 03:49/ 0 赞/ 181 阅读

相关 2016百度之星资格赛1001-1004

不加头文件了。。看着乱 1001：逆元的应用求出第一个字符到后面每个字符的哈希值，存储到数组ansss\[\]中求出第一个字符到后面每个字符哈希值的逆元的乘积

àì夳堔傛蜴生んèń/ 2022年07月24日 06:22/ 0 赞/ 170 阅读

相关百度之星初赛B

A ：传送门：[点我][Link 1] 求联通块个数，对于简单图而言，就是c=v-e,其中c就是联通块个数，v是顶点数，e是边数 include <algorith

àì夳堔傛蜴生んèń/ 2022年05月16日 00:06/ 0 赞/ 173 阅读

相关百度之星初赛 A 杭电6375

B 度度熊学队列链接：[点我][Link 1] Problem Description 度度熊正在学习双端队列，他对其翻转和合并产生了很大的兴趣。初始时有 N

﹏ヽ暗。殇╰゛Y/ 2022年05月15日 00:14/ 0 赞/ 221 阅读

相关 2019百度之星初赛第二场度度熊与运算式1

题意： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L

系统管理员/ 2021年10月12日 19:19/ 0 赞/ 244 阅读