好久没写题了……
最近好像能做出2D了,不过上分还是困难。
比赛传送门
这场出题人作的要死,对于题面内容这里不再提。
本场关键词
贪心、找规律、前缀和、二分
A.Park Lighting
题意
给你$n\times m$的网格,你可以在两个网格之间的边上放一个灯,这个灯将会照亮这两个网格。
求出照亮所有的$n\times m$个格子的最小需要的灯数。
思路
贪心,只要$n$和$m$中间有一个是偶数,那么答案就是总格子数除以二;如果都为奇数,那么先暂时去掉一行,将这部分如上计算,再对剩下这一行贪心考虑。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007; signed main() { int t,n,m; cin>>t; while(t--) { cin>>n>>m; ll ans=0; if(n%2==0) ans=n/2*m; else if(m%2==0) ans=m/2*n; else{ ans=n/2*m; ans+=m/2+1; } cout<<ans<<endl; } return 0; }
|
B.Maria Breaks the Self-isolation
题意
小M在办聚会,他现在想邀请$n$个人,第$i$个人有一个数值$a_i$,表示当他到小M家时,如果在场的人(不包括他自己)达到$a_i$,这个人就会留下。
求这场聚会最多可以邀请多少人,人数包括小M。
思路
排序之后贪心,如果$a_i$被邀请了,那么数值小于等于$a_i$的人一定也会被邀请。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007; ll a[maxn]; signed main() { int t,n; cin>>t; while(t--) { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; ll ans=0,tot=0; sort(a+1,a+n+1); for(int i=1;i<=n;i++) { tot++; if(a[i]<=tot) ans=tot; } cout<<ans+1<<endl; } return 0; }
|
C.Celex Update
题意

