HZOJ 矩阵游戏

矩阵式决策: 利用矩阵图评估项目风险与收益 #生活技巧# #团队建设技巧# #团队决策方法#

大水题一个，然而由于两颗线段树的阴影我死了……

算法一：对于50%的数据： 送分，直接一个一个乘，时间复杂度O(KN)。

算法二：对于80%的数据：如果我们不一个一个乘，将第i行的和乘x ,第j列的和乘y ,所计算出的结果与正解不同的地方仅仅是（i,j）这一个元素。而这样的数不足K2个。所以我们把这些元素单独计算一遍就可以了，时间复杂度O（K2）。

算法三：对于100%的数据：设h[i]为第i行总共乘的数,l[j]表示第j列总共乘的数，根据题意map[i][j]=(i-1)*m+j,显然最后$ans=\sum\limits_{i=1}^{n} \sum \limits_{j=1}^{m} h[i]*l[j]*((i-1)*m+j)$,这样复杂度是O（nm）的，再把求和拆一下，ans=$\sum\limits_{i=1}^{n}$ h[i]*(∑l[j]*j)+$\sum\limits_{j=1}^{m}$ l[j]*(∑h[i]*(i-1)*m)这样复杂度就是O（m+n）的了。

1 #include<iostream> 2 #include<cstdio> 3 #define LL long long 4 #define MAXN 1000010 5 #define mod 1000000007 6 using namespace std; 7 LL h[MAXN],l[MAXN]; 8 int n,m,k; 9 char op;int x,y; 10 LL lj_j[MAXN],hi_i[MAXN]; 11 signed main() 12 { 13 cin>>n>>m>>k; 14 for(int j=1;j<=m;j++)l[j]=1; 15 for(int i=1;i<=n;i++)h[i]=1; 16 for(int i=1;i<=k;i++) 17 { 18 cin>>op>>x>>y; 19 if(op=='R')h[x]=h[x]*y%mod; 20 else l[x]=l[x]*y%mod; 21 } 22 LL sumj=0,sumi=0; 23 for(int j=1;j<=m;j++)lj_j[j]=l[j]*j%mod,sumj=(sumj+lj_j[j])%mod; 24 for(int i=1;i<=n;i++)hi_i[i]=h[i]*(i-1)%mod*m%mod,sumi=(sumi+hi_i[i])%mod; 25 LL ans=0; 26 for(int i=1;i<=n;i++)ans=(ans+h[i]*sumj)%mod; 27 for(int j=1;j<=m;j++)ans=(ans+l[j]*sumi)%mod; 28 printf("%lld\n",ans); 29 } View Code

转载于:https://www.cnblogs.com/Al-Ca/p/11306655.html

总结

以上是生活随笔为你收集整理的HZOJ 矩阵游戏的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。

网址：HZOJ 矩阵游戏 https://www.yuejiaxmz.com/news/view/1250053

相关内容

正交矩阵； 实对称矩阵； 为什么实对称矩阵一定可以对角化； AB=0 r(A)+r(B)＜=n 证明； 初等矩阵； 初等矩阵的逆矩阵； 矩阵的左除右除；
为什么共现矩阵* 评分矩阵=推荐结果
矩阵行列式
设矩阵A=是正定矩阵,则a满足( )
可以教会孩子守规矩的小亲子游戏
矩阵车膜：潮又值！
SHAREit Group产品矩阵从0到全球24亿用户的增长秘笈
求基础矩阵F方法
小红书矩阵营销是什么？小红书矩阵账号引流方法有哪些？
以长效增长为纲 知识矩阵与IP增量“双向奔赴”

随便看看