zhangas

Pay more attention

0%

Veröffentlicht am

206. Reverse Linked List

How to exchange the nodes without changing their values?
from the side to another: u could see[pre, cur, cur->next]
it’s easy to know when “cur” gets NULL, the “pre” is at the end of linked list.
we could store “cur->next” in temp then makes “cur” at front of “pre”
so now “pre” turned to “cur” and “cur” turned to the temp’s value(used to be “cur->next”)

1
2
3
4
5
6
7
8
9
10
11
ListNode* reverseList(ListNode* head) {
        ListNode* pre=NULL;
        ListNode* cur=head;
        while(cur!=NULL){
            auto t=cur->next;
            cur->next=pre;
            pre=cur;
            cur=t; 
        }
        return pre;
}

Veröffentlicht am Bearbeitet am

Foreword

进厂真不如保安，反正都学不到东西

Chapter one : 日结工作

加入本地兼职群

去问问保安,尤其是那些兼职的,黑衣服黑鞋黑裤子,然后衣服脏一点的。
你去给他一根烟,让他拉你本地兼职群,因为他们每天任务，都会建群。

比如今天1月20号，他们先建一个群，然后群里发时间你几点去。
记住这个时间，在他们之前去！！ 他们都是人够了，然后在群里说，路上的不用来了，
你还亏地铁费路费。
part-time jobs groups

初涉工作

去了之后，站队，站齐，面对面建群。群名就是工资群。
然后跟好你的带队的，记住他长啥样，下班就找他的队伍
工资发了别退，这个群以后你的带队可能会发任务，
然后上班期间，你尽量找没人地方玩手机，下班过去了就行。

工作雷区

  1. 景区 : 这是最恶心的，因为有的游客就是傻逼 + 领导还不停来
  2. 小区保安 : 来给给业主们当孙子

推荐工作

  1. 拆迁保安 : 去了朝那一坐, 抽烟玩手机就行, 反正就是装逼
    还分为便衣保安 : 钱多但要抬人的，也可能打架，千万不要去！！
    我第一回去不知道就他妈当的便衣，200多个人火拼
  2. 定时拍照 : 比如商场周围的, 每隔一个小时发点照片, 只需多拍几张，
    水印相机改时间就行。其他时间做亭子里打王者抽烟搞基没人管你
  3. 工程施工保安 ：夜班睡一觉领钱就完事了。
    他不给你发钱你直接在群里说这带队的不发钱或者扣钱，他不会把你怎么样的。
    实在不发你把衣服穿走，他自己要垫钱的。
    2019年6月19号 我带队的没给我发120工资，老子把他三套保安服，一个盾，
    一个棍子，三双鞋当垃圾扔了，本来把我删了后来又加我来了，问我衣服呢。

成为带队

通过巴结领导，说我要当你带队的，每天还能多几十的工资，在20年都快干成队长了

Veröffentlicht am Bearbeitet am

按位的数学运算，也叫半加运算(不进位加法运算)
转换为二进制后 对应相同为1 不同为0
①归零律a^a=0
②恒等率a^0=a
③交换律结合律
④自反性a^b^a=b
实现交换两个数a=3 b=4
a=a^b b=a^b a=a^b 之后a=4 b=3

选数异或 蓝桥13届A组D

给定一个长度为 n 的数列 A1,A2,⋅⋅⋅,An 和一个非负整数 x，给定 m 次查询，每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x。

输入格式
输入的第一行包含三个整数 n,m,x。
第二行包含 n 个整数 A1,A2,⋅⋅⋅,An。
接下来 m 行，每行包含两个整数 [l,r] 表示询问区间 [l,r]。

输出格式
对于每个询问，如果该区间内存在两个数的异或为 x 则输出 yes，否则输出 no。
input：
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3

output：
yes
no
yes
no

解题思路

性质 若a^b=x 则a^x=b
预处理出每个序号满足条件的最大左端点
再判断满足条件 [l,r] 中r的最大序数dp[r]是否比l大

样例解释

