好久没有写博客了
csp模拟38
我是A题
真是服了，好好一个题怎么恶心的时间空间，自家oj的评测机真是欠修理。
考虑 \(z\) 从大到小时计算每层的剩下的值，割去的一定是一个阶梯状的图形，考虑到每一层，新增加的就是两条线割剩下的，且这两条线从上到下递增，维护前缀和计算就可以。
点击查看代码
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
#include<bits/stdc++.h>
#define max(x,y) (x)>(y)?(x):(y)
#define rg register
using namespace std;
const int N = 3e7 + 1;
typedef unsigned long long ull;
int n, A, B, C;
struct asd{
int x,y,z;
}a[N];
inline ull Rand (rg ull &k1, rg ull &k2) {
ull k3 = k1, k4 = k2;
k1 = k4;
k3 ^= (k3 << 23);
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return k2 + k4;
}
inline void print(__int128 x){
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+48);
}
inline bool amp(const asd &a,const asd &b){
return a.z>b.z;
}
inline int Mod(ull x,int p){
return x<p?x:x%p;
}
void GetData () {
ull x, y;
scanf("%d%d%d%d%llu%llu",&n,&A,&B,&C,&x,&y);
for (int i = 1; i <= n; ++i) {
a[i].x = Mod(Rand(x, y) , A) + 1;
a[i].y = Mod(Rand(x, y) , B) + 1;
a[i].z = Mod(Rand(x, y) , C) + 1;
if (Rand(x, y) % 3 == 0) a[i].x = A;
if (Rand(x, y) % 3 == 0) a[i].y = B;
if ((a[i].x != A) && (a[i].y != B)) a[i].z = C;
}
}
int ma[N];
__int128 sma[N];
int mb[N];
__int128 smb[N];
int la[N],lb[N];
signed main(){
GetData();
__int128 r=1;//r*
rg int h=a[1].z;
rg int tp=0;
for(rg int i=1;i<=n;++i){
h=max(h,a[i].z);
if(a[i].x==A) lb[a[i].z]=max(lb[a[i].z],a[i].y);
if(a[i].y==B) la[a[i].z]=max(la[a[i].z],a[i].x);
}
for(int i=1;i<=n;i++){
if(a[i].z==h){
ma[a[i].x]=max(ma[a[i].x],a[i].y);
mb[a[i].y]=max(mb[a[i].y],a[i].x);
}
}
__int128 ans=0;
__int128 sma1=0;
for(rg int i=A;i;--i){
ma[i]=max(ma[i],ma[i+1]);
sma1=sma1+r*ma[i];
}
for(rg int i=B;i;--i){
mb[i]=max(mb[i],mb[i+1]);
}
__int128 sma=0,smb=0;
ans+=r*A*B-sma1;
rg int sa=0,sb=0;
for(rg int i=h-1;i;--i){
if(sa<=la[i]){
for(int j=sa+1;j<=la[i];j++){
sma=sma+r*ma[j];
}
sa=la[i];
}
if(sb<=lb[i]){
for(int j=sb+1;j<=lb[i];j++){
smb=smb+r*mb[j];
}
sb=lb[i];
}
__int128 op;
if(sb==0) op=1;
else op=sb;
if(mb[op]<sa){
ans+=r*(A-sa)*(B-sb);
}
else{
__int128 s1=r*A*sb-smb;//(smb[1]-smb[sb+1]);
__int128 s2=r*B*sa-sma;//(sma[1]-sma[sa+1]);
ans+=r*A*B-sma1-s1-s2;
}
}
__int128 uk=r*A*B*C-ans-r*A*B*(C-h);
print(uk);
}
/*
100 99 98 97 114514 1919810
2 10 10 10 114514 1919810
1000 43112 88371 27391 114514 1919810
104349748515623
9 7 10
7 10 3
*/
我是B题
考试只会状压。
设 \(dp[i][j]\) 表示到第 \(i\) 个机器时，目标物品排名为 \(j\) 的概率。
这里采用刷表法好写一点：
枚举质量为 \(rnk\) 的物品；
初始值 \(dp[1][rnk]=1\)
转移方程：
\(dp[i+1][j−1]+=dp[i][j]×(1−(1−p_i)^{j−1})\) //删除的是 \(j\) 前面的数，不可能让 \(j\) 前面的数全部逃掉
\(dp[i+1][j]+=dp[i][j]×(1−p_i)^j\) //删除的是 \(j\) 后面的数，\(j\) 及 \(j\) 前面的数必须全部逃掉
答案 \(\sum_{rnk=1}^{n} dp[n][1] \times rnk\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int mgml(int x,int p){
x=(x+mod)%mod;
int ans=1;
while(p){
if(p&1) ans=(ans*x)%mod;
x=(x*x)%mod;
p>>=1;
}
return ans;
}
int dp[305][305];
int p[305];
int n;
int work(int d){
memset(dp,0,sizeof(dp));
dp[0][d-1]=1;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(dp[i][j]==0) continue;
dp[i+1][j]+=dp[i][j]*mgml(1-p[i+1],j+1)%mod;
dp[i+1][j]%=mod;
if(j>0) dp[i+1][j-1]+=(dp[i][j]*(1-mgml(1-p[i+1],j)+mod)%mod)%mod;
if(j>0) dp[i+1][j-1]%=mod;
}
}
return dp[n-1][0];
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<n;i++){
scanf("%lld",&p[i]);
}
int ans=0;
for(int i=1;i<=n;i++){
int d=work(i);
ans+=i*d%mod;
ans%=mod;
}
printf("%lld",ans);
}
我是C题
首先一次找出所有出现次数较小的数字比较耗时，我们可以找到任意一个出现次数不满足要求的数字，并且从这个数字处把区间分成两半进行递归，并不会影响正确性，还大大降低了编程复杂度。
但是由于分治两边可能不均等，会导致时间复杂度退化成 \(O(n^2)\) ,维护 \(cnt_i\) 表示 \(i\) 出现的次数。所以选择只遍历小的区间。第一遍删去小区间的值，然后递归大区间，第二遍加上小区间的值递归小区间，不合法的区间以及合法的区间统计完后记得删去 \(cnt\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],b[N];
int cnt[N],d[N];
int ans=0;
void solve(int l,int r){
if(r-l+1<b[r-l+1]){
for(int i=l;i<=r;i++){
cnt[a[i]]--;
}
return;
}
if(l==r){
if(b[1]<=1) ans=max(ans,ans);
cnt[a[l]]--;
return;
}
int mid=(l+r)/2;
int pos=-1,k=b[r-l+1];
for(int i=l;i<=r;i++){
if(cnt[a[i]]<k){
pos=i;
break;
}
}
if(pos==-1){
for(int i=l;i<=r;i++) cnt[a[i]]--;
ans=max(ans,r-l+1);
return;
}
if(pos<=mid){
for(int i=l;i<=pos;i++) cnt[a[i]]--;
solve(pos+1,r);
for(int i=l;i<pos;i++) cnt[a[i]]++;
solve(l,pos-1);
}
else{
for(int i=pos;i<=r;i++) cnt[a[i]]--;
solve(l,pos-1);
for(int i=pos+1;i<=r;i++) cnt[a[i]]++;
solve(pos+1,r);
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
cnt[a[i]]++;
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
solve(1,n);
cout<<ans<<endl;
}