友情提示：BZOJ 3233~3278 (3276权限题)

本题解缺BZOJ 3235 好方的蛇

BZOJ 3233 找硬币

f[i]表示最大面额为i的最小硬币数量，那么转移就是

$f[i] = min \{f[j] - \sum_{j|i} \frac{w[k]}{i}*(\frac{i}{j}-1) \}$

那么我们可以预处理出来i的最小的质因数。然后进行优化即可。

# include <stdio.h>
# include <string.h>
using namespace std;
const int M=300010, Ms=51;
int n, w[Ms];
int f[M], maxn, z[M], p[M], pn, ans;
// f[i] 最大面值为i，买所有兔纸花的最少硬币数
// f[i] = min{f[j]-sigma(w[k]/i*(i/j-1))}, j|i


int main() {
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) {
		scanf("%d", &w[i]);
		f[1] += w[i];
		if (maxn < w[i]) maxn = w[i];
	}	
	for (int i=2; i<=maxn; ++i) {
		if (z[i] == 0) {
			p[++pn] = i;
			z[i] = i;
		}
		for (int j=1; j<=pn && p[j] * i <= maxn; ++j) {
			z[p[j] * i] = p[j];
			if(i % p[j] == 0) break;
		}
	}
	for (int i=2; i<=maxn; ++i) f[i] = f[1];
	ans = f[1];
	for (int i=2; i<=maxn; ++i) {
		int j = i, t;
		while(j > 1) {
			t = f[i/z[j]];
			for (int k=1; k<=n; ++k)
				t = t - w[k] / i *(z[j] - 1);
			if(f[i] > t) f[i] = t;
			while(z[j] == z[j/z[j]]) j = j/z[j];
			j = j/z[j];
		}
		if(ans > f[i]) ans = f[i];
	}
	printf("%d\n", ans);
	return 0;
}

BZOJ 3234 立方体

标号后做三维前缀和然后就可以判断啦

