浙江广厦大学第七届程序设计竞赛-题解

A 种植所有植物所需时间

累加 n 个植物所需的阳光总和除以 50 向上取整即是需要获得的阳光次数

每次获取阳光需要 5 秒,乘以 5 即是答案,时间复杂度 O(n)

注意输入较多,请使用较快读入方式

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
const int N=3e5+10;
ll t,sum;
int main() {
	IOS
	cin>>t;
	while(t--) {
		ll x; cin>>x;
		sum+=x;
	}
	cout<<((sum-1)/50+1)*5;
    return 0;
}

B 小马喝水

以 x 轴为轴作马厩的对称点,两点之间直线最短

算出小马和对称点的两点之间距离,向下取整即是答案

因为距离较大,可以用__int128来存,以及用二分答案来逼近开根后的值,时间复杂度 O( log w )

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
typedef __int128 i8;
const int N=3e5+10;
i8 dis(i8 x1,i8 y1,i8 x2,i8 y2) {
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int main() {
	ll x1,y1,x2,y2,ans;
	cin>>x1>>y1>>x2>>y2; y2*=-1;
	i8 ds=dis(x1,y1,x2,y2);
	i8 l=0,r=1e18;
	while(l<r) {
		i8 mid=(l+r+1)>>1;
		if(mid*mid<=ds) l=mid;
		else r=mid-1;
	}
	cout<<(ans=r);
	return 0;
}

C 菠萝蜜多斩

对于一个区间,求区间内出现次数为奇数次的数的异或和就是这个区间的异或和,设为 x

所以我们可以通过求出区间内所有不同的数的异或和,设为 y,x 异或 y 即是答案

x 可以简单地通过前缀数组的形式求出,求出 y 的一种方法是用离线排序+树状数组,时间复杂度 O( m×log n )

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vii;
typedef vector<string> vs;
typedef vector<char> vc;
const int N=1e6+10;
int n,m,k=1e6;
int p[N],f[N],xo;
int ans[N],pos[N];
struct l {
	int l,r,id;
};
vector<l> g;
int c[N];
int lowbit(int x) {
	return x&(-x);
}
void add(int x,int d) {
	for(int i=x;i<=k;i+=lowbit(i)) c[i]^=d;
}
int qry(int x) {
	int res=0;
	for(int i=x;i>=1;i-=lowbit(i)) res^=c[i];
	return res; 
}
map<int,int> mp;
bool cmp(l &a,l &b) {
	return a.l<b.l;
}
int main() {
	IOS
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>p[i];
		f[i]=f[i-1]^p[i];
	}
	for(int i=1;i<=m;i++) {
		int l,r; cin>>l>>r;
		ans[i]=f[r]^f[l-1];
		g.push_back({l,r,i});
	}
	sort(g.begin(),g.end(),cmp);
	for(int i=1;i<=n;i++) {
		if(!mp[p[i]]++) add(i,p[i]);
	}
	for(int i=1;i<=n;i++) mp[p[i]]=n+1;
	for(int i=n;i>=1;i--) {
		pos[i]=mp[p[i]];
		mp[p[i]]=i;
	}
	int left=1;
	for(auto i:g) {
		while(left<i.l) add(pos[left],p[left]),left++;
		ans[i.id]^=(qry(i.r)^qry(i.l-1));
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
	return 0;
}

D 扫雷游戏

签到题,根据条件分类讨论,按题意统计模拟即可,时间复杂度 O(n×m×8)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
const int inf=0x3f;
const int N=1e3+10;
int n,m;
int p[N][N],ans[N][N];
int xx[8]={0,0,1,-1,1,-1,1,-1};
int yy[8]={1,-1,0,0,1,-1,-1,1};
int main() {
	IOS
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		string s; cin>>s;
		for(int j=1;j<=m;j++) {
			if(s[j-1]=='*') p[i][j]=1;
		}
	}
	memset(ans,-1,sizeof(ans));
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			if(p[i][j]) continue;
			for(int k=0;k<8;k++) {
				int dx=i+xx[k];
				int dy=j+yy[k];
				if(dx<1||dx>n||dy<1||dy>m) continue;
				if(p[dx][dy]==0) continue;
				ans[i][j]++;
			}
			ans[i][j]++;
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			cout<<ans[i][j]<<' ';
		}
		cout<<endl;
	}
    return 0;
}

E 始皇一问

在题目限制条件下,从 (1,1) 走到 (n,m) 一共会走 n+m-2 步

题目所求方案数可以看作从 n+m-2 步中选 m-1 步往右走,所以答案即是 C(n+m-2,m-1)