异或运算
显然维护的dp[3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
map<int,int>mp;//key是Ai value是序号
void solve(){
    int l=read(),r=read();
    if(dp[r]>=l)puts("yes");
    else puts("no");
}
int n=read(),m=read(),x=read();
    for(int i=1;i<=n;i++){
        int t=read();
        dp[i]=max(dp[i-1],mp[t^x]);//t^x反求出 与t满足 ans^t==x的最小ans
        mp[t]=i;
    }
    //预处理 a^b=x a^x=b 处理出dp[r]满足条件的最小左序号
    
    while(m--){
        solve();
    }

Veröffentlicht am Bearbeitet am

2020七段码

分类讨论数数
①不包含G
放置个数1:6 2:6 3:6 4:6 5:6 6:1
sum1=31
②包含G
放置个数1:1 2:4 3:10 4:14 5:13 6:6 7:1
sum2=49
放3个有10种情况
放3个有10种情况
放4个有14种情况
放4个有14种情况
放5个有13种情况
去3个有13种情况

共有80种情况 答案为80

Veröffentlicht am Bearbeitet am

22年12月20日晚上11点16分记完了单词准备上床睡觉
但是刚躺下几分钟感觉浑身发冷打颤
大脑像是裂开一样 量了下体温发现发烧了38.9
寄了 轮到我成为小🐏人了 尝试睡觉
睡着后2点20分左右醒了 发现我浑身还是冰凉
同时感到身体像是被揍了一顿一样 翻个身都很费劲
我把衣服全穿上睡觉 8点40分醒了 到了最恶心的时刻了
头疼+嗓子吃刀片 这下真的要寄了 心里面一直在骂娘
中间又昏睡着一次 现在是中午11.30 头还是很疼 身体发软

Veröffentlicht am Bearbeitet am

数位排序 前缀和与差分

若将一维数组a的[l,r]区间加上c 且时间复杂度为O(n)
设b[]是 a[]的差分 先将a的[l,+∞]加上c 再讲a[r+1,+∞]减去c

1
2
3
4
void insert(int l,int r){
    b[l]+=c;
    b[r+1]-=c; 
}

统计出现的次数cnt[]记录

1
2
3
4
5
6
7
8
9
10
11
12
while(m--){
    int l,r;scanf("%d%d",&l,&r);
    //如果直接嵌套循环会TLE
    //for(int i=l;i<=r;i++)cnt[i]++;
    //转化为差分 在循环外面求差分
    cnt[l]++;cnt[r+1]--;
}
for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
sort(a+1,a+n+1);sort(cnt+1,cnt+1+n);
ll sum2=0;
for(int i=1;i<=n;i++)sum2+=cnt[i]*a[i];
printf("%lld",sum2-sum1);

孤独的照片

给一个只含’A’,’B’两种字符的字符串
找出所有字串中 含有单个元素的个数
input：
5
GHGHG
output：
3

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
易知'A'和'B'地位相同
情况分为两种
① AAB BAAA B前面或者后面A的个数-1 即为方案数
② ABA ABAA B前后A的个数之积 即为方案数
先预处理打上序号
const int N=5e5+5;
ll g[2][N],h[2][N];
//第0行表示从前往后连续出现的个数
//第1行表示从后往前连续出现的个数
for(int i=1;i<=n;i++){
    if(c[i]=='H') h[0][i]=h[0][i-1]+1;
    else g[0][i]=g[0][i-1]+1;
}
for(int i=n;i>=1;i--){
    if(c[i]=='H') h[1][i]=h[1][i+1]+1;
    else g[1][i]=g[1][i+1]+1;
}
//遍历计算两种方案
ll ans=0;
for(int i=1;i<=n;i++){
    if(c[i]=='H'){
        if(c[i-1]=='G'&&g[0][i-1]>1) ans+=g[0][i-1]-1;
        if(c[i+1]=='G'&&g[1][i+1]>1) ans+=g[1][i+1]-1;
        if(c[i-1]=='G'&&c[i+1]=='G') ans+=g[0][i-1]*g[1][i+1];
    }
    else{
        if(c[i-1]=='H'&&h[0][i-1]>1) ans+=h[0][i-1]-1;
        if(c[i+1]=='H'&&h[1][i+1]>1) ans+=h[1][i+1]-1;
        if(c[i-1]=='H'&&c[i+1]=='H') ans+=h[0][i-1]*h[i+1];
    }
}cout<<ans<<endl;

统计次数 记忆化递归

求从1到n这n个正整数的十进制表示中 k出现的次数。
1≤ n≤ 10^6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N=1e6+5;
int f[N],v[N]={1};//v[0]=1 && f[0]=0;
int count(int i,int k){
    if(v[i]) return f[i];
    f[i]=f[i/10]+(i%10)==k;
    v[i]=1;
    return f[i];
}
int main(){
    int n,k;cin>>n>>k;
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=count(i,k);
    }
    cout<<ans<<endl;
}

上课睡觉 数论

有 N 堆石子，每堆的石子数量分别为 a1,a2,…,aN。
可以对石子堆进行合并操作，将两个相邻的石子堆合并为一个石子堆，例如，如果 a=[1,2,3,4,5]，合并第 2,3 堆石子，则石子堆集合变为 a=[1,5,4,5]。
我们希望通过尽可能少的操作，使得石子堆集合中的每堆石子的数量都相同。
请你输出所需的最少操作次数。本题一定有解，因为可以将所有石子堆合并为一堆。
1≤ N ≤10^5

