S+ CSP 模拟赛
这题就是直接暴力就解决了~
赛时判除数为 0 时写错了，挂了 10 分…(
赛时只能写暴力…（悲催
正解是状压dp;
因为数据范围给了，$ B-A \le 72$ ，所以容易得出 $\text{gcd}(A,B)\le 72$，进一步容易得出可以使用状压dp，二进制第 $i$ 位表示这个数是不是 $72$ 以内第 $i$ 个质数的因数；当两数按位或为 0 时为合法解。
话不多说，看代码~
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e3+10,M=2e6+10;
bool p[N];
int l,r,cnt,pri[N],dp[2][M];
bool isPrime(int a) {
if (a==1) return 0;
if (a==2) return 1;
for (int i=2;i*i<=a;i++) {
if (a
}
return 1;
}
int get(int a) {
int ans=0;
for (int i=0;i<cnt;i++) {
if (a
}
return ans;
}
signed main(){
freopen("coprime.in","r",stdin);
freopen("coprime.out","w",stdout);
Cios;
for (int i=2;i<=72;i++) {
if (isPrime(i)) pri[cnt++]=i;
}
cin>>l>>r;
dp[0][0]=1;
bool now=1;
for (int i=1;i<=r-l+1;i++) {
int s=get(l+i-1);
for (int j=0;j<=(1<<cnt)-1;j++) {
if ((s|j)!=j) {
dp[now][j]=dp[!now][j];
continue;
}
dp[now][j]=dp[!now][j]+dp[!now][j-s];
}
now=!now;
}
int ans=0;
for (int i=0;i<=(1<<cnt)-1;i++) ans+=dp[!now][i];
cout<<ans;
return 0;
}学习知识点：扫描线
扫描线模版，直接给代码：
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define lc p<<1
#define rc p<<1|1
intc N=2e5+10;
int n,x[N];
struct node{
int x1,x2,y;
int cnt;
bool operator <(const node &a) const{
return y<a.y;
}
}li[N];
struct tree{
int l,r;
int cnt,len;
};
class setTree{
public:
tree tr[N<<3];
void pushup(int p){
int l=tr[p].l,r=tr[p].r;
if(tr[p].cnt) tr[p].len=x[r+1]-x[l];
else tr[p].len=tr[lc].len+tr[rc].len;
}
void build(int p,int l,int r){
//cout<<l<<" "<<r<<endl;
tr[p]={l,r,0,0};
if(l==r) return;
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void update(int p,int l,int r,int tag){
//cout<<p<<endl;
if(l<=tr[p].l&&tr[p].r<=r){
tr[p].cnt+=tag;
pushup(p);
return;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid) update(lc,l,r,tag);
if(r>mid) update(rc,l,r,tag);
pushup(p);
}
}st;
signed main(){
Cios;
cin>>n;
for(int i=1;i<=n;i++){
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
li[i]={x1,x2,y1,1};
li[i+n]={x1,x2,y2,-1};
x[i]=x1;
x[i+n]=x2;
}
n*=2;
sort(li+1,li+1+n);
sort(x+1,x+1+n);
int nn=unique(x+1,x+1+n)-x-1;
st.build(1,1,nn-1);
//cout<<"- \n";
intl ans=0;
for(int i=1;i<n;i++){
int l=lower_bound(x+1,x+1+nn,li[i].x1)-x;
int r=lower_bound(x+1,x+1+nn,li[i].x2)-x;
st.update(1,l,r-1,li[i].cnt);
ans+=(intl)st.tr[1].len*(li[i+1].y-li[i].y);
}
cout<<ans;
return 0;
}
评论（0）
暂无评论