【BZOJ 1414】[ZJOI2009] 对称的正方形

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1414

题号“1414”,还真的是把我做得“要死要死的”!做了一整天QAQ
Hash version:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
 
const int MX = 0;
const int MAXN = 2000+9;
unsigned int SEEDX = 37;
unsigned int SEEDY = 137;
 
int n,m; LL vout;
unsigned int px[2000+9],py[2000+9],mat[MAXN][MAXN],f[5][MAXN][MAXN];
 
inline int read(){
    char c=getchar(); int ret=0;
    while (c<'0'||c>'9') c=getchar();
    while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
    return ret;
}
 
inline void init(){
    m = read(); n = read(); vout = (unsigned int)n*m;
    for (int j=1;j<=m;j++) {
        for (int i=1;i<=n*2+1;i++) mat[i][j*2-1] = MX;
        for (int i=1;i<=n;i++) mat[i*2][j*2] = read(), mat[i*2-1][j*2] = MX;
        mat[n*2+1][j*2] = MX;
    } for (int i=1;i<=n*2+1;i++) mat[i][m*2+1] = MX;
    n = n*2+1; m = m*2+1;
}
 
inline void Hash_init(){
    px[0] = 1; for (int i=1;i<=2001;i++) px[i] = SEEDX*px[i-1];
    py[0] = 1; for (int i=1;i<=2001;i++) py[i] = SEEDY*py[i-1];
    for (int i=n,g=1;i;i--,g++) for (int j=1,h=1;j<=m;j++,h++) f[1][i][j] = px[g]*py[h]*mat[i][j] + f[1][i+1][j] + f[1][i][j-1] - f[1][i+1][j-1];
    for (int i=1,g=1;i<=n;i++,g++) for (int j=1,h=1;j<=m;j++,h++) f[2][i][j] = px[g]*py[h]*mat[i][j] + f[2][i-1][j] + f[2][i][j-1] - f[2][i-1][j-1];
    for (int i=1,g=1;i<=n;i++,g++) for (int j=m,h=1;j;j--,h++) f[3][i][j] = px[g]*py[h]*mat[i][j] + f[3][i-1][j] + f[3][i][j+1] - f[3][i-1][j+1];
    for (int i=n,g=1;i;i--,g++) for (int j=m,h=1;j;j--,h++) f[4][i][j] = px[g]*py[h]*mat[i][j] + f[4][i+1][j] + f[4][i][j+1] - f[4][i+1][j+1];
}
 
inline unsigned int Get_Hash(int t, int x1, int y1, int x2, int y2){
    if (t == 1) return (f[1][x1][y1] + f[1][x2+1][y2-1] - f[1][x2+1][y1] - f[1][x1][y2-1]) * px[2001-(n-x1+1)] * py[2001-y1];
    else if (t == 2) return (f[2][x1][y1] + f[2][x2-1][y2-1] - f[2][x2-1][y1] - f[2][x1][y2-1])* px[2001-x1] * py[2001-y1];
    else if (t == 3) return (f[3][x1][y1] + f[3][x2-1][y2+1] - f[3][x2-1][y1] - f[3][x1][y2+1]) * px[2001-x1] * py[2001-(m-y1+1)];
    else return (f[4][x1][y1] + f[4][x2+1][y2+1] - f[4][x2+1][y1] - f[4][x1][y2+1]) * px[2001-(n-x1+1)] * py[2001-(m-y1+1)];
}
 
inline bool judge(int x, int y, int len){
    unsigned int t1 = Get_Hash(1,x,y,x+len,y-len),t2 = Get_Hash(2,x,y,x-len,y-len);
    if (t1 != t2) return false;
    t1 = Get_Hash(3,x,y,x-len,y+len);
    if (t1 != t2) return false;
    t2 = Get_Hash(4,x,y,x+len,y+len);
    if (t1 != t2) return false;
    else return true;
}
 
inline void solve(){
    for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if ((i&1) + (j&1) != 1) {
        int l=2,r=min(min(i-1,j-1),min(n-i,m-j)),ans=0,mid;
        while (l <= r) {
            mid = l + r >> 1;
            if (judge(i,j,mid)) l = mid+1, ans = mid;
            else r = mid-1;
        }vout += ans/2;
    }
}
 
int main(){
    init(); Hash_init(); solve();
    printf("%lld\n",vout);
    return 0;
}  

Manacher version:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
 
const int MAXN = 2000+9;
 
int mat[MAXN][MAXN],n,m,tmp[MAXN],ans[MAXN],que[MAXN],tot,pos[MAXN];
int res_x[MAXN][MAXN],res_y[MAXN][MAXN],sa_y[MAXN][MAXN],sa_x[MAXN][MAXN];
 
