首页 > 其他分享 >「杂题乱刷」P8572

「杂题乱刷」P8572

时间:2024-05-28 21:25:48浏览次数:21  
标签:cout P8572 -- sum forl long 杂题 define

链接

发现这东西就很根号分治。

考虑两种情况:

  • \(k \le 1000\),这部分直接用前缀和维护然后暴力做,时间复杂度 \(O(kq)\)。

  • \(k > 1000\),此时 \(n \le 500\),这部分直接预处理答案,时间复杂度 \(O(n^2 k)\)。

两个时间复杂度均正确,因此可以通过此题。

代码:

点击查看代码
/*
Tips:
你数组开小了吗?
你MLE了吗?
你觉得是贪心,是不是该想想dp?
一个小时没调出来,是不是该考虑换题?
打 cf 不要用 umap!!!

记住,rating 是身外之物。

该冲正解时冲正解!

Problem:

算法:

思路:

*/
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define forl(i,a,b) for(register long long i=a;i<=b;i++)
#define forr(i,a,b) for(register long long i=a;i>=b;i--)
#define forll(i,a,b,c) for(register long long i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(register long long i=a;i>=b;i-=c)
#define lc(x) x<<1
#define rc(x) x<<1|1
#define mid ((l+r)>>1)
#define cin(x) scanf("%lld",&x)
#define cout(x) printf("%lld",x)
#define lowbit(x) (x&-x)
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define ll long long
#define ull unsigned long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
ll t;
ll n,m,q;
void solve()
{
	cin>>n>>m>>q;
	ll a[m+5][n+5]={0},sum[m+5][n+5]={0};
	forl(i,1,m)
		forl(j,1,n)
			cin>>a[i][j],sum[i][j]=sum[i][j-1]+a[i][j];
	if(m<=1000)
	{
		while(q--)
		{
			ll l,r,ans=0;
			cin>>l>>r;
			forl(i,1,m)
				ans=max(ans,sum[i][r]-sum[i][l-1]);
			cout<<ans<<endl;
		}
	}
	else
	{
		ll ans[n+5][n+5]={0};
		forl(i,1,n)
		{
			ll maxn=0;
			forl(j,i,n)
			{
				forl(k,1,m)
					maxn=max(maxn,sum[k][j]-sum[k][i-1]);
				ans[i][j]=maxn;
			}
		}
		while(q--)
		{
			ll l,r;
			cin>>l>>r;
			cout<<ans[l][r]<<endl;
		}
	}
}
int main()
{
	IOS;
	t=1;
//	cin>>t;
	while(t--)
		solve();
    /******************/
	/*while(L<q[i].l) */
	/*    del(a[L++]);*/
	/*while(L>q[i].l) */
	/*    add(a[--L]);*/
	/*while(R<q[i].r) */
	/*	  add(a[++R]);*/
	/*while(R>q[i].r) */
	/*    del(a[R--]);*/
    /******************/
	QwQ;
}

标签:cout,P8572,--,sum,forl,long,杂题,define
From: https://www.cnblogs.com/wangmarui/p/18218924

相关文章

  • 「杂题乱刷」CF1977B
    题目链接CF1977B(luogu)CF1977B(codeforces)解题思路考虑通用做法。我们发现如果直接用二进制来表示的话这个数会只包含\(0,1\)这两个数字。发现这时阻碍我们构造的是连续的数字\(1\)。考虑消除连续的数字\(1\)。容易发现连续的数字\(1\)可以转化成将这一段最高位......
  • 「杂题乱刷」CF1977C
    题目链接CF1977C(luogu)CF1977C(codeforces)解题思路首先这题有一个简单的思路,就是当这个序列的LCM大于\(10^9\)时,显然取所有数字数字是合法的。然后我们接下来考虑LCM小于等于\(10^9\)的情况。发现这种情况LCM很小,且有一个简单的结论,就是你在序列中任选一个子......
  • 5月杂题
    CF1970G3Min-FundPrison(Hard)添加的边肯定是固定的,为连通块个数\(-1\)。跑个边双,问题转换成给一些数,可以把其中一个数分裂成两个(这两个数之和为原数),再分成两个集合\(A,B\),使得集合\(A\)的权和的平方加\(B\)权和的平方最小。可以用背包DP出第一个集合\(A\)的权和,设......
  • 「杂题乱刷」CF1650E
    题目链接CF1650E(luogu)CF1650E(codeforces)解题思路首先,你发现你只能改一个日期,那么我们肯定是改距离最近的旁边的两场考试,此时我们就可以将操作转化为删去一场考试并添加一场新考试的最小的休息时长,容易使用贪心\(O(n)\)解决。总时间复杂度\(O(n\log_2n)\),瓶颈在于......
  • 「杂题乱刷」CF1650F
    题目链接CF1650F(luogu)CF1650F(codeforces)解题思路我们发现要想让第\(i\)个数变换一次就需要给第\(i\simn\)中的一个位置做一次操作,因此我们很自然的就想到了倒推,容易证明这样是不劣的。时间复杂度\(O(n^2)\)。参考代码#include<bits/stdc++.h>usingnamespace......
  • 杂题选讲 cy
    CF1666KKingdomPartition我们首先钦定\(A\)点选了A,\(B\)点选了B,其它点选了C,这样会有一个代价。然后我们尝试将每个C点改成A或者改成B。我们将其看成一个物品,其代价为其所有向外的连边之和。而同时,对于每条边,如果其两端是不同的颜色,其会使代价减少\(2l\)。我们将......
  • 「杂题乱刷」CF1759F
    题目链接CF1759FAllPossibleDigits(luogu)CF1759FAllPossibleDigits(codeforces)题意简述有一个长度为\(n\)的\(p\)进制数,你需要求出至少通过几次操作才可以让\(0\simp-1\)这\(p\)个数字都至少出现过一遍(包括中间过程)。解题思路我们很容易就能发现答案是......
  • 「杂题乱刷」CF1973D
    链接算简单题。你发现最大值肯定可以用\(n\)次查出来。然后可以证明\(ans\le\frac{n}{k}\)。总次数为\(n+\frac{n}{k}\timesk\le2n\)。代码:点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打c......
  • 「杂题乱刷」AT_abc354_f
    大家一起来做下这个典题。链接(at)链接(luogu)我们很容易可以想到处理前后缀的最长上升子序列的长度,然后容易\(O(n\log_2n)\)预处理。做完了。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要......
  • 「杂题乱刷」洛谷 P10467
    题目链接P10467[CCC2007]SnowflakeSnowSnowflakes解题思路字符串哈希板子题。思路就是我们给每个数列的所有排列都哈希一个值,然后判断是否有不同的数列的哈希值相同,如果有,就输出Twinsnowflakesfound.,否则就输出Notwosnowflakesarealike.。参考代码这里使用双哈......