分享一下自己的笔记
差分
(时间复杂度为线性,比正常算要少一个指数级)
图片: https://uploader.shimo.im/f/x1XbhzWCNYFU5ZC3.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3MDg3MDkzMzksImZpbGVHVUlEIjoiNXhrR29HNzl4OVNNcFZrWCIsImlhdCI6MTcwODcwOTAzOSwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwidXNlcklkIjo3Mjg4MzIzNX0.qvW0g5ygYkNco2bxNyfxY_0Tffrrpn2cHaETH-eCoVg
差分核心代码:
图片: https://uploader.shimo.im/f/svnxNm4pecKPSXeF.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3MDg3MDkzMzksImZpbGVHVUlEIjoiNXhrR29HNzl4OVNNcFZrWCIsImlhdCI6MTcwODcwOTAzOSwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwidXNlcklkIjo3Mjg4MzIzNX0.qvW0g5ygYkNco2bxNyfxY_0Tffrrpn2cHaETH-eCoVg
差分思路
图片: https://uploader.shimo.im/f/uo2IQCHDAFbkL10z.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3MDg3MDkzMzksImZpbGVHVUlEIjoiNXhrR29HNzl4OVNNcFZrWCIsImlhdCI6MTcwODcwOTAzOSwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwidXNlcklkIjo3Mjg4MzIzNX0.qvW0g5ygYkNco2bxNyfxY_0Tffrrpn2cHaETH-eCoVg
差分模版
图片: https://uploader.shimo.im/f/YNVdhdl3oftUd8Op.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3MDg3MDkzMzksImZpbGVHVUlEIjoiNXhrR29HNzl4OVNNcFZrWCIsImlhdCI6MTcwODcwOTAzOSwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwidXNlcklkIjo3Mjg4MzIzNX0.qvW0g5ygYkNco2bxNyfxY_0Tffrrpn2cHaETH-eCoVg
最后也可以用图片: https://uploader.shimo.im/f/Fv28FsvPZ7KgCGQ7.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3MDg3MDkzMzksImZpbGVHVUlEIjoiNXhrR29HNzl4OVNNcFZrWCIsImlhdCI6MTcwODcwOTAzOSwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwidXNlcklkIjo3Mjg4MzIzNX0.qvW0g5ygYkNco2bxNyfxY_0Tffrrpn2cHaETH-eCoVg即用b来存原始数组,省空间
题目和解析
图片: https://uploader.shimo.im/f/YHQmtJE3AiIFxBCU.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3MDg3MDkzMzksImZpbGVHVUlEIjoiNXhrR29HNzl4OVNNcFZrWCIsImlhdCI6MTcwODcwOTAzOSwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwidXNlcklkIjo3Mjg4MzIzNX0.qvW0g5ygYkNco2bxNyfxY_0Tffrrpn2cHaETH-eCoVg
图片: https://uploader.shimo.im/f/B1SYKhcEud61WBKu.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3MDg3MDkzMzksImZpbGVHVUlEIjoiNXhrR29HNzl4OVNNcFZrWCIsImlhdCI6MTcwODcwOTAzOSwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwidXNlcklkIjo3Mjg4MzIzNX0.qvW0g5ygYkNco2bxNyfxY_0Tffrrpn2cHaETH-eCoVg
数据范围10^5,所以复杂度要小于nlogn
改变数组元素题代码
图片: https://uploader.shimo.im/f/ydpYGLzo26AJjRdz.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3MDg3MDkzMzksImZpbGVHVUlEIjoiNXhrR29HNzl4OVNNcFZrWCIsImlhdCI6MTcwODcwOTAzOSwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwidXNlcklkIjo3Mjg4MzIzNX0.qvW0g5ygYkNco2bxNyfxY_0Tffrrpn2cHaETH-eCoVg
因为初始都为0,所以省去了差分模版第一步(省去了计算差分数组,差分数组直接全为0)
memset:
图片: https://uploader.shimo.im/f/r6W25OJqgMwAR0Qp.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3MDg3MDkzMzksImZpbGVHVUlEIjoiNXhrR29HNzl4OVNNcFZrWCIsImlhdCI6MTcwODcwOTAzOSwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwidXNlcklkIjo3Mjg4MzIzNX0.qvW0g5ygYkNco2bxNyfxY_0Tffrrpn2cHaETH-eCoVg
memset初始化数组函数:图片: https://uploader.shimo.im/f/aG2YsTIgKIk86cQl.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3MDg3MDkzMzksImZpbGVHVUlEIjoiNXhrR29HNzl4OVNNcFZrWCIsImlhdCI6MTcwODcwOTAzOSwiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwidXNlcklkIjo3Mjg4MzIzNX0.qvW0g5ygYkNco2bxNyfxY_0Tffrrpn2cHaETH-eCoVg函数第三个元素为需要初始化的数组大小,但在本题中要省时间
调试心得
1、注意换行
2、如果数据是一次一次输出的,直接复制完整测试数据的话可能只会显示输出最后一行,所以测试数据要记得手打
#include<bits/stdc++.h>
using namespace std;
int main() {
int T, n, x, l, r;
int b[200010]={0};
cin >> T;
for (int i = 1; i <= T; i++)
{
cin >> n;
memset(b, 0, (n + 1) * 4);
for (int j = 1; j <= n; j++)
{
cin >> x;
x = min(x, j);
l = j - x + 1; r = j;
b[l] += 1; b[r + 1] -= 1;
}
for (int j = 1; j <= n; j++)
{
b[j] += b[j - 1];
cout << !!b[j] << " ";
}
cout << endl;
}
}