坑 PA2008(7)

挖下巨大的坑！主要是因为最近过于颓废，而且发现智商低到连POI都切不动。。于是黈力就推荐给我PA2008，听说题目从一眼秒的斯波题到黈力也做不出的神题都有，看来非常适合我这种由于智商不够而AFO的选手。

开学了好忙啊。。学考好烦啊。。政史地好难啊。。学习压力好大啊。。感觉根本没时间来机房啊。。看来在学考之前我要进入切傻逼题保持手感的不归路了。。。还有几道难题先坑着吧。。。我联赛结束后会来填的！（随便找个借口就坑掉真的好吗。。随便立flag真的好吗。。）

黈力说不写题解骗不来访问量。。那我写一发简单题解。。

kot：怎么暴力怎么来。。

#include<cstdio>
#include<cstring>
char s[500001];

char a[6][101]={"","`1234567890-=","qwertyuiop[]\\QWERTYUIOP","asdfghjkl;'ASDFGHJKL","zxcvbnm,./ZXCVBNM"," "};
int main()
{
	int i,j,k;
	gets(s);
	for(i=0;s[i];i++)
	{
		for(j=1;j<=5;j++)
		{
			for(k=0;a[j][k];k++)if(a[j][k]==s[i]){putchar('0'+j);break;}
			if(a[j][k])break;
		}
	}
	puts("");
	return 0;
}
	

pap：从低到高摞，如果=0就计算到当前为止最大能摞出多少，否则把这一位/2加到下一位去，这一位变成这一位%2（伪科学做法。。不要问我为什么是对的）

#include<cstdio>
int n,a[31];
int main()
{
	int i,j,k;
	scanf("%d",&n);
	for(i=0;i<=n;i++)scanf("%d",&a[i]);
	for(i=0;i<=30;i++)
	{
		if(a[i]==0)
		{
			int ans=0;
			for(j=i;j>=0;j--)ans=(ans<<1)+a[j];
			printf("%d\n",ans+1);
			break;
		}
		else {a[i+1]+=a[i]>>1;a[i]&=1;}
	}
	return 0;
}
		

bug：拆点最短路，根据长度的奇偶分别更新就好了

#include<cstdio>
int n,m;
int head[200001],end[1000001],len[1000001],next[1000001],tp=0;
int dis[400001],iq[400001];
int hp[400001],th=0,wz[400001];
const int inf=1<<29;
void pushup(int p)
{
    int tt=hp[p];
    while(p>1&&dis[hp[p/2]]>dis[tt]){hp[p]=hp[p/2];wz[hp[p]]=p;p/=2;}
    hp[p]=tt;wz[hp[p]]=p;
}
void pushdown(int p)
{
    int ch=p*2,tt=hp[p];
    if(ch<th&&dis[hp[ch+1]]<dis[hp[ch]])ch++;
    while(ch<=th&&dis[hp[ch]]<dis[tt])
    {
        hp[p]=hp[ch];wz[hp[p]]=p;p=ch;ch=p*2;if(ch<th&&dis[hp[ch+1]]<dis[hp[ch]])ch++;
    }
    hp[p]=tt;wz[hp[p]]=p;
}
long long dij(int b,int e,int s,int t)
{
    int i,j,k;
    for(i=b;i<=e;i++)dis[i]=inf;
    dis[s]=0;th=0;
    for(i=b;i<=e;i++){hp[++th]=i;wz[i]=th;pushup(th);}
    while(th>1)
    {
        int tt=hp[1];hp[1]=hp[th--];wz[hp[1]]=1;pushdown(1);
        if(dis[tt]==inf)break;
        int t1=(tt>n?tt-n:tt);
        for(i=head[t1];i;i=next[i])
        {
			int t2=((dis[tt]+len[i])&1?end[i]+n:end[i]);
			if(dis[t2]>dis[tt]+len[i])
	        {
	            dis[t2]=dis[tt]+len[i];pushup(wz[t2]);
	        }
	    }
    }
     
    return dis[t];
}
int main()
{
	int i,j,k;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		next[++tp]=head[x];head[x]=tp;end[tp]=y;len[tp]=z;
		next[++tp]=head[y];head[y]=tp;end[tp]=x;len[tp]=z;
	}
	for(i=1;i<=400000;i++)dis[i]=inf;
	dis[1]=0;
	
	if(dij(1,n+n,1,n+n)<inf)printf("%d\n",dis[n+n]);else puts("0");
	return 0;
}
		