设操作x次成功 合并后有N-x堆
设每组有y个 y*(N-x)=Σai
性质有 sum%y==0 当y最小时 x也取到最小
可以从小到大枚举sum的因数 并检测一下是否符合题意

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
const int N=1e5+5;
int n;
int a[N];
bool check(int y){
    int t=0;
    for(int i=1;i<=n;i++){
        t+=a[i];
        if(t==y)t=0;
        else if(t>y)return false;
    }
    return true;
}
void volve(){
    int mx=0,sum=0;
    cin>>n;for(int i=1;i<=n;i++){
        cin>>a[i];sum+=a[i];mx=max(a[i],mx);
    }
    if(mx==0){
        cout<<"0"<<endl;
        return;
    }
    //枚举sum的因数并检查是否符合 找出最小的y即可
    for(int i=mx;i<=sum;i++){
        if(sum%i==0&&check(i)){
            cout<<n-sum/i<<endl;
            return;
        }
    }

}
int main(){
    int t;cin>>t;
    while(t--)solve();
    return 0;
}

Veröffentlicht am Bearbeitet am

CF836div2

T2:给定数字n 构造数列a1…an s.t.
a1^a2^…^an=(a1+a2+…+an)/n &&(ai>=1)
intput:
3
1
4
3
output:
69
13 2 8 1
7 7 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
性质 a为偶数的时候a^1==a+1 a为奇数的时候 a^1==a-1
a^a=0 0^a=a 
so: 当n为奇数的时候 n个1满足条件 1^1^1==1 (1+1+1)/3=1成立
当n为偶数的时候 1^3==2 (1+3)/2==2 只需让其余的全为2即可
void solve(){
    int t=read();while(t--){
        int n=read();
        if(t%2){
            for(int i=0;i<n;i++){
                cout<<"1 ";
            }
        }
        else{
            cout<<"1 3 ";
            for(int i=0;i<n-2;i++){
                cout<<"2 ";
            }
        }
        puts("");
    }
}

T4 构造严格递增数列满足 max(a1,a2,a3…an)-min(a1,a2,a3…an)=√a1+a2+…+an

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
假定每个数为4n 那么 a1+a2+...+an==4n^2 √a1+a2+...+an==2n
设最大值为x最小值为y x+y=8n x-y=2n -> x=5n y=3n 
如果输入的n是奇数 中间的数为4n 向左为4n-1 4n-2... 向右为4n+1 4n+2...
void solve(){
    int t=read();while(t--){
        int n=read();
        cout<<3*n<<" ";
        int t=4*n-n/2+1;
        for(int i=0;i<n/2-1;i++){
            cout<<t<<" ";
            t++;
        }
        if(n%2)cout<<4*n<<" ";
        t=4n+1;
        for(int i=0;i<n/2-1;i++){
            cout<<t<<" ";
            t++;
        }
        cout<<5*n；
        puts("");
    }
}

ABC279

