12-15模拟赛
其实很简单，其实真的很烂到家了:(
T1 坦克
考虑一次性快进到减少或者减少的时间，需要的回合数，然后算出回合之后的状态 。
重复这个过程，直到某一方的坦克被打完，时间复杂度\(O(n+m)\)
很简单的一道小模拟，记录每回合的损失情况，处理好盈余攻击力即可
代码如下（有些丑）
#include<bits/stdc++.h>
using namespace std;
int T;
int n,m,a,b,vm,vn,jx,jy,bn,bm;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;
for(int i=1;i<=T;i++){
cin>>n>>m>>a>>b;
vm=a,vn=b;//盈余攻击力
while(n&&m){
jx=jy=0;//每回合双方会被消灭的坦克数
int xn=n,xm=m;//双方攻击力
if(xn>=vm){
xn-=vm,jy++;
if(xn>=a){
bm=xn/a;
jy+=bm;
if(xn%a) vm=a-(xn%a);
else vm=a;
}
else vm=a-xn;
}
else vm-=xn;
if(xm>=vn){
xm-=vn,jx++;
if(xm>=b){
bn=xm/b;
jx+=bn;
if(xm%b) vn=b-(xm%b);
else vn=b;
}
else vn=b-xm;
}
else vn-=xm;
n-=jx,m-=jy;
if(n<=0){
cout<<"0"<<"\n";
break;
}
else if(m<=0){
cout<<n<<"\n";
break;
}
}
}
return 0;
}
但是我的赛时代码成功的零分了(大胜利
补充 \(j0,j1,jn;y0,y1,yn\) 均包含于cmath头文件当然我只记住了y0,y1,yn，警钟撅烂
T2 火柴棍
csp2024-j组T3,只是加了一个取模
代码如下
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244853;
int T,n,num;
long long pw[150000],lz[150000],ans;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
pw[0]=1;
for(int i=1;i<=149999;i++) lz[i]=(lz[i-1]*10+1)%mod,pw[i]=pw[i-1]*10%mod;
cin>>T;
while(T--){
cin>>n;
if(n<7){
if(n==2) cout<<"1\n";
if(n==3) cout<<"7\n";
if(n==4) cout<<"4\n";
if(n==5) cout<<"2\n";
if(n==6) cout<<"0\n";
continue;
}
num=n/7,n=n%7,ans=0;
if(n==1) num--,ans=10;
if(n==2) ans=1;
if(n==3){
if(num>1) num-=2,ans=200;
else num--, ans=22;
}
if(n==4) num--,ans=20;
if(n==5) ans=2;
if(n==6) ans=6;
cout<<(ans*pw[num]%mod+lz[num]%mod*8%mod)%mod<<"\n";
}
return 0;
}
分讨模数，预处理8的字符串即可
以后这种大考结束后，切记把题都看一遍，改一遍，说不定哪天就会考到
T3 子集计数
计数DP是比较容易想到的，暴力做法就是每次枚举从 \(1\) 到 \(i-1\) 的$ a_{i}$ ，满足子集关系则加上答案，时间复杂度 \(O(n^2)\)，可以拿到20分。（ 补充一些二进制下判断子集的方法：\(a \wedge b == a\) , \(a \vee b == b\) 均表示 \(a\) 是 \(b\) 的子集 ps: \(\wedge\) 代表&， \(\vee\) 代表| ）代码如下
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,a[100005],dp[100005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(a[j]<=a[i]&&(a[j]|a[i])==a[i])dp[i]+=dp[j];
}
cout<<dp[i]<<"\n";
}
return 0;
}
考虑优化：
观察到数据范围 \(2^{16}\) ，这其实是一个并不大的数，我们有两种方向可以考虑
1、从 \(a_{i}\) 的子集出发：
设 \(g_{s}\)是所有 \(a_{j} = s\) 的 \(f_j\) 之和
转移时枚举 \(s \subseteq a_i , f_i \leftarrow g_s\)（ 时间复杂度 \(O(2^m)\) )
转移后 \(g_{a_i} \leftarrow f_i\)
这样的时间复杂度是 \(O(n·2^m)\) ，期望30分
2、从包含 \(a_i\) 的集合出发：
设 \(g_s\) 是所有\(a_j \subseteq s\) 的 \(f_j\) 之和
转移时 \(f_i \leftarrow g_{a_i}\)
转移后枚举 \(s\) 满足 \(a_i \subseteq s , g_s \leftarrow f_i\) ( 时间复杂度 $O(2^m) )
时间复杂度仍为 \(O(n·2^m)\) ，30分
然后呢？
我们发现两个转移方法的复杂度瓶颈都在枚举包含或包含于的集合上，这是直接跟 \(log2(a_i)\) 挂钩的，并且 \(a_i \leq 2_{16}\)
那么对单个 \(a_i\) ，运用状压的思想，将它折半，就可以用两个不大于 \(2_{16}\) 的数表示出来
同样的， \(g\) 数组也可以用这样的思想存储（ 不要被固化思维误导，一个 \(2^8\) 的二维数组是完全开的下的 ），在它的二维中，一位存相等，一位存包含于的集合，这样不论在转移还是更新是，都只需要枚举一维，另一位是可以直接表示出来的，时间复杂度就成功的缩减到了 \(O(n·2^{m/2})\) !
形式化的，我们设 \(g_{s,t}\) 表示 \(a_j>>8 \subseteq s\) 且 \(a_j \wedge 256 = t\) 的所有 \(f_j\) 的和 （ \(a_j>>8\) 即取二进制前八位 ，\(a_j \wedge 255\) 即取二进制后八位 ）
转移时枚举 \(t \subseteq a \wedge 255\) ，令 \(s=a_i>>8\) ，\(f_i \leftarrow g_{s,t}\)
转移后枚举 \(s\) 满足 \(a_i>>8 \subseteq s\) ，令 \(t=a_i \wedge 255\) ，\(g_{s,t} \leftarrow f_i\)
时间复杂度 \(O(n·2^{m/2})\) ，期望得分 100
代码如下
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
ll n,a[100005],m;
ll f[100005],g[300][300];
int main(){
// freopen("count.in","r",stdin);
// freopen("ans.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
f[i]=1;
}
for(int i=1;i<=n;i++){
int x=a[i]&255;
for(int t=0;t<=x;t++){
if((t|x)==x) f[i]=(f[i]+g[a[i]>>8][t])%mod;
}
for(int s=0;s<=255;s++){
if(((a[i]>>8)|s)==s) g[s][a[i]&255]=(g[s][a[i]&255]+f[i])%mod;
}
cout<<f[i]%mod<<"\n";
}
return 0;
}
DP还是要多练练，千万不能产生畏难心理
标签：记录,int,复杂度,cin,long,vm,改题,vn,模拟 From： https://www.cnblogs.com/zhangchenhua-awa/p/18608773