可以预处理组合数来计算,时间复杂度 O(n)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
const int inf=0x3f;
const int mod=998244353;
const int N=2e6+10;
ll q[N];
ll inv[N];
ll pow_mod(ll a,ll b) {
	ll res=1;
	while(b) {
		if(b&1) res=(res*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return res;
}
void init() {
	q[0]=1;
	for(int i=1;i<N;i++) q[i]=q[i-1]*i%mod;
	inv[N-1]=pow_mod(q[N-1],mod-2);
	for(int i=N-1;i>=1;i--) inv[i-1]=inv[i]*i%mod;
}
ll C(ll n,ll m) {
	if(n<m||n<0||m<0) return 0;
    if(n==m||m==0) return 1;
	return q[n]*inv[m]%mod*inv[n-m]%mod;
}
int main() {
	int t;
	cin>>t;
    init();
	while(t--) {
		ll n,m; cin>>n>>m;
		cout<<C(n+m-2,m-1)<<endl;
	} 
    return 0;
}

F 压缩文章

签到题,遍历+判断字符即可,时间复杂度 O(n)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
int n,now=-1,cnt;
string s;
int main() {
	cin>>s;
	s+='#';
	string ans;
	for(auto i:s) {
		if(i==now) cnt++;
        else if(now<0) now=i,cnt=1;
		else {
			ans+=to_string(cnt);
			ans+=(char)now;
            now=i,cnt=1;
		}
	}
	cout<<ans;
    return 0;
}

G 原神启动 (hard版本)

二分答案 x,考虑如何 check ,因为原石在积攒了超过一次抽奖的价格后,再攒下去无疑是不优的,所以直接贪心,攒够了原石就抽掉,不难想到贪心的一个实现方法是直接遍历 n 次活动,攒够就抽,但这样会超时

考虑优化,积攒原石的的过程显然并不重要,我们只需要在每一次抽完后知道下一次攒够原石的位置即可,用前缀和+二分来得到这个位置,一旦抽的次数超过 k 说明二分的值有效,时间复杂度 O( k × log w × log n)

注意输入较多,请使用较快读入方式,以及特判 n < k 的情况

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef vector<char> vc;
const int inf=0x3f;
const int N=1e7+5;
ll n,k,p[N],q[N];
bool check(ll x) {
	ll now=0,cnt=0;
	while(now<=n) {
		auto it=lower_bound(q+1,q+n+1,q[now]+x)-q;
		if(it<=n) now=it,cnt++;
		else return 0;
		if(cnt>=k) return 1;
	}
	return cnt>=k;
}
int main() {
	IOS
	cin>>n>>k;
	if(n<k) {
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=n;i++) {
		cin>>p[i];
		q[i]=q[i-1]+p[i];
	}
	ll l=1,r=q[n];
	while(l<r) {
		ll mid=(l+r+1)>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l;
    return 0;
}

H 原神启动 (easy版本)

会发现原石可以累积到 n 次活动结束后再一起抽

统计原石总数 sum,x 即为 sum 除以 k 向下取整,注意特判 n < k 的情况,时间复杂度 O(n)

注意输入较多,请使用较快读入方式

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
const int inf=0x3f;
const int N=1e7+10;
ll n,k,sum;
int main() {
	IOS
	cin>>n>>k;
	for(int i=1;i<=n;i++) {
		ll x; cin>>x;
		sum+=x;
	}
	ll ans=sum/k;
	if(ans==0) ans=-1;
	cout<<ans;
    return 0;
}

I 古神话

可以遍历每一个格子,求出所有以该格子为右下角的所有全 0 矩形的个数,统计后即答案

对于每一个空格子,可以在线性复杂度下预处理出其上方有几个空格子,这个值设为 g(i,j)

对于每一个作为右下角的格子 (x,y),g(x,y) 即以 (x,y) 为右下角,底长为 1 的矩形的最大高度

会发现,随着矩形的左边往左扩散,底长会单调递增,最大高度会单调不升,直到底边无法往左扩散

会发现底长的增长是规律的,而最大高度从最大的 y' 满足 y' < y 且 g(x,y') < g(x,y) 的时候才会开始减少

我们可以用单调栈找到最大的 y' ,并用前缀和配合统计贡献,时间复杂度 O(n×m)。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef vector<char> vc;
const int N=5000+5;
int n,m;
short p[N][N];
short h[N][N];
short l[N][N];
ll s[N];
int main() {
	IOS
	cin>>n>>m;
	for(ll i=1;i<=n;i++) {
		for(ll j=1;j<=m;j++) {
			cin>>p[i][j]; p[i][j]^=1;
			if(p[i][j]) h[i][j]=h[i-1][j]+1;
		}
	}
	ll res=0;
	for(ll i=1;i<=n;i++) {
		memset(s,0,sizeof(s));
		for(ll j=1;j<=m;j++) {
			if(p[i][j]==0) continue;
			l[i][j]=j-1;
			while(l[i][j]>0&&h[i][l[i][j]]>=h[i][j]) l[i][j]=l[i][l[i][j]];
			s[j]=s[l[i][j]]+h[i][j]*(j-l[i][j]);
			res+=s[j];
		}
	}
	cout<<res%(10000000007)<<endl;
	return 0;
}

J 青铜门下

对于一个后缀,其母序列的长度是固定的,所以我们对每个后缀,考虑其权值不为 0 的母序列个数

设当前后缀的长度为 k ,后缀中 0 的个数为 c0 ,1 的个数为 c1,那么母序列还有 k-1 个位置可以填,那么如果要使母序列的第一个数是序列众数,假设第一个数是 0,则在 k-1 个位置中至少还要填 c1 个 0,在这个限制下,母序列的个数是: F(k,0)=C(k-1,c1)+C(k-1,c1+1)+...+C(k-1,k-1),直接遍历算会 TLE

考虑优化,注意到在顺序遍历每个后缀的情况下,每一次的后缀可以看作是上一次的后缀接上一个数,所以我们可以维护两个数 F0 和 F1,代表 F(k,0) 和 F(k,1),k 每次会加上一,c0 和 c1 会实时更新,分类讨论新接上的数是 0 或 1 的情况,维护 F0 和 F1,在更新 F0 的情况下,第一种情况是后缀新接上的数是 0,F0=C(k-1,c1)+...+C(k-1,k-1) 变成 F0'=C(k,c1)+... + C(k,k),可以通过组合递推式得出 F0'=F0×2+C(k-1,c1-1),类似地可得 F1'=F1×2+C(k-1,c0-2)-C(k,c0-1),新接上的数是 1 同理,时间复杂度 O(n)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef vector<char> vc;
const int inf=0x3f;
const int N=1e6+10;
const int mod=100000007;
ll pow_mod(ll a,ll b) {
	ll res=1;
	while(b) {
		if(b&1) res=(res*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return res%mod;
}
ll q[N];
ll inv[N];
void init() {
	q[0]=1;
	for(int i=1;i<N;i++) q[i]=q[i-1]*i%mod;
	inv[N-1]=pow_mod(q[N-1],mod-2);
	for(int i=N-1;i>=1;i--) inv[i-1]=inv[i]*i%mod;
}
ll C(ll n,ll m) {
	if(n<m) return 0;
	if(n==m||m==0) return 1;
	if(n<0||m<0) return 0;
	return q[n]*inv[m]%mod*inv[n-m]%mod;
}
ll n,m,p[N],c[2],d[2],res;
int main() {
	IOS
	init();
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i];
	reverse(p+1,p+n+1);
	for(ll i=0;i<n;i++) {
		ll x=p[i+1],sum=0; c[x]++;
		if(x) {
			d[1]=C(i-1,c[0]-1)+d[1]+d[1]; d[1]=(d[1]%mod+mod)%mod;
			d[0]=C(i-1,c[1]-2)+d[0]+d[0]-C(i,c[1]-1); d[0]=(d[0]%mod+mod)%mod;
			sum=(sum+d[1])%mod;
		}
		else {
			d[0]=C(i-1,c[1]-1)+d[0]+d[0]; d[0]=(d[0]%mod+mod)%mod;
			d[1]=C(i-1,c[0]-2)+d[1]+d[1]-C(i,c[0]-1); d[1]=(d[1]%mod+mod)%mod;
			sum=(sum+d[0])%mod;
		}
		res=(res+sum*(i<<1|1))%mod;
	}
	cout<<(res%mod+mod)%mod;
	return 0;
}

全部评论
I题我看了30分钟都没看出题意
1
送花
回复 分享
发布于 06-12 11:32 浙江
爱了
点赞
送花
回复 分享
发布于 06-11 23:00 浙江
秋招专场
校招火热招聘中
官网直投
哥们模数太幽默
点赞
送花
回复 分享
发布于 06-12 07:15 江苏
c的y怎么算的不太懂啊
点赞
送花
回复 分享
发布于 06-12 22:13 黑龙江
这把比赛我感觉不好的有几个点 1.考快读对其他语言不太友好 2.题意有点不清晰,如果实在写不明白题意可以弄个样例解释 3.模数有点不太合常理,1e10+7和1e8+7是测试数0吗?
点赞
送花
回复 分享
发布于 06-12 22:15 湖南

相关推荐

点赞 评论 收藏
分享
6 4 评论
分享
牛客网
牛客企业服务