T3 给定两个大小相同A B字符矩阵 问A矩阵可以通过列的交换化成B矩阵吗? 可以的话输出Yes 否则输出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
32
33
34
35
36
将A字符矩阵的每一个列向量存入map中 接着讲B字符矩阵从map中减去
const int N=4e5;
mp<vector<char>,int>mp;
string s[N];
int main(){
    int h=read(),w=read();
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    for(int j=0;j<w;j++){
        vector<char>v;
        for(int i=0;i<h;i++){
            v.push_back(s[i][j]);
        }
        mp[v]++;
    }
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    for(int j=0;j<w;j++){
        vector<char>v;
        for(int i=0;i<h;i++){
            v.push_back(s[i][j]);
        }
        mp[v]--;
    }
    //检查是否合法
    for(auto i:mp){
        if(i.second){//不为0
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}

Veröffentlicht am Bearbeitet am

队列模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<queue>
queue<int>ql;
int n=read(),k=read();
for(int i=1;i<=n;i++){
    q.push(i);
}
//开始操作
int now=1;//用来计数 当now == k的时候满足条件 让q.front() 输出并出列
while(q.size()){
    if(now==k){
        cout<<q.front()<<" ";
        q.pop();
        now=1;//初始化
    }
    else{//如果不满足是第k个, 则将队头转移到队尾
        now++;
        q.push(q.front());
        q.pop();
    }
}

公式法

f(10,3)=(f(9,3)+3)%10
∴ 从n中依次删去第k的数子
f(n,k)=(f(n-1,k)+k)%n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//函数的两种实现方式
int josephus(int n,int k){
    if(n==1)return 0;
    return (josephus(n-1,k)+k)%n;
}
//第二种
int josephus(int n,int k){
    //从底层向上推
    int value=0;//value 即为f(0,k) -> 向上递推到 f(m,k)
    for(int i=1;i<=n;i++){//从n 一直到 1推出答案 共n次
        value=(value+k)%i; //i即使n的变化值
    }
    return value;
}
int n=read(),k=read();
cout<<josephus(n,k)+1<<endl;

Veröffentlicht am Bearbeitet am

背包问题

线性DP

数字三角形

从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
input:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
output:
30

1
2
3
4
5
6
7
8
9
10
11
//从下向上DP更新
//f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
for(int j=1;j<=n;j++){
    f[n][j]=a[n][j];//将最后一行输入到f数组中
}
for(int i=n-1;i>=1;i--){//从n-1行开始
    for(int j=1;j<=i;j++){
        f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
    }
}
cout<<f[1][1];

最长上升子序列

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
input:
7
3 1 2 1 8 5 6
output:
1 2 5 6
4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> q;
q.push_back(a[0]);
for(int i=0;i<n;i++){
    if(a[i]>q.back()){
        q.push_back(a[i]);
    }
    else{
        *lower_bound(q.begin(),q.end(),a[i])=a[i];
    }
}
for(auto i:q){
    cout<<i<<" ";
}

cout<<endl<<q.size();

最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
input：
4 5
acbd
abedc
output：
abd
3

1
2
3
4
5
6
7
8
9
10
11
12
13
//f[i][j]表示A的前i个于B的前j个的最长公共子序列
//f[i][j]=max(f[i-1][j-1]AB都不选,f[i][j-1]A选B不选,f[i-1][j]A不选B选,f[i-1][j-1]+1AB都选)
const int N=1005;
char a[N],b[N];
int f[N][N];
int n=read(),m=read();
scanf("%s,a+1);scanf("%s,b+1);
for(int i=1;i<=n;++i){
    for(int j=1;j<=m;j++){
        f[i][j]=max(f[i-1][j],f[i][j-1]);
        if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
    }
}

区间DP

石子合并

设有 N 堆石子排成一排，其编号为 1，2，3，…N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
input：
4
1 3 5 2
output：
22
假设f[i][j]表示从第i个到第j个合并所付出的最小的代价 f[1][n]即为答案 

1
2


Veröffentlicht am Bearbeitet am

整数转string

1
string str = to_string(*val);

and support int, LL, ULL, double types

进制转换

1
2
3
4
5
6
7
十进制转十六进制
char c[30];
sprintf(c,"%x",num);
cout<<c;
十进制转八进制
sprintf(c,"%o",num);
cout<<c;

factorial n.阶乘
inversion n.倒置,反转 (逆元)
fact[]表示阶乘 infact表示阶乘的逆元

回文串

输入字符串s 判断是否是回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
scanf("%s",&c);
int l=strlen(c);
	int f=0;
	for(int i=0, j=l - 1;i<j;i++,j--){
        if(c[i]!=c[j]){
           	f=1;
           	printf("No.\n");
            break;
        }
    }
	if(!f){
		printf("Yes.\n");
	}

计算e

利用公式e=1+1/(1!)+…+1/(n!) 求e的近似值 

1
2
3
4
5
6
7
8
int n;
scanf("%d",&n);
double fn=1.0,sum=1.0;//fn计算阶乘 注意两者都为浮点型
for(int i=1;i<=n;i++){
    fn*=i;
    sum+=1/fn;
}
printf("%.*lf",10,sum);

前导0输出

printf输出数字,位数不够前面补0，适用于输出编号

printf的输出格式%[flags][width][.perc][F|N|h|l]type
用到了flags中的0,将输出的前面补上0,直到占满指定列宽为止

1
2
int a=1;
printf("%03d",a);

output: 001

1
2
3
int a=1;
int n=3; //n表示位数 用 * 代替位数，在后面的参数列表中用变量控制
printf("%0*d",n,a);

output: 001

最小公倍数和最大公约数的计算

借助库函数__gcd()

int、long long类型都可以，需要注意的是两个类型必须要相同，还有不能用浮点型

最大公约数

1
2
3
4
5
6
7
8
9
#include<iostream> 
#include<algorithm>
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	cout<<__gcd(a,b);
	return 0;
}

最小公倍数*最大公约数=两数之积

1
cout<<a*b/__gcd(a,b);