板子

### Beautiful Sequence

要求严格小于和严格大于,且数字范围是$[1-3]$  因此结果只能是1 2....2 3

那么直接$dp$ 即可 $dp_{ij}$ 前$i$ 个以$j$ 结尾的方案数

首先当前数不加入$dp_{ij} = dp_{i-1,j}$

如果当前数是$1$ 那么$dp_{i1} += 1$ 

如果当前数是$2$ 那么$dpi2 += dp_{i-1,2}+dp_{i-1,1}$

如果当前数是$3$ 那么$ dpi3 += dp_{i-1,2}$




```c++
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define dbg(x...) \
do { \
    cout << #x << " -> "; \
    err(x); \
} while (0)

void err() {
    cout << endl << endl;
}
 
template<class T, class... Ts>
void err(T arg, Ts ... args) {
    cout << fixed << setprecision(10) << arg << ' ';
    err(args...);
}
template<const int T>
struct ModInt {
	const static int mod = T;
	int x;
	ModInt(int x = 0) : x(x % mod) {}
	// ModInt(long long x) : x(int(x % mod)) {} 
	int val() { return x; }
	ModInt operator + (const ModInt &a) const { 
		int x0 = x + a.x;
		return ModInt(x0 < mod ? x0 : x0 - mod); 
	}
	ModInt operator - (const ModInt &a) const {
		int x0 = x - a.x;
		return ModInt(x0 < 0 ? x0 + mod : x0);
	}
	ModInt operator * (const ModInt &a) const {
		return ModInt(1LL * x * a.x % mod);
	}
	ModInt operator / (const ModInt &a) const {
		return *this * a.inv();
	}
	bool operator == (const ModInt &a) const {
		return x == a.x;
	}
	bool operator != (const ModInt &a) const {
		return x != a.x;
	}
	void operator += (const ModInt &a) {
		x += a.x;
		if (x >= mod) x -= mod;
	}
	void operator -= (const ModInt &a) {
		x -= a.x;
		if (x < 0) x += mod;
	}
	void operator *= (const ModInt &a) {
		x = 1LL * x * a.x % mod;
	}			
	void operator /= (const ModInt &a) {
		*this = *this / a;
	}
	friend ModInt operator + (int y, const ModInt &a){
		int x0 = y + a.x;
		return ModInt(x0 < mod ? x0 : x0 - mod);
	}
	friend ModInt operator - (int y, const ModInt &a){
		int x0 = y - a.x;
		return ModInt(x0 < 0 ? x0 + mod : x0);
	}			
	friend ModInt operator * (int y, const ModInt &a){
		return ModInt(1LL * y * a.x % mod);
	}
	friend ModInt operator / (int y, const ModInt &a){
		return ModInt(y) / a;
	}
	friend ostream &operator<<(ostream &os, const ModInt &a) {
		return os << a.x;
	}
	friend istream &operator>>(istream &is, ModInt &t){
		return is >> t.x;
	}						
				
	ModInt pow(long long n) const {
	ModInt res(1), mul(x);
		while(n){
			if (n & 1) res *= mul;
			mul *= mul;
			n >>= 1;
		}
		return res;
	}
				
	ModInt inv() const {
		int a = x, b = mod, u = 1, v = 0;
		while (b) {
			int t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		if (u < 0) u += mod;
		return u;
	}
				
};
constexpr int mod = 998244353;
using mint =ModInt<mod>;
void solve(){
    int n; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector dp(4, vector<mint>(n + 1));
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= 3; j++)dp[j][i] = dp[j][i - 1];
		if(a[i] == 1){
			dp[1][i] += 1;
		}else if(a[i] == 2){
			dp[2][i] = dp[2][i] * 2 + dp[1][i];
		}else{
			dp[3][i] += dp[2][i];
		}
	}
	cout << dp[3][n] << '\n';
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--)solve();
    return 0;
}
/*
1 2...2 ...3
*/
```

### Palindrome Shuffle

首先保证长度为偶数且数据合法, 也就是说每个数都是成对出现

长度为n 一定可以, 然后考虑缩短

- 如果头和尾相同,那么两边都缩短没关系
- 如果不同这时候一端肯定要固定住了, 枚举固定左端点还是右端点另一边继续缩短$check$ 是否可以就行

缩短的时候注意跨对称轴

