Codeforces Round #841(A-D)
创始人
2024-05-02 10:53:10
0

A. Joey Takes Money

思路:

累乘在加上n-1即可

Code:

#include
#include
#include
#include
#include
typedef long long LL;
using namespace std;
void solve()
{int n;cin>>n;LL res=1;for(int i=1;i<=n;i++){int x;cin>>x;res*=x;}cout<<2022*(res+n-1)<<'\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int test;cin>>test;while(test--) solve();
}

B. Kill Demodogs

思路:

贪心:靠中心走。

求和化简得n*(n+1)*(2n+1)/3-n*(n+1)/2

Code:

#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;
const long long mod=1e9+7;
ll ksm(ll a,ll b)
{ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b/=2;}return res;
}
void solve()
{ll n;cin>>n;ll a,b,c;a=n%mod;b=(n+1)%mod;c=(2*n+1)%mod;ll res=a*b%mod*c%mod*ksm(3,mod-2)%mod;ll tmp=a*b%mod*ksm(2,mod-2)%mod;res=((res-tmp)%mod+mod)%mod*2022%mod;//注意相减可能为负cout<>test;while(test--) solve();
}

C. Even Subarrays 

思路:

维护前缀异或和数组s[]

区间[l,r]异或和为s[r]^s[l-1]

暴力枚举区间O(n^2)必超时

 因子个数为奇数的一定是平方数,可以枚举所有x,x^s[r]为平方数。考虑到ai的范围,平方数的大小不会超过512*512。

具体做法:枚举右端点,t[]数组维护前i-1个s[]值的个数,减去平方的即可。

Code:

#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;
const int N=4e6+10;
int a[N],s[N],t[N];
void solve()
{int n,mx=0;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]^a[i];mx=max(mx,a[i]);}for(int i=0;i<=10*mx;i++) t[i]=0;ll res=0;t[0]=1;for(int r=1;r<=n;r++){int cnt=0;for(int i=0;i<=513;i++){int tmp=s[r]^(i*i);cnt+=t[tmp];}t[s[r]]++;res+=(ll)r-cnt;}cout<>test;while(test--) solve();
}

 D. Valiant's New Map

思路:

边长具有单调性,考虑二分边长

如何判断矩形满足条件

暴力判断O(mid*mid)

考虑判断矩形大于mid的个数,维护数组b。如果a[i]>=mid b[i]=1,否则b[i]=0.

在维护前缀和prefix,即为数组中大于mid的个数,就可以O(1)判断矩形是否满足条件

时间复杂度(n*m*log(n))

Code:

#pragma GCC optimize(2)
#include
#include
#include
#include
#include
#include
#define endl "\n"
typedef long long LL;
using namespace std;
int n,m;
bool check(int mid,vector> a)
{vector> sum(n+1,vector(m+1));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(a[i][j]>=mid) a[i][j]=1;else a[i][j]=0; sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(i+mid-1>n||j+mid-1>m) continue;int tmp=sum[i-1][j-1]+sum[i+mid-1][j+mid-1]-sum[i-1][j+mid-1]-sum[i+mid-1][j-1];if(tmp>=mid*mid) return true;}return false;
}
void solve()
{cin>>n>>m;vector> a(n+1,vector(m+1));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];int l=0,r=min(n,m)+1;while(l+1>test;while(test--) solve();
}

tips:

一开始我把计算矩阵和写为函数cal(int x1,int y1,int x2,int y2,vector> sum)

时间超限了。

我猜是因为以数组为形参会把数组的数都遍历一遍,就和暴力的复杂度一样了 

相关内容

热门资讯

安卓双系统添加应用,轻松实现多... 你有没有想过,你的安卓手机里可以同时运行两个系统呢?听起来是不是很酷?想象一边是熟悉的安卓系统,一边...
pipo安卓进系统慢,探究pi... 最近是不是发现你的Pipo安卓系统更新或者运行起来特别慢?别急,今天就来给你好好分析分析这个问题,让...
怎样使用安卓手机系统,安卓手机... 你有没有发现,安卓手机已经成为我们生活中不可或缺的一部分呢?从早晨闹钟响起,到晚上睡前刷剧,安卓手机...
双系统安卓安装caj,轻松实现... 你有没有想过,你的安卓手机里装上双系统,是不是就能同时享受安卓和Windows系统的乐趣呢?没错,这...
安卓使用ios系统教程,安卓用... 你是不是也和我一样,对安卓手机上的iOS系统充满了好奇?想要体验一下苹果的优雅和流畅?别急,今天我就...
安卓系统gps快速定位,畅享便... 你有没有遇到过这样的情况:手机里装了各种地图导航软件,但每次出门前都要等上好几分钟才能定位成功,急得...
安卓手机系统更新原理,原理与流... 你有没有发现,你的安卓手机最近是不是总在提醒你更新系统呢?别急,别急,让我来给你揭秘一下安卓手机系统...
安卓系统通知管理,全面解析与优... 你有没有发现,手机里的通知就像是一群调皮的小精灵,时不时地跳出来和你互动?没错,说的就是安卓系统的通...
安卓系统手机哪买,揭秘哪里购买... 你有没有想过,拥有一部安卓系统手机是多么酷的事情呢?想象你可以自由安装各种应用,不受限制地探索各种功...
安卓系统 ipv4,基于安卓系... 你知道吗?在智能手机的世界里,有一个系统可是无人不知、无人不晓,那就是安卓系统。而在这个庞大的安卓家...
目前安卓是什么系统,探索安卓系... 亲爱的读者,你是否曾好奇过,如今安卓系统究竟是什么模样?在这个科技飞速发展的时代,操作系统如同人体的...
安卓6.0系统比5.0,从5.... 你有没有发现,自从手机更新了安卓6.0系统,感觉整个人都清爽了不少呢?没错,今天咱们就来聊聊这个话题...
安卓2.36系统升级,功能革新... 你知道吗?最近安卓系统又来了一次大变身,那就是安卓2.36系统升级!这可不是一个小打小闹的更新,而是...
安卓系统源码怎么打开,并可能需... 你有没有想过,安卓系统的源码就像是一扇神秘的门,隐藏着无数的技术秘密?想要打开这扇门,你得掌握一些小...
安卓8.0系统体验视频,智能革... 你有没有听说安卓8.0系统最近可是火得一塌糊涂啊!作为一个紧跟科技潮流的数码达人,我当然要来给你好好...
宣传系统漫画app安卓,探索安... 亲爱的读者们,你是否曾在某个午后,百无聊赖地打开手机,想要寻找一些轻松愉悦的读物?今天,我要给你介绍...
鸿蒙替换安卓系统吗,开启智能生... 你知道吗?最近科技圈里可是炸开了锅,因为华为的新操作系统鸿蒙系统,据说要大举进军手机市场,替换掉安卓...
手机安卓系统深度清理,解锁手机... 手机里的东西是不是越来越多,感觉就像一个装满了杂物的储物柜?别急,今天就来教你一招——手机安卓系统深...
安卓上的windows系统,融... 你有没有想过,在安卓手机上也能体验到Windows系统的魅力呢?没错,这就是今天我要跟你分享的神奇故...
安卓系统焦点变化事件,Andr... 你知道吗?在安卓系统的世界里,最近发生了一件超级有趣的事情——焦点变化事件。这可不是什么小打小闹,它...