bzoj 4004 向量拟阵

题解RT.

eps = 1e-10 WrongAnswer

eps = 1e-5 Accepted

 1 /**************************************************************
 2     Problem: 4004
 3     User: idy002
 4     Language: C++
 5     Result: Accepted
 6     Time:516 ms
 7     Memory:2844 kb
 8 ****************************************************************/
 9
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 #define eps 1e-5
14 #define N 510
15 using namespace std;
16
17 int n, m;
18 double aa[N][N];
19 int cost[N];
20 int vid[N];
21 int kid[N];
22
23 int sg( double x ) {
24     return (x>-eps)-(x<eps);
25 }
26 bool cmp( int a, int b ) { return cost[a]<cost[b]; }
27 bool join( int id ) {
28     for( int i=1; i<=m; i++ ) {
29         if( sg(aa[id][i])==0 ) continue;
30         if( kid[i]==0 ) {
31             kid[i]=id;
32             return true;
33         }
34         int uid = kid[i];
35         double k = aa[id][i]/aa[uid][i];
36         for( int j=i; j<=m; j++ )
37             aa[id][j] -= k*aa[uid][j];
38     }
39     return false;
40 }
41 int main() {
42     scanf( "%d%d", &n, &m );
43     for( int i=1; i<=n; i++ )
44         for( int j=1; j<=m; j++ )
45             scanf( "%lf", &aa[i][j] );
46     for( int i=1; i<=n; i++ )
47         scanf( "%d", cost+i );
48     for( int i=1; i<=n; i++ )
49         vid[i] = i;
50     sort( vid+1, vid+1+n, cmp );
51     memset( kid, 0, sizeof(kid) );
52     int cnt=0, ans=0;
53     for( int i=1; i<=n; i++ ) {
54         int id = vid[i];
55         if( join(id) ) {
56             cnt++;
57             ans+=cost[id];
58         }
59     }
60     printf( "%d %d\n", cnt, ans );
61 }

时间: 06-07

bzoj 4004 向量拟阵的相关文章

bzoj 4004: [JLOI2015]装备购买 拟阵 &amp;&amp; 高消

4004: [JLOI2015]装备购买 Time Limit: 20 Sec  Memory Limit: 128 MBSubmit: 337  Solved: 139[Submit][Status][Discuss] Description 脸 哥最近在玩一款神奇的游戏,这个游戏里有 n 件装备,每件装备有 m 个属性,用向量zi(aj ,.....,am) 表示 (1 <= i <= n; 1 <= j <= m),每个装备需要花费 ci,现在脸哥想买一些装备,但是脸哥很穷,

bzoj 4004 [JLOI2015]装备购买——拟阵证明贪心+线性基

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4004 看Zinn博客水过去-- 运用拟阵可以证明按价格从小到大买的贪心是正确的.但自己还不会. 然后如果当前物品可以被线性表出就不买了.否则买,在第一个不能线性表出的位置上记录这个物品,表示按已经被消成这样的这个物品的这一位来消掉这一位是可以和前面那些位的消的情况吻合的. 然后因为卡精度而用long double.在printf里是Lf. #include<iostream> #incl

BZOJ 4004 [JLOI 2015] 装备购买 解题报告

哎这个题 WA 了无数遍...果然人太弱... 首先我们把这些装备按照花费从小到大排序,然后依次考虑是否能买这个装备. 至于这样为什么是对的,好像有一个叫拟阵的东西可以证明,然而我不会.TATQAQ 至于怎么考虑是否能买这个装备呢,我们可以动态更新线性基,具体操作: 对当前向量进行高斯消元,注意要从从高位往低位消. 如果消元完毕后当前向量变成了 $0$ 向量,那么我们就可以用之前的装备凑出当前装备,否则就不能凑出来. 每次更新线性基需要 $O(m^2)$ 的时间,要更新 $O(n)$ 次. 时间

[BZOJ]3243 向量内积(Noi2016)

小C做了之后很有感觉的题目之一,但因为姿势不对调了很久. Description 两个d 维向量A=[a1,a2,...,ad]与B=[b1,b2,...,bd]的内积为其相对应维度的权值的乘积和,即: 现有 n 个d 维向量x1,...,xn ,小喵喵想知道是否存在两个向量的内积为k的倍数.请帮助她解决这个问题. Input 第一行包含3个正整数n,d,k,分别表示向量的个数,维数以及待检测的倍数.接下来n行每行有d个非负整数,其中第i行的第j个整数表示向量xi的第j维权值xi,j. N<=1

BZOJ 4004: [JLOI2015]装备购买

4004: [JLOI2015]装备购买 Time Limit: 20 Sec  Memory Limit: 128 MBSubmit: 1158  Solved: 377[Submit][Status][Discuss] Description 脸哥最近在玩一款神奇的游戏,这个游戏里有 n 件装备,每件装备有 m 个属性,用向量zi(aj ,.....,am) 表示 (1 <= i <= n; 1 <= j <= m),每个装备需要花费 ci,现在脸哥想买一些装备,但是脸哥很穷,

BZOJ 2299 向量(裴蜀定理)

题意:给你一对数a,b,你可以任意使用(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量,问你能不能拼出另一个向量(x,y). 实际上前四个向量能拼出(ma,nb)(m%2=n%2).后四个向量拼出(xb,ya)(x%2=y%2). 这样可以枚举这四个未知数在模二意义下的解.这两个向量相加为(ma+xb,nb+ya). 对于ma+xb=X.根据系数的奇偶性,如果有系数为奇数,可使得等式两边都减去一个数使得系数都为偶

BZOJ 4004: [JLOI2015]装备购买 [高斯消元同余 线性基]

和前两(一)题一样,不过不是异或方程组了..... 然后bzoj的新数据是用来卡精度的吧..... 所有只好在模意义下做啦 只是巨慢无比 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <bitset> using namespace std; typedef long lon

BZOJ 4311: 向量( 按时间分治 + 线段树 )

离线, 然后按时间分治, 每个向量都有出现时间[l, r], 直接插入时间线段树(一个向量只会影响O(logN)数量级的线段树节点). 在线段树每个节点弄出凸壳然后二分. 时间复杂度O(Nlog^2N) --------------------------------------------------------------------------- #include<cstdio> #include<cctype> #include<cstring> #includ

BZOJ 4311 向量

shallot+向量集 混合版? 首先我们考虑每个向量的存在时间为[L,R] 那么我们知道任意一个区间在线段树上最多被分解成logn个区间 那么我们可以像shallot一样进行区间覆盖 注意到本题的查询是在凸壳上完成的,而凸壳不像shallot的线性基一样有固定的时间复杂度 但是本题的查询是可分离的,那么我们不需要将向量下传,只需要在线段树的每一层做凸壳即可 查询时每走一层对该层三分取最优解,建造凸壳和三分方法同向量集 QAQ 上午因为排序不小心写反了符号调了好久 QAQ 时间复杂度O(nlog