[Elite 2010 January Competition Gold 【telephone】]树形dp

【题目链接】http://ace.delos.com/ioigate
另外八中OJ的1785也是。不过八中的可能pascal会爆栈。。。
【算法分析】
首先建议看英文，八中的翻译有点歧义。
这个一颗无根树，于是我们可以选一个非叶结点出来当根，那么就可以搞了。
然后我们注意到，如果两个叶子搞在一块的话，那么必然是连到它们的LCA那里去搞了。
如果是这样的话，如果是从某一个结点搞上它父亲那里的话，无论是哪个都是一样的。
因为都是占用父亲的链。
而且显然是越早解决越好。
于是我们直接用一个rest数组记录剩下多少个需要用连向父亲这条边来解决。
然后，都算不上dp了，就是统计算一下就可以了。
【其它】1Y
【CODE】
/*
ID:jie22221
TASK:telephone
LANG:C++
*/
#include #include #include #include using namespace std;
const int N=105555;
struct edge{int x,y,next;}g[N*2];
int n,k,e,root,ans;
int ls[N],du[N],rest[N];

void add(int x,int y){
e++;
g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}

void init(){
memset(ls,0,sizeof(ls));
memset(du,0,sizeof(du));
e=0;
scanf("%d%d",&n,&k);
for (int x,y,i=1;i scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
du[x]++; du[y]++;
}
}

void dfs(int p,int fa){
if (du[p]==1){
rest[p]=1;
return;
}
for (int t=ls[p];t;t=g[t].next)
if (g[t].y!=fa){
dfs(g[t].y,p);
rest[p]+=rest[g[t].y];
}
if (rest[p]<=2*k && rest[p]%2){
ans+=rest[p]>>1;
rest[p]=1;
}
else{
if (rest[p]>2*k) ans+=k;
else ans+=rest[p]>>1;
rest[p]=0;
}
}

void solve(){
if (n<=2){
printf("%dn",n);
return;
}
for (int i=1;i<=n;i++)
if (du[i]>1){
root=i;
break;
}
memset(rest,0,sizeof(rest));
ans=0;
dfs(root,0);
}

int main(){
init();
solve();
cout << ans << endl;
return 0;
}

[JSOI2010 缓存交换]贪心、二叉堆

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1826
【算法分析】
如果一个x已经在缓存中，那么本次x进入就不需要再被计算。
也就是说，无论弄谁，本质上都是一样的。
而且当前这个点，必须被push进缓存。
容易得到一个贪心解法：
设当前值为x，就是按下一个x的位置前后排个序里，越后的越废。
于是只取前m个就可以了。于是可以用个二叉堆优化。
【时间复杂度】O(n lg n)
【其它】2Y。一开始把堆得del函数写错了呃@.@，因为删的不一定是第一个，写不习惯了。。
【CODE】
#include using namespace std;
const int N=105555;
struct edge{int y,next,pos;}g[N];
int n,m,e;
int a[N],lx[N],ls[N],Next[N],zz[N];

struct Heap_t{
int tot;
struct Node{int key,pos;}h[N];
void Swap(int i,int j){
Node tmp=h[i]; h[i]=h[j]; h[j]=tmp;
zz[h[i].pos]=i;
zz[h[j].pos]=j;
}
void up(int k){
while (k>1 && h[k].key>h[k/2].key){
Swap(k,k/2);
k/=2;
}
}

void down(int p){
int k;
while (p*2<=tot){
k=p*2;
if (k if (h[k].key>h[p].key){
Swap(k,p);
p=k;
}else break;
}
}

void ins(int key,int pos){
tot++;
h[tot].key=key;
h[tot].pos=pos;
zz[pos]=tot;
up(tot);
}

void del(int p){
Swap(p,tot);
zz[h[tot].pos]=0;
tot–;
up(p);
down(p);
}
}heap;

int Find(int x){
int l=1,r=n,mid;
while (l mid=(l+r)/2;
if (x>lx[mid]) l=mid+1;
else r=mid;
}
return l;
}

void init(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
lx[i]=a[i];
}
sort(lx+1,lx+n+1);
for (int i=1;i<=n;i++) a[i]=Find(a[i]);
for (int i=1;i<=n;i++) ls[i]=n+1;
for (int i=n;i>=1;i–){
Next[i]=ls[a[i]];
ls[a[i]]=i;
}
}

