T1
原題：[Codeforces 793G]Oleg and chess
題解在這裡。
#include<bits/stdc++.h>
#define N 5000005
#define inf 0x3f3f3f3f
using namespace std;
int n,q,S,T,t=1,cnt,tot;
int first[N],v[N],w[N],nxt[N];
struct Line{int y1,y2,flag;};
vector<Line>l[N];
void add(int x,int y,int z){
nxt[++t]=first[x],first[x]=t,v[t]=y,w[t]=z;
nxt[++t]=first[y],first[y]=t,v[t]=x,w[t]=0;
}
namespace Segment_Tree{
int point[N],cov[N];
#define mid ((l+r)>>1)
void pushup(int root){
point[root]=++tot;
if(!cov[root<<1]) add(point[root],point[root<<1],inf);
if(!cov[root<<1|1]) add(point[root],point[root<<1|1],inf);
}
void build(int root,int l,int r){
if(l==r) {point[root]=n+l;return;}
build(root<<1,l,mid),build(root<<1|1,mid+1,r);
pushup(root);
}
void Modify(int root,int l,int r,int x,int y,int val){
if(l>=x&&r<=y) {cov[root]+=val;return;}
if(x<=mid) Modify(root<<1,l,mid,x,y,val);
if(y> mid) Modify(root<<1|1,mid+1,r,x,y,val);
pushup(root);
}
#undef mid
}
using namespace Segment_Tree;
namespace DINIC{
int d[N],f[N];
bool bfs(){
memset(d,-1,sizeof(d));
memcpy(f,first,sizeof(f));
queue<int>Q;Q.push(S),d[S]=0;
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=first[x];i;i=nxt[i]){
int to=v[i];
if(w[i]&&d[to]==-1) d[to]=d[x]+1,Q.push(to);
}
}
return d[T]!=-1;
}
int dinic(int now,int flow){
if(now==T) return flow;
int delta,ans=0;
for(int &i=f[now];i;i=nxt[i]){
int x=v[i];
if(w[i]&&d[x]==d[now]+1){
delta=dinic(x,min(flow,w[i]));
w[i]-=delta,w[i^1]+=delta,flow-=delta,ans+=delta;
if(!flow) return ans;
}
}
return ans;
}
}
using namespace DINIC;
int main(){
int x1,y1,x2,y2;
scanf("%d%d",&n,&q);
while(q--){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
l[x1].push_back((Line){y1,y2,1});
l[x2+1].push_back((Line){y1,y2,-1});
}
S=0,T=tot=2*n+1;
for(int i=1;i<=n;++i) add(S,i,1),add(n+i,T,1);
build(1,1,n);
for(int i=1;i<=n;++i){
for(int j=0;j<l[i].size();++j){
Line x=l[i][j];
Modify(1,1,n,x.y1,x.y2,x.flag);
}
if(!cov[1]) add(i,point[1],inf);
}
int ans=0;
while(bfs()) ans+=dinic(S,inf);
printf("%d\n",ans);
return 0;
}
T2
原題：[Codeforces 335E]Counting Skyscrapers
題解在這裡。
#include<bits/stdc++.h>
using namespace std;
char S[10];
double P[35];
double power(double a,int b){
double ans=1;
for(;b;b>>=1,a*=a) if(b&1) ans*=a;
return ans;
}
int main(){
int n,h;
scanf("%s%d%d",S,&n,&h),P[0]=1;
for(int i=1;i<=30;++i) P[i]=P[i-1]*2;
if(S[0]=='B') printf("%.9lf\n",(double)n);
else{
double ans=n;
for(int i=1;i<=n;++i)
for(int j=1;j<=h;++j)
ans+=(n-i)/P[j]/P[j]*power(1.0-1.0/P[j],i-1)*(P[j]-P[j-1]*(1.0+(i-1)/(P[j]-1)));
printf("%.9lf\n",ans);
}
return 0;
}
T3
原題：[Codeforces 809E]Surprise me!
題解在這裡。
#include<bits/stdc++.h>
#define N 200005
#define P 1000000007
using namespace std;
int n,tot;
int a[N],pos[N],dfn[N],dep[N],fa[N][21];
struct edge{
int t,first[N],v[N<<1],nxt[N<<1];
void add(int x,int y){
nxt[++t]=first[x],first[x]=t,v[t]=y;
}
}T,VT;
int add(int x,int y) {return x+y>=P?x+y-P:x+y;}
int dec(int x,int y) {return x-y< 0?x-y+P:x-y;}
int mul(int x,int y) {return 1ll*x*y%P;}
int power(int a,int b){
int ans=1;
for(;b;b>>=1,a=mul(a,a)) if(b&1) ans=mul(ans,a);
return ans;
}
int inv(int x) {return power(x,P-2);}
bool comp(const int &p,const int &q) {return dfn[p]<dfn[q];}
int sum,prime[N],mark[N],mu[N],phi[N],f[N];
void linear_sieves(){
phi[1]=mu[1]=1;
for(int i=2;i<N;++i){
if(!mark[i]) prime[++sum]=i,mu[i]=P-1,phi[i]=i-1;
for(int j=1;j<=sum&&i*prime[j]<N;++j){
mark[i*prime[j]]=1;
if(i%prime[j]) mu[i*prime[j]]=P-mu[i],phi[i*prime[j]]=phi[i]*(prime[j]-1);
else {mu[i*prime[j]]=0,phi[i*prime[j]]=phi[i]*prime[j];break;}
}
}
for(int i=1;i<N;++i){
int Inv=inv(phi[i]);
for(int j=1;i*j<N;++j)
f[i*j]=add(f[i*j],mul(mul(i,mu[j]),Inv));
}
}
void dfs(int x){
dfn[x]=++tot;
for(int i=1;i<=20;++i)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=T.first[x];i;i=T.nxt[i]){
int to=T.v[i];
if(to==fa[x][0]) continue;
fa[to][0]=x,dep[to]=dep[x]+1;
dfs(to);
}
}
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;~i;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=20;~i;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
namespace Virtual_Tree{
int sum,res,cnt,top;
int p[N],S[N],stk[N];
void Insert(int x){
if(top==1) {stk[++top]=x;return;}
int lca=LCA(x,stk[top]);
if(lca==stk[top]) {stk[++top]=x;return;}
while(top>1&&dfn[lca]<=dfn[stk[top-1]])
VT.add(stk[top-1],stk[top]),top--;
if(lca!=stk[top]) VT.add(lca,stk[top]),stk[top]=lca;
stk[++top]=x;
}
int dis(int x,int y) {return dep[x]+dep[y]-2*dep[LCA(x,y)];}
void dp(int x){
for(int i=VT.first[x];i;i=VT.nxt[i]){
int to=VT.v[i],len=dis(x,to);
dp(to);
res=add(res,mul(len,mul(dec(sum,S[to]),S[to])));
S[x]=add(S[x],S[to]);
}
}
void Clear(int x){
for(int i=VT.first[x];i;i=VT.nxt[i]) Clear(VT.v[i]);
S[x]=VT.first[x]=0;
}
int calc(int x){
VT.t=cnt=sum=res=0;
for(int i=1;i*x<=n;++i) p[++cnt]=pos[i*x],S[p[cnt]]=phi[i*x],sum=add(sum,phi[i*x]);
sort(p+1,p+cnt+1,comp),stk[top=1]=1;
for(int i=1;i<=cnt;++i) if(p[i]!=1) Insert(p[i]);
while(--top) VT.add(stk[top],stk[top+1]);
dp(1),Clear(1);
res=mul(add(res,res),f[x]);
return res;
}
}
using namespace Virtual_Tree;
int main(){
scanf("%d",&n),linear_sieves();
for(int i=1;i<=n;++i) scanf("%d",&a[i]),pos[a[i]]=i;
for(int i=1,x,y;i<n;++i){
scanf("%d%d",&x,&y);
T.add(x,y),T.add(y,x);
}
dep[1]=1,dfs(1);
int ans=0;
for(int i=1;i<=n;++i) ans=add(ans,calc(i));
printf("%d\n",mul(ans,inv(mul(n,n-1))));
return 0;
}