总结 - 洛谷保存站

### [B3617 古籍翻译](https://www.luogu.com.cn/problem/B3617)
思路：       
直接把 $8$ 进制转 $10$ 进制再转成 $16$ 进制显然超出 long long，所以考虑优化。$4$ 个 $8$ 进制能拆成 $12$ 个二进制，$3$ 个 $16$ 进制也能拆成 $12$个二进制，所以把 $8$ 进制按照 $4$ 位 $4$ 位的拆开，在转成 $10$ 进制，然后 $16$ 进制，这样就不会超出 int 了。
```cpp
#include<bits/stdc++.h>
using namespace std;

string s;

int zhuang(int l,int r){
	int res=0;
	for(int i=l;i<=r;i++){
		res*=8;
		res+=s[i]-'0';
	}
	return res;
}

void dfs(int len){
	int cur=max(0,len-4);
	int x=zhuang(cur,len-1);
	if(cur){
		dfs(cur);
		printf("%03x",x);
	}else{
		printf("%x",x);
	}
	return;
}

int main(){
	cin>>s;
	dfs(s.size());
	return 0;
}
```
### [P1020 [NOIP 1999 提高组] 导弹拦截](https://www.luogu.com.cn/problem/P1020)
思路：       
其实就是在求最长不下降子序列，和最长上升子序列，先考虑暴力转移。
```cpp
for(int i=1;i<=n;i++){
		f[i]=1;
		for(int j=1;j<i;j++){
			if(a[i]<=a[j]){
				f[i]=max(f[i],f[j]+1);
			}	
		}
		maxx=max(maxx,f[i]);
	}
```
时间复杂度 $\mathcal O(n^{2})$，足以通过 NOIP 原数据，但是另外新增的数据 $n\le 5\times 10^5$，会超时，考虑优化，观察第二层循环，其实就是在求 $\max\{f_j\}(a_i\le a_j)$ 就是二维偏序问题，可以使用树状数组优化，每次查询 $<a_i$ 的最大 $f_j$，然后更新 $a_i$ 为 $f_i$，但又出现了一个问题，在问题 $2$ 中需要查询区间后缀最大值，和可以通过减法求出，但是最大值不行，此时可以逆序遍历，将后缀转为前缀，就可以使用树状数组解决了。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;

int tr[maxn],a[maxn],f[maxn],n,ans1,ans2;

int lowbit(int x){
	return x&-x;
}

void upd(int x,int k){
	while(x<=1e5){
		tr[x]=max(tr[x],k);
		x+=lowbit(x);
	}
	return;
}

int qmax(int x){
	int res=0;
	while(x){
		res=max(res,tr[x]);
		x-=lowbit(x);
	}
	return res;
}

int main(){
	while(cin>>a[++n]);
	n--;
	for(int i=n;i>=1;i--){
		f[i]=qmax(a[i])+1;
		upd(a[i],f[i]);
		ans1=max(ans1,f[i]);
	}
	cout<<ans1<<'\n';
	memset(f,0,sizeof(f));
	memset(tr,0,sizeof(tr));
	for(int i=1;i<=n;i++){
		f[i]=qmax(a[i]-1)+1;
		upd(a[i],f[i]);
		ans2=max(ans2,f[i]);
	}
	cout<<ans2;
	return 0;
}
```

正在渲染内容...