浙江广厦大学第七届程序设计竞赛-题解
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;
}
