CF1208
打的话貌似能够涨分的样子?
A
水题
B
枚举左端点,看看右端点的最近位置
开一个类似于桶的东西维护一下上一次出现位置
左端点左边就删掉,否则就要将上一次出现的位置删掉
时间复杂度(O(n^2))或者(O(n^2logn))取决于是否离散化
貌似一个log就是二分答案
然后(O(n))check一遍
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<map>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 2003;
int a[N];
int pre[N];
map <int,int> m;
int n;
inline int read(){
int v = 0,c = 1;char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') c = -1;
ch = getchar();
}
while(isdigit(ch)){
v = v * 10 + ch - 48;
ch = getchar();
}
return v * c;
}
int main(){
int ans = 0x3f3f3f3f;
n = read();
for(int i = 1;i <= n;++i){
a[i] = read();
if(!m[a[i]]) m[a[i]] = i;
else pre[i] = m[a[i]];
m[a[i]] = i;
// printf("%d
",pre[i]);
}
bool flag = 1;
for(int i = 1;i <= n;++i){
m.clear();
int r = 0;
for(int j = 0;j < i;++j){
if(m[a[j]] == -1) {flag = 0;break;}
m[a[j]] = -1;
}
if(!flag) break;
for(int j = i;j <= n;++j){
if(m[a[j]] == -1) r = max(r,j);
else if(m[a[j]] != 0){
r = max(r,m[a[j]]);
m[a[j]] = j;
}
else m[a[j]] = j;
}
if(r != 0) ans = min(ans,r - i + 1);
else ans = 0;
}
cout << ans;
return 0;
}
听说貌似有(O(n))做法不大会
C
构造题
分成四块考虑,因为题目中保证是(4)的倍数
首先,如果没有(0-n^2-1)这个限制
这样子肯定符合要求
(egin{array}{cccc}{0} & {0} & {1} & {1} \ {0} & {0} & {1} & {1} \ {2} & {2} & {3} & {3} \ {2} & {2} & {3} & {3}end{array})
但是这样肯定不符合题意
那么我们就对于给每一部分编号
把这一部分整体+4
(egin{array}{cccc}{0} & {4} & {1} & {5} \ {8} & {12} & {9} & {13} \ {2} & {6} & {3} & {7} \ {10} & {14} & {11} & {15}end{array})
如果没有保证(n)是(4)的倍数,那么这样构造一定不对,因为每一行都有数出现了奇数次
由于每一行每一列
每个(4)的倍数都只被加了两次
异或起来都答案是没有影响的
那么我们照着这样子构造就好了
D
感觉D是个一眼题,CD应该换一下位置的
最右边的(0)对应的位置一定是(1)
然后把(1)的贡献去掉之后,最右边的(0)一定是(2)
以此类推
线段树搞一搞就好了
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 3;
const LL INF = 1e15;
LL dis[N];
int an[N];
int n,root;
inline LL read(){
LL v = 0,c = 1;char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') c = -1;
ch = getchar();
}
while(isdigit(ch)){
v = v * 10 + ch - 48;
ch = getchar();
}
return v * c;
}
struct Tree{
int t;
struct node{
LL maxx;
LL tag;int pos;
int lc,rc;
}a[N << 2];
inline void pushup(int u){
if(a[a[u].lc].maxx < a[a[u].rc].maxx) a[u].maxx = a[a[u].lc].maxx,a[u].pos = a[a[u].lc].pos;
else a[u].maxx = a[a[u].rc].maxx,a[u].pos = a[a[u].rc].pos;
}
inline void pushdown(int u,int l,int r){
if(!a[u].tag) return;
a[a[u].lc].maxx += a[u].tag;
a[a[u].rc].maxx += a[u].tag;
a[a[u].lc].tag += a[u].tag;
a[a[u].rc].tag += a[u].tag;
a[u].tag = 0;
return ;
}
inline void build(int &u,int l,int r){
if(!u) u = ++t;
if(l == r){
a[u].maxx = dis[l];
a[u].pos = l;
return ;
}
int mid = (l + r) >> 1;
build(a[u].lc,l,mid);build(a[u].rc,mid + 1,r);
pushup(u);
}
inline void updata(int u,int l,int r,int ll,int rr,LL w){
if(ll > rr) return;
if(l == ll && r == rr){
a[u].maxx += w;
a[u].tag += w;
return ;
}
pushdown(u,l,r);
int mid = (l + r) >> 1;
if(rr <= mid) updata(a[u].lc,l,mid,ll,rr,w);
else if(ll > mid) updata(a[u].rc,mid + 1,r,ll,rr,w);
else{
updata(a[u].lc,l,mid,ll,mid,w);
updata(a[u].rc,mid + 1,r,mid + 1,rr,w);
}
pushup(u);
}
inline int query(){return a[root].pos;}
}T;
int main(){
n = read();
for(int i = 1;i <= n;++i) dis[i] = read();
T.build(root,1,n);
// cout << "GG" << endl;
for(int i = 1;i <= n;++i){
int x = T.query();
an[x] = i;
T.updata(root,1,n,x + 1,n,-i);
T.updata(root,1,n,x,x,INF);
}
for(int i = 1;i <= n;++i) printf("%d ",an[i]);
return 0;
}
E
当时就硬是没想出来差分的技巧
首先每个位置可以取到的数肯定是
([x - (w - len),x+(w -len)])这个区间的最大值
之后我们分两种情况讨论
首先
当(len >= w -len)时
这时候会长成这个样子
我们设(d = w - len)表示能够滑动的距离
对于一个位置(x)
首先,绿色部分是只能够从左向右取最大值([x - d,x])
红色只能从右向左取最大值([x,x + d])
中间部分呢？这一部分你会发现
这一部分其实可以和红色或者绿色任意一部分合起来算
这个时候注意不要把黄色部分重复计算就好
当(len < w - len)时
这个时候,中间的黄色部分的答案,就变成了序列中的最大值和(0)取max
因为中间部分是可以取到序列中的任意数
所以我们只需要维护区间最大值,这个东西随便搞搞吧
注意判断越界时要和(0)取max,表示可以不选
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<deque>
#include<ctime>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 3;
const int INF = 2e9;
int n,len,w;
int f[21][N];
LL ans[N];
int lg[N];
inline int read(){
int v = 0,c = 1;char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') c = -1;
ch = getchar();
}
while(isdigit(ch)){
v = v * 10 + ch - 48;
ch = getchar();
}
return v * c;
}
inline void pre(){
for(int j = 1;(1 << j) <= len;++j){
for(int i = 1;i + (1 << j) - 1 <= len;++i)
f[j][i] = max(f[j - 1][i],f[j - 1][i + (1 << (j - 1))]);
}
}
inline int work(int l,int r){
int k = lg[r - l + 1];
return max(f[k][l],f[k][r - (1 << k) + 1]);
}
inline int query(int l,int r){
if(l < 1 || r > len) return max(0,work(max(1,l),min(len,r)));
else return work(l,r);
}
int main(){
lg[1] = 0;
for(int i = 2;i <= 1000000;++i) lg[i] = lg[i >> 1] + 1;
n = read(),w = read();
for(int i = 1;i <= n;++i){
len = read();
for(int j = 1;j <= len;++j) f[0][j] = read();
pre();
for(int i = 1;i <= len;++i){
int k = query(i,i + w - len);
ans[i + w - len] += k;
ans[i + w - len + 1] -= k;
}
for(int i = 1;i <= min(len,w - len);++i){
int k = query(i - w + len,i);
ans[i] += k;
ans[i + 1] -= k;
}
if(len < w - len){
int k = max(0,query(1,len));
ans[len + 1] += k;
ans[w - len + 1] -= k;
}
}
for(int i = 1;i <= w;++i) {ans[i] += ans[i - 1];printf("%lld ",ans[i]);}
return 0;
}
F
神仙题解(SOS DP)
题目大意求((i,j,j)i < j < k)使得(a_i | (a_j &a_i))最大
(n <= 10^6,a_i < 2^{21})
考虑从从后向前枚举(i)
从高位向低位贪心
设(dp_x)表示(x)设个二进制集合被多少数完全包含
每次对于一个(a_i)
从大到小枚举所有位
如果这个位(j)不是(1)同时满足当前贪心的结果(x),(x | (1 << j))被超过两个数包含(保证(&)完之后有这个数)就将这一位加入贪心的答案
更新完答案之后就把每一位包含(a_i)的加入
时间复杂度貌似有点爆炸
但是我们发现如果(dp_x >=2)那么直接return
所以每个位置最多被更新两次
均摊是(2^{21})的复杂度
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 3;
int a[N];
int cnt[N << 2];
int n;
inline int read(){
int v = 0,c = 1;char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') c = -1;
ch = getchar();
}
while(isdigit(ch)){
v = v * 10 + ch - 48;
ch = getchar();
}
return v * c;
}
int ans = 0;
inline void ins(int x,int d){
if(cnt[x] >= 2) return;
if(d == -1){cnt[x]++;return;}
ins(x,d - 1);
if(x & (1 << d)) ins(x ^ (1 << d),d - 1);
}
inline int query(int x){
int now = 0;
for(int i = 20;i >= 0;--i) if(((x & (1 << i)) == 0) && cnt[now | (1 << i)] >= 2) now |= 1 << i;
return now | x;
}
int main(){
n = read();
for(int i = 1;i <= n;++i) a[i] = read();
for(int i = n;i >= 1;--i){
if(i <= n - 2) ans = max(ans,query(a[i]));
ins(a[i],20);
}
printf("%d
",ans);
return 0;
}