牛客小白月赛23
牛客小白月赛
A.膜法记录 题意：给n行m列的矩阵，矩阵中的每个位置都可能有敌人
现在你能消灭a行和b列的敌人，问是否有可能将所有敌人都消灭。
数据范围：n<=20,m<=1e5
观察到n最大只有20，容易想到二进制枚举行的消除，然后能否消除剩下的列。
但是列是1e5的，稍微计算一下复杂度发现如果每次都遍历列显然会超时。
容易想到预处理，但是怎么预处理呢，题解给出的做法：
考虑到每一列是可以交换顺序而不影响结果的，因为行最大只有20，因此可以直接状压每一列。
用cnt[sta]表示行选择状态为sta的时，不需要消除的列数量，用SosDp计算出cnt数组。
#include
using namespace std;
#define int long long
#define ll long long
char s[25][100000+5];
int cnt[1<>T;
while(T--){
cin>>n>>m>>a>>b;
for(int i=0;i<n;i++){
scanf("%s",s[i]);
}
for(int i=0;i<(1<<n);i++)cnt[i]=0;
for(int j=0;j<m;j++){
int t=0;//这一列的状态
for(int i=0;i<n;i++){
if(s[i][j]=='*'){
t|=(1<<i);
}
}
cnt[t]++;//这时候cnt[sta]表示当行状态为sta时有多少列是不用消除的
}
for(int i=0;i<n;i++){//SosDp计算出完整的cnt数组
for(int j=0;j<(1<>i&1)){
cnt[j|(1<<i)]+=cnt[j];
}
}
}
int ok=0;
for(int i=0;i<(1<<n);i++){
int tot=0;
for(int j=0;j>j&1)tot++;
if(tot!=a)continue;
if(b>=m-cnt[i]){//m-cnt[i]就是需要消除的列数量了
ok=1;
break;
}
}
if(ok)cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
return 0;
}
B.阶乘
题意：
给定p，要求找到一个最小的n，满足n的阶乘是p的倍数
思路：先将p质因子分解，记录质因子a(i)以及这个质因子的次数b(i)。
然后二分枚举n，假设当前二分到的是mid。
遍历p的质因子，假设当前质因子为a(i)，次数为b(i)，就判断mid的阶乘中是否能分解出不少于b(i)个a(i)
#include
using namespace std;
const int maxm=1e5+5;
int a[maxm],b[maxm],cnt;
int cal(int n,int x){
int ans=0;
while(n>=x){
ans+=n/x;
n/=x;
}
return ans;
}
bool check(int mid){
for(int i=1;i<=cnt;i++){
int num=cal(mid,a[i]);
if(num>T;
while(T--){
int p;
cin>>p;
int pp=p;
cnt=0;
for(int i=2;i*i<=p;i++){
if(p%i==0){
int num=0;
while(p%i==0)p/=i,num++;
cnt++,a[cnt]=i,b[cnt]=num;
}
}
if(p!=1)cnt++,a[cnt]=p,b[cnt]=1;
int l=1,r=pp;
int ans=pp;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
cout<<ans<<endl;
}
return 0;
}
D.病毒传染(
I.美丽的序列I(
作者：我到底在干嘛
