在考场上就想出来的，因为时间只有最后40分钟，再加上我做事磨磨唧唧，码完之后没有调试就结束了，然后$APIO$就光荣打铁了（合肥八中历史最低分）（说出来都丢脸，不过我还是觉得没有省选的时候丢脸）。没考过$AYSN$也就算了（都是八中学子，同甘共苦）。但是如果加上这些分，能考过$why$的（话说$why$好像从初中以来一直吊打我，虽然我们共同拥有一个菜的抠脚的物理老师$wqq$），可能就有脸去找一下女神了吧，但是现在打铁了，真是不可原谅自己，只能等到$NOIP2019$一雪前耻了。
题面https://loj.ac/problem/3144
题解：非常简单。推一波公式，找到循环节，然后维护线段交就可以了。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define ri register int #define N 1000050 #define LL long long using namespace std; int n; LL a,b; LL l[N],r[N],L; LL gcd(LL a, LL b) { if (b==0) return a; else return gcd(b,a%b); } void solve1() { LL a,b,ret=0; for (ri i=1;i<=n;i++) { scanf("%lld %lld",&a,&b); ret+=b-a+1; } printf("%lld",ret); return; } int ton[N<<2]; LL siz[N<<2]; struct jiao { struct node { LL x,id; bool operator < (const node &rhs) const { return x<rhs.x; } } a[N<<1]; LL cnt; LL lil[N],lir[N]; void insert(LL l,LL r) { cnt++; a[cnt*2-1].x=l; a[cnt*2-1].id=cnt; a[cnt*2].x=r+1; a[cnt*2].id=cnt; } LL solve() { int cc=1; sort(a+1,a+cnt*2+1); a[0].x=0; a[cnt*2+1].x=L; siz[1]=1; for (ri i=1;i<=cnt*2+1;i++) { if (a[i].x!=a[i-1].x) { if (a[i].x-a[i-1].x>1) { cc++; siz[cc]=a[i].x-a[i-1].x-1; } cc++; siz[cc]=1; } if (lil[a[i].id]==0) lil[a[i].id]=cc; else lir[a[i].id]=cc; } for (ri i=1;i<=cnt;i++) { ton[lil[i]]++; ton[lir[i]]--; } for (ri i=1;i<=cc;i++) ton[i]+=ton[i-1]; LL ret=0LL; for (ri i=0; i<=cc; i++) if (ton[i]>0) ret+=siz[i]; return ret; } } y; int main() { scanf("%d %lld %lld",&n,&a,&b); LL d=gcd(a,b+1); long double aa=a, bb=b, dd=d; L=a/d*(b+1)-a/d; for (ri i=1;i<=n;i++) { scanf("%lld %lld",&l[i],&r[i]); LL nl=l[i]%L; if (r[i]-l[i]>=L-1) { cout<<L<<endl; return 0; } LL nr=nl+(r[i]-l[i]); if (nr>=L) { nr=nr-L; y.insert(0,nr); y.insert(nl,L-1); } else { y.insert(nl,nr); } } printf("%lld",y.solve()); return 0; }
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#define ri register int#define N 1000050#define LL long longusing namespace std;int n;LL a,b;LL l[N],r[N],L;LL gcd(LL a, LL b) { if (b==0) return a; else return gcd(b,a%b);}void solve1() { LL a,b,ret=0; for (ri i=1;i<=n;i++) { scanf("%lld %lld",&a,&b); ret+=b-a+1; } printf("%lld",ret); return;}int ton[N<<2]; LL siz[N<<2];struct jiao { struct node { LL x,id; bool operator < (const node &rhs) const { return x<rhs.x; } } a[N<<1]; LL cnt; LL lil[N],lir[N]; void insert(LL l,LL r) { cnt++; a[cnt*2-1].x=l; a[cnt*2-1].id=cnt; a[cnt*2].x=r+1; a[cnt*2].id=cnt; } LL solve() { int cc=1; sort(a+1,a+cnt*2+1); a[0].x=0; a[cnt*2+1].x=L; siz[1]=1; for (ri i=1;i<=cnt*2+1;i++) { if (a[i].x!=a[i-1].x) { if (a[i].x-a[i-1].x>1) { cc++; siz[cc]=a[i].x-a[i-1].x-1; } cc++; siz[cc]=1; } if (lil[a[i].id]==0) lil[a[i].id]=cc; else lir[a[i].id]=cc; } for (ri i=1;i<=cnt;i++) { ton[lil[i]]++; ton[lir[i]]--; } for (ri i=1;i<=cc;i++) ton[i]+=ton[i-1]; LL ret=0LL; for (ri i=0; i<=cc; i++) if (ton[i]>0) ret+=siz[i]; return ret; }} y;int main() { scanf("%d %lld %lld",&n,&a,&b); LL d=gcd(a,b+1); long double aa=a, bb=b, dd=d; L=a/d*(b+1)-a/d; for (ri i=1;i<=n;i++) { scanf("%lld %lld",&l[i],&r[i]); LL nl=l[i]%L; if (r[i]-l[i]>=L-1) { cout<<L<<endl; return 0; } LL nr=nl+(r[i]-l[i]); if (nr>=L) { nr=nr-L; y.insert(0,nr); y.insert(nl,L-1); } else { y.insert(nl,nr); } } printf("%lld",y.solve()); return 0;}
转载于:https://www.cnblogs.com/shxnb666/p/11135939.html
相关资源：各显卡算力对照表！