inline int read(){
    char c=getchar(); int ret=0;
    while (c<'0'||c>'9') c=getchar();
    while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
    return ret;
}
 
inline void manacher(int lim){
    int MX=0; ans[0] = 0;
    for (int i=1;i<=lim;i++) {
        if (MX+ans[MX] > i) ans[i] = min(MX+ans[MX]-i, ans[MX*2-i]);
        else ans[i] = 0;
        while (tmp[i+ans[i]+1] == tmp[i-ans[i]-1]) ans[i]++;
        if (ans[i]+i > MX+ans[MX]) MX = i;
    }
}
 
inline void DP(int lim){
    tot = 0; pos[0] = 0; int sta = 0;
    for (int i=1;i<=lim;i++) {
        while (tot && ans[i] <= que[tot]) tot--; sta = min(sta, tot);
        que[++tot] = ans[i]; pos[tot] = i; int w = sta;
        while (w < tot && min(que[w],(i-pos[w-1])*2-1) <= min(que[w+1],(i-pos[w])*2-1)) w++;
        sta = w; tmp[i] = min(que[w],(i-pos[w-1])*2-1);
    } 
}

int main(){
    m = read(); n = read();
    for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) mat[i*2][j*2] = read();
    n = n * 2 + 1; m = m * 2 + 1;
     
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) tmp[j] = mat[i][j]; tmp[0] = -1; tmp[m+1] = -2;
        manacher(m); 
        for (int j=1;j<=m;j++) sa_y[i][j] = ans[j];
    }
    for (int j=1;j<=m;j++) {
        for (int i=1;i<=n;i++) ans[i] = sa_y[i][j]*2+1;
        DP(n);
        for (int i=1;i<=n;i++) res_x[i][j] = tmp[i];
        for (int i=1;i*2<=n;i++) swap(ans[i],ans[n-i+1]);
        DP(n);
        for (int i=1;i<=n;i++) res_x[i][j] = min(res_x[i][j],tmp[n-i+1]);
    } 
         
    for (int j=1;j<=m;j++) {
        for (int i=1;i<=n;i++) tmp[i] = mat[i][j]; tmp[0] = -1; tmp[n+1] = -2;
        manacher(n); 
        for (int i=1;i<=n;i++) sa_x[i][j] = ans[i];
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) ans[j] = sa_x[i][j]*2+1;
        DP(m);
        for (int j=1;j<=m;j++) res_y[i][j] = tmp[j];
        for (int j=1;j*2<=m;j++) swap(ans[j],ans[m-j+1]);
        DP(m);
        for (int j=1;j<=m;j++) res_y[i][j] = min(res_y[i][j], tmp[m-j+1]);
    } 
     
    LL vout = (n/2)*(m/2);
    for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if ((i+j) % 2 == 0)
        vout += max(0,(min(res_x[i][j]-1,res_y[i][j]-1)/2)/2);
    printf("%lld\n",vout);
    return 0;
} 

【BZOJ 1505】[NOI2004] 小H的小屋

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1505

仍然是决策单调性QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 100+9;
const int MX = 100;

double f[2][MAXN][MAXN],k1,k2;
int n,m,sz[MAXN],sta=1;

#define cal_up(l,r) (k1*((r)-(l))*((r)-(l)))

inline double cal_down(int l, int r, int t){
	int len = r-l, tmp = 0; double ret = 0;
	for (int i=1;i<=t;i++) sz[i] = len/t, tmp += sz[i];
	while (tmp < len) for (int i=1;i<=t && tmp < len;i++) sz[i]++, tmp++;
	for (int i=1;i<=t;i++) ret += k2*sz[i]*sz[i];
	return ret; 
}

inline void Dynamic_Programing(int w, int t){
	for (int i=1;i<=MX;i++) memset(f[w][i],0,sizeof(f[w][i]));
	for (int j=1,t1=1,t2=1;j<=n;j++,t1=1,t2=1) for (int i=1;i<=MX;i++) if (j <= i) {
		for (int h=max(1,t1-3);h<i;h++) for (int g=max(t2-3,1);g<j;g++) if (f[t][h][g]) {			
			double tmp = f[t][h][g] + cal_up(h,i) + cal_down(h,i,j-g);
			if (!f[w][i][j] || f[w][i][j] > tmp) f[w][i][j] = tmp, t1=h, t2=g;
		}
	}
}

