记录一些散题 / 价值不大但还是想记下来的题目 / 没正八经写博客的题目
8.24
Luogu P1508 沙雕题数字三角形的二维升级版，但是注意阅读理解，李大水牛从桌子最后一行下侧开始吃，而本题是自下而上，其实按自上而下做也行，只不过最后的答案变成了三者取一最值。（面前、左上、右上）其他与数字三角形无异。
1 #include<cstdio> 2 #include<algorithm> 3 4 using namespace std; 5 6 int n,m; 7 int f[400][400]; 8 9 int main() 10 { 11 scanf("%d%d",&n,&m); 12 for(int i=1;i<=n;i++) 13 for(int j=1;j<=m;j++) 14 scanf("%d",&f[i][j]); 15 for(int i=1;i<=n;i++) 16 for(int j=1;j<=m;j++) 17 f[i][j]+=max(f[i-1][j-1],max(f[i-1][j],f[i-1][j+1])); 18 int qwq=(m+1)>>1; 19 printf("%d",max(f[n][qwq],max(f[n][qwq-1],f[n][qwq+1]))); 20 return 0; 21 }
8.23
Luogu P1550 最小生成树。（这题记得第一次月考完和Chemist在机房想一起刷点贪心，我抽到了这个题，两人一起做，后来才发现是MIT，但是我没做，大神写了qwq我四个月以后才写qwq）.鉴于每个农庄自己凿井的情形，我们可以再构造一个源点，让所有自己凿井的情况与源点连边。然后就是裸的MIT了。但是注意无向边开两倍，还因为这个制杖错误没能1A，热了三个点orz。。。
Luogu P1993 差分约束系统。判断不等式组是否有解，直接建图判是否有负环。实践了一下可爱lyc的差分约束系统理论，但是漏洞百出。果然实践出针织qwq。
几个注意地方：1 不等式要化对
2 最后把所有的点和0连0权边，而不是仅把输入中涉及的点连
3 据说本题会卡bfs-spfa判负环，抄题解学习了一下dfs版本的spfa判负环，可以留当板子用。
4 spfa中dis[0]=0（这还需要说嘛）
5 head数组初值为-1，因为有编号为0的点存在。（没有亲测如果不赋会怎样，题解中不赋貌似也能过，可能是数据较弱的缘故）。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 5 using namespace std; 6 7 int n,m,tot; 8 int head[10090],vis[10090],dis[10090]; 9 struct node{ 10 int next,to,val; 11 }edge[100090]; 12 13 void add(int x,int y,int z) 14 { 15 edge[++tot].val=z; 16 edge[tot].to=y; 17 edge[tot].next=head[x]; 18 head[x]=tot; 19 } 20 21 bool spfa(int u) 22 { 23 vis[u]=1; 24 for(int i=head[u];i!=-1;i=edge[i].next) 25 if(dis[edge[i].to]>dis[u]+edge[i].val) 26 { 27 dis[edge[i].to]=dis[u]+edge[i].val; 28 if(vis[edge[i].to]) return 0; 29 if(!spfa(edge[i].to)) return 0; 30 } 31 vis[u]=0; 32 return 1; 33 } 34 35 int main() 36 { 37 scanf("%d%d",&n,&m); 38 memset(head,-1,sizeof(head)); 39 memset(dis,127,sizeof(dis)); 40 for(int i=1;i<=m;i++) 41 { 42 int opt=0,a=0,b=0,c=0; 43 scanf("%d",&opt); 44 if(opt==1) 45 { 46 scanf("%d%d%d",&a,&b,&c); 47 add(a,b,-c); 48 } 49 else if(opt==2) 50 { 51 scanf("%d%d%d",&a,&b,&c); 52 add(b,a,c); 53 } 54 else if(opt==3) 55 { 56 scanf("%d%d",&a,&b); 57 add(a,b,0); 58 add(b,a,0); 59 } 60 } 61 for(int i=1;i<=n;i++) add(0,i,0); 62 dis[0]=0; 63 if(spfa(0)) printf("Yes"); 64 else printf("No"); 65 return 0; 66 }
留几个待填坑吧：
瓶颈树
集合
控制公司
无向图tarjan
奶牛家谱
派对灯