spi：太神了不会做TAT

prz：考虑两条对角线相交就是说一条对角线的一个端点在另一条的两个端点之间，而另一个端点不在两个端点之间，那么对于每一条对角线只需要找到一个端点在这条对角线的端点之间的对角线中另一个端点最远的，那么就变成了一个rmq问题，ST算法加读入优化可以卡着时间和内存过。。。（标算应该是\(O(m)\)的，然而我不会。。）

#include<cstdio>
#include<cmath>
int n,m;
struct point{int x,y,yw;}a[10000001];
int b[32][1000001];
int max(int x,int y){return a[x].y>a[y].y?x:y;}
void read(int &a){int ch;do ch=getchar();while(ch<48||ch>57);a=0;do{a=a*10+ch-48;ch=getchar();}while(ch>47&&ch<58);}
int main()
{
	int i,j,k;
	//scanf("%d%d",&n,&m);
	read(n);read(m);
	for(i=1;i<=m;i++)
	{
		int x,y;
		//scanf("%d%d",&x,&y);
		read(x);read(y);
		if(x>y){int t=x;x=y;y=t;}
		a[i].x=x;a[i].y=y;a[i].yw=i;
		if(b[0][x]==0||a[b[0][x]].y<y)b[0][x]=i;
	}
	for(i=1,j=1;j<=n;i++,j<<=1)
	for(k=1;k+j<=n;k++)b[i][k]=max(b[i-1][k],b[i-1][k+j]);
	for(i=1;i<=m;i++)
	{
		j=(int)log2(a[i].y-a[i].x-1);
		int ans=max(b[j][a[i].x+1],b[j][a[i].y-(1<<j)]);
		if(a[ans].y>a[i].y){printf("%d %d\n",i,ans);break;}
	}
	if(i>m)puts("NIE");
	return 0;
}

stu：就是黈力膜你赛“走走走”题，floyd就好了

#include<cstdio>
#include<cstring>
int n,m;
long long a[301][301];
int b[301][301];
int ans[301],tp=0;
int main()
{
	int i,j,k;
	//freopen("walk.in","r",stdin);freopen("walk.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(a,0x3f,sizeof(a));
	//for(i=1;i<=n;i++){a[i][i]=0;b[i][i]=1;}
	for(i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		z=-z;
		if(a[x][y]>z)a[x][y]=z;
		b[x][y]=1;
	}
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	for(k=1;k<=n;k++)
	{
		if(a[j][i]+a[i][k]<a[j][k])a[j][k]=a[j][i]+a[i][k];
		b[j][k]|=b[j][i]&b[i][k];
	}
	//for(i=1;i<=n;i++){for(j=1;j<=n;j++)printf("%d ",a[i][j]);puts("");}
	 
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)if(a[j][j]<0&&b[i][j]&&b[j][i]){ans[++tp]=i;break;}
	printf("%d\n",tp);
	for(i=1;i<=tp;i++)printf("%d ",ans[i]);puts("");
	//fclose(stdout);
	return 0;
}

moz：暴力出奇迹！\(O(\frac {n^4} {32})\)可过不要虚

#include<cstdio>
#include<bitset>
int n;
int l[301],a[301][301];
int ans[301];
std::bitset<301> b[100001];
int main()
{
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&l[i]);
		for(j=1;j<=l[i];j++){scanf("%d",&a[i][j]);b[a[i][j]][i]=1;}
	}
	for(i=1;i<=n;i++)
	for(j=1;j<=l[i];j++)
	for(k=j+1;k<=l[i];k++)
	{
		int a1=(b[a[i][j]]&~b[a[i][k]]).count(),a2=(b[a[i][k]]&~b[a[i][j]]).count();
		ans[i]+=a1*a2;
		//printf("i=%d j=%d k=%d a1=%d a2=%d\n",i,j,k,a1,a2);
	}
	for(i=1;i<=n;i++)printf("%d\n",ans[i]);
	return 0;
}

zak：后缀数组模板题，扭出height之后就随便搞了

