[LibreOJ 2472][九省联考2018]IIIDX
一直没有填的坑……今天乱写了写跑过了然后厚颜无耻凑一篇题解
还有样例过于草（出题人钦点淫梦运营）
考虑从小到大枚举序列的每一位置\(p\)，然后我们发现每一位置的值的合法性事单调的（小的合法，大了就不合法），这样可以对每一个位置二分答案。
然后我们考虑二分完了答案\(x\)怎么判定。把值离散化一下然后用一个线段树来维护\(T_i\)（表示当前还没有被预定的大于等于\(i\)的数有多少个），然后判定答案就看到\(x\)的前缀区间是否都不小于\(p\)所在子树的大小。同时注意顺次枚举每个点的时候要去除他对他父亲的影响，然后每次一个点确定是什么值了也要修改对应的前缀区间。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
using R = long double;
const int maxn = 500005;
const int maxno = maxn << 2;
int n; R k;
int minv[maxno], addv[maxno];
void maintain(int o) {
int lc = o << 1, rc = o << 1 | 1;
minv[o] = std::min(minv[lc], minv[rc]);
}
void paint(int o, int v) {
addv[o] += v; minv[o] += v;
}
void pushdown(int o) {
if(addv[o] != 0) {
int lc = o << 1, rc = o << 1 | 1;
paint(lc, addv[o]); paint(rc, addv[o]);
addv[o] = 0;
}
}
int left[maxn];
void build_tree(int o, int L, int R) {
// addv[o] = 0;
if(L == R) {
minv[o] = left[L];
} else {
int M = (L + R) / 2;
build_tree(o << 1, L, M);
build_tree(o << 1 | 1, M + 1, R);
maintain(o);
}
}
void update(int o, int L, int R, int ql, int qr, int v) {
if(ql <= L && R <= qr) {
paint(o, v);
} else {
pushdown(o);
int M = (L + R) / 2;
if(ql <= M) update(o << 1, L, M, ql, qr, v);
if(qr > M) update(o << 1 | 1, M + 1, R, ql, qr, v);
maintain(o);
}
}
const int INF = 0x7f7f7f7f;
int query_min(int o, int L, int R, int ql, int qr) {
if(ql <= L && R <= qr) {
return minv[o];
} else {
pushdown(o);
int M = (L + R) / 2, ans = INF;
if(ql <= M) ans = std::min(ans, query_min(o << 1, L, M, ql, qr));
if(qr > M) ans = std::min(ans, query_min(o << 1 | 1, M + 1, R, ql, qr));
return ans;
}
}
int d[maxn], d2[maxn];
int lsiz;
void process() {
std::sort(d + 1, d + 1 + n);
std::sort(d2 + 1, d2 + 1 + n);
lsiz = std::unique(d2 + 1, d2 + 1 + n) - d2 - 1;
for(int i = 1; i <= n; i ++) {
d[i] = std::lower_bound(d2 + 1, d2 + 1 + lsiz, d[i]) - d2;
left[d[i]] ++;
}
for(int i = lsiz - 1; i >= 1; i --) {
left[i] += left[i + 1];
}
build_tree(1, 1, lsiz);
}
int A[maxn], siz[maxn];
void solve() {
for(int i = n; i >= 1; i --) {
siz[i] ++;
int f = (int)floor((R(i)) / k);
siz[f] += siz[i];
}
for(int i = 1; i <= n; i ++) {
int f = (int)floor((R(i)) / k);
if(f > 0) {
update(1, 1, lsiz, 1, A[f], siz[i]);
}
int L = (f == 0) ? 1 : A[f], R = lsiz, ret;
while(true) {
if(R - L <= 3) {
for(int j = R; j >= L; j --) {
if(query_min(1, 1, lsiz, 1, j) >= siz[i]) {
ret = j; break;
}
}
break;
}
int M = L + (R - L) / 2;
if(query_min(1, 1, lsiz, 1, M) >= siz[i]) {
L = M;
} else {
R = M;
}
}
A[i] = ret; update(1, 1, lsiz, 1, ret, -siz[i]);
}
}
int main() {
scanf("%d%Lf", &n, &k);
for(int i = 1; i <= n; i ++) {
scanf("%d", &d[i]); d2[i] = d[i];
}
process(); solve();
for(int i = 1; i <= n; i ++) {
if(i > 1) putchar(' ');
printf("%d", d2[A[i]]);
}
puts(""); return 0;
}
[BZOJ 2653]middle
前几天想用Github+org-mode替代这个博客，后来想了想，还是算了吧。毕竟博客对大家更方便。
这个题真不愧是陈老师的题啊……exciting！
首先我们看到左端点在[tex][a,b][/tex]，右端点在[tex][c,d][/tex]，一股GSS5的气味扑来？
为了方便，我们先将序列离散化。然后我们将序列中大于等于x的值变为1，小于x的值变为-1，则某段区间的区间和若大于等于0，则该区间的中位数大于等于x，反之则其中位数小于x（注意，此题的中位数定义比较奇怪）。
然后我们可以对每个x建一棵树，然后二分答案，对于每个答案在对应的树上跑一遍GSS5即可（不过这题[tex]a<b<c<d[/tex]，所以不需要复杂的分类讨论）。
但是如果每个x都建一棵树，肯定会MLE吧？这个时候就要用主席树了= =
代码：
/**************************************************************
Problem: 2653
User: danihao123
Language: C++
Result: Accepted
Time:2220 ms
Memory:1956 kb
****************************************************************/
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=20005;
struct Node{
Node *lc,*rc;
int maxPSum,maxSSum,sum;
Node(int x){
lc=rc=NULL;
maxPSum=maxSSum=sum=x;
}
Node(Node *l,Node *r){
lc=l;rc=r;
}
void maintain(){
maxPSum=max(lc->maxPSum,lc->sum+rc->maxPSum);
maxSSum=max(rc->maxSSum,rc->sum+lc->maxSSum);
sum=lc->sum+rc->sum;
}
};
Node* build_tree(int L,int R){
if(L==R){
return new Node(1);
}
int M=L+(R-L)/2;
Node *ans=new Node(build_tree(L,M),build_tree(M+1,R));
ans->maintain();
return ans;
}
int p,v;
Node* insert(Node *o,int L,int R){
if(L==R){
return new Node(v);
}else{
Node *ans=new Node(o->lc,o->rc);
int M=L+(R-L)/2;
if(p<=M){
ans->lc=insert(ans->lc,L,M);
}else{
ans->rc=insert(ans->rc,M+1,R);
}
ans->maintain();
return ans;
}
}
int ql,qr;
Node queryPSum(Node *o,int L,int R){
if(ql<=L && R<=qr){
return *o;
}else{
int M=L+(R-L)/2;
if(qr<=M){
return queryPSum(o->lc,L,M);
}else{
if(ql<=M){
Node l=queryPSum(o->lc,L,M);
Node r=queryPSum(o->rc,M+1,R);
Node ans(l.sum+r.sum);
ans.maxPSum=max(l.maxPSum,l.sum+r.maxPSum);
return ans;
}else{
return queryPSum(o->rc,M+1,R);
}
}
}
}
Node querySSum(Node *o,int L,int R){
if(ql<=L && R<=qr){
return *o;
}else{
int M=L+(R-L)/2;
if(qr<=M){
return querySSum(o->lc,L,M);
}else{
if(ql<=M){
Node l=querySSum(o->lc,L,M);
Node r=querySSum(o->rc,M+1,R);
Node ans(l.sum+r.sum);
ans.maxSSum=max(r.maxSSum,r.sum+l.maxSSum);
return ans;
}else{
return querySSum(o->rc,M+1,R);
}
}
}
}
int querySum(Node *o,int L,int R){
if(ql<=L && R<=qr){
return o->sum;
}else{
int M=L+(R-L)/2;
int ans=0;
if(ql<=M){
ans+=querySum(o->lc,L,M);
}
if(qr>M){
ans+=querySum(o->rc,M+1,R);
}
return ans;
}
}
Node *root[maxn];
int n;
int A[maxn],A2[maxn];
vector<int> V[maxn];
int lsh_siz;
inline void lsh(){
sort(A2+1,A2+1+n);
lsh_siz=unique(A2+1,A2+1+n)-A2-1;
for(register int i=1;i<=n;i++){
A[i]=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
V[A[i]].push_back(i);
}
}
int q[4];
inline bool Check(int M){
register int l,m,r;
if(q[1]+1<=q[2]-1){
ql=q[1]+1;
qr=q[2]-1;
m=querySum(root[M],1,lsh_siz);
}else{
m=0;
}
ql=q[0];qr=q[1];
l=querySSum(root[M],1,lsh_siz).maxSSum;
ql=q[2];qr=q[3];
r=queryPSum(root[M],1,lsh_siz).maxPSum;
#ifdef DEBUG
printf("Case %d: %d %d %d\n",M,l,m,r);
#endif
return l+m+r>=0;
}
int main(){
register int i,j,L,M,R,ans=0;
int t;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&A[i]);
A2[i]=A[i];
}
lsh();
root[1]=build_tree(1,n);
for(i=2;i<=lsh_siz;i++){
root[i]=root[i-1];
for(j=0;j<V[i-1].size();j++){
p=V[i-1][j];
v=-1;
root[i]=insert(root[i],1,lsh_siz);
}
}
scanf("%d",&t);
while(t--){
for(i=0;i<4;i++){
scanf("%d",&q[i]);
q[i]=(q[i]+ans)%n;
}
sort(q,q+4);
for(i=0;i<4;i++){
q[i]++;
#ifdef DEBUG
printf("%d ",q[i]);
if(i==3){
puts("");
}
#endif
}
L=1;R=lsh_siz;
while(true){
if(R-L<=3){
for(i=R;i>=L;i--){
if(Check(i)){
ans=A2[i];
break;
}
}
break;
}
M=L+(R-L)/2;
if(Check(M)){
L=M;
}else{
R=M;
}
}
printf("%d\n",ans);
}
return 0;
}
[CodeVS 1217]借教室
很容易想到线段树水过。
很可惜，这样估计也就70分。
然后这个问题是符合单调性的……可以二分答案哒。不过怎么判定？
不知道诸位还记得差分序列？记得就好，用差分序列的方法维护即可。
等等，我怎么感觉你这个做法是[tex]O(nlogn)[/tex]的，能过？
推荐一个行之有效的优化：注意一下每一次修改都是在之前的基础上反悔或前进几次，所以就可以直接在原基础上修改差分序列辣~这样效率是很高滴~
代码：
#include <cstdio>
const int maxn=1e6+5;
typedef long long ll;
ll A[maxn];
int l[maxn],r[maxn];
ll d[maxn];
ll C[maxn];
int n,m,last=0;
bool Check(int x){
register int i,cnt=0;
if(x>last)
for(i=last+1;i<=x;i++){
C[l[i]]+=d[i];
C[r[i]+1]-=d[i];
}
if(x<last)
for(i=x+1;i<=last;i++){
C[l[i]]-=d[i];
C[r[i]+1]+=d[i];
}
last=x;
for(i=1;i<=n;i++){
cnt+=C[i];
if(cnt>A[i])
return false;
}
return true;
}
int main(){
register int i,L,M,R;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%lld",&A[i]);
}
for(i=1;i<=m;i++){
scanf("%lld%d%d",&d[i],&l[i],&r[i]);
}
L=1;
R=m+1;
while(L<R){
M=L+(R-L)/2;
if(Check(M)){
L=M+1;
}else{
R=M;
}
}
if(L==m+1)
puts("0");
else
printf("-1\n%d\n",L);
return 0;
}
[POJ 2455]Secret Milking Machine
这个题要求最大边最小，很明显要二分答案。
考虑验证谓词[tex]C(x)[/tex]。我们可以将所有边权小于等于[tex]x[/tex]的边加入图，然后判断是否有[tex]T[/tex]条从1到N的不重复路径。
不过这个怎么做呢？我们可以把边加入（注意我们要加入的边都是无向边），并把容量设为1，从1到N跑一遍最大流，就是不重复路径条数。
为什么可以这样呢？每个边容量只有1，最多只能让一条路径使用并“推送”到终点，所以从1到N的最大流就是不重复路径条数辣。
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=205,maxp=40005;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
namespace Dinic{
struct Edge{
int u,v,cap,flow;
};
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
inline void ClearGraph(){
register int i;
edges.clear();
m=0;
REP(i,maxn){
G[i].clear();
}
}
bool vis[maxn];
int d[maxn],cur[maxn];
int s,t;
inline bool BFS(){
register int i,u;
queue<int> Q;
CL_ARR(vis,0);
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
REP(i,G[u].size()){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
vis[e.v]=1;
d[e.v]=d[u]+1;
Q.push(e.v);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t || a==0)
return a;
int flow=0,temp;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[e.v]==d[x]+1){
temp=DFS(e.v,min(a,e.cap-e.flow));
if(temp>0){
e.flow+=temp;
edges[G[x][i]^1].flow-=temp;
flow+=temp;
a-=temp;
if(a==0)
break;
}
}
}
return flow;
}
inline int Maxflow(int S,int T){
s=S;
t=T;
register int ans=0;
while(BFS()){
CL_ARR(cur,0);
ans+=DFS(s,0x7f7f7f7f);
}
return ans;
}
};
struct Edge{
int u,v,d;
bool operator <(const Edge& x) const{
return d<x.d;
}
};
Edge EdgePool[maxp];
int n,p,t;
inline bool Check(int x){
register int i;
Dinic::ClearGraph();
REP_B(i,p){
if(EdgePool[i].d>x)
break;
Dinic::AddEdge(EdgePool[i].u,EdgePool[i].v,1);
Dinic::AddEdge(EdgePool[i].v,EdgePool[i].u,1);
}
if((Dinic::Maxflow(1,n))<t)
return false;
else
return true;
}
int main(){
register int i,L=0,M,R=0;
scanf("%d%d%d",&n,&p,&t);
REP_B(i,p){
scanf("%d%d%d",&EdgePool[i].u,&EdgePool[i].v,&EdgePool[i].d);
R=max(R,EdgePool[i].d+1);
}
sort(EdgePool+1,EdgePool+1+p);
while(L<R){
M=L+(R-L)/2;
if(Check(M))
R=M;
else
L=M+1;
}
printf("%d\n",L);
return 0;
}
[BZOJ 1196]公路修建问题
挺简单的二分答案题……然而到现在才A
思路很明显，直接二分最终答案。那么判定如何做呢？
假设判定谓词为[tex]C(x)[/tex]，那么我们首先考虑选白边。贪心加入边权小于[tex]x[/tex]的边（当然是否有必要就要用并查集判定了。并且这样就算加的超过了[tex]k[/tex]条也不会对答案造成影响）。然后白边加的不够[tex]k[/tex]谓词就是假了。
然后再考虑黑边，接下来的事情就很简单了。
代码：
/**************************************************************
Problem: 1196
User: danihao123
Language: C++
Result: Accepted
Time:672 ms
Memory:1212 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define RAP(i,n) for(i=1;i<=(n);i++)
const int maxn=10001,maxm=20001;
struct Edge{
int u,v,d1,d2;
};
bool cmp1(const Edge& x,const Edge& y){
return x.d1<y.d1;
}
bool cmp2(const Edge& x,const Edge& y){
return x.d2<y.d2;
}
int n;
int p[maxn],rank[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
inline void link_set(int x,int y){
if(rank[x]>rank[y]){
p[y]=x;
}else{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
inline void union_set(int x,int y){
link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
return find_set(x)==find_set(y);
}
inline void init_set(){
register int i;
for(i=1;i<=n;i++)
p[i]=i;
memset(rank,0,sizeof(rank));
}
int k,m;
Edge E[maxm];
inline bool check(int x){
register int i,first_cnt=0,cnt=0;
init_set();
sort(E,E+m,cmp1);
REP(i,m){
if(E[i].d1>x){
break;
}else{
if(!is_same(E[i].u,E[i].v)){
first_cnt++;
cnt++;
union_set(E[i].u,E[i].v);
}
}
if(cnt==n-1){
return true;
}
}
if(first_cnt<k)
return false;
sort(E,E+m,cmp2);
REP(i,m){
if(E[i].d2>x){
break;
}else{
if(!is_same(E[i].u,E[i].v)){
cnt++;
union_set(E[i].u,E[i].v);
}
}
if(cnt==n-1)
return true;
}
return false;
}
int main(){
register int i,L=1,M,R=0;
scanf("%d%d%d",&n,&k,&m);
m--;
REP(i,m){
scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].d1,&E[i].d2);
R=max(R,E[i].d1);
}
R++;
while(L<R){
M=L+(R-L)/2;
if(check(M))
R=M;
else
L=M+1;
}
printf("%d\n",L);
return 0;
}
[BZOJ 4326]运输计划
很容易想到树剖直接搞一发的玩法。估计复杂度是[tex]O(nlog^2n)[/tex]的，有点吃不消，再加上会被卡常，咔嚓掉。
考虑二分答案。我们可以直接二分最终答案，那么如何验证？
假设验证谓词为[tex]C(t)[/tex]，表示通过把一条边清零可以使得用时为[tex]t[/tex]。那么所有用时大于[tex]t[/tex]的计划都要被清掉一条边。可见我们需要清零的边是所有用时大于[tex]t[/tex]的计划的边的交集中的最大边。
那么如何求交集呢？可以考虑树上差分，对于每次计划[tex](u,v)[/tex]，我们求出其最近公共祖先[tex]L[/tex]，然后对[tex]d[u][/tex]和[tex]d[v][/tex]分别加一，对[tex]d[L][/tex]则减二。随后将d上标记上推，可以求出每个点连向父亲的边被几个计划经过。易求交集。
至此方向已明确：二分答案，树上差分验证，同时我们还要用到LCA。LCA建议使用总计[tex]O(n)[/tex]的TarjanLCA离线算法，倍增也可。
代码：
/**************************************************************
Problem: 4326
User: danihao123
Language: C++
Result: Accepted
Time:4756 ms
Memory:62188 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=300001,maxm=300001*2;
const int BUFSIZE=10000001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
int n;
namespace FastIO{
char buf[BUFSIZE];
int IO_tot=0;
inline void InitFastIO(){
fread(buf,sizeof(char),BUFSIZE-1,stdin);
}
inline char GetC(){
return buf[IO_tot++];
}
inline int readint(){
register int x=0;
register char c=GetC();
while(!isdigit(c))
c=GetC();
while(isdigit(c)){
x=10*x+c-'0';
c=GetC();
}
return x;
}
int bf[10];
inline void putint(int x){
register int siz=0,i;
if(!x){
bf[siz++]=0;
}else{
while(x){
bf[siz++]=x%10;
x/=10;
}
}
for(i=siz-1;i>=0;i--)
putchar(bf[i]+'0');
putchar('\n');
}
};
namespace Tree{
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int tot=0;
inline void Add_Edge(int u,int v,int d){
tot++;
next[tot]=first[u];
first[u]=tot;
to[tot]=v;
dist[tot]=d;
}
int d[maxn],father[maxn];
vector<int> hx;
void dfs_1(int x,int fa,int dis){
d[x]=dis;
father[x]=fa;
int i;
GRAPH_REP(i,x){
if(to[i]!=fa)
dfs_1(to[i],x,dis+dist[i]);
}
hx.push_back(x);
}
int lazy[maxn];
inline void ClearLazy(){
memset(lazy,0,sizeof(lazy));
}
inline int DealCheck(int x){
register int i,v,ans=0;
REP_B(i,n){
v=hx[i-1];
lazy[father[v]]+=lazy[v];
}
REP_B(i,n){
if(lazy[i]==x){
ans=max(ans,d[i]-d[father[i]]);
}
}
return ans;
}
// Djoin Set
int p[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
inline void union_set(int x,int y){
p[find_set(y)]=find_set(x);
}
inline void make_set(int x){
p[x]=x;
}
// LCA
struct Query{
int u,v,b;
};
bool vis[maxn];
vector<Query> qs;
vector<int> querys[maxn];
inline void Add_Query(int x,int y,int b){
querys[x].push_back(qs.size());
qs.push_back((Query){x,y,b});
}
int res[maxn][3];
int n;
void LCA(int u){
make_set(u);
vis[u]=true;
int i,temp;
REP(i,querys[u].size()){
Query& tep=qs[querys[u][i]];
if(vis[tep.v])
res[tep.b][2]=find_set(tep.v);
}
for(i=first[u];i;i=next[i]){
temp=to[i];
if(!vis[temp]){
LCA(temp);
union_set(u,temp);
}
}
}
};
using namespace FastIO;
struct Deal{
int u,v,lca,d;
bool operator <(const Deal& x) const{
return d<x.d;
}
};
vector<Deal> V;
int m;
inline bool Check(int x){
register int i,ideal=0,yh=V[m-1].d;
Tree::ClearLazy();
for(i=m-1;i>=0;i--){
int& u=V[i].u,v=V[i].v,lca=V[i].lca,d=V[i].d;
if(d>x){
ideal++;
Tree::lazy[u]++;
Tree::lazy[v]++;
Tree::lazy[lca]-=2;
}else{
break;
}
}
yh-=Tree::DealCheck(ideal);
return yh<=x;
}
int main(){
register int i,u,v,lca,d;
FastIO::InitFastIO();
n=readint();
m=readint();
REP(i,n-1){
u=readint();
v=readint();
d=readint();
Tree::Add_Edge(u,v,d);
Tree::Add_Edge(v,u,d);
}
REP(i,m){
u=readint();
v=readint();
Tree::Add_Query(u,v,i);
Tree::Add_Query(v,u,i);
Tree::res[i][0]=u;
Tree::res[i][1]=v;
}
Tree::dfs_1(1,0,0);
Tree::LCA(1);
REP(i,m){
u=Tree::res[i][0];
v=Tree::res[i][1];
lca=Tree::res[i][2];
d=Tree::d[u]+Tree::d[v]-2*Tree::d[lca];
V.push_back((Deal){u,v,lca,d});
}
sort(V.begin(),V.end());
u=0;
v=V[m-1].d+1;
while(u<v){
d=u+(v-u)/2;
if(Check(d))
v=d;
else
u=d+1;
}
putint(u);
return 0;
}