int main(){
	scanf("%lf%lf%d%d",&k1,&k2,&m,&n);
	for (int i=1;i<=MX;i++) for (int j=1,lim=min(n,i);j<=lim;j++)
		f[1][i][j] = cal_up(0,i) + cal_down(0,i,j);
	for (int k=2;k<=m;k++,sta^=1) Dynamic_Programing(sta^1,sta);
	printf("%.1lf\n",f[sta][MX][n]);
	return 0;
} 

【BZOJ 2216】[Poi2011] Lightning Conductor

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2216

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 500000+9;
const double EPS = 1e-8;

int arr[MAXN],n,f[MAXN],l[MAXN],r[MAXN],que[MAXN],head,tail;

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret;
}

inline double cal(int a, int b){
	return sqrt(abs(a-b)) + arr[a];
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) arr[i] = read();
	
	l[tail=head=1] = 1; r[1] = n; que[1]=1;
	for (int i=2;i<=n;i++) {
		l[tail]++;
		while (tail <= head && r[tail] < l[tail]) tail++;
		f[i] = max(f[i], int(ceil(cal(que[tail],i))+EPS));
		if (cal(i,r[head]) < cal(que[head],r[head])) continue;
		else {
			while (tail <= head && cal(i,l[head]) > cal(que[head],l[head])) head--; 
			if (tail <= head) {
				int ls=l[head],rs=r[head],mid,ans=r[head]-1;
				while (ls <= rs) {
					mid = ls + rs >> 1;
					if (cal(i,mid) < cal(que[head],mid)) ls = mid+1;
					else ans = mid, rs = mid-1;
				}
				r[head] = ans; l[++head] = ans+1; r[head] = n; que[head] = i;
			} else que[++head] = i, l[head] = i, r[head] = n;
		}
	}
	
	l[tail=head=1] = n; r[1] = 1; que[1]=n; que[0]=1;
	for (int i=n-1;i;i--) {
		l[tail]--;
		while (tail <= head && r[tail] > l[tail]) tail++;
		f[i] = max(f[i], int(ceil(cal(que[tail],i))+EPS));
		if (cal(i,r[head]) < cal(que[head],r[head])) continue;
		else {
			while (tail <= head && cal(i,l[head]) > cal(que[head],l[head])) head--; 
			if (tail <= head) {
				int ls=l[head],rs=r[head],mid,ans=r[head]+1;
				while (ls >= rs) {
					mid = ls + rs >> 1;
					if (cal(i,mid) < cal(que[head],mid)) ls = mid-1;
					else ans = mid, rs = mid+1;
				}
				r[head] = ans; l[++head] = ans-1; r[head] = 1; que[head] = i;
			} else que[++head] = i, l[head] = i, r[head] = 1;
		}
	}
	
	for (int i=1;i<=n;i++) printf("%d\n",max(f[i]-arr[i],0));
	return 0;
}

【BZOJ 1563】[NOI2009] 诗人小G

题目传送门: http://www.lydsy.com/JudgeOnline/problem.php?id=1563

决策单调性

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define LD long double
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 100000+9;
const LD EPS = 1e-8;
const LD MX = 1e18+EPS;

int arr[MAXN],n,L,p,l[MAXN],r[MAXN],que[MAXN],head,tail;
LD f[MAXN];
char pat[50];

inline LD cal(int a, int b){
	return f[b]+pow((LD)abs(arr[a]-arr[b]+a-b-1-L),p);
}

int main(){
	int T; cin>>T;
	while (T--) {
		scanf("%d%d%d",&n,&L,&p);
		for (int i=1;i<=n;i++) scanf("%s",pat+1), arr[i] = arr[i-1] + strlen(pat+1);
		l[head=tail=0] = 1; r[0] = n; f[0] = 0; que[0] = 0;
		for (int i=1;i<=n;i++) {
			while (r[tail] < i) tail++;
			f[i] = cal(i,que[tail]);
			if (cal(r[head],que[head]) < cal(r[head],i)) continue;
			else {
				while (head >= tail && cal(l[head],que[head]) >= cal(l[head],i)) head--;
				if (head >= tail) {
					int ls=l[head],rs=n,ans=0,mid;
					while (ls <= rs) {
						mid = ls + rs >> 1;
						if (cal(mid,que[head]) < cal(mid,i)) ans = mid, ls = mid+1;
						else rs = mid-1;
					}
					r[head] = ans; l[head+1] = ans+1; r[head+1] = n;
				} else l[head+1] = 1, r[head+1] = n;
				que[++head] = i; 
			}	
		}
		if (f[n] <= MX) printf("%lld\n",(LL)(f[n]+EPS));
		else printf("Too hard to arrange\n");
		puts("--------------------");
	}
	return 0;
}