【日常学习】【模拟，树形DP-非递归！和拆点最短路】10.26.2015校内测试总结

Love The Way You Lie 2022-08-09 14:40 7阅读 0赞

距离NOIP还有九天

昨天忙，没能写总结，今天补上。XBOI第N次校内胡测，由Archon=iostream0=隔壁TY君提供，特别鸣谢隔壁LOI seavot神犇的支持

1.stone 题目即RQNOJ100 魔法师之恋

大致意思是有很多矩形像俄罗斯方块那样落下来，规则相同，尽量使高度最低，高度相同时尽量靠左，求最小高度

实际上是模拟，但不幸地我的水平方向模拟挂啦

然而还是把代码放上吧，这个代码全WA

//stone
    //copyright by ametake
    //line
    //copyright by ametake
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    using namespace std;
    
    const int maxn=2000+10;
    bool a[maxn][25];
    int low=1,high=1;//可以填的最低一行，最高一行 
    int n,w;
    
    inline int read()
    {
        int f=1,a=0;
        char ch=getchar();
        while (ch<'0'||ch>'9')
        {
            if (ch=='-') f=-1;
            ch=getchar();
        }
        while (ch>='0'&&ch<='9')
        {
            a=a*10+ch-'0';
            ch=getchar();
        }
        a*=f;
        return a;
    }
    
    int main()
    {
    	//freopen("1.txt","r",stdin);
    	freopen("stone.in","r",stdin);
    	freopen("stone.out","w",stdout);
    	n=read();
        w=read();
        //for (int i=1;i<=maxn;i++) a[i][0]=w;
        int x;
        for (int c=1;c<=n;c++)
        {
        	x=read();
        	int now=low-1,hav=0,en=0;//记录目前搜索的层，有几个连续空格，如果满足条件空格终点 
        	while (hav<x)
        	{
        		now++;
        		hav=0;
        		for (int i=1;i<=w;i++)
        	    {
        		    if (!a[now][i])
        		    {
        		    	hav++;
        		    	if (hav==x)
        		    	{
        			    	en=i;
        			    	break;
    			     	}
    			    }
    			    else hav=0;
    		    }
    		}
    		int st=en-x+1;
    		for (int i=now;i<=now+x-1;i++)
    		{
    			for (int j=st;j<=en;j++)
    			{
    				a[i][j]=true;
    			}
    		}
    	    int r=now;
    	    while (r>0)
    	    {
    	    	if (!a[r][w]) r--;
    	    	else break;
    		}
    		low=r+1;
    		high=max(high,now+x-1)            ;
    	}
        printf("%d\n",high);
        return 0;
    }

事实上，正解的思路是这样的（来自t14t41t神犇）：以列为单位，记录此列的高度，然后把每个矩形当成移动窗口那样，从左到右移动，每次记录窗口所覆盖的列的最大高度，然后在这些最大高度里选最小的那个放下方块即可。

2.line

求树上一条链，使这条链上各边权值和最大，**有负权！有负权！有负权！！！**

因为有负权，这道题目不是求树的直径。听说隔壁LOI小盆友们BFS一片80，安之若素小妹妹摸头···我们所用的DFS或BFS球直径，是从叶子到叶子，在没有负权时作为最长链的确是对的。而这里的最长链由于有负权，举个最简单的例子，一个链三条边分别是-1,1，-1，显然应该输出1，但是如果直接求直径显然就WA了

那么怎么办呢？恩···树状DP是个好主意

具体怎么做？我们随便取一个点作为根，对于树上每一个点，记录其向下（也就是通向儿子们）的最长路径和次长路径（次长路是下一步用到的），再向上计算最长路径，加和就是通过这个点的最长链。最后扫一遍取MAX即可。事先预设ans==0 如果出现负数直接输出0，相当于路径只是一个节点

