这个场由于系统出问题 unrated了
题目都还挺短小精悍的
A
题目大意是
有n个询问(10^4)，每个询问是找出在[l,r]区间内二进制位1最多的数
l,r范围是10^18
然后就是贪心。 用 l 从低位往上贪就行了，0变1如果不超范围就变
long long l, r;
int n;
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%I64d%I64d", &l, &r);
for(int j = 0; j < 61; j++) {
long long tmp = 1LL << j;
if(l & tmp) continue;
else if((l ^ tmp) <= r) l ^= tmp;
}
printf("%I64d\n", l);
}
return 0;
}
B
给一个序列a，长度2*10^5，每个数的范围是10^6
然后问最大的a[i]%a[j] 其中要求的是a[i] >= a[j]
一看这个范围基本就是专卡nlognlogn的了
试了一下果然T了
然后有nlogn的做法
就是对任意的a[i]，标记为1，然后
从1到mx，扫一遍统计比当前数小的最大的a[i]是多少，其中mx应该是2000000
然后枚举，对每个数，枚举倍数
如果该数为x,倍数为y， 则去找比x * y小的最大的a[i]，用a[i] - x *(y -1) 就求出了一个可能的解
bool v[2111111];
int pre[2111111];
int a[222222];
int n;
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
v[a[i]] = 1;
}
int mx = 2000005;
for(int i = 1; i < mx; i++) {
pre[i] = pre[i - 1];
if(v[i - 1]) pre[i] = i - 1;
}
int ans = 0;
for(int i = 1; i < mx; i++) {
if(!v[i]) continue;
for(int j = 2 * i; j < mx; j += i) {
ans = max(ans, pre[j] + i - j);
}
}
printf("%d\n", ans);
return 0;
}
C
题目大意
给出一个串，长度为n，有m个操作，m*n <=10^6
对每个操作，有两个整数，k和d
表示从左到右依次对长度为k的子串进行d-sort
所谓d-sort表示的是对某个子串，先不管它在主串中什么位置，就以该子串的首位置为下标0，
在0到k-1这个区间内，按照下标对d取模的值进行分类，如%d=1, %d=2.....
排序就是按照这个值从小到大排的，如果值相同就按其在子串中的相对位置来
然后就先把%d=0的位置的字符先放前面，接着%d=1的，依次类推
然后当前区间搞定后，就去下一个长度为k的子串，显然这两个子串之间有重复的部分
样例里解释的还是比较清楚
问每次操作后的主串长啥样
注意，这些操作造成的变化都是没有复原的
这题刚开始我是不会的，我模拟了下d-sort的过程，感觉可能会出现若干个循环节那种。但是不知道怎么搞出来。
后来看了别人的一个代码才知道了，不过我跟他想的还是有些不一样。
首先对于一个串，将其最左边的长度为k的子串进行d-sort后，观察其变化，
可以发现第一个位置的字符不会再改变了，那么我们只需管后面没这个字符的子串就行
观察这个子串，如果我们把他当做一个主串，不考虑其在原来的主串中的位置，以其开始位置为下标0
那么可以得到它跟原来主串的一个位置映射
以第一个样例为例子
进行完第一个子串的d-sort后，串由qwerty变成了qewrty
观察ewrty
得到位置映射如下
p[0] = 2
p[1] = 1
p[2] = 3
p[3] = 4
p[4] = 5
p[5] = 0
p[i]表示的是在这个子串中第i个字符原来在主串中的位置,p[5]这里没有字符我们先设为0（就是为了图方便，实际上我们不会用到p[5] = 0）
然后我们发现，这里面有循环节
0,2,3,4,5 和 1
对第一个循环节，解释一下，表示一次变换，原来主串中位置为2的就变到新主串的0位置了，两次就是3变到0，三次就是4变到0
然后一次d-sort至少能确定一个字符不会再变
那么我们就这样，以主串d-sort完最开始的那个长度为k的区间后，去掉第一个字符，以这个子串作为主串，接着进行变换，直到最后一个区间
然后发现，每个区间的开始位置，是每次变换所能确定的字符，假设位置为i则需要的变换次数为i，意思是最开始那个主串中某个位置的字符经过了i次变换
变成了第i个主串第0个字符，意思就是使用0所在的循环节计算了，实际上对于0所在的这个循环节，我们不会用到p[5]=0，所以也就是说不会出现4变成5然后变成0这样的情况
那么由于变换总共有n-k+1个，也就是说最开始的主串中n-k+1到n-1这个闭区间的字符都会经过n-k+1次变换 ，而这个区间的字符也不能作为某个新主串的开始位置了
假设某位置在原始主串的下标为j, 那么j - (n - k + 1)就是该位置字符在最后一个新主串中的位置，利用这个值去找相应的循环节去计算
总体的复杂度是O(m * n)
#define MAXN 1111111
#define MAXM 400005
using namespace std;
char s[MAXN], s1[MAXN];
int pre0[MAXN], pre[MAXN], a[MAXN];
bool vis[MAXN];
int n, cnt;
void gao(int k, int d) {
cnt = 0;
for(int i = 0; i < d; i++) {
for(int j = i; j < k; j += d) {
pre0[cnt++] = j;
}
}
for(int i = k; i < n; i++) pre0[i] = i;
for(int i = 0; i < n - 1; i++) pre[i] = pre0[i + 1];
pre[n - 1] = pre0[0];
for(int i = 0; i < n; i++) vis[i] = 0;
for(int i = 0; i < n; i++) {
if(!vis[i]) {
cnt = 0;
a[cnt++] = i;
vis[i] = 1;
int j = pre[i];
while(j != i) {
a[cnt++] = j;
vis[j] = 1;
j = pre[j];
}
if(i == 0) {
for(j = 0; j <= n - k + 1; j++) {
s1[j] = s[a[j]];
}
}
for(j = 0; j < cnt; j++) {
int p = a[j] + n - k + 1;
if(p < n && p > n - k + 1) s1[p] = s[a[(j + n - k + 1) % cnt]];
}
}
}
s1[n] = '\0';
for(int i = 0; i < n; i++) s[i] = s1[i];
puts(s1);
}
int main() {
scanf("%s", s);
n = strlen(s);
int T, k, d;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &k, &d);
gao(k, d);
}
return 0;
}
D
给出一个序列 长度10^6
然后要分组，每组是这个序列中某一段连续的子序列，不能为空
然后每组计算一个 maxvalue - minvalue
最后求和
问怎么分组，这个和最大
裸的dp方程是 dp[i] =max( dp[j- 1] + mx[j][i] - mi[j][i] )
肯定不行啊。复杂度太高了
有两种做法。
1. 我们把这个序列看成由若干单增单降的序列组成的，
那么显然，将这个序列划分为若干这些个单增单降的连续子序列 会 最优
那么对一个极点，划分有两种情况，左边或者右边，取最优即可
int a[1111111];
long long dp[1111111];
int main() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
int pos = 1;
for(int i = 2; i <= n; i++) {
dp[i] = dp[pos - 1] + abs(a[i] - a[pos]);
dp[i] = max(dp[i], dp[pos] + abs(a[i] - a[pos + 1]));
if(a[i] >= a[i - 1] && a[i] >= a[i + 1]) pos = i;
if(a[i] <= a[i - 1] && a[i] <= a[i + 1]) pos = i;
}
printf("%I64d\n", dp[n]);
return 0;
}
2.对dp方程进行变化
有两种情况
第一种，当前位置的值可能是最大值
那么dp[i] =(dp[j- 1] - mi[j][i] )+ a[i]
另一种，就是当前位置是最小值，
dp[i] = (dp[j - 1] + mx[j][i]) - a[i]
其他情况， 都是无效的状态，即使你更新也不会影响到结果
对于这两种情况
将(dp[j- 1] - mi[j][i] ) 和(dp[j - 1] + mx[j][i]) 进行维护即可
维护时也并不是像这个式子显示的这么复杂
对于到i位置时，我们只要取当前位置之前最大的dp[j]，然后假设a[i]为最大值和最小值，去更新这两个式子即可
可以发现覆盖到了所有情况
int main() {
int n;
scanf("%d", &n);
long long ans = 0, x = 0, y = 0;
int a;
for(int i = 0; i < n; i++){
scanf("%d", &a);
if(!i || ans - a > x) x = ans - a;
if(!i || ans + a > y) y = ans + a;
ans = max(ans, x + a);
ans = max(ans, y - a);
}
printf("%I64d\n", ans);
return 0;
}
E
给出一个数字序列 ， 长度10^5， 数字范围10^9
有若干个询问（10^5）
每个询问由L,R,w组成
问的是L,R区间中，最大的（某个长度为w的子区间中数字的最小值）
有两种做法
先说第一个做法，主席树+二分
所谓主席树也就是可持久化线段树
首先把序列从大到小排序，注意把在原来序列中的位置都存下来
然后用数字在序列中的位置建立主席树
序列值从大到小，把相应的在原序列中的位置依次插入主席树，相当于把树中对应位置的值由0变成了1
然后维护llen,rlen,mxlen，分别表示，区间内从左端点开始的连续为1的子区间长度，区间内从右端点开始的连续为1的区间长度，mxlen表示区间中最长的连续为1的子区间的长度
对一个询问
二分时间点，去寻找最早能满足询问条件的时间点，即区间的最长连续为1的子区间长度>=w ,而因为之前我们是按数字的值从大到小排序，所以越早满足条件说明求出的结果越大
注意，这里线段树需要使用三段式，因为两个区间合并时，左区间的rlen+右区间的llen可能会是最优值
然后在status里看别人的代码时发现，有个人使用了一个变量就能做到合并这个信息，不像很多代码里都是开一个结构体，用类似于up操作的方法，去更新
然后这题zhou神看完题就给出了解法并且瞬间秒了，真是可怕
#define INF 1000000001
#define MAXN 111111
#define MAXM 2500005
using namespace std;
int n, tot, q;
int T[MAXM], lson[MAXM], rson[MAXM], mxlen[MAXM], llen[MAXM], rlen[MAXM];
struct node {
int val, pos;
}a[MAXN];
bool cmp(node x, node y) {
return x.val > y.val;
}
inline void up(int rt, int l, int r, int m) {
mxlen[rt] = max(mxlen[lson[rt]], mxlen[rson[rt]]);
mxlen[rt] = max(mxlen[rt], rlen[lson[rt]] + llen[rson[rt]]);
llen[rt] = llen[lson[rt]];
if(llen[rt] == m - l + 1) llen[rt] += llen[rson[rt]];
rlen[rt] = rlen[rson[rt]];
if(rlen[rt] == r - m) rlen[rt] += rlen[lson[rt]];
}
int update(int rt, int l, int r, int pos) {
int newrt = ++tot;
if(l == r) {
llen[newrt] = rlen[newrt] = mxlen[newrt] = 1;
return newrt;
}
int m = (l + r) >> 1;
if(pos <= m) {
lson[newrt] = update(lson[rt], l, m, pos);
rson[newrt] = rson[rt];
} else {
lson[newrt] = lson[rt];
rson[newrt] = update(rson[rt], m + 1, r, pos);
}
up(newrt, l, r, m);
return newrt;
}
int ans, now;
void query(int rt, int l, int r, int L, int R) {
if(L <= l && R >= r) {
ans = max(ans, mxlen[rt]);
ans = max(ans, now + llen[rt]);
if(rlen[rt] == r - l + 1) now += rlen[rt];
else now = rlen[rt];
return;
}
int m = (l + r) >> 1;
if(R <= m) return query(lson[rt], l, m, L, R);
else if(L > m) return query(rson[rt], m + 1, r, L, R);
else {
query(lson[rt], l, m, L, m);
query(rson[rt], m + 1, r, m + 1, R);
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i].val);
a[i].pos = i;
}
sort(a + 1, a + n + 1, cmp);
for(int i = 1; i <= n; i++) {
T[i] = update(T[i - 1], 1, n, a[i].pos);
}
scanf("%d", &q);
int L, R, w;
while(q--) {
scanf("%d%d%d", &L, &R, &w);
int l = 1, r = n, pos = n;
while(l <= r) {
int mid = (l + r) >> 1;
ans = 0, now = 0;
query(T[mid], 1, n, L, R);
if(ans >= w) {
pos = min(pos, mid);
r = mid - 1;
} else l = mid + 1;
}
printf("%d\n", a[pos].val);
}
return 0;
}
第二种方法
xiaodao给出的cdq分治解法
这个方法的优越性就在于不需要使用可持久化线段树了，一般线段树就可以做
没看过cdq的可以先看我之前写的一篇关于cdq分治的斜率优化题
首先序列从大到小排序
注意把在原来序列中的位置都存下来
然后用数字在序列中的位置建立线段树
然后将所有询问存入一个集合中
对这个集合和排好序的序列，采取cdq分治
把排好序后的序列的对应区间前一半的数字(也就是最大的那一半)的位置先插入线段树
然后看询问集合中哪些可以满足要求，哪些不能
满足要求的说明这些询问可能有最优的解，不满足要求的询问说明还需要继续的往里插入更小数字的位置才可能满足要求
那么将这个集合分成两部分，左部分是满足要求的询问，右部分是不满足要求的询问
然后先在区间的后半部分去递归求右部分的询问，当右边的询问求完之后，将区间的前一半数字的位置从线段树中删掉，再去区间的前半部分去递归求解左部分的询问
一个询问最终被确定是在，递归求解到最深层后，是一个单点，加入该点刚好能满足询问的需求，则该点对应的数值就是答案
而为什么先去递归右部分，是因为如果先去递归左部分，再去递归右部分的时候，会多进行一次删除和插入操作
想一下就会发现，这样就可以求出了最终的最优解
速度也还可以吧
#define INF 1000000001
#define MAXN 111111
#define MAXM 400005
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int n;
int llen[MAXM], rlen[MAXM], mxlen[MAXM];
int ll[MAXN], rr[MAXN], w[MAXN];
struct node {
int val, pos;
}a[MAXN];
bool cmp(node x, node y) {
return x.val > y.val;
}
inline void up(int rt, int l, int r, int m) {
mxlen[rt] = max(mxlen[lch(rt)], mxlen[rch(rt)]);
mxlen[rt] = max(mxlen[rt], rlen[lch(rt)] + llen[rch(rt)]);
llen[rt] = llen[lch(rt)];
if(llen[rt] == m - l + 1) llen[rt] += llen[rch(rt)];
rlen[rt] = rlen[rch(rt)];
if(rlen[rt] == r - m) rlen[rt] += rlen[lch(rt)];
}
void update(int pos, int v, int l, int r, int rt) {
if(l == r) {
mxlen[rt] = llen[rt] = rlen[rt] = v;
return;
}
int m = (l + r) >> 1;
if(pos <= m) update(pos, v, lson);
else update(pos, v, rson);
up(rt, l, r, m);
}
int ans, now;
void query(int L, int R, int l, int r, int rt) {
if(L <= l && R >= r) {
ans = max(ans, mxlen[rt]);
ans = max(ans, now + llen[rt]);
if(rlen[rt] == r - l + 1) now += rlen[rt];
else now = rlen[rt];
return;
}
int m = (l + r) >> 1;
if(R <= m) return query(L, R, lson);
else if(L > m) return query(L, R, rson);
else {
query(L, m, lson);
query(m + 1, R, rson);
}
}
int res[MAXN];
void cdq(vector<int> Q, int l, int r) {
int sz = Q.size();
if(l == r) {
for(int i = 0; i < sz; i++) res[Q[i]] = l;
return;
}
int m = (l + r) >> 1;
for(int i = l; i <= m; i++) update(a[i].pos, 1, 1, n, 1);
vector<int>QL, QR;
for(int i = 0; i < sz; i++) {
int j = Q[i];
ans = 0, now = 0;
query(ll[j], rr[j], 1, n, 1);
if(ans >= w[j]) QL.push_back(j);
else QR.push_back(j);
}
cdq(QR, m + 1, r);
for(int i = l; i <= m; i++) update(a[i].pos, 0, 1, n, 1);
cdq(QL, l, m);
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i].val);
a[i].pos = i;
}
sort(a + 1, a + n + 1, cmp);
vector<int> Q;
int m;
scanf("%d", &m);
for(int i = 1; i <= m; i++) {
scanf("%d%d%d", &ll[i], &rr[i], &w[i]);
Q.push_back(i);
}
cdq(Q, 1, n);
for(int i = 1; i <= m; i++) printf("%d\n", a[res[i]].val);
return 0;
}