总分201，rank3
T2图上的简单题，但调了好久，T3暴力分很足，st表加减枝91，T1嘛，卡读题啊，QAQ……
先说坑爹的T1:
先是没看见每种喜悦值只能获得一次，改的时候又发现一次只可以买一个，233
状压每个状态表示每种物品是否被买，转移时可能转移到自己或新的状态，导一下式子倒推就好了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
using namespace std;
int n,bit[21];
long long all,v[21];
double p[21],pp,pll,now,f[1<<21];
int main(){
bit[0]=1;for(int i=1;i<=20;i++)bit[i]=bit[i-1]<<1;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lld",&p[i],&v[i]);
all+=v[i];
pll+=p[i];
}
f[bit[n]-1]=0;
for(int i=bit[n]-2;i>=0;i--){
pp=0,now=0;
for(int j=1;j<=n;j++){
if(!(i&bit[j-1])){
now+=p[j]*f[i|bit[j-1]];
pp+=p[j];
}
}
f[i]=(now+1.0)/(1.0*pp);
}
printf("%lld
%0.3lf
",all,f[0]);
}T2，就是缩点，然后贪心倒着找最小花费
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#define N 100050
#define M 200050
using namespace std;
int head[2*N],e=1;
struct edge{
int u,v,w,next;
}ed[2*M];
void add(int u,int v,int w){
ed[e].u=u;ed[e].v=v;ed[e].w=w;
ed[e].next=head[u];head[u]=e++;
}
int dfn[N],low[N],top,q[N],tot,id[N];
bool bo[N];
void tarjan(int x){
dfn[x]=low[x]=++top;
q[top]=x; bo[x]=1;
for(int i=head[x];i;i=ed[i].next){
int v=ed[i].v;
if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(bo[v])
low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x]){
int y;tot++;
do{
y=q[top--];
id[y]=tot;
bo[y]=0;
}while(y!=x);
}
}
int n,m,ans,out[2*N];
bool vis[2*N];
queue<int> qu;
void init(){
e=1;ans=0;top=0;tot=n;
memset(head,0,sizeof head);
memset(dfn,0,sizeof dfn);
memset(vis,0,sizeof vis);
memset(bo,0,sizeof bo);
memset(out,0,sizeof out);
}
int main(){
while(scanf("%d%d",&n,&m)==2&&!(n==0&&m==0)){
init();
int u,v,w;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
u++;v++;
add(u,v,w);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
for(int i=1;i<=m;i++){
int u=ed[i].u,v=ed[i].v;
if(id[u]!=id[v]){
add(id[v],id[u],ed[i].w);
out[id[u]]++;
}
}
for(int i=n+1;i<=tot;i++)
if(!out[i]){
qu.push(i);
vis[i]=1;
}
while(!qu.empty()){
int now=qu.front();qu.pop();
int minn=0x7fffffff,nxt=-1;
for(int i=head[now];i;i=ed[i].next){
int v=ed[i].v;
if(vis[v])continue;
if(ed[i].w<minn){minn=ed[i].w;nxt=v;}
}
if(nxt==-1)break;
for(int i=head[now];i;i=ed[i].next){
if(vis[v])continue;
out[ed[i].v]--;
if(!out[ed[i].v]){
qu.push(ed[i].v);
vis[ed[i].v]=1;
}
}
ans+=minn;
}
printf("%d
",ans);
}
return 0;
}T3,考试暴力水了91
暴力
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define N 50050
using namespace std;
int n,a[N],maxn[N][20],minn[N][20],ans;
void init(){
for(int i=1;i<=n;i++)maxn[i][0]=a[i];
for(int i=0;(1<<(i+1))<=n;i++)
for(int j=1;(j+(1<<(i+1)))-1<=n;j++)
maxn[j][i+1]=max(maxn[j][i],maxn[j+(1<<i)][i]);
for(int i=1;i<=n;i++)minn[i][0]=a[i];
for(int i=0;(1<<(i+1))<=n;i++)
for(int j=1;(j+(1<<(i+1)))-1<=n;j++)
minn[j][i+1]=min(minn[j][i],minn[j+(1<<i)][i]);
}
int work(int x,int y){
int k=0;
while((1<<(k+1))<y-x+1)k++;
int dd=max(maxn[x][k],maxn[y-(1<<k)+1][k]);
int xx=min(minn[x][k],minn[y-(1<<k)+1][k]);
return dd-xx;
}
int main(){
scanf("%d",&n);
int x,y;
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
a[x]=y;
}
init();
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
int de=work(i,j);
if(de<=j-i)ans++;
else j=i+de-1;
}
}
printf("%d
",ans);
}
正解分治，work(l,r)=work(l,mid)+work(mid+1,r)+跨过mid的，怎么算呢，分为四种情况搞，大小|，|大小,大|小，小|大。
根据max-min=r-l瞎搞就好了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 300005
using namespace std;
int maxl[N],maxr[N],minl[N],minr[N],b[4*N],a[N],n;
int work(int l,int r){
if(l==r)return 1;
long long ans=0;
int mid=(l+r)>>1;
maxl[mid]=minl[mid]=a[mid];
for(int i=mid-1;i>=l;i--){
maxl[i]=max(maxl[i+1],a[i]);
minl[i]=min(minl[i+1],a[i]);
}
maxr[mid+1]=minr[mid+1]=a[mid+1];
for(int i=mid+2;i<=r;i++){
maxr[i]=max(maxr[i-1],a[i]);
minr[i]=min(minr[i-1],a[i]);
}
for(int i=mid;i>=l;i--){
int d=i+maxl[i]-minl[i];
if(d<=mid||d>r)continue;
if(minr[d]>minl[i]&&maxr[d]<maxl[i])ans++;
}
for(int i=mid+1;i<=r;i++){
int d=i-maxr[i]+minr[i];
if(d>mid||d<l)continue;
if(minl[d]>minr[i]&&maxl[d]<maxr[i])ans++;
}
int r1=mid+1,r2=mid;
for(int i=mid;i>=l;i--){
while(minr[r2+1]>minl[i]&&r2<r){
r2++;
b[maxr[r2]-r2+2*N]++;
}
while(maxr[r1]<maxl[i]&&r1<=r){
b[maxr[r1]-r1+2*N]--;
r1++;
}
if(r1>r)break;
if(r1<=r2)ans+=b[minl[i]-i+2*N];
}
for(int i=mid+1;i<=r;i++)b[maxr[i]-i+2*N]=0;
int l1=mid,l2=mid+1;
for(int i=mid+1;i<=r;i++){
while(minl[l2-1]>minr[i]&&l2>l){
l2--;
b[maxl[l2]+l2+2*N]++;
}
while(maxl[l1]<maxr[i]&&l1>=l){
b[maxl[l1]+l1+2*N]--;
l1--;
}
if(l1<l)break;
if(l1>=l2)ans+=b[minr[i]+i+2*N];
}
for(int i=l;i<=mid;i++)b[maxl[i]+i+2*N]=0;
return ans+work(l,mid)+work(mid+1,r);
}
int main(){
scanf("%d",&n);
int x,y;
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
a[x]=y;
}
printf("%d
",work(1,n));
return 0;
}