#include<cstdio>
#include<cstring>
int n;
char s[510001];
int l;
int sa[1010001],rank[1010001],tsa[1010001],trank[1010001];
int h[1010001];
int sum[1120001];
int ans[500001];
int max(int a,int b){return a>b?a:b;}
int main()
{
	int i,j,k;
	scanf("%d",&n);
	scanf("%s",s);
	const int l=n;
	int p=255;
    for(i=0;i<l;i++)trank[i+1]=s[i];
    for(i=1;i<=l;i++)sum[trank[i]]++;
    for(i=1;i<=p;i++)sum[i]+=sum[i-1];
    for(i=l;i>=1;i--)sa[sum[trank[i]]--]=i;
    rank[sa[1]]=p=1;
    for(i=2;i<=l;i++)
    {
        if(trank[sa[i]]>trank[sa[i-1]])p++;
        rank[sa[i]]=p;
    }
    for(j=1;j<=l;j*=2)
    {
        memset(sum,0,sizeof(sum));
        for(i=1;i<=l;i++)sum[rank[i+j]]++;
        for(i=1;i<=p;i++)sum[i]+=sum[i-1];
        for(i=l;i>0;i--)tsa[sum[rank[i+j]]--]=i;
        memset(sum,0,sizeof(sum));
        for(i=1;i<=l;i++)sum[rank[i]]++;
        for(i=1;i<=p;i++)sum[i]+=sum[i-1];
        for(i=l;i>0;i--)sa[sum[rank[tsa[i]]]--]=tsa[i];trank[sa[1]]=p=1;
        trank[sa[1]]=p=1;
        for(i=2;i<=l;i++)
        {
            if(rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+j]!=rank[sa[i-1]+j])p++;
            trank[sa[i]]=p;
        }
        for(i=1;i<=l;i++)rank[i]=trank[i];
    }
	for(i=1,j=0;i<=l;i++)
	{
		if(rank[i]==1)continue;
		for(;s[i+j-1]==s[sa[rank[i]-1]+j-1];j++);
		h[rank[i]]=j;
		if(j>0)j--;
	}
	ans[sa[1]]=h[2];
	for(i=2;i<n;i++)ans[sa[i]]=max(h[i],h[i+1]);
	ans[sa[n]]=h[n];
	for(i=1;i<=n;i++)printf("%d\n",ans[i]);
	return 0;
}

kli：首先你要知道有个叫五边形数定理的东西，然后就没有了

#include<cstdio>
//#include<ctime>
int n,m;
const int mod=1000000000-401;
int a[200001];
long long p[200001];
long long power(long long a,long long b){long long ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
int main()
{
	int i,j,k;
	scanf("%d%d",&n,&m);
	//int tttt=clock();
	a[0]=0;
	for(i=1;i<=100000;i++)
	{
		a[i+i-1]=i*(3*i-1)/2;
		a[i+i]=(-i)*(-3*i-1)/2;
	}
	//for(i=1;i<=100;i++)printf("%d ",a[i]);puts("");
	p[0]=1;
	for(i=1;i<=n;i++)
	for(j=1;a[j]<=i;j++)if(j%4==1||j%4==2)
	{
		p[i]+=p[i-a[j]];
		if(p[i]>=mod-1)p[i]-=mod-1;
	}
	else 
	{
		p[i]-=p[i-a[j]];
		if(p[i]<0)p[i]+=mod-1;
	}
	printf("%lld\n",power(m,p[n]));
	//printf("%d\n",clock()-tttt);
	return 0;
}

pod：大力容斥就好了，扭脖了好几天才想出来。。。太差了

#include<cstdio>
#include<cstring>
int n,m,k,d;
int mod=1000000009;
int ans;
struct mat
{
	long long a[21][21];
	int x,y;
	mat(int xx=0,int yy=0){x=xx;y=yy;memset(a,0,sizeof(a));}
	mat operator *(const mat &b)const
	{
		mat c(x,b.y);
		int i,j,k;
		for(i=1;i<=x;i++)
		for(j=1;j<=b.y;j++)
		for(k=1;k<=y;k++)c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%mod)%mod;
		return c;
	}
	mat operator *=(const mat &b){return *this=*this*b;}
	void print()
	{
		for(int i=1;i<=x;i++)
		{
			for(int j=1;j<=y;j++)printf("%d ",a[i][j]);
			puts("");
		}
		puts("");
	}
}a,b;
mat power(mat a,int b)
{
	mat ans(n,n);
	for(int i=1;i<=n;i++)ans.a[i][i]=1;
	for(;b;b>>=1,a*=a)if(b&1)ans*=a;
	return ans;
}
int ppcnt(int a){int x=0;for(;a;a-=a&-a)x++;return x;}
int main()
{
	int i,j,l;
	scanf("%d%d%d%d",&n,&m,&k,&d);
	if(d==1)
	{
		printf("%d\n",k);
		return 0;
	}
	d--;
	a.x=a.y=b.x=b.y=n;
	for(i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a.a[x][y]=a.a[y][x]=1;
	}
	for(i=0;i<(1<<k);i++)
	{
		for(j=1;j<=n;j++)
		for(l=1;l<=n;l++)if(i&(1<<j-1)|i&(1<<l-1))b.a[j][l]=0;else b.a[j][l]=a.a[j][l];
		//b.print();
		b=power(b,d);
		
		int s=0;
		for(j=1;j<=n;j++)
		for(l=1;l<=n;l++)s=(s+b.a[j][l])%mod;
		if(ppcnt(i)&1)ans=(ans-s+mod)%mod;else ans=(ans+s)%mod;
		//printf("i=%d s=%lld\n",i,s);
	}
	printf("%d\n",ans);
	return 0;
}

