有生之年系列之POI 2014 (12/17)
某人说xj的大神们都喜欢开这样的坑，于是非得怂恿我开这么一个坑。
最近为了提高能力，所以已经下定决心尽量不看题解（本来是打算说绝不看题解的，但是我好像做不到的样子），做题的速度慢到爆，感觉开了坑之后有生之年恐怕是难以填完了。
Stage I
Salad bar
将p当成1，j当成-1，然后单调队列求出每个位置往左往右第一个前缀和小于该位置的地方记为l[i]和r[i]，接着对每个位置查询[i,r[i]]之间最大的一个x满足l[x]<=i，那么x-i+1就是满足要求的序列，我用单调队列+二分求解。
Hotels
这题暴力就行，开始以为暴力是[tex]O(n^3)[/tex]，后来才发现暴力就是[tex]O(n^2)[/tex]的，证明写起来麻烦就不给出来了。
Bricks
贪心，假如只有一个端点限定或者干脆没有左右端点的话，我们可以从左到右填，对于每个位置i填下符合要求的且剩余次数最多的一个数x，用堆维护一下就行了。有了左右端点的话，就将相应点的次数减掉，再用同样的方法从左到右填，如果倒数第二位和最后一位的颜色一样，看看能否讲倒数第二位和倒数第三位调换，否则无解。另外，还有一些情况需要特判，具体的看我的程序好了。
Couriers
特殊版本的区间众数，开始想到用主席树搞，因为脑子突然出了点问题，感觉主席树又不能搞，就用莫队搞，结果有两个点超时。后来还是听从Claris的建议用主席树搞，对于每次查询，往出现次数多的方向走，最后看看符合不符合要求，要注意的是，用这种方法求区间众数的话是会出问题的，但这道题实际上已经转化成了求区间中位数，所以可以用主席树搞。
Snake
不会搞，似乎全世界还没有人AC的样子，估计只能等题解出来了再搞了。
Stage II
Cards
线段树，对于每个结点都维护一个f数组，f[x][0][0]表示结点x左端的位置选小的那个，右端也选小的那个是否可能，剩下的还有三种情况，就不赘述了。交换两个点就等于修改两个点，每个非叶结点都等于其两个子结点合并一下。据Claris说我的程序在BZOJ上可能会被卡，但是我没有权限，无法在BZOJ上提交，也不知道是否真是这样。
Criminals
这道题其实是一道很水的题目，应该算是Noip难度的，但是我坑了很久没有坑出来，直到最近打算把这题坑出来，于是向Claris请教了一下他的做法，发现和我的想法几乎是一模一样的！然而，我稍稍YY了一下，感觉是可以卡的。经过我的仔细研究之后，终于发现了问题所在——我TMD题目看错了！大致做法是这样的，预处理出如果一个位置是汇合的位置，那么左端起始位置大概是哪个区间，右端起始位置大概是哪个区间，只要用一个双向链表记录下各个颜色的上一次出现位置和下一次出现位置，在题目保证中间经过的房间的颜色均不相同的情况下，就可以$O(n)$求出这个东西了，之后再用类似莫队的搞法就可以$O(n)$做出这道题了。
Supercomputer
Little Bird
单调队列优化DP，因为做了已经比较久，转移方程都忘了，你们自己看我的程序吧。
Rally
跪PoPoQQQ，跪Gromah，跪Claris！果然是神思路题，但是觉得没有什么好讲的，大致就是增加源和汇，然后从源往每个点连一条边，从每个点往汇连一条边，再拓扑，求出每个点到源的距离和到汇的距离，那么一条边的边权就是其近源的点到源的距离+近汇的点到汇的距离，最后在拓扑一遍，用线段树维护边权就可以了，具体做法可以@PoPoQQQ。
Stage III
FarmCraft
类似于国王游戏的那种贪心，只不过是树上版本，深搜的时候求一下就行了。
Around the world
目前还不会做，据说是卡内存神题。
Ant colony
深搜+二分，先深搜预处理一下，接着再对每个点用二分求，同样是很久以前做的，具体看程序。
Tourism
听说也是神题，不会做。
Solar lamps
目前还不会做
Solar panels
数学题，枚举1到[tex]\sqrt{\max(b,d)}[/tex]，对于之间的每个数都判断一下是否可以成为答案。
Freight
目前还不会做
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1000010;
struct node{int l,r;}p[N];
char s[N];
int n,tot,l[N],r[N],f[N],v[N<<1],ans;
int Q[N],R;
bool cmp(const node &a,const node &b) {return a.r<b.r||(a.r==b.r&&a.l<b.l);}
int check(int a,int b,int x) {
int mid,t=a;
while (a<=b) {
mid=(a+b)>>1;
if (l[Q[mid]]<=x) a=(t=mid)+1;
else b=mid-1;
} return t;
}
int main() {
int i,j=0,tmp;
scanf("%d%s",&n,s+1);
f[0]=f[n+1]=1000000;
for (i=1;i<=n;i++) {
if (s[i]=='p') {
f[i]=f[i-1]-1;
l[i]=v[f[i]-1]+1;
} else if (s[i]=='j') {
f[i]=f[i-1]+1;
l[i]=n+1;
} v[f[i]]=i;
}
for (i=1000000-n;i<=1000000+n;i++) v[i]=n+1;
for (i=n;i;i--) {
if (s[i]=='p') {
f[i]=f[i+1]-1;
r[i]=v[f[i]-1]-1;
p[++tot].r=r[i];
p[tot].l=i;
} else if (s[i]=='j') {
f[i]=f[i+1]+1;
r[i]=0;
} v[f[i]]=i;
}
sort(p+1,p+1+tot,cmp);
for (i=1;i<=tot;i++) {
while (j<p[i].r) {
j++;
if (s[j]=='j') continue;
while (R&&l[Q[R]]>=l[j]) R--;
Q[++R]=j;
} tmp=check(1,R,p[i].l);
if (Q[tmp]-p[i].l+1>ans) ans=Q[tmp]-p[i].l+1;
} printf("%d\n",ans);
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=5010;
int n,ma;
int g[N],to[N<<1],nxt[N<<1],tot;
ll f[N][3],d[N],ans;
void Max(short &x,short y) {if (x<y) x=y;}
void addedge(int x,int y) {
to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
to[++tot]=x; nxt[tot]=g[y]; g[y]=tot;
}
void dfs(int x,int fat,int dep) {
d[dep]++; if (dep>ma) ma=dep;
for (int k=g[x];k;k=nxt[k]) {
if (to[k]==fat) continue;
dfs(to[k],x,dep+1);
}
}
int main() {
int i,k,x,y;
scanf("%d",&n);
for (i=1;i<n;i++) {
scanf("%d%d",&x,&y);
addedge(x,y);
}
for (x=1;x<=n;x++) {
memset(f,0,sizeof(f));
for (k=g[x];k;k=nxt[k]) {
ma=0;
memset(d,0,sizeof(d));
dfs(to[k],x,1);
for (i=1;i<=ma;i++) {
ans+=d[i]*f[i][1];
f[i][1]+=d[i]*f[i][0];
f[i][0]+=d[i];
}
}
} printf("%lld\n",ans);
return 0;
}
#include <cstdio>
#include <algorithm>
#include <queue>
#define mp make_pair
#define X first
#define Y second
using namespace std;
const int N=1000100;
priority_queue<pair<int,int> > q;
int n,k,st,ed,p[N],b[N];
bool ok;
void print(int n) {
for (int i=0;i<n;i++) printf("%d ",p[i]);
printf("%d\n",p[n]);
}
int main() {
int i,x,x1,x2,y1,y2;
scanf("%d%d%d",&k,&st,&ed);
for (i=1;i<=k;i++) {
scanf("%d",&b[i]);
n+=b[i];
} b[st]--; b[ed]--;
n--; p[0]=st; p[n]=ed;
if (!n) {
if (st!=ed) return puts("0"),0;
else return printf("%d\n",st),0;
}
for (i=1;i<=k;i++) if (b[i]>0) q.push(mp(b[i],i));
for (i=1;i<n;i++) {
x1=q.top().X;
y1=q.top().Y;
q.pop();
if (y1!=p[i-1]) {
p[i]=y1;
if (x1>1) q.push(mp(x1-1,y1));
} else {
if (q.empty()) return puts("0"),0;
x2=q.top().X;
y2=q.top().Y;
q.pop();
p[i]=y2;
q.push(mp(x1,y1));
if (x2>1) q.push(mp(x2-1,y2));
}
}
if (!q.empty()) return puts("0"),0;
if (p[n-1]!=p[n]) print(n);
else {
if (p[n-3]!=p[n-1]) {
swap(p[n-2],p[n-1]);
print(n);
} else return puts("0"),0;
}
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=500010;
const int M=10000100;
int n,m,head[N],len;
int l[M],r[M],f[M],ans,num;
int add(int i,int a,int b,int x) {
int t=++len,mid=(a+b)>>1;
f[t]=f[i]+1;
if (a==b) return t;
if (x<=mid) r[t]=r[i],l[t]=add(l[i],a,mid,x);
else l[t]=l[i],r[t]=add(r[i],mid+1,b,x);
return t;
}
void query(int x,int y,int a,int b) {
if (a==b) {
num=f[y]-f[x];
ans=a;
return;
} int mid=(a+b)>>1;
if (f[l[y]]-f[l[x]]<f[r[y]]-f[r[x]]) query(r[x],r[y],mid+1,b);
else query(l[x],l[y],a,mid);
}
int main() {
int i,x,y;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d",&x),head[i]=add(head[i-1],1,n,x);
for (i=1;i<=m;i++) {
scanf("%d%d",&x,&y);
query(head[x-1],head[y],1,n);
if ((num<<1)>y-x+1) printf("%d\n",ans);
else puts("0");
} return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=200010;
struct node{int x1,y1,x2,y2;}p[N<<2],tmp;
int n,m,w[N];
bool f[N<<2][2][2];
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void merge(int i,int x,int y) {
f[i][0][0]=f[i][0][1]=0;
f[i][1][0]=f[i][1][1]=0;
p[i].x1=p[i<<1].x1;
p[i].y1=p[i<<1].y1;
p[i].x2=p[i<<1|1].x2;
p[i].y2=p[i<<1|1].y2;
if (p[x].x2<=p[y].x1) {
if (f[x][0][0]&&f[y][0][0]) f[i][0][0]=1;
if (f[x][1][0]&&f[y][0][0]) f[i][1][0]=1;
if (f[x][0][0]&&f[y][0][1]) f[i][0][1]=1;
if (f[x][1][0]&&f[y][0][1]) f[i][1][1]=1;
}
if (p[x].x2<=p[y].y1) {
if (f[x][0][0]&&f[y][1][0]) f[i][0][0]=1;
if (f[x][1][0]&&f[y][1][0]) f[i][1][0]=1;
if (f[x][0][0]&&f[y][1][1]) f[i][0][1]=1;
if (f[x][1][0]&&f[y][1][1]) f[i][1][1]=1;
}
if (p[x].y2<=p[y].x1) {
if (f[x][0][1]&&f[y][0][0]) f[i][0][0]=1;
if (f[x][1][1]&&f[y][0][0]) f[i][1][0]=1;
if (f[x][0][1]&&f[y][0][1]) f[i][0][1]=1;
if (f[x][1][1]&&f[y][0][1]) f[i][1][1]=1;
}
if (p[x].y2<=p[y].y1) {
if (f[x][0][1]&&f[y][1][0]) f[i][0][0]=1;
if (f[x][1][1]&&f[y][1][0]) f[i][1][0]=1;
if (f[x][0][1]&&f[y][1][1]) f[i][0][1]=1;
if (f[x][1][1]&&f[y][1][1]) f[i][1][1]=1;
}
}
void build(int i,int l,int r) {
if (l==r) {
w[l]=i;
read(p[i].x1);
read(p[i].y1);
if (p[i].x1>p[i].y1) swap(p[i].x1,p[i].y1);
p[i].x2=p[i].x1;
p[i].y2=p[i].y1;
f[i][0][0]=f[i][1][1]=1;
return;
} int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
merge(i,i<<1,i<<1|1);
}
void change(int i,int l,int r,int x,node t) {
if (l==r) {
p[i]=t;
return;
} int mid=(l+r)>>1;
if (x<=mid) change(i<<1,l,mid,x,t);
else change(i<<1|1,mid+1,r,x,t);
merge(i,i<<1,i<<1|1);
}
int main() {
int i,x,y;
scanf("%d",&n);
build(1,1,n);
scanf("%d",&m);
for (i=1;i<=m;i++) {
scanf("%d%d",&x,&y); tmp=p[w[x]];
change(1,1,n,x,p[w[y]]);
change(1,1,n,y,tmp);
if (f[1][0][0]||f[1][0][1]||f[1][1][0]||f[1][1][1]) puts("TAK");
else puts("NIE");
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1000010;
int n,m,nl,nr,c[N],cl[N],cr[N];
int suc[N],pre[N],pos[N],l[N],r[N];
int f[N],fl[N],fr[N],ans[N],tot,num;
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
int main() {
read(n); read(m);
for (int i=1;i<=n;i++) read(c[i]),r[i]=n;
for (int i=1;i<=n;i++) pre[i]=f[c[i]],f[c[i]]=i;
for (int i=1;i<=m;i++) f[i]=n+1;
for (int i=n;i;i--) suc[i]=f[c[i]],f[c[i]]=i;
read(nl); read(nr);
for (int i=1;i<=nl;i++) read(cl[i]);
for (int i=1;i<=nr;i++) read(cr[i]);
for (int i=1,j=1;i<=nl;i++) {
while (c[j]!=cl[i]&&j<=n) j++;
if (j>n) return puts("0"),0;
pos[i]=j;
}
for (int i=nl-1;i;i--) while (suc[pos[i]]<pos[i+1]) pos[i]=suc[pos[i]];
for (int i=pos[nl];i<=n;i++) {
if (c[i]==cl[nl]) {
pos[nl]=i;
for (int j=nl-1;j;j--) {
if (suc[pos[j]]<pos[j+1]) {
while (suc[pos[j]]<pos[j+1]) pos[j]=suc[pos[j]];
} else break;
}
} l[i]=pos[1];
}
for (int i=1,j=n;i<=nr;i++) {
while (c[j]!=cr[i]&&j) j--;
if (j<1) return puts("0"),0;
pos[i]=j;
}
for (int i=nr-1;i;i--) while (pre[pos[i]]>pos[i+1]) pos[i]=pre[pos[i]];
for (int i=pos[nr];i;i--) {
if (c[i]==cr[nr]) {
pos[nr]=i;
for (int j=nr-1;j;j--) {
if (pre[pos[j]]>pos[j+1]) {
while (pre[pos[j]]>pos[j+1]) pos[j]=pre[pos[j]];
} else break;
}
} r[i]=pos[1];
} int indexl=1,indexr=r[1];
for (int i=n;i>r[1];i--) fr[c[i]]++;
for (int i=1;i<=n;i++) {
while (indexl<l[i]) {
int color=c[indexl++];
if (!fl[color]&&fr[color]) num++;
fl[color]++;
}
while (indexr<r[i]) {
int color=c[++indexr];
fr[color]--;
if (fl[color]&&!fr[color]) num--;
} if (num&&c[i]==cl[nl]) ans[++tot]=i;
} printf("%d\n",tot);
for (int i=1;i<=tot;i++) printf("%d ",ans[i]);
return 0;
}
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1000100;
int n,m,p[N];
int fa[N],f[N],d[N],ans[N];
int st[N],L,R,deep=1;
bool ok(int i,int j,int k) { return (ll)(f[k]-f[j])*(i-j)>=(ll)(f[j]-f[i])*(j-k);}
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
int main() {
int i,j;
read(n); read(m); f[d[1]=0]=deep=1;
for (i=1;i<=m;i++) read(p[i]);
for (i=2;i<=n;i++) {
read(fa[i]);
d[i]=d[fa[i]]+1; f[d[i]]++;
if (d[i]>=deep) deep=d[i]+1;
}
for (i=deep;~i;i--) f[i]=f[i]+f[i+1];
for (i=deep;~i;i--) {
while (R>1&&ok(st[R-1],st[R],i)) R--;
st[++R]=i;
}
for (L=1,i=n;i;i--) {
while (L<R&&(ll)i*(st[L]-st[L+1])<=f[st[L+1]]-f[st[L]]) L++;
if (f[st[L]]%i==0) ans[i]=st[L]+f[st[L]]/i;
else ans[i]=st[L]+f[st[L]]/i+1;
}
for (i=1;i<m;i++) if (p[i]>n) printf("%d ",deep);
else printf("%d ",ans[p[i]]);
if (p[i]>n) printf("%d\n",deep);
else printf("%d\n",ans[p[i]]);
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1000100;
int n,m,k,d[N],f[N];
int team[N],head,tail;
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void solve(int k) {
int i,j;
f[team[head=tail=0]=1]=0;
for (i=2;i<=n;i++) {
while (head<tail&&team[head]+k<i) head++;
if (d[team[head]]<=d[i]) f[i]=f[team[head]]+1;
else f[i]=f[team[head]];
while (head<=tail&&(f[team[tail]]>f[i]||(f[team[tail]]==f[i]&&d[team[tail]]<d[i]))) tail--;
team[++tail]=i;
} cout<<f[n]<<endl;
}
int main() {
int i;
for (read(n),i=1;i<=n;i++) read(d[i]);
for (read(m),i=1;i<=m;i++) read(k),solve(k);
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1000010;
int n,d[N],c[N],f[N],num[N];
int g[N],to[N],nxt[N],tot;
int s[N],cnt;
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void addedge(int x,int y) {
to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
to[++tot]=x; nxt[tot]=g[y]; g[y]=tot;
}
void Min(int &x,int y) {if (x>y) x=y;}
void Max(int &x,int y) {if (x<y) x=y;}
bool cmp(const int &a,const int &b) {return num[a]+f[b]<num[b]+f[a];}
void dfs(int x,int fat) {
int st=cnt+1,i,k,time=0;
for (k=g[x];k;k=nxt[k]) if (to[k]!=fat) {
dfs(to[k],x);
num[x]+=num[to[k]];
num[to[k]]=num[to[k]]<<1;
s[++cnt]=to[k];
}
if (st<=cnt) sort(s+st,s+cnt+1,cmp);
for (i=st;i<=cnt;i++) {
Max(f[x],time+f[s[i]]+1);
time+=num[s[i]];
} cnt=st-1; num[x]++;
Max(f[x],c[x]);
}
int main() {
int i,x,y; read(n);
for (i=1;i<=n;i++) read(c[i]);
for (i=1;i<n;i++) {
read(x); read(y);
addedge(x,y);
} dfs(1,0);
Max(f[1],(n-1)*2+c[1]);
cout<<f[1]<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
const int infi=2147483647;
const int P=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1000100;
int n,m,k,r1,r2,a[N],d[N];
int g[N],to[N<<1],nxt[N<<1],tot;
ll low[N],top[N],ans;
void read(int &a) {
char ch; while (!((ch=getchar())>='0'&&ch<='9'));
a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void addedge(int x,int y) {
to[++tot]=y; nxt[tot]=g[x]; g[x]=tot; d[x]++;
to[++tot]=x; nxt[tot]=g[y]; g[y]=tot; d[y]++;
}
void dfs(int x,int fat) {
ll t1=low[x]*(d[x]-1),t2=top[x]*(d[x]-1)+d[x]-2;
if (t1>a[m]) return;
for (int k=g[x];k;k=nxt[k]) {
if (to[k]==fat) continue;
low[to[k]]=t1;
top[to[k]]=t2;
dfs(to[k],x);
}
}
int ask(int l,int r,int x) {
int mid,t=0;
while (l<=r) {
mid=(l+r)>>1;
if (a[mid]<=x) l=(t=mid)+1;
else r=mid-1;
} return t;
}
int main() {
int i,x,y;
read(n); read(m); read(k);
for (i=1;i<=m;i++) read(a[i]);
sort(a+1,a+1+m);
read(r1); read(r2);
low[r1]=top[r1]=k; d[r1]++;
low[r2]=top[r2]=k; d[r2]++;
for (i=2;i<n;i++) {
read(x); read(y);
addedge(x,y);
} dfs(r1,0); dfs(r2,0);
for (i=1;i<=n;i++) if (d[i]==1&&low[i]) {
ans+=ask(1,m,top[i])*k;
ans-=ask(1,m,low[i]-1)*k;
} cout<<ans<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
const int infi=2147483647;
const int P=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
int T,a,b,c,d,i,j,ans,top;
int main() {
scanf("%d",&T);
while (T--) {
scanf("%d%d%d%d",&a,&b,&c,&d);
ans=0; a=a-1; c=c-1; top=max(b,d);
for (i=1;i*i<=top;i++) {
if (b/i>a/i&&d/i>c/i&&i>ans) ans=i;
j=b/i; if (b/j>a/j&&d/j>c/j&&j>ans) ans=j;
j=d/i; if (b/j>a/j&&d/j>c/j&&j>ans) ans=j;
} printf("%d\n",ans);
}
return 0;
}
评论 (0)
