arrow_upward

分类-题解

大半年打一次cf结果因为评测机出锅unrated了,非常不爽。这次比赛是和@Duanyll大佬合作打的,但因为我很弱出了很多锅坑了他,不过幸好是unrated。好歹还是A了四道题的,还是总结一下吧。A. Lunar New Year and Cross Counting题意给你一个矩阵,只要满足 $M(i,j)=M(i-1,j-1)=M(i-1,j+1)=M(i+1,j-1)=M(i+1,j...
   题解    0 条评论
卧槽竟然一遍就A了,可把身为蒟蒻的我nb坏了刚开始让我做这道题,我是拒绝的,然后看完题发现,这就是道裸的最短路,连边搞就是了。然后发现它只给三个点,看了题解才知道第四个点可以用向量点乘判断垂直来求,路燕我对不起你。思路就是把一个城市分成四个点,同一个城市坐车,不同城市坐飞机,得到所有点的坐标和所在城市以后跑一遍最短路就行了。因为我很菜只会dijkstra,所以我就写的dijkstra。#de...
   题解    0 条评论
提高+/省选-
这是一道由ljq大佬出的绝世好题,虽然看似容易,实则考察了诸位OIer对于C++语言的熟悉程度。同时,该题目又以我校物竞第一大佬PS作为题目背景,充满大佬之气,值得各位前来吸收RP。而原标程又由wzx大佬亲笔书写,可以相信几乎没有疏忽之处。所以,此题也配得上黑题这一难度评分。以下仅代表个人拙见,已AC,但不代表是最终正确程序。我们先来梳理下编译错误有哪些情况:#define和#undef后面...
   题解    5 条评论
NOI/NOI+/CTSC
显然用dp,用 $f[i]$ 表示前 $i$ 辆车过桥的最短时间,枚举上一个分组的最后一辆车 $j$ 进行转移,方程式为:$$f[i]=min \begin{cases} f[i] \\ f[j-1]+len\div s[i] \times 60 & j<=i, \sum ^{i}_{k=j}w[k]<=wmax \end{cases}$$其中 $tmax$ 是这一组中最...
   题解    0 条评论
普及+/提高
这道题应该是迄今为止我做的时间跨度最久的题,在2018.5.17第一次提交,直到今天(2019.1.26)才终于AC。题意就是给你一棵树,起初所有节点上的数是 $0$ ,对于每次操作 $(a,b,c)$ ,把 $a$ 和 $b$ 及之间的节点全部加上 $c$ ,最后输出每个节点上的数。其实题本身很简单,就是一道裸的树剖,但是有多组数据,所以一定要记得清空数组!!!需要被清空的数组:前向星的边...
   题解    0 条评论
省选/NOI-
就是一道区间dp+高精,最开始还想拿int_128来水水的,结果算算还是不太够,就老老实实写了高精。$f[st][ed][cnt]$ 表示在区间 $st..ed$ 放 $cnt$ 个乘号的最大值,转移方程式为:$$f[st][ed][cnt]=\max \{ f[st][mid][x]\times f[mid+1][ed][cnt-x-1] \}$$每次转移时枚举放乘号的位置 $(mid)$...
   题解    0 条评论
普及/提高-
看到是蓝题我就知道不可能是那道黄题的做法了,不过还是打了个暴力,无氧60,吸氧70bool mp[16][16],vis[16],vis2[32],vis3[32]; //x-y+14;x+y int n,m,a,b,c,ans; void dfs(int x) { if (x==n+1) { ans++; return; } ...
   题解    0 条评论
提高+/省选-
重题,双倍经验。https://blog.llf0703.com/p/uva-1292.html而且uva的题还有多组输出,删掉就行了。struct Edge{ int next,to; } edge[3005]; int head[1505],n,m,a,b,c,cnt,f[1505][2],out[1505]; inline void add(int u,int v) { ...
   题解    0 条评论
提高+/省选-
要不是徐妈让我做,我这辈子都不可能碰这道题的。这是我做过的代码最长的非数据结构题,模拟题最长也就一百来行,这道题第一次原生态(包括注释和调试)交上去有214行,删掉调试输出和合并一些if后也有174行。况且我一点优化都没加,纯种裸暴搜,加了优化不知道有多复杂。不过这题暴力能过就是了,吸氧前最大点1618ms,吸氧后774ms。思路整个过程可以分为 移动 --> 移动后的掉落 -->...
   题解    0 条评论
提高+/省选-
跟舞会那道题差不多,如果父节点没有取那么所有子节点都必须取;如果父节点取了,子节点取或不取皆可。$$\begin{cases} f[i][1]=\sum \min(f[j][0],f[j][1]) \\ f[i][0]=\sum f[j][1] \end{cases}$$需要注意的是题目中已经把子树说明了,这就意味着只能有一个点作为根节点,所以应该连单向边,并且事先找到那个点作为根节点。st...
   题解    0 条评论
提高+/省选-