T1 極好的問題
不是很難的題，考場上抽了，有一個細節挂了隻有 80 80 80 分。
由于要求本質不同的三元組 ( x , y , z ) (x,y,z) (x,y,z) 數量，我分了三種情況：
- ( a , a , a ) (a,a,a) (a,a,a)。直接判一下即可。
- ( a , a , b ) (a,a,b) (a,a,b)。 O ( n 2 ) O(n^2) O(n2) 枚舉 a , b a,b a,b 判斷即可。
- ( a , b , c ) (a,b,c) (a,b,c)。我的做法是枚舉 b , c b,c b,c，把 b b b 之前的 a a a 的逆元加進 map 裡，然後直接詢問就可以了。
考場上由于怕 map 跑的太慢，就手寫了哈希表。
#include<bits/stdc++.h>
using namespace std;
const int N=2505;
int n,P,a[N],b[N],num[N];
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?1ll*x*y%P:x*y;}
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);}
void Max(int &x,int y) {if(x<y)x=y;}
void Min(int &x,int y) {if(x>y)x=y;}
namespace Hash_Table{
const int N=1e6+10,mod=1e6+3;
int t,first[N],v[N],w[N],nxt[N];
void add(int x,int y){
nxt[++t]=first[x],first[x]=t,v[t]=y,w[t]=1;
}
void ADD(int x,int val){
int pos=x%mod;
for(int i=first[pos];i;i=nxt[i])
if(v[i]==x) {w[i]+=val;return;}
add(pos,x);
}
int Query(int x){
int pos=x%mod;
for(int i=first[pos];i;i=nxt[i])
if(v[i]==x) return w[i];
return 0;
}
}
using namespace Hash_Table;
int m,tot;
int main(){
scanf("%d%d",&n,&P);
for(int i=1,x;i<=n;++i){
scanf("%d",&x);
if(x%P) a[++tot]=x;
}
sort(a+1,a+tot+1);
for(int i=1;i<=tot;++i){
a[i]==a[i-1]?num[m]++:(b[++m]=a[i],num[m]=1);
}
int ans=0;
for(int i=1;i<=m;++i){
for(int j=i+1;j<=m;++j)
ans+=Query(mul(b[i],b[j]));
ADD(Inv(b[i]%P),1);
}
for(int i=1;i<=m;++i){
if(num[i]>=3) ans+=(power(b[i],3)==1);
for(int j=1;j<=m;++j)
if(i!=j&&num[i]>=2) ans+=(mul(mul(b[i],b[i]),b[j])==1);
}
printf("%d\n",ans);
return 0;
}
T2 背包問題
按照 w w w 排序之後，這就有點像 LIS 問題了，但是有背包容量的限制。
一個顯然的貪心是，如果我們選了 k k k 個物品，那麼用容量最大的 k k k 個背包會最優。
那麼按照背包容量從大到小排序，物品按照 w w w 從大到小排序。由于還有 v v v 的限制，我們需要樹狀數組來存答案。每次更新答案的時候在樹狀數組裡查 ≥ v \geq v ≥v 部分的最大答案，判斷背包的限制然後更新答案即可。
時間複雜度 O ( n log n ) O(n\log n) O(nlogn)。
#include<bits/stdc++.h>
using namespace std;
namespace IO{
const int Rlen=1<<22|1;
char buf[Rlen],*p1,*p2;
inline char gc(){
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T Read(){
char c=gc();T x=0,f=1;
while(!isdigit(c)) f^=(c=='-'),c=gc();
while( isdigit(c)) x=(x+(x<<2)<<1)+(c^48),c=gc();
return f?x:-x;
}
inline int in() {return Read<int>();}
}
using IO::in;
const int N=1e5+5;
int n,m,k,bag[N],d[N];
struct node{int w,v;}p[N];
bool operator<(const node &p,const node &q) {return (p.w==q.w)?p.v>q.v:p.w>q.w;}
void discrete(){
sort(d+1,d+n+1),k=unique(d+1,d+n+1)-d-1;
for(int i=1;i<=n;++i) p[i].v=lower_bound(d+1,d+k+1,p[i].v)-d;
}
void Max(int &x,int y) {if(x<y)x=y;}
void Min(int &x,int y) {if(x>y)x=y;}
namespace BIT{
int bit[N];
#define lowbit(x) (x&(-x))
void Clear() {memset(bit,0,sizeof(bit));}
void add(int x,int val) {for(;x;x-=lowbit(x))Max(bit[x],val);}
int Query(int x,int ans=0) {for(;x<=k;x+=lowbit(x))Max(ans,bit[x]);return ans;}
#undef lowbit
}
int main(){
int T=in();
while(T--){
n=in();
for(int i=1;i<=n;++i){
p[i].w=in(),p[i].v=in(),d[i]=p[i].v;
}
sort(p+1,p+n+1),discrete();
m=in();
for(int i=1;i<=m;++i) bag[i]=in();
sort(bag+1,bag+m+1,greater<int>());
int pos=0,ans=0;
BIT::Clear();
for(int i=1;i<=n;++i){
while(pos<m&&bag[pos+1]>=p[i].w) ++pos;
int now=min(BIT::Query(p[i].v)+1,pos);
BIT::add(p[i].v,now),Max(ans,now);
}
printf("%d\n",ans);
}
return 0;
}
T3 子樹問題
計數類 d p dp dp 題。永遠都想不到。。
設 f [ i ] [ j ] f[i][j] f[i][j] 表示有 i i i 節點的深度不超過 d d d 的有根樹的數量。先不考慮限制，則：
f [ i ] [ j ] = ∑ k = 1 i − 1 f [ i − k ] [ j ] × f [ k ] [ j − 1 ] × ( i − 2 j − 1 ) f[i][j]=\sum_{k=1}^{i-1}f[i-k][j]\times f[k][j-1]\times \binom{i-2}{j-1} f[i][j]=k=1∑i−1f[i−k][j]×f[k][j−1]×(j−1i−2)
後面乘的組合數就是給這些點配置設定标号。
對于數量限制的點，直接把 f [ i ] [ j ] f[i][j] f[i][j] 置成 0 0 0 即可。
最後 d d d 的答案就是 f [ n ] [ d ] − f [ n ] [ d − 1 ] f[n][d]-f[n][d-1] f[n][d]−f[n][d−1]。
時間複雜度 O ( n 3 ) O(n^3) O(n3)。
#include<bits/stdc++.h>
using namespace std;
namespace IO{
const int Rlen=1<<22|1;
char buf[Rlen],*p1,*p2;
inline char gc(){
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T Read(){
char c=gc();T x=0,f=1;
while(!isdigit(c)) f^=(c=='-'),c=gc();
while( isdigit(c)) x=(x+(x<<2)<<1)+(c^48),c=gc();
return f?x:-x;
}
inline int in() {return Read<int>();}
}
using IO::in;
const int N=505,P=998244353;
int n,k,ban[N],L,R,C[N][N],f[N][N];
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?1ll*x*y%P:x*y;}
void prework(){
C[0][0]=1;
for(int i=1;i<=n;++i){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;++j) C[i][j]=add(C[i-1][j],C[i-1][j-1]);
}
}
int main(){
n=in(),k=in(),prework();
for(int i=1,x;i<=k;++i) ban[in()]=1;
L=in(),R=in();
f[1][1]=ban[1]?0:1;
for(int d=2;d<=n;++d){
for(int i=1;i<=n;++i){
if(i==1) {f[i][d]=1;continue;}
for(int j=1;j<i;++j) f[i][d]=add(f[i][d],mul(mul(f[i-j][d],f[j][d-1]),C[i-2][j-1]));
}
for(int i=1;i<=n;++i) if(ban[i]) f[i][d]=0;
}
for(int i=L;i<=R;++i) printf("%d ",dec(f[n][i],f[n][i-1]));
return 0;
}