```c++
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define dbg(x...) \
do { \
    cout << #x << " -> "; \
    err(x); \
} while (0)

void err() {
    cout << endl << endl;
}
 
template<class T, class... Ts>
void err(T arg, Ts ... args) {
    cout << fixed << setprecision(10) << arg << ' ';
    err(args...);
}
void solve(){
    string s; cin >> s;
    int n = s.size();
    s = ' ' + s;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++){
    	a[i] = s[i] - 'a';
    }
    int ans = n;
    int l = 1, r = n;
    while(l <= r && a[l] == a[r]){
    	l++;
    	r--;
    	ans -= 2;
    }
    vector<int> cnt1(26, 0), cnt2(26, 0);
    for(int i = l; i <= r; i++){
    	cnt1[a[i]]++;
    }
    int mid = n / 2;
    for(int i = l; i <= r; i++){
    	cnt1[a[i]]--;
    	cnt2[a[i]]++;
    	if(i > mid){
    		if(a[i] == a[mid - (i - mid - 1)]){
    			cnt2[a[i]] -= 2;
    		}
    	}
    	if(cnt2[a[i]] > cnt1[a[i]])break;
    	ans = min(ans, (r - i));
    }
    for(int i = 0; i < 26; i++){
    	cnt1[i] = cnt2[i] = 0;
    }
    for(int i = l; i <= r; i++){
    	cnt1[a[i]]++;
    }
    for(int i = r; i >= l; i--){
    	cnt1[a[i]]--;
    	cnt2[a[i]]++;
    	if(i <= mid){
    		if(a[i] == a[mid + (mid - i + 1)]){
    			cnt2[a[i]] -=2;
    		}
    	}
    	if(cnt2[a[i]] > cnt1[a[i]])break;
    	ans = min(ans, (i - l));
    }
    cout << ans << '\n';
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--)solve();
    return 0;
}
/*
长度为偶数也就是说成对出现
反转子串
那么一开始是 1 - n
如何1和n能对上 不需要管
不能对上则至少保留一边
枚举保留那一边?
跨界可以调整中间对称
*/
```

### Remove the Ends

正保留右边, 负保留左边

所以最终的操作序列一定是正.....正负负.....负

做个前后缀和, 然后枚举分界点即可

```c++
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define dbg(x...) \
do { \
    cout << #x << " -> "; \
    err(x); \
} while (0)

void err() {
    cout << endl << endl;
}
 
template<class T, class... Ts>
void err(T arg, Ts ... args) {
    cout << fixed << setprecision(10) << arg << ' ';
    err(args...);
}
void solve(){
    int n; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<int> b(n + 1);
	for(int i = 1; i <= n; i++){
		if(a[i] < 0)b[i] = 0;
		else b[i] = 1;
	}
	vector pre(2, vector<int>(n + 1));
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= 1; j++){
			pre[j][i] += pre[j][i - 1];
		}
		pre[b[i]][i] += abs(a[i]);
	}
	int ans = 0;
	// dbg(ans);
	ans = pre[0][n];
    for(int i = 1; i <= n; i++){
    	int res = pre[1][i] + pre[0][n] - pre[0][i];
    	ans = max(ans, res);
    }
    cout << ans << '\n';
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--)solve();
    return 0;
}
/*
正保留右边

负保留左边

正正....负负
*/
```

### Eating

从右往左吃, 每次价值变成异或, 只有大于等于才能吃

注意到$x$的最高位只会从$1$ 变成 $0$ 也就是说只会变$log$次

那么考虑每次位置变化应该是吃一段区间,这段区间数的最高位$1$小于$x$的最高位$1$  因此二分即可