sza：按行或列或对角线排序，然后那些能挡路的就一定是前驱或后继了，螺一螺就好了

#include<cstdio>
#include<algorithm>
using std::sort;
int n,m;
struct piece{int x,y,yw;char c;}a[200001];
long long ans[200001];
int cmpx(piece x,piece y){return x.x<y.x||x.x==y.x&&x.y<y.y;}
int cmpy(piece x,piece y){return x.y<y.y||x.y==y.y&&x.x<y.x;}
int cmpp(piece x,piece y){return x.x+x.y<y.x+y.y||x.x+x.y==y.x+y.y&&x.y<y.y;}
int cmpm(piece x,piece y){return x.x-x.y<y.x-y.y||x.x-x.y==y.x-y.y&&x.y<y.y;}
int find(int x,int y)
{
	if(x<1||x>m||y<1||y>m)return 1;
	int ll=0,rr=n+1,mm;
	while(ll<rr-1)
	{
		mm=ll+rr>>1;
		//if(a[mm].x==x&&a[mm].y==y)return mm;
		if(a[mm].x<x||a[mm].x==x&&a[mm].y<y)ll=mm;else rr=mm;
	}
	if(a[rr].x==x&&a[rr].y==y)return 1;else return 0;
}
int main()
{
	int i,j,k;
	//freopen("sza7.in","r",stdin);freopen("sza.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		char ch[11];
		scanf("%s",ch);
		a[i].c=ch[0];
		scanf("%d%d",&a[i].x,&a[i].y);a[i].yw=i;
	}
	sort(a+1,a+n+1,cmpx);
	for(i=1;i<=n;i++)
	{
		if(a[i].c=='H'||a[i].c=='W')
		{
			if(i==1||a[i-1].x<a[i].x)ans[a[i].yw]+=a[i].y-1;else ans[a[i].yw]+=a[i].y-a[i-1].y-1;
			if(i==n||a[i+1].x>a[i].x)ans[a[i].yw]+=m-a[i].y;else ans[a[i].yw]+=a[i+1].y-a[i].y-1;
		}
		else if(a[i].c=='K')
		{
			if(a[i].x>1&&(i==1||!(a[i-1].x==a[i].x&&a[i-1].y==a[i].y-1)))ans[a[i].yw]++;
			if(a[i].x<m&&(i==n||!(a[i+1].x==a[i].x&&a[i+1].y==a[i].y+1)))ans[a[i].yw]++;
		}
		else if(a[i].c=='S')
		{
			if(!find(a[i].x-1,a[i].y-2))ans[a[i].yw]++;
			if(!find(a[i].x+1,a[i].y-2))ans[a[i].yw]++;
			if(!find(a[i].x-1,a[i].y+2))ans[a[i].yw]++;
			if(!find(a[i].x+1,a[i].y+2))ans[a[i].yw]++;
			if(!find(a[i].x-2,a[i].y-1))ans[a[i].yw]++;
			if(!find(a[i].x+2,a[i].y-1))ans[a[i].yw]++;
			if(!find(a[i].x-2,a[i].y+1))ans[a[i].yw]++;
			if(!find(a[i].x+2,a[i].y+1))ans[a[i].yw]++;
		}
	}
	sort(a+1,a+n+1,cmpy);
	for(i=1;i<=n;i++)
	{
		if(a[i].c=='H'||a[i].c=='W')
		{
			if(i==1||a[i-1].y<a[i].y)ans[a[i].yw]+=a[i].x-1;else ans[a[i].yw]+=a[i].x-a[i-1].x-1;
			if(i==n||a[i+1].y>a[i].y)ans[a[i].yw]+=m-a[i].x;else ans[a[i].yw]+=a[i+1].x-a[i].x-1;
		}
		else if(a[i].c=='K')
		{
			if(a[i].y>1&&(i==1||!(a[i-1].y==a[i].y&&a[i-1].x==a[i].x-1)))ans[a[i].yw]++;
			if(a[i].y<m&&(i==n||!(a[i+1].y==a[i].y&&a[i+1].x==a[i].x+1)))ans[a[i].yw]++;
		}
	}
	sort(a+1,a+n+1,cmpp);
	for(i=1;i<=n;i++)
	{
		if(a[i].c=='H'||a[i].c=='G')
		{
			if(i==1||a[i-1].x+a[i-1].y<a[i].x+a[i].y)ans[a[i].yw]+=(a[i].x+a[i].y<=m?a[i].y-1:m-a[i].x);else ans[a[i].yw]+=a[i].y-a[i-1].y-1;
			if(i==n||a[i+1].x+a[i+1].y>a[i].x+a[i].y)ans[a[i].yw]+=(a[i].x+a[i].y<=m?a[i].x-1:m-a[i].y);else ans[a[i].yw]+=a[i+1].y-a[i].y-1;
		}
		else if(a[i].c=='K')
		{
			if(a[i].y>1&&a[i].x<m&&(i==1||!(a[i-1].y==a[i].y-1&&a[i-1].x==a[i].x+1)))ans[a[i].yw]++;
			if(a[i].y<m&&a[i].x>1&&(i==n||!(a[i+1].y==a[i].y+1&&a[i+1].x==a[i].x-1)))ans[a[i].yw]++;
		}
	}
	sort(a+1,a+n+1,cmpm);
	for(i=1;i<=n;i++)
	{
		if(a[i].c=='H'||a[i].c=='G')
		{
			if(i==1||a[i-1].x-a[i-1].y<a[i].x-a[i].y)ans[a[i].yw]+=(a[i].x-a[i].y<=0?a[i].x-1:a[i].y-1);else ans[a[i].yw]+=a[i].x-a[i-1].x-1;
			if(i==n||a[i+1].x-a[i+1].y>a[i].x-a[i].y)ans[a[i].yw]+=(a[i].x-a[i].y<=0?m-a[i].y:m-a[i].x);else ans[a[i].yw]+=a[i+1].x-a[i].x-1;
		}
		else if(a[i].c=='K')
		{
			if(a[i].y>1&&a[i].x>1&&(i==1||!(a[i-1].y==a[i].y-1&&a[i-1].x==a[i].x-1)))ans[a[i].yw]++;
			if(a[i].y<m&&a[i].x<m&&(i==n||!(a[i+1].y==a[i].y+1&&a[i+1].x==a[i].x+1)))ans[a[i].yw]++;
		}
	}
	for(i=1;i<=n;i++)printf("%lld\n",ans[i]);
	return 0;
}
			

