简单题目指 黄+ ~ 蓝
Easy
考虑朴素 dp，设 \(dp[i][j]\)，表示第 \(j\) 轮球在 \(i\) 手中的方案数，时间复杂度 \(O(nm)\)。
观察到如果两个人均不是 \(1\) 号且没有传球和接球的限制，那么这两个人本质相同，于是第一维总共只有 \(O(k)\) 个，时间复杂度 \(O(km)\)。
Code
1Easy
枚举第一次取前 \(i\) 个数，令这些数之和为 \(s\)，看对于此种情况有哪些 \(x\) 能够满足。
若后面无论取多少个数其和都不及 \(s\)，则 \(x\in[s,+\infty)\) 全部满足。
否则二分找到之后第一个数 \(k\) 满足 \((i+1,k]\) 的和 \(s'>s\)，则 \(x\in[s,s')\) 全部满足。
观察到满足可以视作区间加，差分维护即可。
Code
#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
#define timeused() (double)clock()/CLOCKS_PER_SEC
#define rep(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define repp(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x){
T f=1;x=0;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
x*=f;
return x;
}
ll n,a[1000005],k,cf[1000005];
int main(){
rd(n);
rep(i,1,n){
rd(a[i]);
a[i]+=a[i-1];
}
rd(k);
rep(i,1,n){
if(a[n]<2*a[i]){
if(a[i]<=k) ++cf[a[i]];
continue;
}
ll l=i+1,r=n;
while(r-l>1){
ll mid=l+r>>1;
if(a[mid]>=2*a[i]) r=mid;
else l=mid+1;
}
if(a[l]>=2*a[i]) r=l;
//printf("%lld ",a[i]);
if(a[i]<=k) ++cf[a[i]];
if(a[r]-a[i]<=k) --cf[a[r]-a[i]];
}
ll cnt=0;
rep(i,1,k){
cf[i]+=cf[i-1];
if(cf[i]) ++cnt;
}
printf("%lld\n",cnt);
rep(i,1,k) if(cf[i]) printf("%d ",i);
}
Easy
按位直接算即可。
Code
#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
#define timeused() (double)clock()/CLOCKS_PER_SEC
#define rep(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define repp(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x){
T f=1;x=0;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
x*=f;
return x;
}
unsigned int n,a[500005],cnt[45],ans;
int main(){
rd(n);
rep(i,1,n){
rd(a[i]);
rep(j,0,31) cnt[j]+=(a[i]>>j)&1;
}
rep(i,0,31) ans+=((n*n-(n-cnt[i])*(n-cnt[i]))*(n*n-cnt[i]*cnt[i])+(n-cnt[i])*(n-cnt[i])*cnt[i]*cnt[i])<<i;
cout<<ans;
}
Easy
先考虑序列中无 \(1\) 的情况。
显然，当一个数旁边有一个 \(1\) 的时候肯定比没有 \(1\) 最优，根据这个采取贪心策略，枚举最后一个被删的数的位置 \(x\)，则它被删的时候两边都是 \(1\)，其左边的所有数从左往右删，其右边的所有数从右往左删（均是为了给每个数凑上一个 \(1\)），维护前缀后缀相邻乘积和可以做到 \(O(n)\)。
序列中有 \(1\) 的话，观察到 \(1\) 把数列分成了独立的若干段，对每段分别求解即可。
Code
#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
#define timeused() (double)clock()/CLOCKS_PER_SEC
#define rep(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define repp(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x){
T f=1;x=0;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
x*=f;
return x;
}
ll n,a[1000005],qz[1000005],hz[1000005],ans;
ll solve(ll l,ll r){
if(l>r) return 0;
rep(i,l,r){
qz[i]=a[i]*a[i+1];
hz[i]=a[i]*a[i-1];
}
rep(i,l,r) qz[i]+=qz[i-1];
repp(i,r,l) hz[i]+=hz[i+1];
ll anss=1ll*inf*inf;
rep(i,l,r) anss=min(anss,a[i]+qz[i-1]+hz[i+1]);
rep(i,l,r) qz[i]=hz[i]=0;
return anss;
}
int main(){
rd(n);
rep(i,1,n) rd(a[i]);
ll lst=0;
rep(i,1,n){
if(a[i]==1){
ans+=solve(lst+1,i-1)+1;
lst=i;
}
}
ans+=solve(lst+1,n);
printf("%lld",ans);
}