```c++
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define dbg(x...) \
do { \
    cout << #x << " -> "; \
    err(x); \
} while (0)

void err() {
    cout << endl << endl;
}
 
template<class T, class... Ts>
void err(T arg, Ts ... args) {
    cout << fixed << setprecision(10) << arg << ' ';
    err(args...);
}
template<class T, 
	class Cmp = std::less<T>>
struct ST{
	int n, k;
	const Cmp cmp = Cmp();
	vector<vector<T>> st;
	ST(){}
	ST(const vector<T> &a){
		init(a);
	}
	void init(const vector<T> &a){
		n = a.size() - 1;
		k = __lg(n);
		st.resize(k + 1, vector<T>(n + 1));
		for(int i = 1; i <= n; i++){
			st[0][i] = a[i];
		}
		for(int s = 1; s <= k; s++){
			for(int i = 1; i + (1 << s) <= n + 1; i++){
				st[s][i] = min(st[s - 1][i], st[s - 1][i + (1 << (s - 1))], cmp);
			}
		}
	}
	T get(int l, int r){
		int d = __lg(r - l + 1);
		return min(st[d][l], st[d][r - (1 << d) + 1], cmp);
	}
};
void solve(){
    int n, q; cin >> n >> q;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<int> p(n + 5);
	for(int i = 1; i <= n; i++){
		p[i] = p[i - 1] ^ a[i];
	}
	p[n + 1] = p[n];
	vector<int> b(n + 1);
    for(int i = 1; i <= n; i++){
    	for(int j = 29; j >= 0; j--){
    		if(a[i] >> j & 1){
    			b[i] = j;
    			break;
    		}
    	}
    }
    ST<int, greater<int>> st(b);
    for(int i = 1; i <= q; i++){
    	int x; cin >> x;
    	int now = n;
    	for(int j = 29; j >= 0; j--){
    		if(now == 0 || x < a[now])break;
    		if(x >> j & 1){
    			int l = 1, r = now;
    			int res = now + 1;
    			while(l <= r){
    				int mid = (l + r) >> 1;
    				if(st.get(mid, r) < j){
    					res = mid;
    					r = mid - 1;
    				}else l = mid + 1;
    			}
    			x ^= (p[now] ^ p[res - 1]);
    			now = res - 1;
    			if(now == 0)break;
    			if(x >= a[now]){
    				x ^= a[now];
    				now--;
    			}
    		}
    	}
    	cout << n - now << ' ';
    }
    cout << '\n';
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--)solve();
    return 0;
}
/*
往左吃，值变异或
先看最高位的1

*/
```

### Devyatkino

只考虑这位的话, 可以发现把这位变成$7$ 操作不会超过$20$ 次

所以考虑把一个数字连续操作$20$ 次取出现$7$的最少次数

```c++
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define dbg(x...) \
do { \
    cout << #x << " -> "; \
    err(x); \
} while (0)

void err() {
    cout << endl << endl;
}
 
template<class T, class... Ts>
void err(T arg, Ts ... args) {
    cout << fixed << setprecision(10) << arg << ' ';
    err(args...);
}
void solve(){
    int n; cin >> n;
    int t = n;
    int ans = 20;
    auto check = [&]() -> bool{
    	string res = to_string(n);
    	return res.find('7') != -1;
    };
    if(check())ans = 0;
    int p = 9;
    for(int i = 1; i <= 10; i++){
    	n = t;
		for(int j = 1; j <= 20; j++){
	    	n += p;
	    	if(check())ans = min(ans, j);
	    }
	    p = p * 10 + 9;
    }
    cout << ans << '\n';
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--)solve();
    return 0;
}
/*
20 次以内
*/
```

### Object Identification

A说明是一个有一个环的有向图

B就是容易两点可达

观察样例 

```
? 1 5

? 5 1
```

发现只需问两次相反的询问

如果是B模型,那么两次询问的结果应该是一样,如果是A模型可能要绕环或者不可达

先考虑不可达

- 如果一个点没有任何出边,那么他到不了其他点, 也就是说$A$模型会返回一个$0$, 而$B$模型一定会返回大于$0$的数

考虑绕环

- 说明其他点都有出边
- 但是一个环长最多只有$n-1$ 那么我们考虑问 $x_i = 1, x_j = n$这样$B$的返回结果一定 大于等于 $n-1$ 且两个数相等, 而$A$ 模型是不可能的

```c++
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define dbg(x...) \
do { \
    cout << #x << " -> "; \
    err(x); \
} while (0)

void err() {
    cout << endl << endl;
}
 
template<class T, class... Ts>
void err(T arg, Ts ... args) {
    cout << fixed << setprecision(10) << arg << ' ';
    err(args...);
}
void solve(){
    int n; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<int> cnt(n + 1);
	for(int i = 1; i <= n; i++){
		cnt[a[i]]++;
	}
	int x = -1, y = -1;
	for(int i = 1; i <= n; i++){
		if(cnt[i] == 0) x = i;
		else y = i;
	}
	auto query = [&](int x, int y) -> int{
		cout << "? " << x << ' ' << y << endl;
		int dis; cin >> dis;
		return dis;
	};
	if(x != -1){
		int dis1 = query(x, y);
		int dis2 = query(y, x);
		if(dis1 && dis2){
			cout << "! B" << endl;
		}else{
			cout << "! A" << endl;
		}
	}else{
		for(int i = 1; i <= n; i++){
			if(a[i] == 1)x = i;
			if(a[i] == n)y = i;
		}
		int dis1 = query(x, y);
		int dis2 = query(y, x);
		if(dis1 >= n - 1 && dis2 >= n - 1 && dis1 == dis2){
			cout << "! B" << endl;
		}else{
			cout << "! A" << endl;
		}
	}
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--)solve();
    return 0;
}
/*
A 带环图
B 两个点可以达
x,y != y,x 那么肯定是A

两个不是排列 

*/
```

