【题解】abc152

D

题意:给 n 个数字,求 m 以内的所有对于一切 $a_i$ 都成立的 $gcd(a_i,k)=1$ 的所有 k。

我们很容易得到一个推论,如果 $k_1$,$k_2$ 都成立,则 $k_1*k_2$ 成立,若有一个不成立则不成立。
于是只需要用筛法,并且求出不成立的所有质数,并将其倍数全部归为不可取,最后就剩下可行的了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int cnt=0;
int prime[maxn];//第i个素数
bool is_prime[maxn];//is_prime[i]为true表示i是素数
void Aishai(int n)//返回n以内的素数
{
    for(int i=0;i<=n;i++)
        is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=n;i++)
        if(is_prime[i])
        {
            prime[++cnt]=i;
            for(int j=2*i;j<=n;j+=i)
                is_prime[j]=false;
        }
    return ;
}
int a[maxn];
int cant[maxn];
int cantt[maxn];
bool exs[maxn];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        is_prime[i]=1;
    }
    Aishai(m);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(exs[a[i]]){
            i--;
            n--;
            continue;
        }
        exs[a[i]]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cnt&&prime[j]<=a[i];j++){
            if(a[i]%prime[j]==0){
                cant[j]=1;
            }
        }
    }
    for(int i=1;i<=cnt;i++){
        if(cant[i]){
            for(int j=prime[i];j<=m;j+=prime[i]){
                cantt[j]=1;
            }
        }
    }
    
    int ans=0;
    for(int i=1;i<=m;i++){
        if(cantt[i]==0){
            ans++;
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=m;i++){
        if(cantt[i]==0){
            cout<<i<<endl;
        }
    }
    return 0;
} 

E

本题看一下数据范围即可确认是状压 DP
设 dpi[k]代表当前为第 i 位,取数状态为 j,最后一个取的数为 k。
则有 dpi[k]=dpi-1[k],即不取数
对于每个第 a[i]位为 1 的 k,如果 k =(1<<a[i])则说明重开了一个数列。则 dpi)][a[i]]++
若当前位的状态没出现过,即当前位取的数之前没有出现过(因为如果出现过就不是 1 <<a[i]了,后面一种情况讨论)则 dpi[a[i]]+=dpi-1)][k]
最后讨论出现过的情况,dpi[a[i]]+=dpi-1[a[i]](之所以要分类是因为前面是 j^(1<<a[i]))

其实本题还可以用滚动数组来优化

#include<bits/stdc++.h>
using namespace std;
const int Mod=998244353;
int n;
string s;
int a[1005];
long long dp[1005][1100][10];
int len=0;
int main(){
    cin>>n;
    cin>>s;
    len=s.length();
    for(int i=0;i<len;i++){
        a[i+1]=s[i]-'A';
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<1024;j++){
            for(int k=0;k<10;k++){
                dp[i][j][k]=dp[i-1][j][k];
            }
        }
        for(int j=1;j<1024;j++){
            if(((j>>a[i])&1)==0){//当前位为0,则跳过 
                continue;
            }
            if(j==(1<<a[i]))dp[i][1<<a[i]][a[i]]++;
            for(int k=0;k<10;k++){
                if(k==a[i])continue;
                dp[i][j][a[i]]+=dp[i-1][j^(1<<a[i])][k];
                dp[i][j][a[i]]%=Mod;
            }
            dp[i][j][a[i]]+=dp[i-1][j][a[i]];
            dp[i][j][a[i]]%=Mod;
        }
    }
    long long ans=0;
    for(int j=0;j<1024;j++){
        for(int k=0;k<10;k++){
            ans+=dp[n][j][k];
            ans%=Mod; 
        }
    }
    cout<<ans<<endl;
    return 0;
} 

F

看数据范围像 O(nlogn) 范围,于是想到采用二分答案。

事实上我放上代码就明白了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
const int inf=1e9+7;
int n;
struct ss{
    int x,y;
}s[maxn];
bool isok(int mid){
    int minn=inf,maxn=0;
    for(int i=1,j=1;i<=n;i++){
        while(j<=n&&s[i].x>=s[j].x+mid){//若x的差大于等于mid
            maxn=max(maxn,s[j].y);
            minn=min(minn,s[j].y);
            j++;
        }
        if(s[i].y<=maxn-mid||s[i].y>=minn+mid)return true;
    }
    return false;
}
bool cmp(ss a,ss b){
    return a.x<b.x;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i].x>>s[i].y;
    }
    sort(s+1,s+1+n,cmp);
    int l=0,r=inf,mid,ans;
    while(l<=r){
        mid=(l+r)>>1;
        if(isok(mid)){
            l=mid+1;
            ans=mid;
        }else{
            r=mid-1;
        }
    }
    cout<<ans<<endl;
    return 0;
}