传送门
A - A+...+B Problem
题意：n个数最大值a，最小值b，求和的可能数量。
#include<cstdio>
#include<algorithm>
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
int n,a,b;
int main(){
n=read();a=read();b=read();
if (n==){
printf("%d\n",a==b);
return ;
}
if (a>b) puts("");else
printf("%lld\n",1LL*(b-a)*(n-)+);
}
B - Evilator
题意：一个电梯，每层只能上或下，问任意两个楼层相互抵达的操作次数之和。保证两两可达。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 110000
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
char s[MN];
long long mmh,n;
int main(){
scanf("%s",s);
n=strlen(s);mmh=(n-)*n;
for (int i=;i<n;i++){
if (s[i]=='U') mmh+=i;else mmh+=n-i-;
}
printf("%lld\n",mmh);
}
C - Nuske vs Phantom Thnook
题意：一个有障碍的地图上，任意两个空地之间至多有一条路，每次询问一个矩形内空地的联通块个数（类似apio2017 T1）
题解：统计矩形内空地数量，满足两端都是空地的边的数量相减即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 2100
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
int n,m,Q,q[MN][MN],w[MN][MN],d[MN][MN],map[MN][MN],x,y,X,Y;
char s[MN];
int main(){
int i,j;
n=read();m=read();Q=read();
for (i=;i<=n;i++){
scanf("%s",s+);
for (j=;j<=m;j++)
map[i][j]=s[j]=='',q[i][j]=q[i-][j]+q[i][j-]-q[i-][j-]+map[i][j];
} for (i=;i<=n;i++)
for (j=;j<=m;j++)
w[i][j]=w[i-][j]+w[i][j-]-w[i-][j-]+(map[i][j]&&map[i][j-]),
d[i][j]=d[i-][j]+d[i][j-]-d[i-][j-]+(map[i][j]&&map[i-][j]); while (Q--){
x=read();y=read();X=read();Y=read();
printf("%d\n",q[X][Y]-q[x-][Y]-q[X][y-]+q[x-][y-]-(w[X][Y]-w[X][y]-w[x-][Y]+w[x-][y])-(d[X][Y]-d[X][y-]-d[x][Y]+d[x][y-]));
}
}
D - A or...or B Problem
题意：给一个区间，问有多少个数能用区间内的数进行or操作得到。
题解：找到l与r最高的不同位（l<2^a<=r），将2^a或上[l,2^a-1]是有贡献的，再递归处理[2^a,r]区间内贡献即可。
比赛结束一分钟过D题样例……
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 2100
#define ll long long
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
long long l,r,mmh;
inline ll max(ll a,ll b){return a>b?a:b;}
inline ll min(ll a,ll b){return a<b?a:b;}
inline ll work(ll l,ll r,ll up){
if (l>r) swap(l,r);
int i;
if (l==r) return ;
for (i=;;i--) if (((r>>i)&)&&(!((l>>i)&))) break;
r&=(1ll<<(i+))-;l&=(1ll<<(i+))-;r^=1ll<<i;up^=1ll<<i;
if (r+>=l) return min(1ll<<i,up)-r-;
ll mmh=work(,r,l);
mmh+=min((1ll<<i),up)-l;
return mmh;
}
int main(){
int i,j;
scanf("%lld%lld",&l,&r);
if (l==r) return puts(""),;
printf("%lld\n",work(l,r,1ll<<)+r-l+);
}
E - Mr.Aoki Incubator
题意：数轴上一些质点，有初始位置和速度，初始时选定一些点染色，运动过程中质点相遇可以相互染色（已染的染到未染的上面），问多少种方式能使足够长时间后所有点都被染色。
题解：赛后看题解才会系列……将所有点按速度排序，对于每个点i找出初始坐标小于它的速度最大的点R和初始坐标大于它的速度最小的点L，那么染上点i后，最终[L,R]内的点都会被染上。证明其实很显然，对于(i,R)中的点，如果初始坐标大于i，那会在R碰到i被染上以后被R染上，如果初始坐标小于i，那它自己会碰到i。(L,i)中的点同理。然后用线段树优化一下DP即可。
#include<cstdio>
#include<algorithm>
#define MN 200001
#define lp p<<1
#define rp p<<1|1
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
const int MOD=1e9+;
inline void M(int &x){while(x>=MOD)x-=MOD;}
inline int _M(int x){M(x);return x;}
struct tree{int p,s,c;tree(){c=;}}t[MN*];
struct na{int l,r;}w[MN];
struct ma{int x,v;}a[MN];
bool operator < (ma a,ma b){return a.v<b.v;}
bool operator < (na a,na b){return a.l<b.l;}
int n,m,stl[MN][],str[MN][];
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
void hb(int p,int c){
t[p].c=1LL*t[p].c*c%MOD;
t[p].s=1LL*t[p].s*c%MOD;
}
void pd(int p){if (t[p].c!=) hb(lp,t[p].c),hb(rp,t[p].c),t[p].c=;}
void gx(int p){M(t[p].s=t[lp].s+t[rp].s);}
void add(int p,int l,int r,int k,int v){
if (l==r){
M(t[p].s+=v);
return;
}
if (l!=r) pd(p);
int mid=l+r>>;
if (k<=mid) add(lp,l,mid,k,v);else add(rp,mid+,r,k,v);
gx(p);
}
int ask(int p,int l,int r,int L,int R){
if (l>=L&&r<=R) return t[p].s;
pd(p);
int mid=l+r>>;
if (R<=mid) return ask(lp,l,mid,L,R);else
if (L>mid) return ask(rp,mid+,r,L,R);else
return _M(ask(lp,l,mid,L,R)+ask(rp,mid+,r,L,R));
}
void cc(int p,int l,int r,int k){
if (l>=k) hb(p,);else{
pd(p);
int mid=l+r>>;
if (k>mid) cc(rp,mid+,r,k);else cc(lp,l,mid,k),cc(rp,mid+,r,k);
gx(p);
}
}
int main(){
int i,j;
n=read();
for (i=;i<=n;i++) a[i].x=read(),a[i].v=read();
sort(a+,a++n);
for (i=;i<=n;i++) for (stl[i][]=a[i].x,j=;j<&&(i>>j);j++) stl[i][j]=min(stl[i][j-],stl[i-(<<(j-))][j-]);
for (i=n;i>=;i--) for (str[i][]=a[i].x,j=;j<&&i+(<<j)-<=n;j++) str[i][j]=max(str[i][j-],str[i+(<<(j-))][j-]); for (i=;i<=n;i++){
int l=,r=n;
for (j=;j>=;j--) if (str[l][j]&&str[l][j]<a[i].x) l+=<<j;
for (j=;j>=;j--) if (stl[r][j]&&stl[r][j]>a[i].x) r-=<<j;
w[i].l=l;w[i].r=r;
} sort(w+,w++n);
add(,,n,,);
for (i=;i<=n;i++){
cc(,,n,w[i].r);
add(,,n,w[i].r,ask(,,n,w[i].l-,w[i].r-));
}
printf("%d\n",ask(,,n,n,n));
}
F结论题留坑