2025-2-25

以下是 **learngitbranching.js.org** 中常用 Git 指令及其用法的总结，按功能分类整理

----




### 基础操作

#### git add

-  **作用**命令可将该文件的修改添加到暂存区。

​	通过运行 **git add** 命令，你可以告诉 Git 哪些文件的修改应该包含在下一次提交（commit）中。

​	添加一个或多个文件到暂存区：

#### git commit

- **作用**：提交代码变更，生成一个新的提交节点。

- **示例**：

    ```
    git commit -m "提交信息"
    ```

#### git branch <分支名>

- **作用**：创建新分支，但不会切换到该分支。

- **示例**：

    bash

    复制

    ```
    git branch feature
    ```

#### git branch -f <分支名> <目标位置>

- **作用**：**强制移动分支**到指定的提交位置（覆盖原有分支指向）。

- **场景**：当需要快速调整分支到某个历史提交时使用（如修复分支指向错误）。

- **示例**：

    bash

    复制

    ```
    git branch -f main HEAD~3  # 强制将 main 分支移动到 HEAD 前 3 个提交
    git branch -f feature a1b2c3d  # 强制将 feature 分支移动到提交 a1b2c3d
    ```

- **注意**：
  
    - 若分支已推送到远程仓库，需配合 `git push -f` 强制推送（慎用）。
    - 适用于本地分支修复，避免在公共分支上强制修改历史。

#### git checkout <分支名/提交哈希>

- **作用**：切换到指定分支或提交（分离头指针模式）。


    git checkout main      # 切换到 main 分支
    git checkout a1b2c3d  # 切换到某个提交

#### git merge <分支名>

- **作用**：将指定分支合并到当前分支，生成一个新的合并提交。


    git merge feature     # 将 feature 分支合并到当前分支

------

### **分支与提交操作**

#### git rebase <目标分支>

- **作用**：将当前分支的提交“复制”到目标分支的最新提交后，使历史线性化。

- **示例**：

    bash

    复制

    ```
    git rebase main       # 将当前分支变基到 main 分支
    ```

#### git rebase -i <目标提交>（交互式变基）

- **作用**：**交互式修改提交历史**（如合并提交、修改提交信息、删除提交等）。

- **场景**：整理本地提交历史，使其更清晰（例如：合并多个临时提交为一个完整提交）。

- **流程**：

    1. 执行命令后进入交互界面：

        ```
git rebase -i HEAD~3  # 修改最近 3 个提交
        ```

    2. 在编辑器中按需修改命令（如 `pick`, `squash`, `reword` 等）：
    
        ```
    pick a1b2c3d 提交A
        squash b2c3d4e 提交B  # 将提交B合并到提交A
    reword c3d4e5f 提交C  # 修改提交C的信息
        ```
    
    3. 保存退出后，Git 会按指令逐条处理提交。

- **常用命令**：

    - `pick`: 保留该提交
    - `reword`: 保留提交但修改信息
    - `edit`: 暂停变基，允许修改提交内容
    - `squash`: 合并到前一个提交，并保留提交信息
    - `fixup`: 合并到前一个提交，但丢弃当前提交信息
    - `drop`: 删除该提交

- **注意**：

    - **仅用于本地未推送的提交**，若已推送需强制覆盖（可能影响他人）。
    - 解决冲突后，使用 `git rebase --continue` 继续。

#### git reset <目标提交>

- **作用**：将当前分支的 HEAD 指针移动到指定提交（默认保留工作区，`--hard` 会丢弃变更）。


    git reset HEAD^       # 回退到上一个提交（保留修改）
    git reset --hard a1b2c3d  # 强制回退到指定提交，丢弃后续修改

#### git cherry-pick <提交哈希>

- **作用**：将指定提交的变更应用到当前分支。


    git cherry-pick a1b2c3d  # 应用提交 a1b2c3d 的变更

------

### **相对引用与 HEAD**

- **`HEAD^`** 或 **`HEAD~1`**

    - **作用**：表示当前提交的父提交（`^` 用于分支合并后的父提交选择，`~` 用于向上移动多步）。

    - **示例**：

        bash

        复制

        ```
        git checkout HEAD^     # 切换到父提交
        git branch -f main HEAD~3  # 强制将 main 分支移动到 HEAD 前 3 个提交
        ```

------

### **远程仓库操作**

#### git clone <远程仓库地址>

- **作用**：克隆远程仓库到本地。

