Retr67的小站

发表于 更新于

设备管理器->通用串行总线控制器->USB根集线器->属性->电源管理->关闭允许计算机关闭此设备以节约电源(如果不能解决，请关闭其他USB的节约电源）

原因：计算机长时间待机会关闭HDMI接口

设备管理器

属性

其他USB

发表于 更新于

题目

给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

洛谷题目链接

读入格式

第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。

接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。

输出格式

输出包含M行，每行包含一个正整数，依次为每一个询问的结果。

输入样例一

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

输出样例一

4
4
1
4
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
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
#include <stdio.h>
#include <iostream>
#define re register

//类模板快读 
template <class T> inline void read(T &x) {
    x=0;char c=getchar();
    for(; '0'>c || c>'9'; c=getchar());
    for(; '0'<=c && c<='9'; c=getchar()) x=(x<<1)+(x<<3)+(c^48);
}

//边数 
int cnt;

//双向建边，双倍空间，不做过多解释 
int To[1000005],Next[1000005],head[500005],d[500005];

//fa[u][i]为u往上跳2^i个点所到达的父亲 
int fa[500005][21];

//链式前向星 
inline void add(int u,int v) {
    To[++cnt]=v;
    Next[cnt]=head[u];
    head[u]=cnt;
}

//记录当前节点和父亲节点 
void dfs(int u,int Dad) {

    //当前深度=父亲+1； 
    d[u]=d[Dad]+1;

    //2^0=1,u往上跳1格所到达的父亲; 
    fa[u][0]=Dad;

    //fa[u][1]=fa[fa[u][0]][0]
    //以u为起点跳2格=自己的父亲跳一格
    //以此类推，感性理解 
    for(re int i=1; (1<<i)<=d[u]; ++i) fa[u][i]=fa[fa[u][i-1]][i-1];

    //遍历u节点为起始点的所有边 
    for(re int i=head[u]; i; i=Next[i])

    //因为之前是双向建边，所以为了防止来回跑，故进行判断 
        if(Dad^To[i]) dfs(To[i],u);
}

//重点！倍增LCA 
inline int LCA(int a,int b) {

    //确保a的深度小于b的深度
    if(d[a]>d[b]) std::swap(a,b);

    //接着要让它们跳到同一层,但一个一个慢慢往上跳太慢了，于是得定义它们的跳跃方式 
    //跳跃方式让我们抽象理解一下 
    //a是一个后面长眼睛的人 
    //最初i很大,跳的非常远，远到天边,深度底
    //而我们要做的是让a,b同层,跳到天边的,看不到,不予理会
    //i慢慢的小了,小到跳到a的后面了，能看到了，那就让b跳到这里
    //随着i慢慢缩小,b越来越小步的往前跳,慢慢缩进距离,直到同一层 
     for(re int i=20; i>=0; --i) 
         if(d[a]<=d[fa[b][i]]) b=fa[b][i];

    //如果跳到同一层后数值相同，证明找到LCA了
    if(a==b) return a;

    //如果跳到同一层后数值仍不同，就一起往上跳，跳到fa[a][0]==fa[b][0]为止
    //跳跃方式与上文类似，只是不比较深度，而改为比较数值是否相同，也就是祖先是否一致
    //同一层开始一起跳，比较深度也没意义吧 
    for(re int i=20; i>=0; --i)
        if(fa[a][i] != fa[b][i]) 
            a=fa[a][i],b=fa[b][i];

    //找到啦!
    return fa[a][0]; 
}

int main() {
    int N,M,S;
    read(N),read(M),read(S);
    for(re int i=1,X,Y; i<N; ++i) {
        read(X),read(Y);

        //双向加边
        add(X,Y),add(Y,X);
    }
    dfs(S,0);
    for(re int i=1,A,B; i<=M; ++i) {
        read(A),read(B);

        //求二者的最近公共祖先 
        printf("%d\n",LCA(A,B));
    }
    return 0;
}

发表于 更新于

题目

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。

windy想知道， 在A和B之间，包括A和B，总共有多少个windy数？

100%的数据，满足1<=A<=B<=2000000000

洛谷题目链接

读入格式

包含两个整数，A B。

输出格式

一个整数

输入样例一

1 10

输出样例一

9

题解

数位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
#include <stdio.h>
#define re register

int a[15];
int f[15][15];

inline int Abs(int x) {return x<0?-x:x;}

inline void Next_Dp() {
    //f[i][j] i为位数，j为第i位的数值
    //f[i][j]=f[i-1][k] 如果（j-k）的绝对值大于等于2 即合法 
    //初始化 f[1][j]=1 j属于0-9
    for(re int j=0; j<=9; ++j) f[1][j]=1;
    for(re int i=2; i<=10; ++i)
        for(re int j=0; j<=9; ++j)
            for(re int k=0; k<=9; ++k)
                if(Abs(j-k)>=2) f[i][j]+=f[i-1][k];
}

//求[0,X) 
inline int Solve(int x) {
    int ans=0,len=0;
    //分解每一位数 
    while(x) {
        a[++len]=x%10;
        x/=10;
    }
    //除了最高位，求每一位的0-9的所有f[i][j] i=1->len-1 j=0->9;
    for(re int i=1; i<len; ++i)
        for(re int j=1; j<=9; ++j)
            ans+=f[i][j];
    //求最高位，小于X的f[i][j]
    for(re int j=1; j<a[len]; ++j) ans+=f[len][j];
    //逐位等于X，往下比 
    for(re int i=len-1; i; --i) {
        for(re int j=0; j<=a[i]-1; ++j)
            if(Abs(j-a[i+1])>=2) ans+=f[i][j];
        if(Abs(a[i+1]-a[i])<2) break;
    }
    return ans;
}

int main() {
    Next_Dp();
    int A,B;
    scanf("%d %d",&A,&B);
    printf("%d\n",Solve(B+1)-Solve(A));
    return 0;
}

发表于 更新于

关于我自己个人对随机值的一些了解，以及水分（RP++）模板

srand(unsigned(time(NULL))); 根据当前时间生成随机种子

rand() 根据种子生成值

1
2
3
4
5
6
7
8
9
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#define re register

int main() {
    srand(unsigned(time(NULL)));
    rand()%2?puts("Yes"):puts("No");
}

发表于 更新于

一个我也忘记我什么时候学的读入优化

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
#include <stdio.h>
#define re register

//fread直接读入文件流到内存中，速度快 ，测试后耗时为getchar（） 的 5分之一 左右 
inline char nc() {
    static char buf[100000],*p1=buf,*p2=buf;
    //static 个人理解为只作用于设定地点的变量，每次返回时数组不变
        //例如：退出函数时，数组存放了1，再次进入函数，数组依然存放着1，所以这句话也可以写成全局变量
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
        //fread(buf,1,100000,stdin) 读入100000次，长度为1，存入buf中，fread返回值为有效读取字符数
    //p1=读入文件头，p2=读入文件尾，如果p1==p2，证明读完文件
    //buf数组清空时才会继续读入
    //可运用C++的调试查看具体过程 
}

//类模板
//可随读入类型的不同，自动变化类型
//fread快读=正常的快读 把getchar改成自定义的读入
template <class T> inline void read(T &x) {
    x=0;char c=nc();bool p=false;
    for(; '0'>c || c>'9'; c=nc()) p|=c=='-';
    for(; '0'<=c && c<='9'; c=nc()) x=(x<<1)+(x<<3)+(c^48);
    x=p?-x:x;
}

int main() {
    freopen("a+b.in","r",stdin);//测试时请使用freopen,提交时可去除----Luogu等在线OJ
    int A,B;
    read(A),read(B);
    printf("%d",A+B);
}

警告 使用此方法后，慎用cin等自带的读入文件方式，用此方法读入后，文件流可能会有残留，造成读入失败

0%