sej：kmp求循环节，然后\(O(n)\)找到那个所有点离它距离最小的点就好了

#include<cstdio>
int n,m;
char s[1000001];
int a[2000001],b[1000001];
int c[1000001];
int ln;
long long ans;
int main()
{
	int i,j,k;
	scanf("%d%d%s",&n,&m,s);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	b[0]=-1;j=-1;
	for(i=1;i<m;i++)
	{
		while(j>=0&&s[j+1]!=s[i])j=b[j];
		if(s[j+1]==s[i])j++;
		b[i]=j;
	}
	if(m%(m-(b[m-1]+1))==0)ln=m-(b[m-1]+1);else ln=m;
	for(i=1;i<=n;i++)a[i]%=ln;
	for(i=1;i<=n;i++)c[a[i]]++;
	for(i=0;i<ln;i++)
	{
		for(j=1;j<=c[i];j++)a[c[i-1]+j]=i;
		c[i]+=c[i-1];
	}
	for(i=n+1;i<=n+n;i++)a[i]=a[i-n]+ln;
	//for(i=1;i<=n+n;i++)printf("%d ",a[i]);puts("");
	long long sm=0;
	for(j=1;j<=n&&a[j]-a[1]<=ln/2;j++)sm+=a[j]-a[1];
	for(i=j;i<=n;i++)sm+=ln-(a[i]-a[1]);
	ans=sm;
	//printf("sm=%lld\n",sm);
	for(i=2;i<=n;i++)
	{
		sm-=1ll*(j-i)*(a[i]-a[i-1]);
		sm+=1ll*(n-(j-i))*(a[i]-a[i-1]);
		for(;j<=n+i&&a[j]-a[i]<=ln/2;j++)
		{
			sm-=ln-(a[j]-a[i]);sm+=a[j]-a[i];
		}
		if(sm<ans)ans=sm;
		//printf("sm=%lld\n",sm);
	}
	printf("%lld\n",ans);
	return 0;
}

