首页 > 其他分享 >CF446B DZY Loves Modification

CF446B DZY Loves Modification

时间:2023-08-15 19:13:42浏览次数:39  
标签:const CF446B 格子 int long Modification DZY 贪心

题目大意

给出一个 \(n \times m\) 的矩阵,并进行 \(k\) 次操作,每次操作将矩阵的一行或一列的所有元素的值减 \(p\),得到的分数为这次修改之前这一列或一行的元素和,求分数最大值。

思路

先说一下假贪心为什么是错的。

有一个很显然的贪心思路,分别用两个堆分别维护行与列的和,每次在两个堆的堆顶选最大的。

这种思路显然是错误的,我们直接给出一个组 hack 数据:

2 6 6 1
1 1 1 1 1 1
1 1 1 1 1 1

如果采用假贪心会导致先选择两个行,答案为 \(8\);但如果选择六列,答案为 \(18\)。

我们从每个格子的角度去考虑,假设我们已知这个格子被选了 \(x\) 次,那么它的贡献应当是 \(a+ a - p + a - 2p + \dots + a - (x - 1)p\)。我们发现贡献与这个格子是在行中被选中还是在列中被选中无关,那么我们就可以假设先操作所有的行,再操作所有的列。

我们还是把行和列分开贪心,记 \(ansLine_i\) 表示行选了 \(i\) 个的最大答案,\(ansRow_i\) 为列的,同理。

那么显然有

\[ans=\max_{i=0}^{k} \left\{ Line_i + Row_i-i\times p (k-i) \right\} \]

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1255;
const int M = 1005000;

long long n,m,k,p;

long long a[N][N];

long long ans = LLONG_MIN + 114514;

priority_queue<long long> queLine,queRow;
// Sum of Line or Row
long long ansLine[M],ansRow[M];

int main() {
    ios::sync_with_stdio(false);
    
	cin >> n >> m >> k >> p;
    
    for(int i = 1;i <= n; i++) 
        for(int j = 1;j <= m; j++) 
            cin >> a[i][j];
    
    long long LineSum = 0;
    for(int i = 1;i <= n; i++) {
        LineSum = 0;
        
        for(int j = 1;j <= m; j++) 
            LineSum += a[i][j];
            
        queLine.push(LineSum);
    }
    
    long long RowSum = 0;
    for(int i = 1;i <= m; i++) {
        RowSum = 0;
        
        for(int j = 1;j <= n; j++) 
            RowSum += a[j][i];
            
        queRow.push(RowSum);
    }
	
    for(int i = 1;i <= k; i++) {
        long long Line,Row;
        Line = queLine.top();
        Row = queRow.top();
        
        queLine.pop();
        queRow.pop();
        
        ansLine[i] = ansLine[i - 1] + Line;
        ansRow[i] = ansRow[i - 1] + Row;

        queLine.push(Line - p * m);
        queRow.push(Row - p * n);
    }

    for(int i = 0;i <= k; i++)
        ans = max(ans,ansLine[i] + ansRow[k - i] - 1ll * i * (k - i) * p);

    cout << ans << "\n";
    return 0;
}

标签:const,CF446B,格子,int,long,Modification,DZY,贪心
From: https://www.cnblogs.com/baijian0212/p/solution-cf446b.html

相关文章

  • java 异常 java.util.ConcurrentModificationException java 删除集合中满足条件的元
    java异常java.util.ConcurrentModificationExceptionjava.util.ConcurrentModificationException是Java中的一个常见异常,通常在使用迭代器或并发操作时发生。当集合在迭代过程中被修改时,就可能会抛出这个异常。这个异常是为了帮助开发人员发现并发访问集合时的潜在问题。在迭代期......
  • DZY Loves Math
    题面对于正整数\(n\),定义\(f(n)\)为\(n\)所含质因子的最大幂指数。例如\(f(1960)=f(23×51×72)=3,f(10007)=1,f(1)=0\)。给定正整数\(a,b\),求下式的值:\[\sum_{i=1}^a\sum_{j=1}^bf(\gcd(a,b))\]题解在下文的推导中,为避免歧义,设\(N=\min(a,b),M=\max(a,b)\),......
  • list - 删除元素 ConcurrentModificationException
     前天看了公众号,说是三年开发都不会删除元素,看了一眼,没想到第二天就用上了........而我也是那个菜鸟哈哈哈哈哈哈.........记录一下吧 publicstaticvoidmain(String[]args){List<String>list=newArrayList<>();list.add("1");list.add("2");lis......
  • CF446C. DZY Loves Fibonacci Numbers
    好牛的题,写一下。题意:维护一个序列\(a\),长度为\(n\),有\(m\)次操作:1lr:对于\(i\in[l,r]\),\(a_i\leftarrowa_i+f_{i-l+1}\)。2lr:求\(\displaystyle\left(\sum_{i=l}^ra_i\right)\bmod(10^9+9)\)。其中\(f_{i}\)表示第\(i\)个斐波那契数(\(f_0=0,f_1=1,f_n=f_......
  • 【CF446C】DZY Loves Fibonacci Numbers(线段树)
    Description给定一个序列,资瓷区间加上一个斐波那契数列,区间求和。Solution有一个性质:fib[a+b]=fib[a−1]×fib[b]+fib[a]×fib[b+1]fib[a+......
  • codeforces#FF DIV2C题DZY Loves Sequences(DP)
    题目地址:http://codeforces.com/contest/447/problem/CC.DZYLovesSequencestimelimitpertestmemorylimitpertestinputoutputa,consistingof nai, ai + 1, .........
  • 未设置 SQLALCHEMY_TRACK_MODIFICATIONS出现的bug
    python解释器报错:FSADeprecationWarning:SQLALCHEMY_TRACK_MODIFICATIONSaddssignificantoverheadandwillbedisabledbydefaultinthefuture.SetittoTrue......
  • DZY Loves Colors
    DZYLovesColors题面翻译有一个\(n\)个元素组成的序列,每个元素有两个属性:颜色\(c_i\)和权值\(w_i\)。\(c_i\)初始为\(i\),\(w_i\)初始为\(0\)。\(m\)次操作,操......
  • Java ConcurrentModificationException异常原因和解决方法
    场景对ArrayList在迭代的时候如果同时对其进行修改就会抛出java.util.ConcurrentModificationException异常。出现异常的代码://删除非此退货单对应的货位f......
  • Codeforces Round #254 (Div. 1) C - DZY Loves Colors 线段树|lazytag维护区间加
    开一个变量维护同一个区间内颜色是否相同,而且显然要用lazytag了递归到颜色相同的区间时就可以直接打标记然后对于标记,维护的就是常规区间加的部分(最开始没写lazy,wa6,没明......