注意，向上求最长路不一定是通向祖先。这里所谓向上是指通向父节点方向的最长路径，可以从父亲或爷爷或其他祖先拐到另一棵子树中去。

打个比方，就是从当前节点往左走和往右走，分别求最长路径。往左，就必定要先走到父亲节点再决定下一步；往右，就要先走到某个儿子再决定下一步。

具体过程就看代码吧！注意，不用单独求父子关系，向下找不需要父子关系，向上找传递参数即可。

//line 树形DP cheer up！
    //就算是一小时一道题今天下午也能把三道题搞出来啊！！！
    //copyright by  ametake 每次写这一行都是满满的自豪感和欢喜
    //看来我今天废话很多一定是因为工程量很大
    //先写递归版本
    
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    #include
           
             using namespace std; const int maxn=100000+10; const int oo=0x3f3f3f3f; int up[maxn],down[maxn][2];//0 && 1 int n; int hd[maxn],t[maxn*2],nxt[maxn*2],v[maxn*2],et; bool vis[maxn]; int gen; stack
            
              s; inline void add(int &x,int &y,int &z) { et++; t[et]=y; v[et]=z; nxt[et]=hd[x]; hd[x]=et; } inline int read() { int f=1,a=0; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { a=a*10+ch-'0'; ch=getchar(); } a*=f; return a; } void caldown(int k)//儿子到根递推 { int p=hd[k]; while (p!=0) { int i=t[p]; if (vis[i]) { p=nxt[p]; continue; } vis[i]=true; caldown(i); if (down[i][0]+v[p]>down[k][0])//如果子树上这条路径更长 { down[k][1]=down[k][0]; down[k][0]=down[i][0]+v[p]; } else if (down[i][0]+v[p]>down[k][1]) down[k][1]=down[i][0]+v[p]; p=nxt[p]; } } void calup(int k,int fa,int vp)//根到儿子递推 { if (k==gen) up[k]=0; else { up[k]=up[fa]+vp;//父亲向上最长路 int tt;//开始考虑从父亲向下走的情况 对于祖先向下走的情况在计算父亲时已经考虑过 if (down[fa][0]==down[k][0]+vp)//如果父亲向下的最长路和自己是同一条路径或长度相同 { tt=down[fa][1]+vp; } else tt=down[fa][0]+vp; up[k]=max(up[k],tt); } for (int i=hd[k];i;i=nxt[i]) { if (t[i]!=fa) calup(t[i],k,v[i]);//参数：儿子，父亲，父子路 } } int main() { freopen("1.txt","r",stdin); freopen("3.txt","w",stdout); int x,y,z; n=read(); for (int i=1;i