smo：神题。。0人A。。推了下发现好像是个卷积？然而它不是离散的？所以要用连续傅里叶变换？这是什么鬼啊。。反正我是不会做

zie：区间dp，类似于取石子石子合并，\(O(n^3*k)\)

#include<cstdio>
int n,k;
int x[201],y[201];
int a[201][201];
int f[101][201][101];
int cj(int x1,int y1,int x2,int y2){return x1*y2-y1*x2;}
int main()
{
	int i,j,ii,jj;
	//freopen("zie.in","r",stdin);
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
	if(cj(x[2]-x[1],y[2]-y[1],x[3]-x[2],y[3]-y[2])<0)
	{
		for(i=1,j=n;i<j;i++,j--){int t=x[i];x[i]=x[j];x[j]=t;t=y[i];y[i]=y[j];y[j]=t;}
	}
	for(i=n+1;i<=n+n;i++){x[i]=x[i-n];y[i]=y[i-n];}
	for(i=1;i<=2*n;i++)
	for(j=1;i+j<=2*n;j++)a[i][i+j]=a[i][i+j-1]+cj(x[i+j-1]-x[i],y[i+j-1]-y[i],x[i+j]-x[i],y[i+j]-y[i]);
	for(i=1;i<=n;i++)
	for(j=1;j+i<=2*n;j++)
	{
		//printf("i=%d j=%d j+i=%d\n",i,j,j+i);
		f[i][j][1]=a[j][j+i];
	}
	for(i=1;i<=n;i++)
	for(j=1;j+i<=n*2;j++)
	for(ii=2;ii<=k;ii++)
	{
		//printf("i=%d j=%d ii=%d\n",i,j,ii);
		f[i][j][ii]=f[i][j][ii-1];
		for(jj=j;jj<=j+i;jj++)
		if(f[jj-j][j][ii-1]+a[jj][j+i]<f[i][j][ii])f[i][j][ii]=f[jj-j][j][ii-1]+a[jj][j+i];
	}
	int ans=1<<30;
	for(i=1;i<=n;i++)if(f[n][i][k]<ans)ans=f[n][i][k];
	printf("%.1lf\n",(a[1][n+1]-ans)/2.0);
	return 0;
}
	