#### git fetch

- **作用**：下载远程仓库的更新，但不自动合并到本地分支。

#### git pull

- **作用**：相当于 `git fetch` + `git merge`，拉取远程更新并合并到当前分支。

#### git push <远程仓库> <分支名>

- **作用**：将本地分支推送到远程仓库。

- **示例**：

    ```
    git push origin main  # 推送 main 分支到 origin
    ```

------

### **高级技巧**

#### git revert <提交哈希>

- **作用**：创建一个新提交，撤销指定提交的变更（适合公共历史记录）。

- **示例**：

    bash

    复制

    ```
    git revert a1b2c3d  # 撤销提交 a1b2c3d 的变更
    ```

#### 交互式 Rebase (`git rebase -i`):

- **作用**：通过交互界面修改提交历史（如合并提交、修改提交信息等）。

#### 强制推送 (`git push -f`)

- **作用**：强制覆盖远程分支（慎用，可能破坏他人代码）。

------

### **其他关键概念**

- **分离头指针 (Detached HEAD)**：直接切换到某个提交（而非分支）时的状态，需创建分支保存更改。
- **冲突解决**：合并或变基时发生冲突，需手动编辑文件后 `git add` 标记为已解决。

------

### **注意**

- **合并分支**：`git merge` 或 `git rebase`（根据是否需要线性历史选择）。
- **撤销变更**：
    - 未推送：`git reset`
    - 已推送：`git revert`
- **同步远程代码**：`git fetch` + `git rebase origin/main`（优于直接 `git pull`）。

git常用命令

## atcoder 293

### F题

小范围暴力,大范围二分判定

### G题

查询区间内每个数的个数

莫队板子题,只进行区间查询不进行修改

### H题待补




## atcoder 294

### F题

被教育了二分(考虑二分的值然后去推一下式子)

### G

题教育树上利用dfs序压成一维然后再利用数据结构进行维护,,,,

### H题为容斥原理,,,容斥原理的实现方式一般为dfs

## atcoder 295

### D题

寻找区间内所有数都出现偶次数,,,,考虑把每个数都处理成一个二进制位这样当他们异或起来如果是偶次那么异或和为0,因此预处理异或和,统计次数然后枚举端点即可(     哈希异或  前缀和)

### E题

神秘的一个期望公式 (高中数学没学好属于是)暴力枚举然后算贡献,

### F题

数位dp思想变成前缀和相减然后  在这个区间上暴力枚举就可以了(注意前导0)

### G题

并查集,图上连通块合并,,直接find就好了为什么要弱智的去找到子节点然后接到这个连通块上呢

### H题待补

## atcoder 296

### D题

暴力发现题目给到m的最大是1e12 因此因子最大不会超过1e6所以只要暴力枚举因子记好了(多看看数据范围想想为什么是1e12)

### E题

(看出了跑环但是不会实现)因此学习了tarjan算法求强连通分量基本思想就是打时间戳然后跑dfs树看看是不是反祖边然后回溯连块

### F题

(只看出了如果有两个数字相同一定是YES因为我可以通过交换让最后只剩下两组不同,然后再让他们交换即可) 而这题还考虑到了逆序对考虑逆序对的奇偶是否相同(以前见过类似题判断奇数码的两个局面能否移动到)如果数组中元素两两不同，则每次交换一定会改变两个数组中逆序对的奇偶性

### G题

计算几何 首先如何判断一个点是否在一个多边形内部题目给出的逆时针的向量因此考虑一个点与逆时针向量的关系如果一个点在所有逆时针向量的左侧那么这个向量就是在这个多边形的内部对于本题因为是凸多边形可以判断两条即可 可以用叉积来考虑如果叉积为正说明在左侧（右手定则）为0说明共线 共线时再用数量级判断是否在线段上 本题只需要把所有点sort一下然后扫描线扫过去更新上边界和下边界然后判断即可**(叉积可以判断点在向量的那侧)**

### H题待补

## atcoder 297

### E题

暴力跑就好了当时似乎弱智了

### F题

暴力枚举边,枚举这个长方形的边长 然后容斥去算在这个长方形的概率(卡容斥了)

### G题