# include <stdio.h>
# include <queue>
using namespace std;
bool vis[210][210][210];
int f[210][210][210], n, maxx, maxy, maxz;
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
int ans = 0;
struct bfsn {
	int x,y,z;
};
queue<bfsn> q;
int main() {
	scanf("%d", &n);
	maxx = maxy = maxz = 0;
	for (int i=1, x1, y1, z1, x2, y2, z2; i<=n; ++i) {
		scanf("%d %d %d %d %d %d", &x1, &y1, &z1, &x2, &y2, &z2);
		x1+=2, y1+=2, z1+=2;
		x2+=2, y2+=2, z2+=2;
		f[x1][y1][z1] ++;
		f[x2][y2][z1] ++;
		f[x1][y2][z2] ++;
		f[x2][y1][z2] ++;
		f[x1][y2][z1] --;
		f[x2][y1][z1] --;
		f[x1][y1][z2] --;
		f[x2][y2][z2] --;
		maxx = max(maxx, x2);
		maxy = max(maxy, y2);
		maxz = max(maxz, z2);
	}
	for (int i=1; i<=maxx+1; ++i)
		for (int j=1; j<=maxy+1; ++j)
			for (int k=1; k<=maxz+1; ++k) 
				f[i][j][k] = f[i][j][k] + f[i-1][j][k] + f[i][j-1][k] + f[i][j][k-1] - f[i-1][j-1][k] - f[i-1][j][k-1] - f[i][j-1][k-1] + f[i-1][j-1][k-1];
	for (int i=0; i<=maxx+2; ++i)
		for (int j=0; j<=maxy+2; ++j)
			for (int k=0; k<=maxz+2; ++k)
				if(i==0 || j==0 || k==0 || i==maxx+2 || j==maxy+2 || k==maxz+2) vis[i][j][k] = 1;
	bfsn begin;
	begin.x = 1;
	begin.y = 1;
	begin.z = 1;
	q.push(begin);
	while(!q.empty()) {
		bfsn top = q.front();
		q.pop();
		if (!vis[top.x][top.y][top.z]) {
			if (f[top.x][top.y][top.z]) ++ans;
			else {
				vis[top.x][top.y][top.z] = 1;
				for (int i=0; i<6; ++i) {
					bfsn s;
					s.x = top.x + dx[i];
					s.y = top.y + dy[i];
					s.z = top.z + dz[i];
					q.push(s);
				}
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

BZOJ 3236 作业

一看就是莫队题，随便套一个分块就行啦

# include <stdio.h>
# include <math.h> 
# include <algorithm>
using namespace std;
int n,m,t,left=1,right;
int a[100010],cnt[100010],w[100010];
int f[10010],g[10010];
int a1[1000010],a2[1000010];
 
 
struct quest {
    int l,r,a,b,id;
    bool operator <(const quest &A) const{
        if (w[l]==w[A.l]) return r<A.r;
        else return l<A.l;
    }
}q[1000010];
 
inline void xy(int l,int r,int id) {
    if(w[l]==w[r]) {
        for (int i=l;i<=r;++i) if(cnt[i]) a1[id]+=cnt[i],a2[id]++;
    } else {
        for (int i=w[l]*t-1;i>=l;--i) if(cnt[i]) a1[id]+=cnt[i],a2[id]++;
        for (int i=w[r]*t-t;i<=r;++i) if(cnt[i]) a1[id]+=cnt[i],a2[id]++; 
        for (int i=w[l]+1;i<w[r];++i) a1[id]+=f[i],a2[id]+=g[i];
    }
}
 
inline void u(int x) {
    ++f[w[x]];++cnt[x];
    if(cnt[x]==1) g[w[x]]++;
}
 
inline void v(int x) {
    --f[w[x]];--cnt[x];
    if(cnt[x]==0) g[w[x]]--;
}
 
int main() {
    scanf("%d%d",&n,&m);
    t=sqrt(n/2);
    for (int i=1;i<=n;++i) scanf("%d",&a[i]),w[i]=i/t+1;
    for (int i=1;i<=m;++i) scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b),q[i].id=i;
    sort(q+1,q+m+1);
    for (int i=1;i<=m;++i) {
        while(right<q[i].r) u(a[++right]);
        while(left<q[i].l) v(a[left++]);
        while(right>q[i].r) v(a[right--]);
        while(left>q[i].l) u(a[--left]);     
        xy(q[i].a,q[i].b,q[i].id); 
    }
    for (int i=1;i<=m;++i) printf("%d %d\n",a1[i],a2[i]);
}

BZOJ 3237 连通图

涨姿势啦，cdq重构图+缩点

要学习学习用指针啦

# include <stdio.h>
# include <algorithm>
# include <string.h>

using namespace std;

const int M=200010;
struct unionset {
	int fa[M], n, tt;
	inline void init(int nn) {
		n = nn;
		for (int i=1; i<=n; ++i) fa[i] = i;
		tt = n;
	}
	inline int getf(int x) {
		return fa[x] == x ? x : fa[x] = getf(fa[x]);
	}
	inline void unions(int x, int y) {
		int fx = getf(x), fy = getf(y);
		if (fx != fy) fa[fx] = fy, --tt;
	}
	inline bool isok() {
		return tt == 1;
	}
}t;

struct edge {
	int x, y;
}e[M*35], *tail = e;

bool ans[M];
int Q, n, m;
inline int read() {
    int s=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
    return s*f;
}
struct quest {
	int n, a[5], id;
}q[M], qt[M*35], *qtail = qt;

int times=0;

bool f[M];
int nE[M], nV[M], g[M];

inline void cdq(int l, int r, int n, int m, edge *last) {
	tail += m;
	edge *e = tail;
	copy(last, tail, e);
	for (int i=0; i<m; ++i) f[i] = 0;
	for (int i=1; i<=n; ++i) nE[i] = nV[i] = g[i] = 0;
	if (l == r) {
		for (int i=1; i <= q[l].n; ++i) f[q[l].a[i]] = 1;
		t.init(n);
		for (int i=0; i<m; ++i)	if(f[i] == 0) t.unions(e[i].x, e[i].y);
		ans[l] = t.isok();
		tail -= m;
		return ;	
	}

	for (int i=l; i<=r; ++i)
		for (int j=1; j<=q[i].n; ++j)
			f[q[i].a[j]] = 1;
	t.init(n);
	for (int i=0; i<m; ++i)
		if(f[i] == 0) t.unions(e[i].x, e[i].y);
	
	int V=0, E=0;
	for (int i=1; i<=n; ++i) {
		g[i] = t.getf(i);
		if(i == g[i]) nV[i] = ++V;
	}
	for (int i=1; i<=n; ++i) 
		if(i != g[i]) nV[i] = nV[g[i]];
	
	for (int i=0; i<m; ++i) e[i].x = nV[e[i].x], e[i].y = nV[e[i].y];
	
	for (int i=0; i<m; ++i) if(f[i]) nE[i] = E++;
	for (int i=0; i<m; ++i) if(f[i]) e[nE[i]] = e[i];
	for (int i=l; i<=r; ++i)
		for (int j=1; j<=q[i].n; ++j)
			q[i].a[j] = nE[q[i].a[j]];
	int mid = l+r>>1, length = mid - l + 1;
	quest *lasts = qtail;
	qtail += length;
	copy(q+l, q+mid+1, lasts);
	cdq(l, mid, V, E, e);
	copy(lasts, lasts+length, q+l);
	qtail -= length;
	cdq(mid+1, r, V, E, e);
	tail -= m;
}
int main() {
	n=read(), m=read();
	for (int i=0; i<m; ++i) e[i].x=read(), e[i].y=read();
	Q=read();
	for (int i=0; i<Q; ++i) {
		q[i].n=read();
		for (int j=1; j<=q[i].n; ++j) q[i].a[j]=read(), q[i].a[j] --;
		q[i].id=i;
	}
	t.init(n);
	cdq(0, Q-1, n, m, e);
	for (int i=0; i<Q; ++i)
		if(ans[i] == 1) puts("Connected");
		else puts("Disconnected");
	return 0;
}

BZOJ 3238 差异

看到lcpxi想到SA，然后单调栈乱搞就好啦！

# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;

const int M=780010;
int sa[M], sa_t[M], rank[M], rank_t[M], rank_t2[M], cnt[M], h[M], s[M], t[M];
//int minst[M], plog[M];

inline bool cmp(int *t, int a, int b, int l) {
	return t[a] == t[b] && t[a+l] == t[b+l];
}

inline void getsa(int n, int m) {
	memset(cnt, 0, sizeof(cnt));
	for (int i=0; i<n; ++i) ++cnt[rank_t[i] = s[i]];
	for (int i=1; i<m; ++i) cnt[i] += cnt[i-1];
	for (int i=n-1; i>=0; --i) sa[--cnt[s[i]]] = i;
	for (int j=1, p=1; p<n; j<<=1, m=p) {
		p=0;
		for (int i=n-j; i<n; ++i) sa_t[p++] = i;
		for (int i=0; i<n; ++i) if(sa[i] >= j) sa_t[p++] = sa[i] - j;
		memset(cnt, 0, sizeof(cnt));
		for (int i=0; i<n; ++i) ++cnt[rank_t2[i] = rank_t[sa_t[i]]];
		for (int i=1; i<m; ++i) cnt[i] += cnt[i-1];
		for (int i=n-1; i>=0; --i) sa[--cnt[rank_t2[i]]] = sa_t[i], t[i] = rank_t[i];
		p=1;
		rank_t[sa[0]] = 0;
		for (int i=1; i<n; ++i)
			rank_t[sa[i]] = cmp(t, sa[i], sa[i-1], j) ? p-1 : p++;
	}
	for (int i=0; i<n; ++i) rank[sa[i]] = i;
}

inline void geth(int n) {
	for (int i=0, k=0; i<n; h[rank[i++]] = k) {
		if(rank[i]) {
			if(k>0) --k;
			for (; s[i+k] == s[sa[rank[i]-1]+k]; ++k);
		} else k=0;
	}
}

char str[M];
int left[M], right[M];
int n;
/*
inline void stprepare() {
	plog[1] = 0;
	for (int i=2; i<=n; ++i) {
		plog[i] = plog[i-1];
		if((1<<plog[i]) == i) plog[i] ++;
	}
	for (int i=0; i<n; ++i) minst[i][0] = h[i];
	for (int i=n-1; i>=0; --i)
		for (int j=1; i+(1<<j)-1 < n; ++j)
			minst[i][j] = min(minst[i][j-1], minst[i+(1<<(j-1))][j-1]);
}

inline void query(int l, int r) {
	int length = r-l+1;
	int k = plog[length];
	return min(minst[l][k], minst[r-(1<<k)+1][k]);
}
*/

long long ans;
int st[M*2], stn=0;
int hi[M];

int main() {
	scanf("%s", str);
	n = strlen(str);
	ans = 1LL*n*(n+1)*(n-1)/2;
	for (int i=0; i<n; ++i) s[i] = str[i];
	s[n] = 0;
	getsa(n+1, 256);
	geth(n+1);
	stn=0; st[stn++] = 1;
	for (int i=1; i<=n; ++i) {
		while(stn && h[st[stn-1]] > h[i]) stn--;
		if(stn) left[i] = st[stn-1] + 1;
		else left[i] = 1;
		st[stn++] = i;
	}
	
	stn=0; st[stn++] = n;
	right[n] = n;
	for (int i=n; i>=1; --i) {
		while(stn && h[st[stn-1]] >= h[i]) stn--;
		if(stn) right[i] = st[stn-1] - 1;
		else right[i] = n;
		st[stn++] = i;
	}
	
	long long del=0;
	for (int i=2; i<=n; ++i) 
		del+=2LL*h[i]*(i-left[i]+1)*(right[i]-i+1);
	ans=ans-del;
	printf("%lld\n", ans);
	return 0;
}