前序
我感觉编程是一个进入大厂的基本门槛，前期在寒假，做过一个月的编程学习，就是每周六会做一下题，现在应该是不搞了，之后我可能会不定期的做一下，好像大厂的题目都来自leetcode上的hard，那我就直接刷leetcode的hard题吧。其实我想精进一下我的python语言，所以我用了python，但感觉后面我还是会用c++，我还是想偏向c++开发类似的岗位。
贪心
1、Circle of Monsters
http://codeforces.com/contest/1334/problem/C
打怪，最优的结果就是所有的爆炸效果都用上，只需要枚举从哪儿开始炸
from sys import stdin
t = int(stdin.buffer.readline())
for _ in range(t):
n = int(stdin.buffer.readline())
a = list()
b = list()
for _ in range(n):
x, y = map(int, stdin.buffer.readline().split())
a.append(x)
b.append(y)
Sum = 0
res = float("inf")
for i in range(n):
d = (a[i] - b[(i - 1 + n) % n]) if a[i] >= b[(i - 1 + n) % n] else 0
Sum += d
res = min(res, a[i] - d)
print(Sum + res)2、 Standard Free2play
http://codeforces.com/problemset/problem/1238/C
直接模拟即可，每次站在x高度的时候，这时候将自己所在高度的平台隐去，将x-1高度平台的状态改变
from sys import stdin
q = int(stdin.buffer.readline())
for _ in range(q):
h, n = map(int, stdin.buffer.readline().split())
a = list(map(int, stdin.buffer.readline().split()))
a.append(0)
ans = 0
i = 1
while i < n:
if a[i] == a[i + 1] + 1: #这里每次假设站在当前坐标的前面高度平台上
i = i + 2
else:
ans += 1
i = i + 1
print(ans)3、School Marks
http://codeforces.com/problemset/problem/540/B
左边补1，右边补y
from sys import stdin
n, k, p, x, y = map(int, stdin.buffer.readline().split())
a = list(map(int, stdin.buffer.readline().split()))
a.sort()
Sum = 0
id = k
flag = False
for i in range(len(a)):
Sum += a[i]
if a[i] >= y and not flag:
flag = True
id = i
if Sum + n - k > x or id > (n // 2):
print(-1)
exit()
res = list()
for i in range(min(n // 2 - id, n - k)):
res.append(1)
Sum += 1
for i in range(min(n // 2 - k + id + 1, n - k)):
res.append(y)
Sum += y
if Sum > x:
print(-1)
else:
print(*res)训练1
1、They Are Everywhere
https://codeforces.com/gym/312363/problem/E
方法：尺取法
from sys import stdin
n = int(stdin.readline())
s = stdin.readline().strip('\n')
flag = [0] * 256
num = len(set(s))
l, r = 0, -1
cnt = 0
MIN = float("inf")
while r < n:
while cnt < num:
r += 1
if r >= n:
break
if flag[ord(s[r])] == 0:
cnt += 1
flag[ord(s[r])] = 1
else:
flag[ord(s[r])] += 1
while cnt == num and l <= r:
if flag[ord(s[l])] > 1:
flag[ord(s[l])] -= 1
else:
cnt -= 1
flag[ord(s[l])] = 0
l += 1
if cnt == num - 1:
MIN = min(MIN, r - l + 2)
print(MIN)2、As Fast As Possible
https://codeforces.com/gym/312363/problem/F
from sys import stdin
n, l, v1, v2, k = map(int, stdin.readline().split())
eps = 1e-6
def check(t):
global n, l, v1, v2, k
cnt = (n + k - 1) // k
t1 = (l - v1 * t * 1.0) / (v2 - v1)
return t1 * cnt + (v2 - v1) * t1 * (cnt - 1) / (v1 + v2) - t <= eps
L = l / v2
R = l / v1
while True:
mid = (L + R) / 2.0
if abs(R - L) <= eps:
break
if check(mid):
R = mid
else:
L = mid
print('{:.10f}'.format(R))3、White Lines
https://codeforces.com/gym/312363/problem/G
反向思维，根据黑格，找到可使黑线变白的矩形，这里二维差分，二维前缀和都可以做
一维差分
二维差分
from sys import stdin
n, k = map(int, stdin.readline().split())
s = list()
for _ in range(n):
s.append(stdin.readline().strip('\n'))
diff = [[0 for j in range(n + 2)] for i in range(n + 2)]
res = 0
for i in range(n):
cnt, l, r = 0, 0, 0
for j in range(n):
if s[i][j] == 'B':
cnt += 1
if cnt == 1:
l, r = j, j
else:
r = j
if cnt == 0:
res += 1
else:
if r - l + 1 > k:
continue
x1, y1 = max(0,i - k + 1), max(0, r - k + 1)
x2, y2 = i, l
diff[x1][y1] += 1
diff[x1][y2+1] -= 1
diff[x2+1][y1] -= 1
diff[x2+1][y2+1] += 1
for i in range(n):
cnt, l, r = 0, 0, 0
for j in range(n):
if s[j][i] == 'B':
cnt += 1
if cnt == 1:
l, r = j, j
else:
r = j
if cnt == 0:
res += 1
else:
if r - l + 1 > k:
continue
x1, y1 = max(0,r - k + 1), max(0, i - k + 1)
x2, y2 = l, i
diff[x1][y1] += 1
diff[x1][y2+1] -= 1
diff[x2+1][y1] -= 1
diff[x2+1][y2+1] += 1
MAX = -1
for i in range(n):
for j in range(n):
if i - 1 >= 0:
diff[i][j] += diff[i - 1][j]
if j - 1 >= 0:
diff[i][j] += diff[i][j - 1]
if i - 1 >= 0 and j - 1 >= 0:
diff[i][j] -= diff[i - 1][j - 1]
MAX = max(MAX, diff[i][j])
print(MAX + res)4、讲解
• 前缀和（求区间和，多次询问）
• st表（求区间最大值，多次询问），O(nlog(n))
• 线段树（求区间最大值，区间和，可修改值，区间修改值）
• 主席树（求区间最大值，历史修改过程区间的最大值）
训练2
本次主要集中于尺取法训练
1、Subsequence
很普通的尺取法，就是写的时候需要注点意，一个算法好的写法真的是事半功倍
```cpp
//
// main.cpp
// test
//
// Created by 张江瑜 on 2021/1/23.
//
#include<iostream>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
const int inf = 0x3f3f3f3f;
LL a[N];
int main()
{
int t;
cin >> t;
while(t--){
int n;
LL s;
cin >> n >> s;
for(int i = 0;i < n;++i){
cin >> a[i];
}
int l = 0,r = 0;
LL sum = 0;
int ans = inf;
while(true){
while(r < n && sum < s){
sum += a[r++];
}
if(sum < s)
break;
ans = min(ans, r - l);
sum -= a[l++];
}
if(ans == inf){
cout << 0 << endl;
continue;
}
cout << ans << endl;
}
return 0;
}2、Jessica’s Reading Problem
非常像训练1的codeforce的题，这里要学会用map映射
//
// main.cpp
// test
//
// Created by 张江瑜 on 2021/1/23.
//
#include<iostream>
#include<map>
#include<set>
using namespace std;
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int a[N];
map<int,int>mp;
set<int>se;
int main()
{
int p;
cin >> p;
for(int i = 0;i < p;++i){
cin >> a[i];
se.insert(a[i]);
}
int num = se.size();
int l = 0,r = 0;
int sum = 0;
int ans = inf;
while(true){
while(r < p && sum < num){
if(mp[a[r++]]++ == 0){
sum++;
}
}
if(sum < num)
break;
ans = min(ans, r - l);
if(--mp[a[l++]] == 0){
sum--;
}
}
cout << ans << endl;
return 0;
}3、Bound Found
这里有负数，所以这样尺取法右指针往右就不能保证更好的答案了
当这里用前缀和后排序处理的话，右指针往右就能一直增大，左指针往右就能缩小答案
注：一定要加一个下标为0的，不然就不对了，因为有些情况就遍历不到了
//
// main.cpp
// test
//
// Created by 张江瑜 on 2021/1/23.
//
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
const LL inf = 0x3f3f3f3f3f3f3f3f;
typedef struct Node{
LL sum;
int id;
friend bool operator < (const Node &a,const Node &b){
return a.sum < b.sum;
}
}Node;
Node node[N];
LL a[N];
int n,k;
LL t;
LL ABS(LL x){
return x > 0? x:-x;
}
int main()
{
while(cin >> n >> k){
if(n == 0 && k == 0){
break;
}
memset(node,0,sizeof(node));
node[0].sum = 0;
node[0].id = 0;
for(int i = 1;i <= n;++i){
cin >> a[i];
node[i].sum = node[i - 1].sum + a[i];
node[i].id = i;
}
sort(node,node + n + 1);
// for(int i = 0;i <= n;++i){
// cout << node[i].sum << " " << node[i].id << endl;
// }
while(k--){
cin >> t;
int l = 0, r = 1;
LL MIN = inf;
int ansL = 0, ansR = 0;
LL ans = 0;
while(r <= n){
LL sum = node[r].sum - node[l].sum;
if(ABS(sum - t) < MIN){
MIN = ABS(sum - t);
ansL = node[l].id;
ans = sum;
ansR = node[r].id;
}
if(sum > t) l++;
else if(sum < t) r++;
else break;
if(l == r){
r++;
}
}
if(ansR < ansL){
int tmp = ansR;
ansR = ansL;
ansL = tmp;
}
cout << ans << " " << ansL + 1 << " " << ansR << endl;
}
}
return 0;
}4、Sum of Consecutive Prime Numbers
就简单的加个筛素数就行
//
// main.cpp
// test
//
// Created by 张江瑜 on 2021/1/23.
//
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int MAXN=10010;
int prime[MAXN];
void getprime()
{
memset(prime,0,sizeof(prime));
//prime[0]储存<=MAXN的素数个数
int i,j;
for(i=2;i<MAXN;++i)
{
if(!prime[i]) prime[++prime[0]]=i;
for(j=1;j<=prime[0]&&prime[j]*i<=MAXN;++j)
{
prime[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
}
int n;
int main()
{
getprime();
while(cin >> n){
if(n == 0)
break;
int cnt = 0;
int l = 1,r = 1;
int sum = 0;
while(true){
while(r < prime[0] && sum < n){
sum += prime[r++];
}
if(sum < n)
break;
if(sum == n){
cnt++;
}
sum -= prime[l++];
}
cout << cnt << endl;
}
return 0;
}5、Graveyard Design
这个也简单
//
// main.cpp
// test
//
// Created by 张江瑜 on 2021/1/23.
//
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 1e7 + 5;
LL n;
typedef struct Node{
int num;
int base;
friend bool operator < (const Node &a,const Node &b){
return a.num > b.num;
}
}Node;
Node node[100010];
int main()
{
cin >> n;
int l = 1, r = 1;
int ansL = 0, ansR = 0;
LL sum = 0;
int num = 0;
while(true){
while(r <= (int)sqrt((double)n) && sum < n){
sum += 1LL * r * r;
r++;
}
if(sum < n)
break;
if(sum == n){
node[num].num = r - l;
node[num++].base = l;
}
sum -= 1LL * l * l;
l++;
}
sort(node,node + num);
cout << num << endl;
for(int i = 0;i < num;++i){
cout << node[i].num;
for(int j = 0;j < node[i].num;++j){
cout << " " << node[i].base + j;
}
cout << endl;
}
return 0;
}训练3
1、pearls in a Row
https://codeforces.com/problemset/problem/620/C
直接模拟即可
from sys import stdin
n = int(stdin.buffer.readline())
a = list(map(int, stdin.buffer.readline().split()))
mp = dict()
l = 0
res = list()
for i in range(n):
if a[i] in mp:
res.append((l + 1, i + 1))
mp.clear()
l = i + 1
else:
mp[a[i]] = 1
if len(res) == 0:
print(-1)
exit()
print(len(res))
for i in range(len(res)):
if i == len(res) - 1:
print(res[i][0],n)
else:
print(res[i][0],res[i][1])2、 Producing Snow
https://codeforces.com/problemset/problem/948/C
简单利用一维差分，二分技巧过题
from sys import stdin
def binary_search(l, r, val):
global prefix
i, j = l, r
while i < j:
mid = (i + j) // 2
ptr = prefix[mid]
if ptr <= val:
i = mid + 1
else:
j = mid
return i
n = int(stdin.buffer.readline())
V = list(map(int, stdin.buffer.readline().split()))
T = list(map(int, stdin.buffer.readline().split()))
cnt = [0] * (n + 1)
res = [0] * (n + 1)
prefix = [0] * (n + 1)
for i in range(n):
if i == 0:
prefix[i] = T[i]
else:
prefix[i] = prefix[i - 1] + T[i]
for i in range(n):
id = None
if i == 0:
id = binary_search(i, n - 1, V[i])
else:
id = binary_search(i, n - 1, V[i] + prefix[i - 1])
if id == n - 1 and V[i] + prefix[i - 1] > prefix[id]:
id += 1
cnt[i] += 1
cnt[id] -= 1
if id == n:
continue
if i == 0:
res[id] += (T[id] - prefix[id] + V[i])
else:
res[id] += (T[id] - prefix[id] + V[i] + prefix[i - 1])
for i in range(n):
if i > 0:
cnt[i] += cnt[i - 1]
res[i] += cnt[i] * T[i]
for i in range(n):
if i == n - 1:
print(res[i])
else:
print(res[i], end = ' ')3、 Salary Changing
https://codeforces.com/problemset/problem/1251/D
from sys import stdin
from operator import itemgetter, attrgetter
def check(salary, mid, s):
cnt = 0
for i in range(len(salary)):
if salary[i][0] > mid:
s -= salary[i][0]
cnt += 1
elif salary[i][0] <= mid and salary[i][1] >= mid:
if cnt < (len(salary) + 1) // 2:
s -= mid
cnt += 1
else:
s -= salary[i][0]
elif salary[i][1] < mid:
s -= salary[i][0]
if cnt >= (len(salary) + 1) // 2 and s >= 0:
return True
else:
return False
t = int(stdin.buffer.readline())
for _ in range(t):
salary = list()
n, s = map(int, stdin.buffer.readline().split())
ansL, ansR = 0x3f3f3f3f3f3f3f3f, -1
for i in range(n):
l, r = map(int, stdin.buffer.readline().split())
ansL = min(ansL, l)
ansR = max(ansR, r)
salary.append((l, r))
salary = sorted(salary, key=itemgetter(0), reverse=True)
l = ansL
r = ansR
ans = None
while l <= r:
mid = (l + r) // 2
if check(salary, mid, s):
ans = mid
l = mid + 1
else:
r = mid - 1
print(ans)4、 分治 二分 线段树也可以http://codeforces.com/contest/768/problem/B
from sys import stdin
import math
#从这里的calnum打表判断出num[n] = n
# def calnum(n):
# if n == 0 or n == 1:
# return n
# return 2 * calnum(n // 2) + calnum(n % 2)
#python的math.log函数不精确。。。
def Log(n):
for i in range(52):
num = int(math.pow(2, i))
if n < num:
return i - 1
def dfs(n, nl, nr, l, r):
if l <= nl and r >= nr:
return n
mid = (nl + nr) // 2
num = 0
if mid >= l and mid <= r:
num += n % 2
if l < mid:
num += dfs(n // 2, nl, mid - 1, l, r)
if r > mid:
num += dfs(n // 2, mid + 1, nr, l, r)
return num
n, l, r = map(int, stdin.buffer.readline().split())
if n == 0:
print(0)
exit()
num = Log(n)
nl, nr = 1, int(math.pow(2, num + 1)) - 1
ans = dfs(n, nl, nr, l, r)
print(ans)5、线段树好题 http://codeforces.com/problemset/problem/914/D
这里剪枝的时候要特别注意
//
// main.cpp
// test
//
// Created by 张江瑜 on 2021/2/6.
//
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 5 * 1e5 + 5;
int n, q;
LL a[N];
LL tree[N << 2];
LL gcd(LL a, LL b){
if(b == 0)
return a;
return gcd(b, a % b);
}
void build(int root, int l, int r){
if(l == r){
tree[root] = a[l];
return ;
}
int mid = (l + r) >> 1;
build(root * 2, l, mid);
build(root * 2 + 1, mid + 1, r);
tree[root] = gcd(tree[root * 2], tree[root * 2 + 1]);
return ;
}
void update(int root, int l, int r, int id, LL val){
if(l == r){
tree[root] = val;
return ;
}
int mid = (l + r) >> 1;
if(id <= mid)
update(root * 2, l, mid, id, val);
if(id > mid)
update(root * 2 + 1, mid + 1, r, id, val);
tree[root] = gcd(tree[root * 2], tree[root * 2 + 1]);
return ;
}
int cnt = 0;
void query(int root, int l,int r, int ql, int qr, LL val){
if(cnt > 1) return ;
int mid = (l + r) >> 1;
if(l >= ql && r <= qr){
if(tree[root] % val == 0){
return ;
}else{
if(l == r){
cnt += 1;
return ;
}
LL lt = tree[root * 2];
LL rt = tree[root * 2 + 1];
if(((lt % val) && (rt % val)) || cnt){
cnt = 2;
return ;
}
//这里比较关键
if(lt % val)
query(root * 2, l, mid, ql, qr, val);
if(rt % val)
query(root * 2 + 1, mid + 1, r, ql, qr, val);
return ;
}
}
if(ql <= mid)
query(root * 2, l, mid, ql, qr, val);
if(qr > mid)
query(root * 2 + 1, mid + 1, r, ql, qr, val);
return ;
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;++i){
scanf("%lld", &a[i]);
}
build(1,1,n);
scanf("%d",&q);
for(int i = 0;i < q;++i){
int num;
scanf("%d",&num);
if(num == 2){
int x;
LL y;
scanf("%d %lld",&x, &y);
update(1, 1, n, x, y);
}else{
int x,y;
LL z;
scanf("%d %d %lld", &x, &y, &z);
cnt = 0;
query(1, 1, n, x, y, z);
if(cnt <= 1){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
}
return 0;
}阿里春招第一题
现在将每行的搭配分为ABA和ABC两种情况
当每一行的种类确定之后，第二行的情况也就确定了，一层推一层
当第一行为ABA时，下一行是有三种ABA情况和两种ABC情况
当第一行为ABC时，下一行是有两种ABA情况和两种ABC情况
例如：
121对应的下一行是212，313，232，231，312
123对应的下一行是212，232，231，312
所以：
当第i行为ABA时，所有情况数: x[i] = 3 * x[i - 1] + 2 * y[i - 1]
当第i行为ABC时，所有情况数: y[i] = 2 * x[i - 1] + 2 * y[i - 1]
class Solution {
public:
typedef long long LL;
const LL mod = 1e9 + 7;
LL x[5005];
LL y[5005];
int numOfWays(int n) {
x[1] = 6;
y[1] = 6;
for(int i = 2;i <= n;++i){
x[i] = (3LL * x[i - 1] % mod + 2LL * y[i - 1] % mod) % mod;
y[i] = (2LL * x[i - 1] % mod + 2LL * y[i - 1] % mod) % mod;
}
return (x[n] + y[n]) % mod;
}
};
