[BZOJ 3531]旅行
发现自己好久没写树链剖分了……唉……
言归正传，这道题很容易想到的做法就是每种宗教开一个线段树，到各个宗教的线段树里面操作即可。
很可惜，直接开线段树的话肯定会MLE。我们可以考虑动态开点，对于不需要的点一律不开。这样内存消耗量就大减了。
注意一些细节：
- 查询时判断当前结点是不是NULL。
- 删除前最好判断一下这个结点是不是NULL吧，以防万一。
- 删除操作时，如果结点没有用了，就删。但是注意，记得delete前要把原指针设为NULL，直接delete会引起悬垂指针问题导致爆炸！
代码：
/**************************************************************
Problem: 3531
User: danihao123
Language: C++
Result: Accepted
Time:10404 ms
Memory:34872 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
int n;
namespace SegmentTree{
struct Node{
int sumv,maxv;
Node *lc,*rc;
Node(){
sumv=maxv=0;
lc=rc=NULL;
}
void maintain(){
if(lc!=NULL){
if(rc!=NULL){
sumv=lc->sumv+rc->sumv;
maxv=max(lc->maxv,rc->maxv);
}else{
sumv=lc->sumv;
maxv=lc->maxv;
}
}else{
if(rc!=NULL){
sumv=rc->sumv;
maxv=rc->maxv;
}
}
}
};
Node* T[maxn];
int p,v;
void _Delete(Node* &o,int L,int R){
if(o==NULL)
return;
if(L==R){
Node *temp=o;
o=NULL;
delete temp;
}else{
int M=L+(R-L)/2;
if(p<=M)
_Delete(o->lc,L,M);
else
_Delete(o->rc,M+1,R);
if(o->lc==NULL && o->rc==NULL){
Node *temp=o;
o=NULL;
delete temp;
}else{
o->maintain();
}
}
}
inline void Delete(int c,int pos){
p=pos;
_Delete(T[c],1,n);
}
void _Insert(Node* &o,int L,int R){
if(o==NULL)
o=new Node();
if(L==R){
o->sumv=o->maxv=v;
}else{
int M=L+(R-L)/2;
if(p<=M)
_Insert(o->lc,L,M);
else
_Insert(o->rc,M+1,R);
}
o->maintain();
}
inline void Insert(int c,int pos,int value){
p=pos;
v=value;
_Insert(T[c],1,n);
}
int ql,qr;
int _query_max(Node *o,int L,int R){
if(o==NULL)
return 0;
if(ql<=L && R<=qr)
return o->maxv;
int M=L+(R-L)/2,ans=0;
if(ql<=M)
ans=max(ans,_query_max(o->lc,L,M));
if(qr>M)
ans=max(ans,_query_max(o->rc,M+1,R));
return ans;
}
inline int query_max(int c,int l,int r){
ql=l;
qr=r;
return _query_max(T[c],1,n);
}
int _query_sum(Node *o,int L,int R){
if(o==NULL)
return 0;
if(ql<=L && R<=qr)
return o->sumv;
int M=L+(R-L)/2,ans=0;
if(ql<=M)
ans+=_query_sum(o->lc,L,M);
if(qr>M)
ans+=_query_sum(o->rc,M+1,R);
return ans;
}
inline int query_sum(int c,int l,int r){
ql=l;
qr=r;
return _query_sum(T[c],1,n);
}
};
#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])
int first[maxn];
int next[maxn*2],to[maxn*2];
int graph_tot=0;
inline void AddEdge(int u,int v){
graph_tot++;
next[graph_tot]=first[u];
first[u]=graph_tot;
to[graph_tot]=v;
}
int dep[maxn],fa[maxn],son[maxn],siz[maxn];
bool vis[maxn];
void dfs_1(int x,int father,int depth){
vis[x]=true;
fa[x]=father;
dep[x]=depth;
siz[x]=1;
int i,temp,max_siz=0;
GRAPH_REP(i,x){
temp=to[i];
if(!vis[temp]){
dfs_1(temp,x,depth+1);
siz[x]+=siz[temp];
if(siz[temp]>max_siz){
son[x]=temp;
max_siz=siz[temp];
}
}
}
}
int hld_cnt=0;
int rlg[maxn];
int d[maxn];
int tid[maxn],top[maxn];
void dfs_2(int x,int a){
vis[x]=true;
top[x]=a;
tid[x]=++hld_cnt;
SegmentTree::Insert(rlg[x],hld_cnt,d[x]);
if(son[x])
dfs_2(son[x],a);
else
return;
int i,temp;
GRAPH_REP(i,x){
temp=to[i];
if(!vis[temp]){
dfs_2(temp,temp);
}
}
}
int query_max(int c,int x,int y){
if(top[x]==top[y]){
if(tid[x]>tid[y])
swap(x,y);
return SegmentTree::query_max(c,tid[x],tid[y]);
}
if(dep[top[x]]<dep[top[y]])
swap(x,y);
return max(SegmentTree::query_max(c,tid[top[x]],tid[x]),query_max(c,fa[top[x]],y));
}
int query_sum(int c,int x,int y){
if(top[x]==top[y]){
if(tid[x]>tid[y])
swap(x,y);
return SegmentTree::query_sum(c,tid[x],tid[y]);
}
if(dep[top[x]]<dep[top[y]])
swap(x,y);
return SegmentTree::query_sum(c,tid[top[x]],tid[x])+query_sum(c,fa[top[x]],y);
}
inline void Replace(int pos,int direction){
int c=rlg[pos];
SegmentTree::Delete(c,tid[pos]);
SegmentTree::Insert(direction,tid[pos],d[pos]);
rlg[pos]=direction;
}
inline void Update(int pos,int v){
d[pos]=v;
SegmentTree::Insert(rlg[pos],tid[pos],v);
}
int main(){
register int i;
int q,u,v;
char buf[5];
scanf("%d%d",&n,&q);
REP_B(i,n){
scanf("%d%d",&d[i],&rlg[i]);
}
REP_B(i,n-1){
scanf("%d%d",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
dfs_1(1,0,1);
memset(vis,0,sizeof(vis));
dfs_2(1,1);
while(q--){
memset(buf,0,sizeof(buf));
scanf("%s%d%d",buf,&u,&v);
if(buf[0]=='C'){
if(buf[1]=='W'){
Update(u,v);
}else{
Replace(u,v);
}
}else{
if(buf[1]=='M'){
printf("%d\n",query_max(rlg[u],u,v));
}else{
printf("%d\n",query_sum(rlg[u],u,v));
}
}
}
return 0;
}
[BZOJ 2054]疯狂的馒头
秒，秒啊……
很容易想到线段树，但是在[tex]N=10^6,M=10^7[/tex]的情况下，线段树肯定会TLE。
考虑修改，我们可以发现真正影响一个馒头颜色的只是作用于此馒头上的最后一个操作。可以考虑倒序枚举操作，然后暴力修改。但是如此暴力修改的话可能覆盖了实际时间线较晚的操作……
考虑并查集！每个节点修改完后将其父亲改为下一个点，这样的话被修改的地方就可以轻松跳过了。
注意一个细节，第[tex]N[/tex]个馒头被染色后，其父亲会被修改为[tex]N+1[/tex]，所以说并查集实际上要开[tex]N+1[/tex]！
代码：
/**************************************************************
Problem: 2054
User: danihao123
Language: C++
Result: Accepted
Time:2476 ms
Memory:39796 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1000005;
int Color[maxn];
int P[maxn];
int n;
int find_set(int x){
if(P[x]==x)
return x;
else
return P[x]=find_set(P[x]);
}
inline void init_set(){
register int i;
for(i=1;i<=(n+1);i++)
P[i]=i;
}
int buf[20];
inline void PutInt(int x){
register int i,p=0;
if(x==0){
buf[p++]=0;
}else{
while(x){
buf[p++]=x%10;
x/=10;
}
}
for(i=p-1;i>=0;i--)
putchar(buf[i]+'0');
putchar('\n');
}
int main(){
int m,p,q;
register int i,j,l,r,k=0;
bool OK=false;
scanf("%d%d%d%d",&n,&m,&p,&q);
init_set();
for(i=m;i>=1;i--){
l=(((i%n)*(p%n))%n+q%n)%n+1;
r=(((i%n)*(q%n))%n+p%n)%n+1;
if(l>r)
swap(l,r);
for(j=find_set(l);j<=r;j=find_set(j)){
Color[j]=i;
P[j]=j+1;
k++;
if(k==n){
OK=true;
break;
}
}
if(OK)
break;
}
for(i=1;i<=n;i++)
PutInt(Color[i]);
return 0;
}
[POJ 1679]The Unique MST
又是一个上百行代码的题……
这个题要求判断MST的唯一性。我们可以通过求非严格的次小生成树，来判断MST的唯一性。
非严格的次小生成树就是枚举考虑将MST外的哪条边加入替换MST中的一条边。替换的方法是，求出MST中待加入边两端路径上最大边，删掉之后再把待加入边加进去。假如有一个非严格次小生成树权值和和MST一样，就说明MST不唯一。
代码：
#include <cstdio>
#include <cstring>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=105,maxm=10005;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int first[maxn];
int next[205],to[205],dist[205];
int graph_cnt=0;
inline void AddEdge(int u,int v,int d){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
dist[graph_cnt]=d;
}
inline void ClearGraph(){
CL_ARR(first,0);
CL_ARR(next,0);
CL_ARR(to,0);
CL_ARR(dist,0);
graph_cnt=0;
}
int anc[maxn][32],maxcost[maxn][32];
int dep[maxn];
void dfs(int x,int depth,int fa,int d){
int i;
dep[x]=depth;
anc[x][0]=fa;
maxcost[x][0]=d;
GRAPH_REP(i,x){
if(to[i]!=fa){
dfs(to[i],depth+1,x,dist[i]);
}
}
}
int n;
inline void process(){
register int i,j,a;
dfs(1,0,0,0);
for(j=1;(1<<j)<n;j++){
REP(i,n){
if(anc[i][j-1]!=-1){
a=anc[i][j-1];
anc[i][j]=anc[a][j-1];
maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]);
}
}
}
}
int query(int x,int y){
register int tmp,log,i,ans=-0x7fffffff;
if(dep[x]<dep[y])
swap(x,y);
for(log=1;(1<<log)<=dep[x];log++);
log--;
for(i=log;i>=0;i--)
if(dep[x]-(1<<log)>=dep[y]){
ans=max(ans,maxcost[x][i]);
x=anc[x][i];
}
if(x==y)
return ans;
for(i=log;i>=0;i--)
if(anc[x][i]!=-1 && anc[x][i]!=anc[y][i]){
ans=max(ans,maxcost[x][i]);
x=anc[x][i];
ans=max(ans,maxcost[y][i]);
y=anc[y][i];
}
ans=max(ans,maxcost[x][0]);
ans=max(ans,maxcost[y][0]);
return ans;
}
int p[maxn],rank[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
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;
REP(i,n)
p[i]=i;
CL_ARR(rank,0);
}
struct Edge{
int u,v,d;
bool operator <(const Edge& x) const{
return d<x.d;
}
};
#define ALL_FT(x) E[x].u,E[x].v
Edge E[maxm];
int m;
bitset<maxn> Choose;
int MST(){
register int i,ans=0,cnt=0;
ClearGraph();
init_set();
Choose.reset();
sort(E+1,E+1+m);
REP(i,m){
if(!is_same(ALL_FT(i))){
Choose[i]=true;
cnt++;
ans+=E[i].d;
union_set(ALL_FT(i));
AddEdge(ALL_FT(i),E[i].d);
AddEdge(E[i].v,E[i].u,E[i].d);
}
if(cnt==(n-1)){
break;
}
}
return ans;
}
int main(){
int T;
int u,v,d;
register int i,ans,temp;
bool OK;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
REP(i,m){
scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
}
ans=MST();
CL_ARR(anc,-1);
process();
OK=true;
REP(i,m){
if(!Choose[i]){
temp=query(ALL_FT(i));
if(temp==E[i].d){
OK=false;
puts("Not Unique!");
break;
}
}
}
if(OK)
printf("%d\n",ans);
}
return 0;
}
[BZOJ 3436]小K的农场
差分约束系统的可行性问题啊……
按照要求连边然后SPFA判负环即可。
代码：
/**************************************************************
Problem: 3436
User: danihao123
Language: C++
Result: Accepted
Time:9224 ms
Memory:1488 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=30005;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(i,x) memset(i,x,sizeof(i))
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
int n;
namespace Graph{
int first[maxn];
int next[maxm],to[maxm];
ll dist[maxm];
int tot=0;
inline void AddEdge(int u,int v,ll d){
tot++;
next[tot]=first[u];
first[u]=tot;
to[tot]=v;
dist[tot]=d;
}
bool inQueue[maxn];
ll d[maxn];
int cnt[maxn];
bool SPFA(){
register int i,u;
queue<int> Q;
REP(i,n){
inQueue[i]=true;
Q.push(i);
}
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
GRAPH_REP(i,u){
if(d[to[i]]>d[u]+dist[i]){
d[to[i]]=d[u]+dist[i];
if(!inQueue[to[i]]){
Q.push(to[i]);
inQueue[to[i]]=true;
if(++cnt[to[i]]>n)
return false;
}
}
}
}
return true;
}
};
int main(){
int m,opt,a,b,c;
register int i;
scanf("%d%d",&n,&m);
REP(i,m){
scanf("%d%d%d",&opt,&a,&b);
if(opt==1){
scanf("%d",&c);
Graph::AddEdge(a,b,-c);
}else{
if(opt==2){
scanf("%d",&c);
Graph::AddEdge(b,a,c);
}else{
Graph::AddEdge(a,b,0);
Graph::AddEdge(b,a,0);
}
}
}
if(Graph::SPFA())
puts("Yes");
else
puts("No");
return 0;
}
[BZOJ 2330]糖果
比较裸一些的差分约束系统题……话说好像第一次写SPFA最长路啊TAT
这个题1,3,5条件直接搞就可以。2,4条件要转化成有等于号的版本。
顺便说一些这题的坑点：
- 有一个点是一个十万个点的链。在从源点连的时候，如果正序连就会炸。倒着连就不会T。
- 有的点的2,4条件出现了[tex]a=b[/tex]的情况，要特判……
- 要开long long！
代码：
/**************************************************************
Problem: 2330
User: danihao123
Language: C++
Result: Accepted
Time:356 ms
Memory:7592 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CL_ARR(i,x) memset(i,x,sizeof(i))
const int maxn=100005,maxm=300005;
typedef long long ll;
int first[maxn];
int next[maxm],to[maxm];
ll dist[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v,ll d){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
dist[graph_cnt]=d;
}
int n;
bool inQueue[maxn];
ll d[maxn];
int cnt[maxn];
ll SPFA(){
register int i,u;
register ll ans=0;
queue<int> Q;
CL_ARR(d,-1);
d[0]=0;
Q.push(0);
inQueue[0]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
GRAPH_REP(i,u){
if(d[u]>-1 && d[to[i]]<d[u]+dist[i]){
d[to[i]]=d[u]+dist[i];
if(!inQueue[to[i]]){
Q.push(to[i]);
inQueue[to[i]]=true;
if((++cnt[to[i]])>(n+1))
return -1;
}
}
}
}
REP(i,n){
ans+=d[i];
}
return ans;
}
int main(){
register int i;
int opt,u,v;
int k;
scanf("%d%d",&n,&k);
REP(i,k){
scanf("%d%d%d",&opt,&u,&v);
if(opt==1){
AddEdge(u,v,0);
AddEdge(v,u,0);
}else{
if(opt==2){
if(u==v){
puts("-1");
return 0;
}
AddEdge(u,v,1);
}else{
if(opt==3){
AddEdge(v,u,0);
}else{
if(opt==4){
if(u==v){
puts("-1");
}
AddEdge(v,u,1);
}else{
AddEdge(u,v,0);
}
}
}
}
}
for(i=n;i>=1;i--){
AddEdge(0,i,1);
}
printf("%lld\n",SPFA());
return 0;
}
[CF 711D]Directed Roads
这个题啊……其实不难。
首先你注意，他告诉你你可以把边弄反。
其次注意，这个图不一定就有一个环。
然后每个环的取反法有[tex]2^x[/tex]种（假设环中有[tex]x[/tex]条边），但是空集不行，全集也不行，因此每个环爆掉的方案有[tex]2^x-2[/tex]种。然后环之外的边随便弄，乘法原理乱搞即可。
然后你是不是感觉这个题似曾相识？是的似乎这个题就是NOIP D1T2的翻版。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=200001;
const ll MOD=1000000007;
int G[maxn];
int in[maxn];
bool vis[maxn];
int n;
inline bool jianz(){
register int i;
bool ans=false;
for(i=1;i<=n;i++){
if(!vis[i] && !in[i]){
ans=true;
in[G[i]]--;
vis[i]=true;
G[i]=0;
}
}
return ans;
}
ll dfs(int x,int y){
if(x==y && vis[x]){
return 0;
}else{
vis[x]=true;
return dfs(G[x],y)+1;
}
}
ll pow_mod(ll a,ll b){
if(!b){
return 1;
}else{
ll ans=pow_mod(a,b/2);
ans=ans*ans%MOD;
if(1&b){
ans=(ans*(a%MOD))%MOD;
}
return ans;
}
}
inline ll solve(){
register int i;
register ll Huan,temp=0,ans=1;
while(jianz());
for(i=1;i<=n;i++)
if(!vis[i]){
Huan=dfs(i,i);
temp+=Huan;
ans=(ans*(pow_mod(2,Huan)+MOD-2))%MOD;
}
ans=(ans*pow_mod(2,n-temp))%MOD;
return ans;
}
int main(){
register int i;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&G[i]);
in[G[i]]++;
}
printf("%I64d\n",solve());
return 0;
}
[BZOJ 1013]球型空间产生器
不行不能颓了……线代其实刚起步……
注意每个点到球心的距离相同，距离之平方亦相同。然后假设所有半径平方为[tex]d[/tex]，那么我们先可以列出两个方程（假设[tex]n=2[/tex]，不过此时事实上可以列三个，但出于方便讨论的目的便只列两个）：
[tex](x_1-a_1)^2+(x_2-a_2)^2=d[/tex]
[tex](x_1-b_1)^2+(x_2-b_2)^2=d[/tex]
两方程作差，得：
[tex](x_1-a_1)^2+(x_2-a_2)^2-(x_1-b_1)^2-(x_2-b_2)^2=0[/tex]
整理，得：
[tex]2(b_1-a_1)x_1+2(b_2-a_2)x_2=(b_1+a_1)(b_1-a_1)+(b_2+a_2)(b_2-a_2)[/tex]
对这种方法加以推广，便可列出[tex]n[/tex]个[tex]n[/tex]元一次方程。高斯消元求解即可。
代码：
/**************************************************************
Problem: 1013
User: danihao123
Language: C++
Result: Accepted
Time:4 ms
Memory:1296 kb
****************************************************************/
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=20;
int n;
double M[maxn][maxn];
double A[maxn][maxn];
inline void Gause(){
register int i,j,k,r;
register double f;
for(i=1;i<=n;i++){
r=i;
for(j=i+1;j<=n;j++)
if(fabs(A[j][i])>fabs(A[r][i]))
r=j;
if(r!=i)
for(j=1;j<=(n+1);j++)
swap(A[r][j],A[i][j]);
for(k=i+1;k<=n;k++){
f=A[k][i]/A[i][i];
for(j=i;j<=n+1;j++)
A[k][j]-=f*A[i][j];
}
}
for(i=n;i>=1;i--){
for(j=i+1;j<=n;j++)
A[i][n+1]-=A[j][n+1]*A[i][j];
A[i][n+1]/=A[i][i];
}
}
int main(){
register int i,j;
bool flag=false;
cin>>n;
for(i=1;i<=(n+1);i++)
for(j=1;j<=n;j++)
cin>>M[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=(n+1);j++)
A[i][j]=0;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
A[i][j]=2*(M[i+1][j]-M[i][j]);
A[i][n+1]+=(M[i+1][j]-M[i][j])*(M[i+1][j]+M[i][j]);
}
}
Gause();
for(i=1;i<=n;i++){
if(flag)
putchar(' ');
flag=true;
printf("%.3f",A[i][n+1]);
}
putchar('\n');
return 0;
}
[BZOJ 1477]青蛙的约会
设用时为[tex]t[/tex]，则本题可视为解方程[tex](mt+x)-(nt+y)=kL[/tex]。
整理变形得[tex](n-m)t+Lk=x-y[/tex]。
明显需要扩欧求解。注意此题有很多细节，可参见下代码：
/**************************************************************
Problem: 1477
User: danihao123
Language: C++
Result: Accepted
Time:0 ms
Memory:1288 kb
****************************************************************/
#include <iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
if(!b)
return a;
else
return gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
if(!b){
d=a;
x=1;
y=0;
}else{
exgcd(b,a%b,d,x,y);
ll t=x;
x=y;
y=t-a/b*y;
}
}
int main(){
ll a,b,c,t,M,k;
ll x,y,m,n,L;
cin>>x>>y>>m>>n>>L;
a=n-m;
b=L;
c=x-y;
k=gcd(a,b);
if(c%k!=0){
cout<<"Impossible"<<endl;
return 0;
}
a/=k;
b/=k;
c/=k;
exgcd(a,b,k,t,M);
t=(((c*t)%b)+b)%b;
if(!t)
t+=b;
cout<<t<<endl;
return 0;
}
[BZOJ 3224]普通平衡树
很好，这很interesting。
最大坑点是数可能重复。然后前驱后驱赶脚也挺坑的……
还有好像BZOJ不滋磁time(0)哎。所以我就用了wyy的生日做随机数种子辣！
代码：
/**************************************************************
Problem: 3224
User: danihao123
Language: C++
Result: Accepted
Time:376 ms
Memory:1880 kb
****************************************************************/
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct Node{
Node *ch[2];
int v;
int r;
int s;
int cnt;
Node(){
v=s=cnt=0;
r=-1;
ch[0]=ch[1]=NULL;
}
Node(int key,Node *lc,Node *rc){
v=key;
r=rand();
s=1;
cnt=1;
ch[0]=lc;
ch[1]=rc;
}
void maintain(){
s=ch[0]->s+ch[1]->s+cnt;
}
};
struct Treap{
Node *null,*root;
Treap(){
null=new Node();
root=null;
}
void rotate(Node* &o,int d){
Node* k=o->ch[d^1];
o->ch[d^1]=k->ch[d];
k->ch[d]=o;
o->maintain();
k->maintain();
o=k;
}
void insert(Node* &o,int x){
if(o==null){
o=new Node(x,null,null);
}else{
if(o->v==x){
o->cnt++;
o->s++;
}else{
int d=x>(o->v);
insert(o->ch[d],x);
if(((o->ch[d])->r)>(o->r))
rotate(o,d^1);
}
}
o->maintain();
}
void del(Node* &o,int x){
if(o->v==x){
if(o->cnt>1){
o->cnt--;
o->s--;
}else{
if(o->ch[0]==null){
Node *u=o;
o=o->ch[1];
delete u;
}else{
if(o->ch[1]==null){
Node *u=o;
o=o->ch[0];
delete u;
}else{
int d=(o->ch[1]->r)>(o->ch[0]->r);
rotate(o,d^1);
del(o->ch[d^1],x);
}
}
}
}else{
int d=x>(o->v);
del(o->ch[d],x);
}
if(o!=null)
o->maintain();
}
int kth(Node *o,int k){
if(k<=(o->ch[0]->s)){
return kth(o->ch[0],k);
}else{
k-=o->ch[0]->s;
if(k<=o->cnt)
return o->v;
else
return kth(o->ch[1],k-(o->cnt));
}
}
int rank(Node *o,int x){
if(o==null)
return 0;
if(x<(o->v)){
return rank(o->ch[0],x);
}else{
if(x==o->v)
return o->ch[0]->s+1;
else
return o->ch[0]->s+o->cnt+rank(o->ch[1],x);
}
}
int pre(int x){
Node *cur=root;
int ans=0;
while(cur!=null){
if(cur->v<x){
ans=cur->v;
cur=cur->ch[1];
}else{
cur=cur->ch[0];
}
}
return ans;
}
int suc(int x){
Node *cur=root;
int ans=0;
while(cur!=null){
if(cur->v>x){
ans=cur->v;
cur=cur->ch[0];
}else{
cur=cur->ch[1];
}
}
return ans;
}
};
int main(){
int n;
int opt,x;
Treap T;
scanf("%d",&n);
srand(20020601);
while(n--){
scanf("%d%d",&opt,&x);
if(opt==1){
T.insert(T.root,x);
}else{
if(opt==2){
T.del(T.root,x);
}else{
if(opt==3){
printf("%d\n",T.rank(T.root,x));
}else{
if(opt==4){
printf("%d\n",T.kth(T.root,x));
}else{
if(opt==5){
printf("%d\n",T.pre(x));
}else{
printf("%d\n",T.suc(x));
}
}
}
}
}
}
return 0;
}
[COGS 396]魔术球问题（简化版）
这简化的真彻底……变成一个贪心水体了……
枚举柱子数，然后每次尽可能放球，放不了球了增加柱子，增加不了了就是最优解：
代码：
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=61;
vector<int> V[maxn];
inline bool isSqr(int x){
register int temp=floor(sqrt(x));
return temp*temp==x;
}
int main(){
int n,temp;
bool flag;
register int i,j,ans=1;
freopen("balla.in","r",stdin);
freopen("balla.out","w+",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++){
while(true){
flag=false;
for(j=0;j<i;j++){
if(V[j].empty() || isSqr(V[j].back()+ans)){
V[j].push_back(ans++);
flag=true;
break;
}
}
if(!flag)
break;
}
}
printf("%d\n",ans-1);
return 0;
}