void work(){
memset(zz,0,sizeof(zz));
heap.tot=0;
int i,ans=0;
for (i=1;i<=n;i++){
if (zz[a[i]]==0){
ans++;
if (heap.tot==m) heap.del(1);
heap.ins(Next[i],a[i]);
}
else{
heap.del(zz[a[i]]);
heap.ins(Next[i],a[i]);
}
}
printf("%dn",ans);
}

int main(){
init();
work();
}

[HAOI2007 理想的正方形]单调队列

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1047
【算法分析】
先弄一个dmax[i][j]和dmin[i][j]数组分别表示(i,j)这个点往下的n（是题目中的n）个点中，最大值（最小值）是多少。然后这样压缩以后横向再来一次就可以。
【其它】
看到群里说2维单调队列，然后师傅就发了这个链接。。。
难道这就是传说中的2维
还以为是很恐怖的东西。。。
【其它】1Y。
【CODE】
#include #include #include #include using namespace std;
const int N=1005;
int m,n,L,i,j,head,tail;
int w[N][N],dmax[N][N],dmin[N][N],a[N][N],b[N][N],qp[N],qf[N];

int main(){
scanf("%d%d%d",&m,&n,&L);
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
scanf("%d",&w[i][j]);
for (j=1;j<=n;j++){
head=1; tail=0;
for (i=1;i while (head<=tail && w[i][j]>qf[tail]) tail--;
qf[++tail]=w[i][j]; qp[tail]=i;
}
for (i=1;i+L-1<=m;i++){
while (head<=tail && w[i+L-1][j]>qf[tail]) tail--;
qf[++tail]=w[i+L-1][j]; qp[tail]=i+L-1;
while (qp[head] dmax[i][j]=qf[head];
}
}

for (j=1;j<=n;j++){
head=1; tail=0;
for (i=1;i while (head<=tail && w[i][j] qf[++tail]=w[i][j]; qp[tail]=i;
}
for (i=1;i+L-1<=m;i++){
while (head<=tail && w[i+L-1][j] qf[++tail]=w[i+L-1][j]; qp[tail]=i+L-1;
while (qp[head] dmin[i][j]=qf[head];
}
}
int ans=0x7FFFFFFF;
for (i=1;i+L-1<=m;i++){
head=1; tail=0;
for (j=1;j<=n;j++){
while (head<=tail && dmax[i][j]>qf[tail]) tail--;
qf[++tail]=dmax[i][j]; qp[tail]=j;
while (qp[head]<=j-L) head++;
a[i][j]=qf[head];
}
head=1; tail=0;
for (j=1;j<=n;j++){
while (head<=tail && dmin[i][j] qf[++tail]=dmin[i][j]; qp[tail]=j;
while (qp[head]<=j-L) head++;
b[i][j]=qf[head];
}
}
for (i=1;i+L-1<=m;i++)
for (j=L;j<=n;j++)
ans=min(ans,a[i][j]-b[i][j]);
printf("%dn",ans);
}

[HDOJ1512 Monkey King]可合并堆

【算法分析】
据Lost天牛的所有算法总结所说，现在一般人能写得起有两种可合并堆，一种是左偏树，一种是斜堆。
然后斜堆好像算法是平摊的还是啥，单次可能变成O(n)@.@。。。
如果不是平摊只是期望的话。。。那么估计想二叉检索树一样对某些特殊数据会悲剧啊。。。
还是老老实实写左偏树比较好。
然后这题就是左偏树的模板题。
当然还要搞个并查集。
【其它】第一个左偏树。1Y
【CODE】
#include #include #include const int N=105555;
int n,m,fa[N];
struct Node{Node *l,*r;int key,dis;}sp[N],*root[N],*null;

void input(){
null=&sp[0];
for (int i=1;i<=n;i++){
scanf("%d",&sp[i].key);
fa[i]=i;
root[i]=&sp[i];
root[i]->dis=0;
root[i]->l=root[i]->r=null;
}
}

inline void swap(Node *&A,Node *&B){Node *tmp=A; A=B; B=tmp;}

int gf(int k){
if (fa[k]==k) return k;
else return fa[k]=gf(fa[k]);
}

Node* Union(Node *p,Node *q){
if (p==null) return q;
if (q==null) return p;
if (p->key p->r=Union(p->r,q);
if (p->l->dis if (p->r==null) p->dis=0;
else p->dis=p->r->dis+1;
return p;
}

void myself_c(Node *&R){
Node *lc=R->l,*rc=R->r;
R->key>>=1; R->l=R->r=null;
R=Union(R,lc);
R=Union(R,rc);
}

void work(){
scanf("%d",&m);
for (int x,y,i=1;i<=m;i++){
scanf("%d%d",&x,&y);
if (gf(x)==gf(y)) printf("-1n");
else{
myself_c(root[fa[x]]);
myself_c(root[fa[y]]);
root[fa[y]]=Union(root[fa[x]],root[fa[y]]);
fa[fa[x]]=fa[y];
printf("%dn",root[fa[y]]->key);
}
}
}

int main(){
while (scanf("%d",&n)!=EOF){
input();
work();
}
}

[JSOI2010 满汉全席]2-sat

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1823
【算法分析】
对于每种材料，有做成满式和汉式两种情况，然后两者取且必须取一种。
而且约束条件是，(A做成XX式 or B做成yy式) = true。
逻辑运算符。。。很容易想到2-sat。
回想2-sat的建图，一条边(A，B)的意义是：如果你选了A，那么就必须选B。
恩，这个题目的逻辑式子转化成：加入你选了A的对立面，那么一定要选B啊。
恩，就这样。。。
【其它】很久没2-sat了，1Y。
【CODE】
#include #include #include const int N=1000;
const int E=1000000;
int n,m,e,times,ct,tot;
int lx[N],ly[N];
int fa[N],order[N];
bool v[N],Type;

struct Graph_t{
struct edge{int x,y;edge *next;}g[E],*ls[N];
void clr(){e=0; memset(ls,0,sizeof(ls));}
void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}

void op(){
int tmp=e;
clr();
for (int i=1;i<=tmp;i++) addedge(g[i].y,g[i].x);
}

void dfs(int p){
v[p]=true;
for (edge *t=ls[p];t;t=t->next)
if (!v[t->y]) dfs(t->y);
if (Type) fa[p]=ct;
else order[++tot]=p;
}
}G;

int Get(){
char ch[20];
int x;
scanf("%s",ch);
sscanf(ch+1,"%d",&x);
if (ch[0]==’h’) x+=n;
return x;
}

void init(){
int i;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
lx[i]=Get();
ly[i]=Get();
}
}

void build(){
G.clr();
int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
if (lx[j]==i+n) G.addedge(i,ly[j]);
if (ly[j]==i+n) G.addedge(i,lx[j]);
}
for (i=n+1;i<=n*2;i++)
for (j=1;j<=m;j++){
if (lx[j]==i-n) G.addedge(i,ly[j]);
if (ly[j]==i-n) G.addedge(i,lx[j]);
}
}

void SCC(){
memset(v,false,sizeof(v));
tot=0;
Type=false;
for (int i=1;i<=2*n;i++)
if (!v[i]) G.dfs(i);
Type=true;
G.op();
memset(v,false,sizeof(v));
for (int i=tot;i>=1;i–)
if (!v[order[i]]){
ct=order[i];
G.dfs(order[i]);
}
}

void output(){
bool ans=true;
for (int i=1;i<=n;i++)
if (fa[i]==fa[i+n]) ans=false;
if (ans) puts("GOOD");
else puts("BAD");
}

int main(){
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
init();
build();
SCC();
output();
}
}