博弈论(补前狠狠恶补了一下https://blog.csdn.net/strangedbly/article/details/51137432) sg函数简单应用打表找规律记好了

### H题待补

## atcoder 298

### F题

(神秘题)一直想不到nlog做法简单的思路就是预处理好每行每列的和然后枚举每一行然后去找最大的列(而在这里就会产生问题在这个点重复算的问题) 因此把这n个点单独拎出来就是行列的焦点有值的情况直接暴力更新答案(On)然后我们枚举每行可以把每列的总和扔到set里然后从后遍历如果枚举这个列和行的焦点有值就跳过,遇到第一个没值就更新答案break然后下一行所以最多只会跳过N次所以时间复杂度是nlogn(所以为什么对操作有影响的点不单独拿出来算呢)

### G题

看到数据量感觉记忆化dfs能过 (传五个参数上边界下边界左边界右边界和切几刀)很明显下一个状态就是横切一刀或者纵切一刀这时候枚举两块切的刀数，dfs返回的是块里的最大值很显然我们应该每次状态一直取min最大的最小，然后枚举每一小块dfs跑一遍包含这块的的方案里M的最小值然后一直更新答案就好了（注意有0所以初始化的时候记忆数组不要赋为0，会T一个点 nnd找了半天才找到）

### H题待补

## atcoder 299

### F题(DP)

首先要考虑一个问题就是如何不重复的拿,建一个next[ i ] [ j ]表示在第i个位置到最后一个j+'a'字母第一次出现的地方 当后面没有这个字符则值为无穷大,然后我们取子序列第一个T(p1 p2 p3...pn)的字符时p1取next[1] [j] (j为从0枚举到26)然后p2取next[p1] [j] 以此类推 第一个子序列T(q1 q2 q3...qn) q1取next[pn] [p1]以此类推 这样可以保证每次取出来的字符串不会重复.接下来我们要怎么算所有的子序列串 定义dp[i] [j]状态为以s[i]为pn s[j]为qn的方案数 容易得到状态转移方程f[next[i+1] [c]] [next[j+1] [c]]=f[next[i+1] [c]] [next[j+1] [c]]+f[i] [j]. 首先枚举pn的位置,然后把p1 q1初始化(即在范围内 p1<=i &&q1<=n)就可以

### G题

单调栈只要当前元素比栈顶元素小切栈顶元素后面还会再出现就pop

### H题待补

## atcoder 300

### E题

注意扔到1一直是一样的对与一个数n来说 n=1/6(n,n*2,n*3,n*4,n*5,n*6) 化简 n=1/5(n* 2,n *3,n* 4,n *5,n* 6)所以转移的时候直接去掉1就可以了然后记忆化搜索或者dp即可解决

### F题

首先显然的是去掉的x应该是连续的而且肯定是在第一个循环的串里,所以枚举开始去掉x的位置然后计算一下o的长度一直更新就好了

### G题,

打表可以得100以内的质数只有25个,如果暴力枚举这个p个质数的值数为多少以最大范围可以看出为2e9这是会tle了那么需要更加高效的搜索方式(折半搜索)(开两个数组,一个数组存一些质数的指数相乘的结果,另一个存剩下的注意控制两个数组的长度应差不多)那么很显然最终的结果可以由两数组相乘得到,所以排序一下二分即可直接计算答案

### (折半搜索样例https://zhuanlan.zhihu.com/p/112563549);

### H题 ....

## atcoder 301

### F题

做法:算贡献 首先直接算没有这个类型的很难算,因此转化为总的方案数-这个类型的数量,DDoS 里面的DD是不好算因此先反转字符串算SoDD

遍历枚举每个位置如果当前位置是小写字母或者问号  

记总的问号数量为tot;  

当目前遍历到位置出现了So算完即可直接退出(由下面计算贡献的方式可以看出)  

(1)So的种类   如果当前位置的前一个开始的大写字母后面都没有出现小写字母则形式是rrrrrRRRRR  

   记当前的?数量为now   记第一次出现大写字母和最后一次出现小写字母(除当前位置)之间的的问号数量为k(当目前还没有出现大写字母时候k为当前位置前一个到   最后一次出现小写字母的问号数量)  

   显然填充的方案是当前位置是小写字母,最后一次小写字母之前都填小写字母,第一次大写字母之后都填大写字母,之间的部分也填写成rrrRRR的形式

   因此当已经出现过大写字母的方案数为     未出现大写字母的方案数为    (2)DD的种类   

   1)如果后面已经出现了两个相同的字母则 方案数为       2)我们直接算的话很难算 同样考虑用总的方案去减掉不合法的   

   记后缀中大写字母未出现的种类有d种   

   我们要的是不合法的,所以后面的问号只能填小写字母或者这d个字母出现一次   

   我们可以枚举后面问号中 出现d中几个大写字母,其他填小写字母  

​    所以 不合法的方案数为     因此DD的方案数为   

### G题

