题解 BZOJ 1313 取整矩阵

题目 题里的矩阵是这样的: A11 A12 A13… A1n-1 B1 A21 ………. A2n-1 B2 …… An-11 An-12….An-1n-1 Bn-1 C1 C2 C3… Cn-1 0 需要取整。每个元素大概有两种选择,一种是floor另一种是ceil。 这两种之间差...

一月 7, 2015 · 1 分钟 · 373 字 · Ruotian

SPOJ QTREE系列

375.QTREE 给你一棵n个点$n-1$条边的树,支持修改一条边的边权、查询两点之间路径上的最大边权。 树链剖分+线段树基础题 code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; int H[10005],X[20005],P[20005],tot, w[20005],E[20005],num[20005]; inline void add(int...

一月 6, 2015 · 2 分钟 · 914 字 · Ruotian

SPOJ GSS 系列

SPOJ GSS系列是一系列序列维护的问题。 大部分用线段树,Splay等可以解决。 1043. GSS1 题意:给定长度为N的数串,M个询问查询[a,b]的的最大连续子...

一月 6, 2015 · 2 分钟 · 949 字 · Ruotian

题解 BZOJ 2527 [Poi2011]Meteors

一个叫做整体二分的东西。 单个国家可以二分。 为了节约时间,可以把情况相同的一同二分。 可以用树状数组做必要的统计。 时间复杂度不明。 code: #include<cstdio>#include<cstring>#include<algorithm>#include<vector>using namespace std; int n,m; vector<int>...

一月 6, 2015 · 1 分钟 · 212 字 · Ruotian

题解 BZOJ 3707 圈地 计算几何

题解: 简单的说就是给定平面上n个点,求这n个点组成三角形的最小面积。 如果分别枚举三个点的话是$O(n^3)$的,时间无法承受。 如果枚举了两个...

九月 18, 2014 · 1 分钟 · 499 字 · Ruotian

题解 BZOJ 3714 [PA2014]Kuglarz

题解: 参考小胖的奇偶那道题。 那道题用的并查集维护。 如果知道 i..j 之间奇偶性的话,实际上知道的是 sum[j]-sum[i-1]的奇偶性(sum为前...

九月 14, 2014 · 1 分钟 · 246 字 · Ruotian

题解 BZOJ 3713 [PA2014]Iloczyn

题解: 鉴于F[44]> 1e9。于是可以把两两乘积算出来,枚举即可。 code: #include<cstdio>#include<cstring>#include<algorithm>#include<set>//by zrt //problem: using namespace std; int f[46]; set<int> s; int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif f[0]=0;f[1]=1; for(int i=2;i<=45;i++){ f[i]=f[i-1]+f[i-2]; } int MAX=1e9; for(int i=0;i<=45;i++) s.insert(f[i]); for(int i=3;i<=45;i++){ for(int j=i;j<=45;j++){ if(f[i]*1LL*f[j]<=MAX){ s.insert(f[i]*f[j]);...

九月 14, 2014 · 1 分钟 · 87 字 · Ruotian

题解 BZOJ 3709 [PA2014]Bohater

题解: 若d[x]<a[x],杀这个怪是有收益的,可以按d值从小到大杀。 若d[x]>a[x],考虑反过来的过程,如果都杀完后血量是...

九月 14, 2014 · 1 分钟 · 215 字 · Ruotian

题解 BZOJ 2442 [Usaco2011 Open]修剪草坪

题解: 定义F[i]为前 i-1 只奶牛工作效率的最大值。 sum[i]是Ei的前缀和。 有F[i]=max{F[j]+sum[i-1]-sum[j]} (i-j<k)...

九月 14, 2014 · 1 分钟 · 157 字 · Ruotian