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这种凶残的题还是不准备现在填坑了= =