提高十连测day3
A
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
const int N = 1e5 + 100;
int cnt,len,ans;
int sum[N],num[N];
char ch[N];
inline int Find(int pos, int x) {
int l = pos, r = cnt;
int pre = cnt + 1;
while(l <= r) {
int mid = (l + r) >> 1;
if(sum[mid] >= x) {
pre = mid;
r = mid-1;
}
else l = mid + 1;
}
return pre;
}
inline void check(int x) {
int key = x, pos = 1, pre = 0;
while(true) {
pos = Find(pos, key);
if(pos == cnt) {
if(pre + x >= x * 2 + 1)
ans = max(pre + x, ans);
return;
}
if(pos == cnt + 1) {
if(pre >= x * 2 + 1)
ans = max(pre, ans);
return;
}
key = sum[pos] + x;
pre += x + 1;
}
return;
}
int main() {
scanf("%s", ch + 1);
len = strlen(ch + 1);
for(int i = 1 ; i <= len ; i++)
num[i] = ch[i] - '0';
num[++len] = 1;
int tmp = 0;
for(int i = 1 ; i <= len - 1 ; i++)
if(!num[i]) tmp = 0;
else {
tmp++;
ans = max(tmp, ans);
}
int now = 0;
for(int i = 1 ; i <= len ; i++) {
if(!num[i]) now++;
else sum[++cnt] = now;
}
for(int i = 1 ; i <= len ; i++) check(i);
printf("%d \n", ans);
//system("pause");
return 0;
}
B
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define LL long long
#define M 410
const int N = 2e5 + 100;
struct Edge {
int to,from;
int data;
}e[N * 2];
LL head[N],degree[N];
LL num[N],n,m,q,cnt;
LL dis[N][M],tmp[N];
queue<int> qu;
inline void add_edge(int x,int y,int z) {
e[++cnt].from = y;
e[cnt].data = z;
e[cnt].to = head[x];
head[x] = cnt;
degree[y]++;
}
void Find(int x,int y,int val) {
int l = 1,r = 1,now = 0;
while(l <= num[x] && r <= num[y]) {
LL u = dis[x][l] + val;
if(u < dis[y][r]) {
while(now >= 2 && u >= tmp[now] && (double)tmp[now - 1] > (double)u / 1.1) now--;
tmp[++now] = u;
l++;
} else {
while(now >= 2 && dis[y][r] >= tmp[now] && (double)tmp[now - 1] > (double)dis[y][r] / 1.1) now--;
tmp[++now] = dis[y][r];
r++;
}
}
while(l <= num[x]) {
LL u = dis[x][l] + val;
while(now >= 2 && u >= tmp[now] && (double)tmp[now - 1] > (double)u / 1.1) now--;
tmp[++now] = u;
l++;
}
while(r <= num[y]) {
while(now >= 2 && dis[y][r] >= tmp[now] && (double)tmp[now - 1] > (double)dis[y][r] / 1.1) now--;
tmp[++now] = dis[y][r];
r++;
}
num[y] = now;
for(int i = 1 ; i <= now ; i++)
dis[y][i] = tmp[i];
}
inline void prework() {
qu.push(1);
dis[1][++num[1]] = 0;
while(!qu.empty()) {
int u = qu.front();
qu.pop();
for(int i = head[u] ; i ; i = e[i].to) {
int v = e[i].from;
Find(u,v,e[i].data);
degree[v]--;
if(!degree[v]) qu.push(v);
}
}
}
int main() {
scanf("%lld%lld%lld",&n,&m,&q);
for(int i = 1 ; i <= m ; i++) {
LL x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
add_edge(x,y,z);
}
prework();
while(q--) {
LL disx,x;
scanf("%lld%lld",&x,&disx);
int pos = lower_bound(dis[x] + 1,dis[x] + num[x] + 1,disx) - dis[x];
if(pos == num[x] + 1) {
puts("NO");
continue;
}
if((double)dis[x][pos] <= (double)1.1 * disx) puts("YES");
else puts("NO");
}
//system("pause");
return 0;
}
C
若我们对⾏和列维护⼀个数组，数组中的值为最后⼀次被清空的时间，那么对于⼀个询问，这个⾏或列在询问中出现当且仅当它的值⼤于等于某个数。我们只需要维护两个操作：找到在 $ x $ 位置后的第⼀个⼤于等于 $ v $ 的位置、找到在 $ x $ 位置前的最后⼀个⼤于等于 $ v $ 的位置。这两个操作可以⽤线段树上⼆分实现,时间复杂度 $ O(\log n) $ 。
对于第三种情况可能需要单独维护⼀个单点修改询问区间极值的线段树。
总复杂度 $ O(Q \log n) $ 。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
#define lson x * 2
#define rson x * 2 + 1
const int N = 1e5 + 100;
struct Segment_Tree {
struct Tree {
int tag, minn, maxx;
}tree[N << 2];
void pushup(int x) {
tree[x].minn = min(tree[lson].minn, tree[rson].minn);
tree[x].maxx = max(tree[lson].maxx, tree[rson].maxx);
}
void build(int x, int l, int r) {
if(l == r) {
tree[x].minn = 0;
tree[x].maxx = 0;
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(x);
}
void pushdown(int x) {
if(tree[x].tag) {
tree[lson].minn += tree[x].tag;
tree[rson].minn += tree[x].tag;
tree[lson].maxx += tree[x].tag;
tree[rson].maxx += tree[x].tag;
tree[lson].tag += tree[x].tag;
tree[rson].tag += tree[x].tag;
tree[x].tag = 0;
}
}
void update(int x, int l, int r, int ll, int rr, int c) {
if(l == ll && r == rr) {
tree[x].tag += c;
tree[x].minn += c;
tree[x].maxx += c;
return;
}
pushdown(x);
int mid = (l + r) >> 1;
if(rr <= mid) update(lson, l, mid, ll, rr, c);
else if (ll > mid) update(rson, mid + 1, r, ll, rr, c);
else {
update(lson, l, mid, ll, mid, c);
update(rson, mid + 1, r, mid + 1, rr, c);
}
pushup(x);
}
void delet(int x, int l, int r, int v) {
if(l == r) {
tree[x].minn = 0;
tree[x].maxx = 0;
return;
}
pushdown(x);
int mid = (l + r) >> 1;
if(v <= mid) delet(lson, l, mid, v);
else delet(rson, mid + 1, r, v);
pushup(x);
}
int query(int x, int l, int r, int ll, int rr, int v) {
if(l == ll && r == rr) {
if(v == 1) return tree[x].minn;
else return tree[x].maxx;
}
pushdown(x);
int mid = (l + r) >> 1;
if(rr <= mid) return query(lson, l, mid, ll, rr, v);
else if(ll > mid) return query(rson, mid + 1, r, ll, rr, v);
else {
if(v == 1) return min(query(lson, l, mid, ll, mid, v), query(rson, mid + 1, r, mid + 1, rr, v));
else return max(query(lson, l, mid, ll, mid, v), query(rson, mid + 1, r, mid + 1, rr, v));
}
}
}line, row;
int n, m, q;
int find1(int x, int v) {
int l = 1, r = x-1, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(row.query(1, 1, m, mid, x-1, 1) <= v) {
res = mid;
l = mid + 1;
}
else r = mid-1;
}
return res;
}
int find2(int x, int v) {
int l = x + 1, r = m, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(row.query(1, 1, m, x + 1, mid, 1) <= v) {
res = mid;
r = mid-1;
}
else l = mid + 1;
}
return res;
}
int find3(int x, int v) {
int l = 1, r = x-1, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(line.query(1, 1, n, mid, x-1, 1) <= v) {
res = mid;
l = mid + 1;
}
else r = mid-1;
}
return res;
}
int find4(int x, int v) {
int l = x + 1, r = n, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(line.query(1, 1, n, x + 1, mid, 1) <= v) {
res = mid;
r = mid-1;
}
else l = mid + 1;
}
return res;
}
bool deal1(int a, int b, int c, int d, int v) {
if(a > c) swap(a, c);
if(line.query(1, 1, n, a, c, 2) <= v) return 1;
if(b > d) swap(b, d);
if(row.query(1, 1, m, b, d, 2) <= v) return 1;
return 0;
}
bool deal2(int a, int b, int c, int d, int v) {
int av = line.query(1, 1, n, a, a, 1);
int bv = row.query(1, 1, m, b, b, 1);
int cv = line.query(1, 1, n, c, c, 1);
int dv = row.query(1, 1, m, d, d, 1);
if(a == c && av <= v) return 1;
if(b == d && bv <= v) return 1;
if(av <= v && dv <= v) return 1;
if(bv <= v && cv <= v) return 1;
if(av <= v && cv <= v && row.query(1, 1, m, min(b, d), max(b, d), 1) <= v) return 1;
if(bv <= v && dv <= v && line.query(1, 1, n, min(a, c), max(a, c), 1) <= v) return 1;
return 0;
}
int deal3(int a, int b, int c, int d, int v) {
int res, mins = 2e9, dis = abs(a - c) + abs(b - d);
if(line.query(1, 1, n, a, a, 2) <= v && line.query(1, 1, n, c, c, 2) <= v) {
res = find1(min(b, d), v);
if(res != -1) mins = min(mins, dis + 2 * abs(res - min(b, d)));
res = find2(max(b, d), v);
if(res != -1) mins = min(mins, dis + 2 * abs(res - max(b, d)));
}
if(row.query(1, 1, n, b, b, 2) <= v && row.query(1, 1, n, d, d, 2) <= v) {
res = find3(min(a, c), v);
if(res != -1) mins = min(mins, dis + 2 * abs(res - min(a, c)));
res = find4(max(a, c), v);
if(res != -1) mins = min(mins, dis + 2 * abs(res - max(a, c)));
}
if(mins == 2e9) return-1;
else return mins;
}
int work() {
int a,b,c,d,v;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&v);
if(a == c && b == d) return 0;
if(deal1(a, b, c, d, v) || deal2(a, b, c, d, v))
return abs(a - c) + abs(b - d);
return deal3(a, b, c, d, v);
}
int main() {
scanf("%d%d%d",&n,&m,&q);
line.build(1, 1, n);
row.build(1, 1, m);
while (q--) {
line.update(1, 1, n, 1, n, 1);
row.update(1, 1, m, 1, m, 1);
int opt,x;;
scanf("%d",&opt);
if(opt == 1) {
scanf("%d",&x);
line.delet(1, 1, n, x);
}
if(opt == 2) {
scanf("%d",&x);
row.delet(1, 1, m, x);
}
if(opt == 3) printf("%d \n",work());
}
//system("pause");
return 0;
}