你最愿意做的哪件事，才是你的天赋所在

0%

发表于 Valine：

题目链接

最大异或子区间

思路

因为异或有前缀和的性质，然后就可以想到用trie树来进行求解，但是要求在线，就可以想到可持续化trie树，主要思想和主席树差不多。

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 6e5+10;
int rt[N],cnt[N*28];
int ch[N*28][2];
int qz[N];
int tt = 1;
int n,m;
void insert(int now, int pre, int t, int x){
    if(t<0)return ;
    int i = (x>>t)&1; // 获取当前的值
    ch[now][!i] = ch[pre][!i]; // 继承上一代的节点
    ch[now][i] = tt++;
    cnt[ch[now][i]]= cnt[ch[pre][i]] + 1;
    insert(ch[now][i], ch[pre][i], t - 1, x);
}
int query(int now,int pre,int t,int x){
    if(t<0)return 0;
    int i = (x>>t)&1;
    if(cnt[ch[pre][!i]] > cnt[ch[now][!i]]){
        return (1<<t)+query(ch[now][!i],ch[pre][!i],t-1,x);
    }else{
        return query(ch[now][i],ch[pre][i],t-1,x);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int a,b,c,i,j;
    char s[5];
    rt[0]=tt++;
    insert(rt[0],0,25,0);
    for(a=1;a<=n;a++){
        scanf("%d",&b);
        qz[a]=qz[a-1]^b;
        rt[a]=tt++;
        insert(rt[a],rt[a-1],25,qz[a]);
    }
    for(a=1;a<=m;a++){
        scanf("%s",s);
        if(s[0]=='A'){
            scanf("%d",&b);
            n++;
            qz[n]=qz[n-1]^b;
            rt[n]=tt++;
            insert(rt[n],rt[n-1],25,qz[n]);
        }else{
            scanf("%d%d%d",&i,&j,&b);
            i--;j--;
            if(i==0)printf("%d\n",query(0,rt[j],25,b^qz[n]));
            else printf("%d\n",query(rt[i-1],rt[j],25,b^qz[n]));
        }
    }
}

发表于 Valine：

比赛过程

一来我们分开看题，从前到后，从后到前，然后我看中间的D题。

一看感觉可以做，先上去打了个表，然后发现规律了，这时候队友说A题是签到题可以写，然后我就让出了电脑，然后我把D题跟队友说一下后修正思路确认了，然后等A题过了我就上去写D题，最后F题队友说启发式暴力合并可以过，但是需要维护一个集合的异或和，最后想到只要按位拆分01的个数维护起来就可以了，然后两个半小时得时候就过了，最后还刻了JKL三道题，最后三个人决定一起写K，然后一开始思路绕进去了，最后队友说一开始的思路是错的，这时候只剩下一个半小时重新想了，然后发现K的对数不是很多，可以先$n \times \sqrt n$的复杂度先处理出来因子，然后找到对数之后启发式暴力合并就可以了。写完只剩下10分钟，最后乱交了几发也没过，很可惜，在情况3的时候，多跑了一个加法。赛后才找到。

阅读全文 »

发表于 分类于 Valine：

Mybatis-Plus

Quick-Start

导入包

1
2
3
4
5
<dependency>
    <groupId>com.baomidou</groupId>
    <artifactId>mybatis-plus-boot-starter</artifactId>
    <version>3.4.0</version>
</dependency>
阅读全文 »

发表于 Valine：

深入理解Mysql(一)

索引数据结构

索引是帮助Mysql高效获取数据的排好序的数据结构

  • 二叉树
  • 红黑树
  • Hash表
  • B-Tree

B-Tree

B+Tree

  • 非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
  • 叶子节点包含所有索引字段
  • 叶子节点用指针连接,提高区间访问性能

[图片侵删]

Mysql的每个节点的大小为

阅读全文 »

发表于 Valine：

LCA(最近公共祖先)

倍增ＬＣＡ

倍增的思路就是利用二进制的性质存储状态

引入一个数组pre[i][j]表示ｉ节点的第$2^j$个祖先

如

pre[4][0]=3

pre[6][1]=2

pre[7][0]=2

pre[7][1]=1

我们可以发现一个很美妙的式子

pre[i][j]=pre[pre[i][j-1]][j-1]]

阅读全文 »

发表于 Valine：

题目大意

给n个点，求

的最大的链，n方的做法有很多，这里说nlogn的做法

先给x排序，然后如果第一维度相同第二维度倒序排序，然后球LIS即可

代码实现

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
class Solution {
    int arr[101001];
    vector<int>v;
    int getLIS(){
        for(int i=0;i<101001;i++)arr[i]=1e9+10;
        int l = 0;
        arr[0]=0;
        for(int i=0;i<v.size();i++){
            if(v[i]>arr[l])arr[++l]=v[i];
            else {
                int pos = lower_bound(arr + 1, arr + l + 1, v[i]) - arr;
                arr[pos]=v[i];
            }
        }
        return l;
    }
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(),envelopes.end(),[](const vector<int>& a,const vector<int>& b){
            return a[0]<b[0]||(a[0]==b[0]&&a[1]>b[1]);});
        for(int i=0;i<envelopes.size();i++){
            v.push_back(envelopes[i][1]);
        }
        return getLIS();

    }
};

发表于 Valine：

思路

类似一个树形DP，考虑如何从左右儿子更新父亲的状态即可，一共有三个状态

0 ： 没被覆盖

1： 放置摄像机

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
class Solution {
private:
    int result;
    int traversal(TreeNode* cur) {
        if(cur==NULL)return 2;
        int left = traversal(cur->left);
        int right = traversal(cur->right);
        if(left == 2 && right == 2){
            return 0;
        }
        else if(left == 0 || right == 0){
            result++;
            return 1;
        }else if(left == 1 || right == 1){
            return 2;
        }
        return -1;
    }

public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};

发表于 更新于 Valine：

Leetcode-685.冗余链接2

思路

1.首先造成冲突有两种方式分别是成环，两个父亲节点

2.如果一个节点有两个父亲节点，那么多余的边肯定在这个节点的两边中出现

3.还有一种情况就是可能会有即成环又有两个父亲节点，如下

1 2
2 3
3 4
1 4
5 2

image-20200917093411767

如果出现这种情况答案肯定是成环的边是多余的边，否则只会单独成环，或者单独冲突

阅读全文 »

发表于 更新于 Valine：

DNS 查询报文和响应报文

  • 当在浏览器中输入网站回车后，浏览器将向本机的DNS模块发送请求。
  • DNS模块是有缓存的，若缓存中有，则直接取ip地址，若没有则向下将DNS发送给UDP
  • UDP协议单元将该数据封装成IP数据包，传递给IP协议单元
  • IP协议单元再进行一层封装，加入DNS服务器的地址
  • 封装好的IP数据包将传递给链路层进行发送
  • 数据链路层发送到DNS服务器，若数据链路层的缓冲区中没有dns服务器的MAC，那么就发送ARP的广播请求等待回应
  • 得到回应之后将ip地址和对应的MAC地址写入APR缓存中，之后进行转发
  • DNS请求被发送到DNS服务器的数据链路层的协议单元
  • DNS服务器的数据链路层的协议单元会解析接收到的关键帧，并讲内部的IP数据包传送给网络层的IP协议单元
  • DNS服务器的IP协议单元解析收到的数据包，然后再向上剥壳，讲UDP数据传递给UDP协议单元
  • UDP将其内部的DNS报文传递给DNS服务单元，然后DNS服务单元解析域名对应IP地址，产生DNS回应报文，再发送给请求地址
阅读全文 »