昆明贤邦网站建设,北京展厅设计制作,微信公众号1000阅读量多少钱,企业网站维护服务1. 扩大区间
P4155 [SCOI2015] 国旗计划例题1#xff1a;P4155 [SCOI2015] 国旗计划
计算能覆盖整个圆圈的最少区间#xff0c;题目给定的所有区间互相不包含#xff0c;按区间左端点排序后#xff0c;区间的右端点也是单增的。
我们首先需要化圆为线#xff0c;然后贪…1. 扩大区间
P4155 [SCOI2015] 国旗计划例题1P4155 [SCOI2015] 国旗计划
计算能覆盖整个圆圈的最少区间题目给定的所有区间互相不包含按区间左端点排序后区间的右端点也是单增的。
我们首先需要化圆为线然后贪心(优化为倍增)选择一个右端点最远的线段并且该线段的左端点在上个线段的内部。
#include bits/stdc.h
#define ll long long
using namespace std;
const int N 4e510;
struct seg{int id, l, r;bool operator (const seg x) const{return l x.l;}
}a[N];
int go[N][20]; //倍增
int n, m, ans[N];
void init() {int nxt 1;for(int i 1; in*2; i) {while(nxt n*2 a[nxt].l a[i].r) nxt;go[i][0] nxt - 1;}for(int i 1; (1i) n; i) { //最多跳2^n, 不超过n for(int st 1; st n*2; st) {go[st][i] go[go[st][i-1]][i-1];}}
}
void getans(int x){int now x, res 1; //从第x个战士出发 for(int i log2(N); i0; i--){ //注意二进制是从高位开始枚举 int pos go[now][i];if(pos a[pos].r a[x].l m) { //跳的那个位置不超过一圈后的自己 res 1i;now pos; //就可以跳 }}ans[a[x].id] res1;
}
int main() {scanf(%d%d, n, m);for(int i 1; in; i) {scanf(%d%d, a[i].l, a[i].r);a[i].id i;if(a[i].r a[i].l) a[i].r m; //化圆为链 }sort(a1, an1);for(int i 1; in; i){ //每一个线段的终点是自己, 想想a[n]是要绕一圈到a[1]的 a[in].id a[i].id;a[in].l a[i].l m;a[in].r a[i].r m;}init();for(int i 1; in; i) getans(i);for(int i 1; in; i){printf(%d , ans[i]);}return 0;
}
例题22021年中国大学生程序设计竞赛女生专场 B攻防演练
与上面的代码很像大概原理都一样的
#include bits/stdc.h
using namespace std;
const int N 2e510;
int pos[30], n, m, dp[N][30];
int main(){scanf(%d%d, m, n);string s; cins;s # s;for(int i 0; i20; i) dp[n1][i] n1; //需要初始化边界, 因为有的dp会跳到最后 for(int i 0; i26; i) pos[i] n1;for(int i n; i 0; i--){ //i 0也要更新, 因为从l-1开始跳 for(int j 0; jm; j)dp[i][0] max(dp[i][0], pos[j]);if(i) pos[s[i]-a] i;}for(int j 1; j 20; j ){ //枚举区间长度 for(int i 0; i n; i){dp[i][j] dp[dp[i][j-1]][j-1];//以i开始跳, 跳2^j次后到达的最大位置; 即以i开始跳, 先跳2^(j-1)次, 然后再跳2^(j-1)次 }}int q; scanf(%d, q);while(q--) {int l, r; scanf(%d%d, l, r);int ans 1, p l-1;for(int j 20; j0; j--){if(dp[p][j]r) {p dp[p][j];ans (1j);}}printf(%d\n, ans);} return 0;
}
2. 区间最大/最小值st表
如果元素满足倍增关系例如快速幂、LCA都可以用到倍增
区间最大值
#include bits/stdc.h
using namespace std;
const int N 2e510, M 25;
int dp[N][M];
int main() {int n; scanf(%d, n);for(int i 1; i n; i) scanf(%d, dp[i][0]);for(int j 1; j 20; j){ //首先枚举区间长度 for(int i 1; i(1j)-1 n; i){ //再枚举起点 dp[i][j] max(dp[i][j-1], dp[i(1(j-1))][j-1]);}}int q; scanf(%d, q);while(q--) {int l, r; scanf(%d%d, l, r);int k log2(r-l1); //区间长度的指数 printf(%d\n, max(dp[l][k], dp[r-(1k)1][k]));}return 0;
}
