分类存档：默认分类

[Elite 2010 January Competition Gold 【hayturn】]博弈类动态规划★★

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1783
【吐槽】
唉唉唉唉。。。
看了解题报告才会。太水了= =。。。
一开始看错题，写了个dp，样例都不过，后来看了解题报告才理解了题意。。。
囧
【算法分析】
下面基本是对解题报告的翻译：
令Fa[i]表示当前到这只牛选，选的范围是[i,n]，然后这只牛到最后最多能得到多少分？
令Fb[i]表示当前到另外一只牛选，选的范围是[i,n]，然后到最后这只牛最多能得到多少分？
然后我们应当注意到，主动权在选的那只牛手里。
现在我们有两种决策。
1、选第i格这个权。
那么Fa[i]=Fb[i+1]+w[i];
同时Fb[i]=Fa[i+1];
2、不选第i格这个权。
那么Fa[i]=Fa[i+1];
同时Fb[i]=Fb[i+1];

注意到主动权在当前选那只牛的手里，那么我们以当前选这只牛为上帝进行决策。
就是要取最大的Fa[i]。
所以只要比较Fb[i+1]+w[i]和Fa[i+1]就可以了。。。
【其它】cin取消同步以后原来不是很慢！！！就是800+MS。我用scanf也就500+MS…
当然，要G++才可以。就像外挂一样。
【CODE】
#include using namespace std;
typedef long long lld;
const lld N=705555;
lld n,w[N],Fa[N],Fb[N];

void solve(){
Fa[n]=w[n];
Fb[n]=0;
int i;
for (i=n-1;i>=1;i–)
if (Fb[i+1]+w[i]>=Fa[i+1]){
Fa[i]=Fb[i+1]+w[i];
Fb[i]=Fa[i+1];
}
else{
Fa[i]=Fa[i+1];
Fb[i]=Fb[i+1];
}
cout << Fa[1] << " " << Fb[1] << endl;
}

int main(){
ios::sync_with_stdio(false);
cin >> n;
for (lld i=1;i<=n;i++) cin >> w[i];
solve();
return 0;
}

[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();
}
}