NOI2015填坑
HJWJBSR
posted @ 2015年9月17日 22:45
in 题解
, 504 阅读
Day1
T1 签到题
T2 树剖裸题
T3 神题:
考场上面就没想出来
重新往状压DP方向想了一(hen)下(jiu)发现依旧没想出来
因为每个数大于sqrt(n)的质因数最多只有1个,所以可以状压前8个质数,然后把每个数依次加进来计算方案。
设f(S,T)为第一个人的状态为S且第二个人状态为T的时候的当前方案个数,然后还设个g0/g1(S,T)分别是两个人选择当前这个质因数的时候的方案数,最后处理完这个质因数就把f处理成g0+g1-f,因为两个都不选算了两遍。
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define N 256 #define M 505 #define fr first #define sc second #define ll long long pair <int,int> li[M]; int f[N][N],g[2][N][N],n,m,ans; const int Prime[]={2,3,5,7,11,13,17,19}; inline int Mod(ll x) {return (x+m)%m;} int main() { cin >>n>>m; for (int i=2;i<=500;i++) { int k=i; for (int j=0;j<8&&k-1;j++) while (k%Prime[j]==0) k/=Prime[j],li[i-1].sc|=1 << j; li[i-1].fr=k; } sort(li+1,li+n); f[0][0]=1; for (int i=1;i<n;i++) { if (li[i].fr==1||li[i].fr!=li[i-1].fr) memcpy(g[0],f,sizeof f),memcpy(g[1],f,sizeof f); for (int k=N-1;k>=0;k--) for (int l=N-1;l>=0;l--) if ((l&li[i].sc)==0) g[0][k|li[i].sc][l]=Mod(g[0][k|li[i].sc][l]+g[0][k][l]); for (int k=N-1;k>=0;k--) if ((k&li[i].sc)==0) for (int l=N-1;l>=0;l--) g[1][k][l|li[i].sc]=Mod(g[1][k][l|li[i].sc]+g[1][k][l]); if (li[i].fr!=li[i+1].fr||li[i].fr==1) for (int k=0;k<N;k++) for (int l=0;l<N;l++) f[k][l]=Mod(g[0][k][l]+g[1][k][l]-f[k][l]); } for (int i=0;i<N;i++) for (int j=0;j<N;j++) ans=Mod(ans+f[i][j]); cout <<ans<<endl; return 0; }
Day2
T1:按哈弗曼树那样贪心,只不过一次选取最小的k个,并且高度也要贪心选取。如果n%k!=0就补位。
由于是考场上面A的就懒得放代码了= =
T2:后缀排序+并查集,后缀排序之后就求出了两两相邻字典序后缀之间的相似程度,就可以从n-1到0扫一遍,每次用相似程度为i的两对更新答案。
#include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <algorithm> using namespace std; #define N 600050 #define fr first #define sc second #define ll long long pair <int,int> a[N];ll ans,Ans[N][2],s[N],ma[N],mi[N],tot,INF; int n,m,fa[N],c[N],d[N],sx[N],sy[N],li[N];char b[N]; inline int Read() { int x=0;char y;bool z=0; do y=getchar(),z|=y=='-'; while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return z?-x:x; } int Find(int x) {return fa[x]==x?x:(fa[x]=Find(fa[x]));} inline ll max(ll x,ll y) {return x<y?y:x;} inline ll min(ll x,ll y) {return x<y?x:y;} void aa(int x) { memset(c,0,sizeof(c));memset(d,0,sizeof(d)); memset(sy,0,sizeof(sy));int ri=x; for (int i=0;i<x;i++) sy[i]=n-i-1; for (int i=0;i<n;i++) if (sx[i]>=x) sy[ri++]=sx[i]-x; for (int i=0;i<n;i++) c[li[i]]++; for (int i=1;i<=n;i++) c[i]+=c[i-1]; for (int i=0;i<n;i++) sx[c[li[sy[i]]-1]++]=sy[i]; d[sx[0]]=1; for (int i=1;i<n;i++) d[sx[i]]=d[sx[i-1]]+1-(li[sx[i]]==li[sx[i-1]]&& li[sx[i]+x]==li[sx[i-1]+x]); for (int i=0;i<n;i++) li[i]=d[i]; } int main() { n=Read(); scanf("%s",b); for (int i=1;i<=n;i++) ma[i]=mi[i]=Read(),fa[i]=i,s[i]=1; for (int i=0;i<n;i++) c[b[i]]++; for (int i=1;i<=256;i++) c[i]+=c[i-1]; for (int i=0;i<n;i++) sx[c[b[i]-1]+(d[b[i]]++)]=i, li[i]=c[b[i]]; for (int i=1;i<n;i <<= 1) aa(i); int now=0,ri=0;ans=INF=-(ll)(1e18); for (int i=0;i<n;i++) { now-=now>0; if (li[i]==1) continue; while (i+now<n&&sx[li[i]-2]+now<n&&b[i+now]==b[sx[li[i]-2]+now]) now++; a[++ri].fr=now;a[ri].sc=i+1; } sort(a+1,a+n);ri=n-1; for (int i=n-1;i>=0;i--) { while (ri&&a[ri].fr==i) { int k=Find(a[ri].sc),l=Find(sx[li[a[ri].sc-1]-2]+1); if (k!=l) fa[k]=l,ans=max(ans,ma[k]*ma[l]), ans=max(ans,mi[k]*mi[l]), ma[l]=max(ma[l],ma[k]),mi[l]=min(mi[k],mi[l]), tot+=s[l]*s[k],s[l]+=s[k]; ri--; } Ans[i][0]=tot;Ans[i][1]=ans; } for (int i=0;i<n;i++) printf("%lld %lld\n",Ans[i][0],!Ans[i][0]?0:Ans[i][1]); return 0; }
T3这种凶残的题还是不准备现在填坑了= =