做法暴力枚举, 先拿到每个点对所产生的直线(除两点x相等),然后处理一下每条直线会有多少点在上面,再枚举两条直线的交点如果交点(x<0)然后就在这个点上加上贡献,遍历所有的点更新答案即可

### H题 无

## atcoder 302

#### F题 **Merge Set**

有两个相同元素的集合可以合并，就是两个集合之间有边，因此本题相当于就是建边然后从包含1的集合开始bfs跑到包含n的集合

### G题 **Sort from 1 to 4**

置换环,与平时排列的不同这里有重复数字不同所以环的大小方案也有很多,因为要交换次数最少显然我们应该先把环长最少的先用掉,这题只有1到4 所以环长最多为4 直接枚举计算即可

### atcoder 303

#### F题

由于不知道回合数所以可以考虑倒着来，即从H<0 的前一天开始考虑很显然这一天应该考虑用d最大的

然后倒二天应该用两天内产生伤害最大的，直到H减小到0，这种对于时间我们可以先按时间排序，然后维护一个后缀的d最大值，来得到当前时间使用那个造成的伤害最大

#### G题

区间DP可以先从爆搜开始想转移方程，DP的定义是在当前区间先手产生的价值为X后手为Y，X-Y的最大值，然后用ST表加快一下就可以了

## atcoder 332

### F题

我们可以先对第一位考虑一下期望，首先期望公式$E(x)=\sum_{i=1}^{k}P_{i}*a_{i}$ 其中$k$ 是包含这个位置所有区间数

因此可以得到期望就是这个数乘以是这个数的概率

也就是说先拿到所有包含这个位置的操作 这个操作对这一位的期望的贡献就是这一位选他后面的操作都不选他的概率 乘以$x$  

那么期望的式子就等价于每次操作$E(i)=E(i)*\frac{len-1}{len}+x*\frac{1}{len}$

那么我们现在来考虑整体，也就是说每次操作我们需要一个区间乘和区间加操作，这不是经典线段树

所以使用线段树维护一下，最后把tag都下传一下就是答案了

## atcoder 339

### D题 Synchronized Players

如果不是两个点一起移动，对两个点同时做bfs即可，一起移动我们依旧考虑bfs，把两个的坐标当作状态一起bfs即可

时间复杂度$n^{4}$

### F题 Product Equality

对数字进行哈希，可能冲突使用双哈 时间复杂度为$n^{2}log$

## atcoder 346

### G题 Alone

首先这个询问区间个数问题，一般都是枚举一个边界，然后log去算另一个边界的贡献

我们枚举左边界，很显然的发现贡献其实是右边每个数字种类，第一次出现和第二次出现的区间大小

也就是说我们需要维护一个区间加+1，区间-1，然后查询区间中>0数的个数

对于这个来说正常做如果tag不传到底是不对的，所以复杂度不对

这里我们可以发现一个小性质就是数的值>=0 也就是说，我们只要维护区间最小值以及最小值的个数

然后就可以做了

## **actoder 361**

### **G - Go Territory**

题意就是四联通, 然后和 $(−1,−1)$ 不联通的点的个数, 暴力的来说我们把每个点都使用并查集联通,然后判和 $(−1,−1)$ 是否在同一连通块即可, 但是这样的点数很多,考虑一行把连续白点缩成一个点, 这样点数是 $O(n)$ 的

具体实现的话可以用 $map$ 套 $vector$ ,这样把一行来缩点, 同时注意应该把上下两行都存下来,然后双指针并查集即可

## **atcoder363**

### **F - Palindromic Expression**

考虑一下最终的答案的结构 让表示翻转后得到的数字

- $n$ 
- 表达式$x∗ $ $(表达式)∗$$rev(x)$$ 

对于第二种可以发现我们可以暴力枚举 $n$ 内的因子来$check$是否有解

复杂度为$\sqrt{n} * n$ 的因子个数 但是大部分实际跑不满

因此只需要暴力搜就行

## actoder366

### F - Maximum Composition

首先考虑对于k个p如何排列比较优，类似于国王游戏，使用微扰法，尽交换两个其他不变，即$f_i f_j (x)$和$f_j f_i(x)$ 那个的值大，化简式子即可得到$\frac{a_i - 1}{b_i}$ 越大放在外面越优，所以先排序后，然后dp的去选k个即可

## atcoder 371

### G - Lexicographically Smallest Permutation

排列交换，容易发现这是一个置换环，那么在一个置换环内要让某一个位置排在第一个就会有一个限制

我们定义操作次数 $X$ 环长$L$ , 第$i$ 个点放第一个的条件就是    $X ≡ i\, (mod\, L)$