jab：大力分类讨论，用树状数组维护前缀最大值就好了。。这么简单的题扭脖了好几天都没想出来。。扭脖了那么多天居然连分类讨论都想不到。。还是黈力一语道破天机。。果然还是太弱了啊TAT。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
struct point{int x,y;}a[100001],b[100001];
int xp[200001],ap[200001],bp[200001];
int np,mp;
int bit[200001];
int ans=1<<30;
void ins(int wz,int p)
{
	int i,j,k;
	for(i=wz;i<=mp;i+=i&-i)if(bit[i]<p)bit[i]=p;
}
int ask(int wz)
{
	int i,j,k;
	int ans=-(1<<29);
	for(i=wz;i;i-=i&-i)if(bit[i]>ans)ans=bit[i];
	return ans;
}
int cmp(point x,point y){return x.x<y.x||x.x==y.x&&x.y<y.y;}
int main()
{
	int i,j,k;
	//freopen("jab.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
	for(i=1;i<=m;i++)scanf("%d%d",&b[i].x,&b[i].y);
	sort(a+1,a+n+1,cmp);sort(b+1,b+m+1,cmp);
	/*for(i=1;i<=n;i++)xp[i]=a[i].x;for(i=1;i<=m;i++)xp[i+n]=b[i].x;
	merge(xp+1,xp+n+1,xp+n+1,xp+n+m+1,ap+1);
	np=unique(ap+1,ap+n+m+1)-ap-1;
	for(i=1;i<=n;i++)a[i].x=lower_bound(ap+1,ap+np+1,a[i].x)-ap;
	for(i=1;i<=m;i++)b[i].x=lower_bound(ap+1,ap+np+1,b[i].x)-ap;*/
	for(i=1;i<=n;i++)bp[i]=a[i].y;for(i=1;i<=m;i++)bp[i+n]=b[i].y;
	sort(bp+1,bp+n+m+1);
	mp=unique(bp+1,bp+n+m+1)-bp-1;
	for(i=1;i<=n;i++)a[i].y=lower_bound(bp+1,bp+mp+1,a[i].y)-bp;
	for(i=1;i<=m;i++)b[i].y=lower_bound(bp+1,bp+mp+1,b[i].y)-bp;
	//for(i=1;i<=mp;i++)printf("%d ",bp[i]);puts("");
	
	for(i=1;i<=200000;i++)bit[i]=-(1<<29);
	for(i=1,j=1;j<=m;j++)
	{
		while(i<=n&&a[i].x<=b[j].x){ins(a[i].y,a[i].x+bp[a[i].y]);i++;}
		int t=b[j].x+bp[b[j].y]-ask(b[j].y);
		if(bp[b[j].y]<0)printf("b[j].y=%d mp=%d\n",b[j].y,mp);
		//printf("a[i].x+bp[a[i].y]=%d b[j].x+bp[b[j].y]=%d t=%d\n",a[i].x+bp[a[i].y],b[j].x+bp[b[j].y],t);
		if(t<ans)ans=t;
	}
	//printf("ans=%d\n",ans);
	for(i=1;i<=200000;i++)bit[i]=-(1<<29);
	for(i=1,j=1;j<=m;j++)
	{
		while(i<=n&&a[i].x<=b[j].x){ins(mp+1-a[i].y,a[i].x-bp[a[i].y]);i++;}
		int t=b[j].x-bp[b[j].y]-ask(mp+1-b[j].y);
		if(t<ans)ans=t;
	}
	//printf("ans=%d\n",ans);
	for(i=1;i<=200000;i++)bit[i]=-(1<<29);
	for(i=n,j=m;j>0;j--)
	{
		while(i>0&&a[i].x>=b[j].x){ins(a[i].y,-a[i].x+bp[a[i].y]);i--;}
		int t=-b[j].x+bp[b[j].y]-ask(b[j].y);
		if(t<ans)ans=t;
		//printf("i=%d j=%d t=%d\n",i,j,t);
	}
	//printf("ans=%d\n",ans);
	for(i=1;i<=200000;i++)bit[i]=-(1<<29);
	for(i=n,j=m;j>0;j--)
	{
		while(i>0&&a[i].x>=b[j].x){ins(mp+1-a[i].y,-a[i].x-bp[a[i].y]);i--;}
		int t=-b[j].x-bp[b[j].y]-ask(mp+1-b[j].y);
		if(t<ans)ans=t;
	}
	printf("%d\n",ans);
	return 0;
}
	
	
	

nie：排序后扫一遍就没了

#include<cstdio>
#include<algorithm>
int n,m;
int a[100002],b[100001];
int ans=1<<30;
int main()
{
	int i,j,k;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<=m;i++)scanf("%d",&b[i]);
	std::sort(a+1,a+n+1);
	std::sort(b+1,b+m+1);
	a[n+1]=1<<30;
	for(i=1,j=1;i<=m;i++)
	{
		for(;a[j]<=b[i];j++);
		if(a[j]-b[i]<ans)ans=a[j]-b[i];
		if(b[i]-a[j-1]<ans)ans=b[i]-a[j-1];
		if(ans==0)break;
	}
	printf("%d\n",ans);
	return 0;
}

fun：就是求合法的排列数使得根据排列置换后得到的函数是个菊花森林，那么显然如果有f[i]=i那么h[g[i]]=i，剩下的没在f中出现的值是可以任意排列的，于是就做完了。（吐槽：main上的数据范围真是奇葩。。n=1000000的题通常是\(O(n*log n)\)的算法，而n=200000的题却有\(O(n)\)算法。。。）

