1.Promotion Counting
给定一棵树，每个点一个权值，求每个点权值比他大的子孙的个数。n<=10^5
题解:离散一下线段树维护。dfs到每个点的时候求一个答案，dfs完它的子孙求一个答案，求差即可。
#include#include #include #define N 131072#define MAXN 100000using 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
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#include #include #include #include #define INF 100000000000000LL#define eps 1e-13using namespace std;#define ll long longll 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< <<" "< <
3.Subsequence Reversal
给定一个长度为N的序列，允许翻转一个子序列，求最长不下降子序列长度。n和数字都<=50
用f[i][j][k][l]表示i-j的区间内只用k-l的数的最大不下降子序列长度。
然后两端的数换不换都转移一下。
复杂度 n^4
#include#include #include #define MAXN 50using 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\n",i,j,x,y,f[i][j][x][y]); } } } printf("%d\n",f[1][n][1][50]); return 0;}