我们贪心的考虑肯定是从左到右的置换环 依次最优， 也就是说当前这个同余条件要和之前的同余方程有解，这个东西就是$exgcd$ 就可以判断， 然后利用中国剩余定理把同余方程合并起来， 但是一直取$lcm$ 会爆__int128,所以不能这么做， 有两种做法

做法1：不合并同余方程，考虑到不同的$L$ 至多只有 $\sqrt{n} $ 个所以暴力每个$check$ ， 复杂度是$n \sqrt{n} logn$

做法2：考虑中国剩余定理的过程

考虑两个同余方程

$X ≡ i\, (mod\, L_i)$

$X ≡ j\, (mod\, L_j)$

有解的条件是 $gcd(L_i, L_j)|(i-j)$ ,所以限制条件变成$i ≡ j\, (mod\, gcd(L_i, L_j))$

所以我们存下因数位置的限制 或者 $p^k, p \in Prim$ 位置的限制然后每次去check即可

## atcoder 373

### F - Knapsack with Diminishing Values

完全背包，但是每次选择有限制，朴素的方法是$n m^2$的复杂度，考虑到第三层循环枚举选的个数的时候是个类似调和级数的东西，也就是说如果每个物品的重量都不一样，那么复杂度就是$m^2 logm$ ，所以我们考虑把同一重量的物品一起考虑，那么我们就要考虑一个东西就是选择$k$个重量的物品的最大价值怎么计算，很显然直接贪心，每次记录一下增加价值和选了多少次，然后用优先队列就可以处理好了

## actoder 374

### E - Sensor Optimization Dilemma 2

首先很自然想到二分答案，然后考虑如何check，也就是取到这个二分值的最少花费，一个很显然的贪心就是取性价比高的那个，假设$a_i * q_i \ge b_i * q_i $ 就是A物品的性价比比较高，那么B物品买的数量不会超过$lcm(a_i, \, b_i) / b_i$ 因为每多这些都可以用A物品来替换达到更低的花费，$lcm(a_i, \, b_i) / b_i$ 不会超过$100$ 所以暴力枚举B物品买了几个即可

## **atcoder 377**

### **E - Permute K times 2**

我们将 $i$  和 $p_i$ 连边，那么 $i$ 出边的方向就是 $p_i$ 的值，对着样例画一下图可以发现，执行 $k$ 次操作，其实就是在环上走 $2^k$ 步，其实就是因为在你走的时候，你的下一个点的出边也走了所以每次是一个 $\times 2$ 的过程

atcoder做题记录

![img](https://www.masttf.fun/static/img/3349d6c4a40483fd4deb6019f12a3ce7.e5def18909e9a2b47f12e0c3d4c5b375.webp)



这个图很好

很好助于理解

![img](https://www.masttf.fun/static/img/54b9d12b192c52dee5454e7a0b50775e.0cfe22162e368e1bd13f25d5d4512024.webp)

假设我二分斜率

这里红色的线就是每点的直线

每条直线的表达式是 y = k（ x - x‘） + g（x’）

我只要求出在 x = k处y的最大值是过哪个点的

我就可以直接斜率该怎么调整

因为这个最大是 过小于k 的点做出来的

说明现在斜率太大了

所以我应该斜率变小

![img](https://www.masttf.fun/static/img/44403905df06bdc8b55be0af6b490f52.3ee8e3fb5b5c0d93d137d8f7d78fe442.webp)



同理

如果是 >k 的点取到了 max

是不是说明斜率太小了

所以我可以根据最后的答案是那个点取到的，来调整斜率， 最后相切在x = k处

 然后我们现在来看这个答案该怎么算

 y = k（ x - x‘） + g（x’）

我要算所有直线在 x = K 时候的最大值

把x = K 代入

 y = k * K - k * x‘ + g（x’）

g（x’） - k*x‘

g（x'）是取 x’ 次的最大值

所以如果我让所有物品都减掉 k

再求出的 g（x‘）

是不是 已经 减掉了 k * x’

然后 求出最大值后最加上 k* K

就是y 的最大值

所以变成无限制

然后wqs要注意的地方

就是三点一线

![img](https://www.masttf.fun/static/img/347e1976b5ccca1574c264146e306271.01b3b1cae0a04f4f0ce62bd2ae339afb.webp)



这种情况

我们应该让 每次取到最左端或者最右端

因为凸壳不应该有三点共线

所以固定取一端

而且共线的点， 他们直线在 x = k 的贡献都是一样的

MD5hash(Linux)

Beautiful Sequence

atcoder 293

F题

G题

H题待补