`看明白了吧 然而很不幸 LOI众神犇决心要把我们踩在脚下，于是卡了递归，爆栈90 于是不畏艰险的XBOI众赴汤蹈火万死不辞勇往直前大刀阔斧改非递归！ 非递归怎么改呢？其实精髓在于：模拟系统栈，深度优先搜索，用栈非空循环控制回溯后对兄弟节点的搜索不断进行下去。 递归到尽头的标志是：栈顶元素等于当前扩展完毕的元素。如果扩展不下去了，显然不是到了叶子就是子树已经遍历完毕了。此时开始递推即可。 对于这道题目，代码一个是根到叶子一个是叶子到根，前者不必先求出最深层因此可以用队列，就像BFS一样扩展。后者必须先求出最深层元素故采用栈。 代码参考了之前写的抢掠计划。特别鸣谢t14t41t神犇耐心指点 //line 树形DP 非递归！
 
 #include           
 #include             
 #include               
 #include                 
 #include                    using namespace std; const int maxn=100000+10; const int oo=0x3f3f3f3f; int up[maxn],down[maxn][2];//0 && 1 int n; int hd[maxn],t[maxn*2],nxt[maxn*2],v[maxn*2],et; bool vis[maxn]; int gen,dfn[maxn]; struct node { int k,fa,vp; }; stack                      s; queue                        q; inline void add(int &x,int &y,int &z) { et++; t[et]=y; v[et]=z; nxt[et]=hd[x]; hd[x]=et; } inline int read() { int f=1,a=0; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { a=a*10+ch-'0'; ch=getchar(); } a*=f; return a; } void caldown(int k) { s.push(k); dfn[k]=1; while (!s.empty()) { int now=s.top(); int p; for (p=hd[now];p!=0;p=nxt[p]) { if (vis[t[p]]==0) { s.push(t[p]); dfn[t[p]]=dfn[now]+1; vis[t[p]]=true; break;//有一个就break 往下深搜 回来因为有大栈循环可以继续搞兄弟 } } if (s.top()==now)//如果深度上扩展不下去了 说明到底了或者子树都搜完了 现在开始计算最底层 { int kk=s.top(); int p=hd[kk]; while (p!=0) { int i=t[p]; if (dfn[i]>dfn[kk]) { if (down[i][0]+v[p]>down[kk][0]) { down[kk][1]=down[kk][0]; down[kk][0]=down[i][0]+v[p]; } else down[k][1]=max(down[k][1],down[i][0]+v[p]); } p=nxt[p]; } s.pop(); } } } void calup(int kk,int faa,int vvp) { q.push((node){kk,faa,vvp}); while (!q.empty()) { int k=q.front().k,fa=q.front().fa,vp=q.front().vp; up[k]=up[fa]+vp;//父亲向上最长路 int tt;//开始考虑从父亲向下走的情况 对于祖先向下走的情况在计算父亲时已经考虑过 if (down[fa][0]==down[k][0]+vp)//如果父亲向下的最长路和自己是同一条路径或长度相同 { tt=down[fa][1]+vp; } else tt=down[fa][0]+vp; up[k]=max(up[k],tt); for (int i=hd[k];i;i=nxt[i]) { if (t[i]!=fa) q.push((node){t[i],k,v[i]});//参数：儿子，父亲，父子路 } q.pop(); } } int main() { freopen("line.in","r",stdin); freopen("line.out","w",stdout); int x,y,z; n=read(); for (int i=1;i                         down[k][0])//如果子树上这条路径更长 { down[k][1]=down[k][0]; down[k][0]=down[i][0]+v[p]; } else if (down[i][0]+v[p]>down[k][1]) down[k][1]=down[i][0]+v[p]; p=nxt[p]; } } void calup(int k,int fa,int vp)//根到儿子递推 { if (k==gen) up[k]=0; else { up[k]=up[fa]+vp;//父亲向上最长路 int tt;//开始考虑从父亲向下走的情况 对于祖先向下走的情况在计算父亲时已经考虑过 if (down[fa][0]==down[k][0]+vp)//如果父亲向下的最长路和自己是同一条路径或长度相同 { tt=down[fa][1]+vp; } else tt=down[fa][0]+vp; up[k]=max(up[k],tt); } for (int i=hd[k];i;i=nxt[i]) { if (t[i]!=fa) calup(t[i],k,v[i]);//参数：儿子，父亲，父子路 } } */                                                                     3.虫洞 即codevs1391伊吹萃香 题目来自东方模拟赛某场 题目描述 Description 在幻想乡，伊吹萃香是能够控制物体密度的鬼王。因为能够控制密度，所以萃香能够制造白洞和黑洞，并可以随时改变它们。某一天萃香闲着无聊，在妖怪之山上设置了一些白洞或黑洞，由于引力的影响，给妖怪们带来了很大的麻烦。于是他们决定找出一条消耗体力最少的路，来方便进出。已知妖怪之山上有N个路口(编号1..N)，每个路口都被萃香设置了一定质量白洞或者黑洞。原本在各个路口之间有M条单向路，走过每一条路需要消耗一定量的体力以及1个单位的时间。由于白洞和黑洞的存在，走过每条路需要消耗的体力也就产生了变化，假设一条道路两端路口黑白洞的质量差为delta： 1. 从有白洞的路口走向有黑洞的路口，消耗的体力值减少delta，若该条路径消耗的体力值变为负数的话，取为0。 2. 从有黑洞的路口走向有白洞的路口，消耗的体力值增加delta。 3. 如果路口两端均为白洞或黑洞，消耗的体力值无变化。 由于光是放置黑洞白洞不足以体现萃香的强大，所以她决定每过1个单位时间，就把所有路口的白洞改成黑洞，黑洞改成白洞。当然在走的过程中你可以选择在一个路口上停留1个单位的时间，如果当前路口为白洞，则不消耗体力，否则消耗s[i]的体力。现在请你计算从路口1走到路口N最小的体力消耗。保证一定存在道路从路口1到路口N。 输入描述 Input Description 第1行：2个正整数N, M 第2行：N个整数，第i个数为0表示第i个路口开始时为白洞，1表示黑洞 第3行：N个整数，第i个数表示第i个路口设置的白洞或黑洞的质量w[i] 第4行：N个整数，第i个数表示在第i个路口停留消耗的体力s[i] 第5..M+4行：每行3个整数，u, v, k，表示在没有影响的情况下，从路口u走到路口v需要消耗k的体力。 输出描述 Output Description 第1行：1个整数，表示消耗的最小体力 样例输入 Sample Input 4 5 1 0 1 0 10 10 100 10 5 20 15 10 1 2 30 2 3 40 1 3 20 1 4 200 3 4 200 样例输出 Sample Output 130 数据范围及提示 Data Size & Hint 对于30%的数据：1 <= N <= 100, 1 <= M <= 500 对于60%的数据：1 <= N <= 1,000, 1 <= M <= 5,000 对于100%的数据：1 <= N <= 5,000, 1 <= M <= 30,000 其中20%的数据为1 <= N <= 3000的链 1 <= u,v <= N, 1 <= k,w[i],s[i] <= 200 按照1 -> 3 -> 4的路线。 黑点白点怎么处理？拆点。把每个店都拆成黑白两个点处理。 实际上应用了一点分层图的思想，我举个例子，如果最初黑点1到黑点2有一条边，那么就从黑点1到白点n+2,也就是黑点2在上面一层所对应的白点 为什么呢？从黑到黑，消耗一个时间单位，走到时原来的黑点实际上已经是白点了。实际上下面和上面两层表示的分别是偶数和奇数时间的状态。 其他节点连接方式同理。如果选择等待，就从某个点到它对应的上层或下层点连一条边，权值为等待的代价。 跑最短路即可。 注意同一层不存在边，所有边都是跨层的。（听说wxjlzbcd神犇写了同层版本，有时间去膜一下） 代码 //holes
 //copyright by ametake
 #include             
 #include               
 #include                 
 #include                   
 #include                      using namespace std; const int maxn=5000+10; const int maxm=30000+10; int n,m; bool black[maxn]; int w[maxn],s[maxn]; struct node { int t,v,nxt; }e[maxm*4]; int t,c,ts,te; int hd[maxn*2]; bool inq[maxn*2]; int dis[maxn*2]; int et=0; int ans=0; void add(int x,int y,int z) { et++; e[et].t=y; e[et].v=z; e[et].nxt=hd[x]; hd[x]=et; } inline int read() { int f=1,a=0; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { a=a*10+ch-'0'; ch=getchar(); } a*=f; return a; } void spfa(int ss) { queue                        q; dis[ss]=0; inq[ss]=1; q.push(ss); while (!q.empty()) { int p=q.front(); q.pop(); inq[p]=0; int pi=hd[p]; while (pi) { if (dis[p]+e[pi].v                                                               下面这句诗很奇怪但这是显摆（实际上是李晨···）提供的 ——揽裙脱丝履,举身赴清池`