JZYshuraK

未归档

/ 注册

全部文章 / 未归档（共392篇）

[bzoj3712][PA2014]Fiolki_倍增LCA

Fiolki bzoj-3712 PA-2014 题目大意：题目链接。注释：略。想法：神题！我们建树：对于一次倾倒操作，我们弄一个新的大瓶子作为两个合并瓶子的父亲节点，与两个瓶子相连。对于一个给定的化学反应，显然他们在这棵又操作构成的森林中他们的LCA处实现。所以我们对...

2018-11-01

0 331

[bzoj2208][Jsoi2010]连通数_bitset_传递闭包floyd

连通数 bzoj-2208 Jsoi-2010 题目大意：给定一个n个节点的有向图，问每个节点可以到达的点的个数和。注释：$1\le n\le 2000$。想法：网上有好多tarjan+拓扑序dp的... 我们考虑暴力怎么做：显然就是用floyd的warshall求出连通矩阵，然后扫...

2018-10-17

0 352

[bzoj2150]部落战争_二分图最小路径覆盖

部落战争 bzoj-2150 题目大意：题目链接。注释：略。想法：显然是最小路径覆盖，我们知道：二分图最小路径覆盖等于节点总数-最大匹配。所以我们用匈牙利或者dinic跑出最大匹配，然后用总结点数相减即可。最后，附上丑陋的代码... ... #include <...

2018-10-17

0 373

[bzoj1059][ZJOI2007]矩阵游戏_二分图最大匹配

矩阵游戏 bzoj-1059 ZJOI-2007 题目大意：给定一个n*n的棋盘，上面有一些格子被染黑，剩下都是白色。你每次可以交换两列或者两行，问你能否通过一系列操作使得棋盘的主对角线上的格子全是黑色。注释：$1\le n\le 200$。想法：我们发现一个小性质，就是两个格子如...

2018-10-16

0 317

[bzoj2962]序列操作_线段树_区间卷积

序列操作 bzoj-2962 题目大意：给定一个n个数的正整数序列，m次操作。支持：1.区间加；2.区间取相反数；3.区间求选c个数的乘积和。注释：$1\le n,m\le 5\cdot 10^4$，$1\le c\le 20$。想法：首先切入点非常明显，我们发现c只有20。又...

2018-10-16

0 506

[bzoj1895][Pku3580]supermemo_非旋转Treap

supermemo bzoj-1895 Pku-3580 题目大意：给定一个n个数的序列，需支持：区间加，区间翻转，区间平移，单点插入，单点删除，查询区间最小值。注释：$1\le n\le 6.1\cdot 10^6$。想法：这数据范围给的我真是醉了。显然用平衡树，这里用非旋转...

2018-09-27

0 376

[bzoj2058][Usaco2010 Nov]Cow Photographs_树状数组_动态规划

Cow Photographs bzoj-2058 Usaco-2010 Nov 题目大意：给定一个n的排列。每次操作可以交换相邻两个数。问将序列变成一个：$i,i+1,i+2,...,n,1,2,...,i-1$形式的序列最少操作次数。注释：$1\le n\le 10^5$。想法： ...

2018-09-27

0 317

[bzoj2443][Usaco2011 Open]奇数度数_树形dp_生成树_并查集

奇数度数 bzoj-2443 Usaco-2011 Open 题目大意：给定一个n个点m条便有向图，问是否有一种选出一些边的方式使得所有点的度数都是奇数。注释：$1\le n \le 5\cdot 10^4$，$1\le m\le 10^5$。想法：结论题：对于一个联通块来讲，如果...

2018-09-27

0 302

[bzoj1612][Usaco2008 Jan]Cow Contest奶牛的比赛_dfs

Cow Contest奶牛的比赛 bzoj-1612 Usaco-2008 Jan 题目大意：题目链接。注释：略。想法：我们对于每个点dfs，看一下比这个点大的点加上比这个点小的点是否是n-1即可。最后，附上丑陋的代码... ... #include <iostr...

2018-09-27

0 554

[bzoj1617][Usaco2008 Mar]River Crossing渡河问题_动态规划

River Crossing渡河问题 bzoj-1617 Usaco-2008 Mar 题目大意：题目链接。注释：略。想法：zcs0724出考试题的时候并没有发现这题我做过... 先把m求前缀和，存在bfr数组里。然后就可以dp了：状态：dp[i]表示送完前i头牛的最小时间。...

2018-09-27

0 443