20秋季普转提day5
dcx谢罪5题场??
然而还是做得像屎一样难看...因为好难啊
A
构造题
我的构造方法是取两端都是0的极长段来构造,这样一定能保证每个数是被最充分准备的
然后这两个位置放上数字,并且让他们中间的所有的都减去2
于是显然当我们从1到n枚举到一个数他的如果已经有数却没有减成就不太行....NoQAQ
std:
在钦点的情况下显然如果相邻两个差超过2就一定不行
那么其实满足这个情况就一定有解!
如果,没有数的话
否则,把i加入候选集合
如果
取候选集合任意一点然后匹配一下即可.....
好简单!
my code:
//你考虑每个我们都找最长的区间,满足两端都是0
//然后连一个青蛙,区间减一下
//查询后继0,支持区间减,在线
//线段树加二分实现
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 7;
int n, p[MAXN], a[MAXN];
const int MAXT = 8e5 + 7;
struct rec {
int V, tag;
} tr[MAXT];
namespace SEG {
#define mid ((l+r)>>1)
inline rec update(rec x, rec y) {
rec z;
z.V = min(x.V, y.V);
return z;
}
inline void pushdown(int k) {
if(!tr[k].tag)return ;
tr[k << 1].V += tr[k].tag;
tr[k << 1 | 1].V += tr[k].tag;
tr[k << 1].tag += tr[k].tag;
tr[k << 1 | 1].tag += tr[k].tag;
tr[k].tag = 0;
}
inline void build(int k, int l, int r) {
if(l == r) {
tr[k].V = p[l];
return ;
}
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
tr[k] = update(tr[k << 1], tr[k << 1 | 1]);
}
inline void modify(int k, int l, int r, int L, int R, int V) {
if(L <= l && r <= R) {
tr[k].V += V;
tr[k].tag += V;
return ;
}
pushdown(k);
if(L <= mid)modify(k << 1, l, mid, L, R, V);
if(R > mid)modify(k << 1 | 1, mid + 1, r, L, R, V);
tr[k] = update(tr[k << 1], tr[k << 1 | 1]);
}
inline rec query(int k, int l, int r, int L, int R) {
if(L <= l && r <= R)
return tr[k];
pushdown(k);
if(R <= mid)return query(k << 1, l, mid, L, R);
else if(L > mid)return query(k << 1 | 1, mid + 1, r, L, R);
return update(query(k << 1, l, mid, L, R), query(k << 1 | 1, mid + 1, r, L, R));
}
#undef mid
};
using namespace SEG;
inline int qry(int l, int r) {
int mid;
int ans = r;
while(l <= r) {
mid = (l + r) >> 1;
if(query(1, 1, n, l, mid).V > 0) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
}
}
return ans;
}
int main() {
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
scanf("%d", &n);
--n;
for (int i = 1; i <= n; ++i) {
scanf("%d", &p[i]);
}
if(p[n] == 0)a[n + 1] = n + 1;
if(n == 0) {
return puts("1"), 0;
}
build(1, 1, n);
for(int i = 1; i <= n; ++i) {
p[i] = query(1, 1, n, i, i).V;
if(p[i] == 0) {
if(!a[i])
a[i] = i;
continue;
}
if(p[i] && a[i]) { //如果这个有数了还自闭了
return puts("No"), 0;
}
int j = qry(i, n); //查询一下哪个位置?
if(a[j + 1]) { //如果已经有数了...
return puts("No"), 0;
}
a[j + 1] = i;
a[i] = j + 1;
modify(1, 1, n, i, j, -2);//区间减少2
p[i] = query(1, 1, n, i, i).V;
if(p[i] != 0) {
return puts("No"), 0;
}
}
puts("Yes");
for(int i = 1; i <= n + 1; ++i) {
printf("%d ", a[i]);
}
return 0;
}
B
考场被降智了,是指被zhq降智了....以为每次只能推一层
实际上是推一个连通块
所以把黑白的缩点然后再一个位置猛点就是标准做法ba
什么你说答案?缩点后直径/2
考场上数组太小了....
code:
//考虑我们求出缩点后的树的直径,因为我们每次能改一个连通块.....
//...好像这个不是答案?
//除以2下取整呢?
//我直接惊恐啊
//好像就是了?
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
int n, a[MAXN], f[MAXN];
struct rec {
int x, y;
} e[MAXN];
int mx, mn;
int vis[MAXN];
int home[MAXN], nxt[MAXN], to[MAXN], ccnt;
inline void ct(int x, int y) {
ccnt++;
nxt[ccnt] = home[x];
home[x] = ccnt;
to[ccnt] = y;
}
inline int getf(int x) {
return f[x] == x ? x : f[x] = getf(f[x]);
}
inline void merge(int x, int y) {
f[getf(x)] = getf(y);
return ;
}
inline void dfs(int x, int dep) {
vis[x] = 1;
if(dep > mx) {
mx = dep;
mn = x;
}
for(int i = home[x]; i; i = nxt[i]) {
int v = to[i];
if(vis[v])continue;
dfs(v, dep + 1);
}
return;
}
int main() {
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
f[i] = i;
}
for(int i = 1; i < n; ++i) {
scanf("%d%d", &e[i].x, &e[i].y);
if(a[e[i].x] == a[e[i].y])merge(e[i].x, e[i].y);
}
for(int i = 1; i < n; ++i) {
if(getf(e[i].x) == getf(e[i].y))continue;
ct(getf(e[i].x), getf(e[i].y));
ct(getf(e[i].y), getf(e[i].x));
}
dfs(getf(1), 1);
memset(vis, 0, sizeof(vis));
dfs(mn, 1); //从最大处再来一遍qwq
printf("%d\n", mx / 2);
return 0;
}
/*
11
0 0 0 1 1 0 1 0 0 1 1
1 2
1 3
2 4
2 5
5 6
5 7
3 8
3 9
3 10
9 11
*/
C
数组又开小了...
直接搞的dp...不太行啊
我们的限制其实可以通过按照重量排序,变成每个位置的LIS不能超过某个长度,然后
正着做好像是限制增加的过程,还是dp
于是我们倒着做,变成求最长下降就是限制减少了!
//考虑dp?LIS?
//从后向前考虑每个物品,他能用的背包数量是单调上升的
//那么我们可以考虑让LIS和背包数取min...
//使用BIT优化
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
vector<int> v;
int T, n, m;
struct rec {
int w, v;
bool operator<(const rec &X)const {
return w == X.w ? v < X.v : w < X.w;
}
} e[MAXN];
int t[MAXN];
namespace fastIO {
#define BUF_SIZE (1<<20)
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
inline char nc() {
if(p1 == pend) {
p1 = buf;
pend = buf + fread(buf, 1, BUF_SIZE, stdin);
}
return *p1++;
}
inline int read() {
int x = 0;
char s = nc();
for(; !isdigit(s); s = nc());
for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
return x;
}
}
using namespace fastIO;
struct BIT {
#define lowbit(x) (x&(-x))
int tr[MAXN];
inline void init() {
memset(tr, 0, sizeof(tr));
}
inline int qry(int x) {
int ret = 0;
for(; x; x -= lowbit(x))ret = max(ret, tr[x]);
return ret;
}
inline void mdf(int x, int V) {
for(; x <= MAXN; x += lowbit(x))tr[x] = max(tr[x], V);
}
} bt;
int Mx, f[MAXN];
inline void solve() {
int ans = 0;
int j = m + 1;
memset(f, 0, sizeof(f));
for(int i = n; i >= 1; --i) {
while(t[j - 1] >= e[i].w)--j;
f[i] = min(bt.qry(Mx - e[i].v + 1) + 1, m - j + 1);
bt.mdf(Mx - e[i].v + 1, f[i]);
ans = max(ans, f[i]);
}
printf("%d\n", ans);
return ;
}
inline int getid(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
inline void init() {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int i = 1; i <= n; ++i) {
e[i].w = getid(e[i].w);
e[i].v = getid(e[i].v);
Mx = max(e[i].v, Mx);
}
for(int i = 1; i <= m; ++i) {
t[i] = getid(t[i]);
}
return ;
}
int main() {
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
T = read();
while(T-- > 0) {
n = read();
for(int i = 1; i <= n; ++i) {
e[i].w = read();
e[i].v = read();
v.push_back(e[i].w);
v.push_back(e[i].v);
}
sort(e + 1, e + n + 1);
bt.init();
m = read();
for(int i = 1; i <= m; ++i) {
t[i] = read();
v.push_back(t[i]);
}
sort(t + 1, t + m + 1);
init();
solve();
}
return 0;
}
/*
2
4
1 2
2 3
5 4
3 1
4
1 10 5 1
4
1 2
2 3
5 4
10 5
5
1 2 3 4 5
*/
E
下面注释已经说得很详细了
思路其实就是枚举一个量,确定两个相等量
然后要发现一定有一个块是一个子树这个性质!
//考虑树上分类讨论???
//正如他所说,一定有一个连通块是原树的一颗子树
//那么我们就可以从此入手,找到答案??
//如果siz x = A
//我们考虑另一个和他相等的连通块...
//y是他的祖先就是2sizx或者是哪个C就是n-sizx
//y不是他的祖先就是sizx或者C - > n-2sizx
//siz x = C
//也就是说A要偷掉C后/2相同!A=(n-sizx)/2
//显然y是x祖先就要加上sizx
//否则直接判断...
//最后所有可行的答案取max即可!
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 4e6 + 7;
int n, ccnt, home[MAXN], nxt[MAXN], to[MAXN], ans;
inline void ct(int x, int y) {
ccnt++;
nxt[ccnt] = home[x];
home[x] = ccnt;
to[ccnt] = y;
}
int siz[MAXN], mp1[MAXN], mp2[MAXN];
inline void dfs1(int u, int F) {
siz[u] = 1;
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(v == F)continue;
dfs1(v, u);
siz[u] += siz[v];
}
mp1[siz[u]]++;
return ;
}
inline void dfs2(int u, int F) {
mp1[siz[u]]--;
if(mp2[2 * siz[u]] || mp2[n - siz[u]]) {
if(n == 2 * siz[u])ans = max(ans, siz[u] - 1);
else ans = max(ans, siz[u]);
}
if(mp1[siz[u]] || (n - 2 * siz[u] > 0 && mp1[n - 2 * siz[u]])) {
if(n == 2 * siz[u])
ans = max(ans, siz[u] - 1);
else ans = max(ans, siz[u]);
}
if(!((n - siz[u]) & 1) && mp1[(n - siz[u]) / 2]) {
ans = max(ans, (n - siz[u]) / 2);
}
if(!((n + siz[u]) & 1) && mp2[(n + siz[u]) / 2]) {
ans = max(ans, (n - siz[u]) / 2);
}
mp2[siz[u]]++;
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(v == F)continue;
dfs2(v, u);
}
mp2[siz[u]]--;
mp1[siz[u]]++;
return ;
}
int main() {
scanf("%d", &n);
for(int i = 1, x, y; i < n; ++i) {
scanf("%d%d", &x, &y);
ct(x, y);
ct(y, x);
}
dfs1(1, 0);//get 所有树siz
dfs2(1, 0);//get ans
printf("%d\n", ans);
return 0;
}
/*
8
1 2
2 3
3 4
1 8
1 5
5 6
5 7
8
2 1
3 2
4 2
5 1
6 3
7 4
8 1
*/
D
问题实质上就是我们给每个蚂蚁硬点一个到达时间,然后满足每个到达时间>=每只蚂蚁的深度...
这个问题好像就能暴力做了
实现方法是我们开一个栈,用深度为i的蚂蚁有多少个
然后我们枚举一个i,每次弹出一只蚂蚁,并且加入个蚂蚁
然后我们知道所有蚂蚁都有编号最大一个就是答案qwq
这个怎么维护呢?维护这个栈每时每刻的剩余蚂蚁数!
做法1
加入一个蚂蚁,相当于一个区间+,直到后面一个连续两个0的位置
删除一个蚂蚁,相当于一个区间-,直到后面一个0的位置
上述加减左端点都是
最后查询最后一个有值的数的位置就好了
第一个连续两个0的维护可以用另一棵树,每个位置记录和是否都为0
要线段树二分QAQ
做法2
会发现,上述做法其实本质很...啊??
用线段树维护一个表示cnt的后缀和
然后答案就是
因为你想如果我们对于i,在前面放了过多的数,这个i一定无法成为答案
而如果在后面放了过多的数,这个i才可能成为答案
只有在那些连续0的时候才会真正增大
所以这个全局max一定能找到答案....
服了