1.Promotion Counting
给定一棵树，每个点一个权值，求每个点权值比他大的子孙的个数。n<=10^5
题解:离散一下线段树维护。dfs到每个点的时候求一个答案，dfs完它的子孙求一个答案，求差即可。
#include<iostream> #include<cstdio> #include<algorithm> #define N 131072 #define MAXN 100000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } int s[MAXN+5]; struct edge{ int to,next; }e[MAXN+5]; int num[MAXN+5]; int head[MAXN+5]; int n,cnt=0; int T[N*2+5]; int ans[MAXN+5]; void renew(int x,int ad) { T[x+=N]+=ad; for(x>>=1;x;x>>=1) T[x]=T[x<<1]+T[(x<<1)+1]; } int query(int l,int r) { int sum=0; for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) { if(~l&1) sum+=T[l+1]; if( r&1) sum+=T[r-1]; } return sum; } inline void ins(int f,int t) { e[++cnt].next=head[f]; head[f]=cnt; e[cnt].to=t; } void dfs(int x) { renew(num[x],1); ans[x]=-query(num[x],n); for(int i=head[x];i>0;i=e[i].next) {dfs(e[i].to);} ans[x]+=query(num[x],n); } int main() { n=read(); for(int i=1;i<=n;i++) s[i]=num[i]=read(); sort(s+1,s+n+1); int j=0; for(int i=1;i<=n;i++) if(s[i]!=s[i-1]) s[++j]=s[i]; for(int i=1;i<=n;i++) num[i]=lower_bound(s+1,s+j+1,num[i])-s; for(int i=1;i<n;i++) {int u=read();ins(u,i+1);} dfs(1); for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }
2.Building a Tall Barn
题目大意：给定长度为N的序列ai，对每个ai分配ci使得ci>0(ci为整数)且ci之和等于K，求出最小的ai/ci之和。
题解：二分每个数最后一次减少了多少(对于一个数，如果已经分到了2，再加1的时候它就减少1/6)
然后对每个数求二元一次方程。 A/n(n+1)=B
复杂度nlogn
#include<iostream> #include<cstdio> #include<algorithm> #include<iomanip> #include<cmath> #define INF 100000000000000LL #define eps 1e-13 using namespace std; #define ll long long ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } int n; ll K; ll ans=INF; double a[100005]; ll cal(double x){return (ll)((sqrt(1+4*x)-1)/2);} bool check(double x) { ll left=K; for(int i=1;i<=n;i++) { if(a[i]<=x) continue; ll xx=cal(a[i]/x); left-=xx; } //cout<<x<<" "<<left<<endl; if(left<0) return false; return true; } int main() { n=read();K=read()-n; for(int i=1;i<=n;i++) a[i]=read(); double l=eps,r=1e12,mid; for(int i=1;i<=200;i++) { mid=(l+r)/2; if(check(mid)) r=mid; else l=mid; } int i; for(i=1,l=0;i<=n;++i)l+=a[i]/(double)(cal(a[i]/r)+1); cout<<(ll)(l+0.5); return 0; }
3.Subsequence Reversal
给定一个长度为N的序列，允许翻转一个子序列，求最长不下降子序列长度。n和数字都<=50
用f[i][j][k][l]表示i-j的区间内只用k-l的数的最大不下降子序列长度。
然后两端的数换不换都转移一下。
复杂度 n^4
#include<iostream> #include<cstdio> #include<algorithm> #define MAXN 50 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } int n,maxn=0; int s[MAXN+5]; int f[MAXN+5][MAXN+5][MAXN+5][MAXN+5]; int main() { n=read(); for(int i=1;i<=n;++i)s[i]=read(); for(int l=1;l<=n;l++) { for(int i=1;i+l-1<=n;i++) { int j=i+l-1; for(int x=50;x>=1;x--) for(int y=x;y<=50;y++) { f[i][j][x][y]=max(f[i][j][x+1][y],f[i][j][x][y-1]); f[i][j][x][y]=max(f[i][j][x][y],f[i+1][j][x][y]); f[i][j][x][y]=max(f[i][j][x][y],f[i][j-1][x][y]); if(s[j]<=s[i]&&x<=s[j]&&y>=s[i]&&l!=1)
f[i][j][x][y]=max(f[i][j][x][y],f[i+1][j-1][s[j]][s[i]]+2); if(s[i]>=x&&y>=s[i]) f[i][j][x][y]=max(f[i][j][x][y],f[i+1][j-1][x][s[i]]+1); if(x<=s[j]&&s[j]<=y) f[i][j][x][y]=max(f[i][j][x][y],f[i+1][j-1][s[j]][y]+1); if(x<=s[i]&&s[i]<=y) f[i][j][x][y]=max(f[i][j][x][y],f[i+1][j][s[i]][y]+1); if(y>=s[j]&&s[j]>=x) f[i][j][x][y]=max(f[i][j][x][y],f[i][j-1][x][s[j]]+1); // printf("%d %d %d %d %d ",i,j,x,y,f[i][j][x][y]); } } } printf("%d ",f[1][n][1][50]); return 0; }