#include<cstdio>
int n,a[200001];
int b[200001];
long long fac[200001],nfac[200001];
const int mod=1000000007;
long long ans;
long long power(long long a,int b){long long ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
int main()
{
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++){scanf("%d",&a[i]);b[a[i]]++;}
	fac[0]=1;
	for(i=1;i<=200000;i++)fac[i]=fac[i-1]*i%mod;
	nfac[200000]=power(fac[200000],mod-2);
	for(i=199999;i>=0;i--)nfac[i]=nfac[i+1]*(i+1)%mod;
	ans=1;
	int np=n;
	for(i=1;i<=n;i++)if(b[i]){ans=ans*b[i]%mod;np--;}
	ans=ans*fac[np]%mod;
	//for(i=1;i<=n;i++)if(b[i])ans=ans*nfac[b[i]-1]%mod;
	printf("%lld\n",ans);
	return 0;
}
	
	

odb：幻想乡重建计划Byteland重建计划，就是黈力膜你赛的“邮邮邮”题，把点分5组然后两两螺杆，注意特判n=7

#include<cstdio>
int n;
int a[101];
int b[6];
int p[10001],isp[10001],tp=0;
int main()
{
	int i,j,k,l;
	scanf("%d",&n);
	isp[1]=1;
	for(i=2;i<=10000;i++)
	{
		if(!isp[i])p[++tp]=i;
		for(j=1;j<=tp&&p[j]*i<=10000;j++)
		{
			isp[p[j]*i]=1;
			if(i%p[j]==0)break;
		}
	}
	for(i=1;i<=n;i++)a[i]=1;
	if(n==7)
	{
		printf("%d\n%d\n%d\n%d\n%d\n%d\n%d\n",2*3*5,2*7*11,2*13*17,3*7*13*19,3*7*13*23,5*11*17*19*23*29,5*11*17*19*23);
		return 0;
	}
	else
	{
		for(i=1;i<6;i++)b[i]=n/5;
		for(i=6-n%5;i<6;i++)b[i]++;
		for(i=1;i<6;i++)b[i]+=b[i-1];
		k=0;
		for(i=1;i<6;i++)
		for(j=i+1;j<6;j++)
		{
			k++;
			for(l=b[i-1]+1;l<=b[i];l++)a[l]*=p[k];
			for(l=b[j-1]+1;l<=b[j];l++)a[l]*=p[k];
		}
		for(i=1;i<6;i++)
		for(j=b[i-1]+2;j<=b[i];j++)a[j]*=p[k+j-b[i-1]-1];
	}
	for(i=1;i<=n;i++)printf("%d\n",a[i]);
	return 0;
}
		

pra：dp，然后树状数组维护前缀和

#include<cstdio>
#include<algorithm>
int n,m,k,r;
struct line{int a,b;}a[1000001];
int f[1000001];
int bit[200001];
int cmp(line a,line b){return a.a<b.a||a.a==b.a&&a.b>b.b;}
int main()
{
	int i,j,ii,jj;
	scanf("%d%d%d%d",&n,&m,&k,&r);
	for(i=1;i<=k;i++)scanf("%d%d",&a[i].a,&a[i].b);
	std::sort(a+1,a+k+1,cmp);
	for(i=1;i<=k;i++)
	{
		f[i]=1;
		for(ii=a[i].b-1;ii;ii-=ii&-ii)f[i]=(f[i]+bit[ii])%r;
		for(ii=a[i].b;ii<=m;ii+=ii&-ii)bit[ii]=(bit[ii]+f[i])%r;
	}
	int ans=1;
	for(i=m;i;i-=i&-i)ans=(ans+bit[i])%r;
	printf("%d\n",ans);
	return 0;
}
		
		

wyz：搞一条长链然后在一端接一大堆点就好了，注意边界情况

#include<cstdio>
int n,d;
int main()
{
	int i,j,k;
	scanf("%d%d",&n,&d);
	if(n==1)
	{
		if(d==0)puts("");else puts("BRAK");
	}
	else if(n==2)
	{
		if(d==1)puts("1 2");else puts("BRAK");
	}
	else if(n<=d||d<2)puts("BRAK");else
	{
		for(i=2;i<=d;i++)printf("%d %d\n",i,i-1);
		for(i=d+1;i<=n;i++)printf("%d %d\n",i,d);
	}
	return 0;
}

感觉跳过的题有点多？没办法毕竟太弱

过半了真开心，然而剩下的题目似乎都不是很切得动的样子。。。没办法毕竟太弱，使劲切吧

那两道组合计数题真是丧病。。

开学了估计切题时间要大大减少了。。TAT不知道什么时候能填完了