给你一个按照上图规律无限扩展的矩阵。
有$t$组询问,每组$x_1,y_1,x_2,y_2$四个整数,保证$x_1\le x_2\ ,y_1\le y_2$,输出$(x_1,y_1)$到$(x_2,y_2)$的所有路径中,权值和不同的路径个数。
$(x,y)$表示在第$x$行$y$列,只能向下或向右行走。
思路
找规律,组合数学
猜一发所有合法路径不会有权值和相同的情况,那么的话单纯计算路径数量只和$x_2-x_1$与$y_2-y_1$有关,$ans=(x_2-x_1)\times (y_2-y_1)+1$。
我也不知道怎么证明……
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| #include<bits/stdc++.h> using namespace std; typedef long long ll; signed main() { ll t,x1,x2,y1,y2; cin>>t; while(t--) { cin>>x1>>y1>>x2>>y2; ll n=x2-x1,m=y2-y1,ans; cout<<n*m+1<<endl; } return 0; }
|
D.The Best Vacation
题意
你将选择一段时间和小C连续在一起度过$x$天假期。
这里一年有$n$个月,第$i$个月有$d_i$天,当你在每个月第$j$日和小C在一起时,他将给你$j$个拥抱。
求你最多能得到多少拥抱数。
保证$1\le x\le d_1+d_2+\dots +d_n$
思路
贪心+前缀和+二分
首先$n$已经达到了2e5,所以我们不可能枚举每一天作为起始点或者结束点。考虑枚举每个月时,可以发现将每个月最后一天作为结束点时是最优的,而因为$x\le d_1+d_2+\dots +d_n$,所以度假期最多只可能跨一次年。
所以这里将$n$翻倍,将相邻两年拼接起来,记$sum2[i]$为第$1$月到第$i$月的累积贡献,$sum3[i]$为第$1$月到第$i$月的累积天数,当确定了结尾的月份时,在$sum3$上二分出起始点所在月份,中间的月份的贡献通过$sum2$查询,在起始点所在月份计算剩余天数的贡献。
记录其中出现的最大值即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| #include<bits/stdc++.h> using namespace std; typedef long long ll; #define int ll const int maxn=1e6+10,inf=0x3f3f3f3f,mod=1000000007; int d[maxn],sum[maxn],sum2[maxn],sum3[maxn]; int get(int a,int b,int n) { return sum[b+n-1]-sum[b-1]; } int getm(int a,int x,int n) { int l=1,r=a,ans=0; while(l<=r) { int mid=(l+r)>>1; if(sum3[a]-sum3[mid-1]>=x) l=mid+1,ans=mid; else r=mid-1; } return ans; } signed main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #ifdef DEBUG freopen("input.in", "r", stdin); #endif for(int i=1;i<maxn;i++) sum[i]=sum[i-1]+i; int n,x,ans=0; cin>>n>>x; for(int i=1;i<=n;i++) cin>>d[i]; for(int i=1;i<=2*n;i++) { sum2[i]=sum2[i-1]; sum3[i]=sum3[i-1]; if(i<=n) sum2[i]+=get(i,1,d[i]),sum3[i]+=d[i]; else sum2[i]+=get(i-n,1,d[i-n]),sum3[i]+=d[i-n]; } for(int i=n+1;i<=2*n;i++) { int now=get(i,max(1ll,d[i-n]-x+1),min(x,d[i-n])),ret,tar; if(d[i-n]>=x) { ans=max(ans,now); continue; } else ret=x-d[i-n]; tar=getm(i-1,ret,n); now+=sum2[i-1]-sum2[tar]; ret-=sum3[i-1]-sum3[tar]; if(tar<=n) now+=get(tar,d[tar]-ret+1,ret); else now+=get(tar,d[tar-n]-ret+1,ret); ans=max(ans,now); } cout<<ans<<endl; return 0; }
|
E.Are You Fired?
哇这题好难搞,看了题解也不是很理解。
题意
给定一个长度为$n$的数组,其中前 $\left\lceil\dfrac{n}{2}\right\rceil$ 项中第$i$项的值为$a_i$,后面所有项值均为$x$。
现在要你确定一个整数$k$,使得数组中任意一个长度为$k$的子段和$>0$,若不存在则输出$-1$。
思路
当有一个$k’\le \left\lfloor\dfrac{1}{n}\right\rfloor$符合条件时,可以确定$k=2k’$一定同样成立,这就说明假如存在解,就一定存在$k>\dfrac {n}{2}$成立。
当$x\geqslant 0$时,可以确定最优情况为$k=n$,判断即可。
否则接着深入研究,尝试找出对每个长度$k$,出现的最小$k$长度子段和。
记$p$为长度为$k$的字段和$s$的差分数组,$s1=a_1+a_2+\dots +a_k$。
而$s{i+1}=s{i}+a{i+k}-ai$,因为$k>\dfrac {n}{2}$,则$a{i+k}=x$。
即$p=[s1,x-a_1,x-a_2,\dots ,x-a_n-k]$。
当$k$增大了$1$时,差分数组$p$的首项$+x$,并去掉最后一项。
任意$k$长度的首项都可以用前缀和$sum$求出。
另开一个$dp$数组,$dp[i]$表示对于$\sum\limits{j=1}^ix-a_j$过程中出现的最小和,用来表示$k=n-i$的差分数组中出现的最小差分前缀和。
然后枚举下$k$,检查一下$sum[k]+dp[n-k]>0$,存在则直接输出。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>pii; #define int ll const int maxn=5e5+10,inf=0x3f3f3f3f,mod=1000000007;
void read(){} template<typename T,typename... T2>inline void read(T &x,T2 &... oth) { x=0; int ch=getchar(),f=0; while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();} while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} if(f)x=-x; read(oth...); } int a[maxn],sum[maxn]; signed main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #ifdef DEBUG freopen("input.in", "r", stdin); #endif int n,lim,x; cin>>n; lim=n/2+(n%2); for(int i=1;i<=lim;i++) cin>>a[i],sum[i]=sum[i-1]+a[i]; cin>>x; for(int i=lim+1;i<=n;i++) sum[i]=sum[i-1]+(a[i]=x); if(x>=0) { cout<<((sum[n]>0)?n:-1)<<endl; return 0; } vector<int>dp(maxn,0); for(int i=1,tot=0;i<=lim;i++) { tot+=x-a[i]; dp[i]=min(dp[i-1],tot); } for(int k=lim;k<=n;k++) { if(sum[k]+dp[n-k]>0) { cout<<k<<endl; return 0; } } cout<<-1<<endl; return 0; }
|