为了锻炼个人能力奋力div1 为了不做原题从200开始
B 两个电线缠在一起了 能不能抓住两头一扯就给扯分开
很明显当len为odd的时候无解 当len为偶数的时候 可以任选一段长度为even的相同字符串给它翻过去 即 ++--++++--++ -> ++--------++ -> ++++++++++++
一直这样下去一定可以翻出结果 但是复杂度很高 不能暴力的去找
考虑用一个栈 依次往里放 每次看到top等于当前的这个字符 意义是当前有一个偶数了 便pop出来 最后判断栈的empty
做完B的我十分欣慰 感觉这样练下去应该提升真的不小
C 磁盘调度算法 读取不花时间 n个磁头 m个地点 划过就算读入了 可以多个磁头一起随便移动 问最少多少时间所有的地点都能被划过
最小化最大值问题 考虑二分一下maxtime 然后枚举磁头来check 对于当前剩余的地点序列 我这个磁头从左到右最远可以读到哪儿
就是做一个类似于双指针的check 磁头的指针后跳 那么地点的指针可能也往后跳 看看最后地点的指针有没有跳完
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
#define L long long
#define pb push_back
#define ph push
#define lala printf(" ---------
") ;
#define rep(i, a, b) for (L i=a;i<=b;++i)
#define dow(i, b, a) for (L i=b;i>=a;--i)
#define fmt(i,n) if(i==n)printf("
");else printf(" ") ;
#define lro ro*2
#define rro ro*2+1
#define fi first
#define se second
template<class T> inline void flc(T &A, L x){memset(A, x, sizeof(A));}
L read(){L x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
L n , m ;
L a[100050] ;
L b[100050] ;
bool check(L time) {
L last = 1 ;
rep(i,1,n){
if(b[last] <= a[i]) {
L xd = a[i] - b[last] ;
if(time < xd) {
return false ;
}
L yy = (time - xd) / 2 ;
L where1 = a[i] + yy ;
L xd2 = time - (a[i] - b[last]) ;
L where2 = (xd2 + b[last]) ;
L where = max(where1 , where2) ;
while(b[last] <= where) {
last ++ ;
}
if(last > m) return true ;
}
else {
L where = a[i] + time ;
while(b[last] <= where) {
last ++ ;
}
if(last > m) return true ;
}
}
return false ;
}
int main () {
n = read() ;
m = read() ;
rep(i,1,n) a[i] = read() ;
rep(i,1,m) b[i] = read() ;
L l = 0 ;
L r = 30000000000 ;
L res = 0 ;
while(l <= r) {
L mid = (l + r) / 2 ;
if(check(mid)) {
r = mid - 1 ;
res = mid ;
}
else {
l = mid + 1 ;
}
}
printf("%I64d
" , res) ;
}
写完C1A了..asuka一脸迷茫 这个C明显比B简单的样子...那个年代的cf有点奇怪的说...
虽然开专题准备做div1BC 但是注意到D好像比C过的还多 于是做一下D
D 一个树 3个操作 op1 把一个点和他的子树群体置1 op2 把一个点和他的直系先辈群体置0 op3 查询一个点的值
dfs序标一下号 建立两个线段树来维护op1和op2
op1 线段树区间更新单点查询 由于val递增 其实不需要lazy标记
op2 线段树单点更新区间维护最大值 查询的意义是一个点的子树区间内谁最后被op2了
op3 对两个线段树询问 比一下谁最大
可能..做久远一点的CF idea都被用惯了 可能还是在做原题啊...
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
#define L long long
#define pb push_back
#define ph push
#define lala printf(" ---------
") ;
#define rep(i, a, b) for (int i=a;i<=b;++i)
#define dow(i, b, a) for (int i=b;i>=a;--i)
#define fmt(i,n) if(i==n)printf("
");else printf(" ") ;
#define lro ro*2
#define rro ro*2+1
#define fi first
#define se second
template<class T> inline void flc(T &A, int x){memset(A, x, sizeof(A));}
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
int n , qnum ;
vector<int>q[500050] ;
int cnt ;
int l[500050] , r[500050] ;
int id[500050] ;
void dfs(int u , int fa) {
cnt ++ ;
l[u] = cnt ;
int siz = q[u].size() ;
rep(i,0,siz-1){
int v = q[u][i] ;
if(v==fa)continue ;
dfs(v,u) ;
}
r[u] = cnt ;
}
int last[500000 * 4] ;
int last2[500000 * 4] ;
/// --- op 1
void build() {
flc(last,0);
flc(last2,0);
}
int ans1 ;
void query(int ro,int l,int r,int pos) {
ans1 = max(ans1,last[ro]);
int mid=(l+r)/2;
if(l==r)return ;
if(pos<=mid)query(lro,l,mid,pos);
else query(rro,mid+1,r,pos);
}
void upda(int ro,int l,int r,int ul,int ur,int val) {
if(l>=ul&&r<=ur){
last[ro]=val;
return;
}
int mid=(l+r)/2;
if(ul<=mid)upda(lro,l,mid,ul,ur,val);
if(ur>=mid+1)upda(rro,mid+1,r,ul,ur,val);
}
/// --- op 2
int query2(int ro,int l,int r,int ul,int ur) {
if(l>=ul&&r<=ur){
return last2[ro];
}
int ans=0;
int mid=(l+r)/2;
if(ul<=mid) ans = max(ans,query2(lro,l,mid,ul,ur)) ;
if(ur>mid) ans = max(ans , query2(rro,mid+1,r,ul,ur)) ;
return ans ;
}
void upda(int ro,int l,int r,int pos,int val) {
if(l==r) {
last2[ro] = val ;
return ;
}
int mid=(l+r)/2;
if(pos<=mid) upda(lro,l,mid,pos,val);
else upda(rro,mid+1,r,pos,val);
last2[ro]=max(last2[lro],last2[rro]) ;
}
/// --- op 3
int solve(int x) {
ans1 = 0 ;
query(1,1,n,l[x]) ;
int ans2 = query2(1,1,n,l[x],r[x]) ;
if(ans1 == 0 && ans2 == 0) {
printf("0
") ;
}
else {
if(ans1 > ans2) printf("1
") ;
else printf("0
") ;
}
}
int main () {
n = read();
rep(i,1,n) q[i].clear() ;
rep(i,1,n-1) {
int u=read();
int v=read() ;
q[u].pb(v);
q[v].pb(u);
}
cnt = 0 ;
dfs(1,-1) ;
build() ;
qnum = read();
rep(i,1,qnum) {
int op = read() ;
int x = read() ;
if(op == 1) {
upda(1,1,n,l[x],r[x],i) ;
}
else if(op == 2) {
upda(1,1,n,l[x],i) ;
}
else {
solve(x) ;
}
}
}