Tag: 部分暴力

相关链接

题目传送门：http://oi.cyo.ng/wp-content/uploads/2017/07/20170623_statement.pdf

解题报告

假如我们钦定某个格子先取走靠左的三角形，那么其余格子是先取走靠左还是靠右就全部定下来了
于是我们暴力枚举一下，复杂度是$O(n^4)$

更进一步，我们发现：

假如我们钦定先取走$(x, y)$这个格子的靠左三角形
那么我们一定得先将$(x – 1, y)$这个格子的左三角形取走，然后再取走一些其他的三角形

于是同一行的信息是可以共用的，然后就可以记忆化搜索了
时间复杂度是$O(n^3)$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500;
const int INF = 1e7;

char mp[N][N];
int n, m, ans[N];
bool up[N][N], dw[N][N], InStack[N][N], vis[N][N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline int F(int x, int y, int t) {
	InStack[y][x] = 1;
	int nx = x + (t == 1? 1: -1), ny = y, nt = t, ret = 1;
	ret += vis[ny][nx]? 0: (InStack[ny][nx]? INF: F(nx, y, t));
	nx = x; ny = up[y][x] == t? y - 1: y + 1; nt = up[y][x] == t? up[ny][nx]: dw[ny][nx];
	ret += vis[ny][nx] || ret >= INF? 0: (InStack[ny][nx]? INF: F(nx, ny, nt));	
	vis[y][x] = 1;
	InStack[y][x] = 0;
	return ret > INF? INF: ret;
}

inline void init() {
	memset(vis, 0, sizeof(vis));
	for (int j = 1; j <= m; j++) {
		vis[j][0] = 1;
		vis[j][n + 1] = 1;
	}
	for (int i = 1; i <= n; i++) {
		vis[0][i] = 1;
		vis[m + 1][i] = 1;
	}
}

int main() {
	m = read(); n = read();
	for (int j = 1; j <= m; j++) {
		scanf("%s", mp[j] + 1);
		for (int i = 1; i <= n; i++) {
			up[j][i] = 1;
			dw[j][i] = 0;
			if (mp[j][i] == 'Z') {
				swap(up[j][i], dw[j][i]);
			}
		}
	}
	for (int j = 1; j <= m; j++) {
		init();
		for (int i = n; i; i--) {
			ans[i] = ans[i + 1] < INF? F(i, j, 1) + ans[i + 1]: INF;
		}
		init();
		for (int i = 1; i <= n; i++) {
			ans[i] = min(ans[i], ans[i - 1] < INF? F(i, j, 0) + ans[i - 1]: INF);
			printf("%d ", ans[i] >= INF? -1: ans[i] << 1);
		}
		putchar('\n');
	}
	return 0;
}

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2471
神犇题解：http://www.cnblogs.com/clrs97/p/5993606.html

解题报告

我们考虑从高位开始，逐位枚举。那么每枚举一位相当于将序列划分为10分，并且取其中一份。
对于一段连续的序列来讲，我们只需要关注其进入这段序列之前会匹配到x的哪一位、匹配完这一段之后匹配到了x的哪一位、这期间总共贡献了多少次成功的匹配。
不难发现这个状态是很少的，于是我们可以记忆化搜索。

另外这题很容易扩展到：“左右边界为任意值的情况”
然后我把这题搬到了今年的全国胡策里，不知道有没有人能切掉

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 16;
const int M = 10;
const int SGZ = 10;
const int MOD = 1000000007;
 
int n, m, nxt[M];
char s[M];
struct Transfer{
    LL pos, cnt;
    inline Transfer() {
    }
    inline Transfer(LL a, LL b):pos(a), cnt(b) {
    }
    inline Transfer operator + (const Transfer &T) {
        return Transfer(T.pos, cnt + T.cnt);
    }
}t[M][SGZ];
map<int, Transfer> f[N][M];
struct MatchStatus{
    int HashVal;
    Transfer t[M];
    inline void GetHashVal() {
        const static int MOD = 1000000007;
        const static int SEED1 = 13, SEED2 = 131;
        HashVal = 0;
        for (int i = 0; i < m; i++) {
            HashVal = (HashVal + (LL)t[i].pos * SEED2 + t[i].cnt) * SEED1 % MOD;
        }
    }
    inline bool operator < (const MatchStatus &MS) const {
        return HashVal < MS.HashVal;
    }
};
 
inline Transfer DFS(int w, int p, const MatchStatus &cur) {
    if (w <= 0) {
        return cur.t[p];
    } else if (f[w][p].count(cur.HashVal)) {
        return f[w][p][cur.HashVal];
    } else {
        Transfer ret(p, 0);
        for (int i = 0; i < SGZ; i++) {
            MatchStatus nw = cur;
            for (int j = 0; j < m; j++) {
                nw.t[j] = nw.t[j] + t[nw.t[j].pos][i];
            }
            nw.GetHashVal();
            ret = ret + DFS(w - 1, ret.pos, nw);
        }
        return f[w][p][cur.HashVal] = ret;
    }
}
 
int main() {
    while (~scanf("%d %s", &n, s + 1) && n) {
        m = strlen(s + 1);
        for (int i = 1; i <= m; i++) {
            s[i] -= '0';
        }
        nxt[1] = 0;
        for (int i = 2, j = 0; i <= m; nxt[i++] = j) {
            for (; j && s[j + 1] != s[i]; j = nxt[j]);
            j += s[j + 1] == s[i];
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < SGZ; j++) {
                int k = i;
                for (; k && s[k + 1] != j; k = nxt[k]);
                k += s[k + 1] == j;
                t[i][j] = k == m? Transfer(nxt[k], 1): Transfer(k, 0);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                f[i][j].clear();
            }
        }
        Transfer ans(0, 0);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < SGZ; j++) {
                MatchStatus cur;
                for (int k = 0; k < m; k++) {
                    cur.t[k] = t[k][j];
                }
                cur.GetHashVal();
                ans = ans + DFS(i - 1, ans.pos, cur);
            }
        }
        printf("%lld\n", ans.cnt);
    }
    return 0;
}

相关链接

题目传送门：https://community.topcoder.com/stat?c=problem_statement&pm=14573&rd=16882

题目大意

给定$n(n \le 10^9)$，问有多少组不同的$a^b=c^d$成立
要求$1 \le a,b,c,d \le n$

解题报告

假设$a^b=c^d$，我们在枚举到$gcd(a,c)$的时候计算
如果$gcd(a,c)=a=c$的话，贡献显然是$n$
所以我们枚举$gcd$只需要枚举到$\sqrt{n}$
又因为次数非常小，所以我们可以暴力算有多少种指数满足要求
于是总的复杂度大概是$\sqrt{n}$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int N = 100000;

int gcd[100][100];
bool vis[N];

class PowerEquation {
    public:
    	int count(int n) {
    		memset(vis, 0, sizeof(vis));
    		for (int i=1;i<=50;i++) {
				for (int j=1;j<=50;j++) {
					gcd[i][j] = GCD(i, j);
				}
			}
			
			int ret = (LL)n * n % MOD, dec = 0;
    		for (int i=2;1;i++) {
				if (i * i > n) {
					ret = (ret + (n - i + 1ll - dec) * n) % MOD;
					break;	
				} else {
					if (vis[i]) continue;
					for (LL j=i*i;j<=n;j*=i) {
						if (j * j <= n) vis[j] = 1;
						else ++dec;
					}
					
					int mx = 1, tmp = 0; LL cur = i;
					while (cur * i <= n) cur *= i, ++mx;
					for (int a=1;a<=mx;a++) {
						for (int b=1;b<=mx;b++) {
							int c = max(b,a) / gcd[a][b];
							tmp = (tmp + n / c) % MOD;
						}
					} 
					ret = (ret + tmp) % MOD;
				}
			}
    	    return ret;
   		}
   	private:
   		int GCD(int a, int b) {
			return b? GCD(b, a%b): a;   
		}
};

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3990
神犇题解：http://blog.csdn.net/regina8023/article/details/45503151

解题报告

最开始一眼看成神题，还在想$SDOI$这是要赶超$ZJOI$的节奏啊
然后就发现看漏条件了 _(:з」∠)_

因为每一次只能交换一个$2^k$的块，并且$2$的不同次幂之间不会相互影响
话一句话来说，考虑交换长度为$2^k$的块时，所有长度为$2^{k-1}$的块的顺序必须已经排好
且长度为$2^k$的块，只能有至多两块位置不对
于是我们搞一发$DFS$就好了，时间复杂度：$O(n \log n)$

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4725
神犇题解：http://blog.csdn.net/lych_cys/article/details/53455978

解题报告

这题看上去一脸不可做QwQ
前前后后想了差不多三个小时吧？
突然反应过来：从第63项开始$a(x)$就大于$10^9$了
换一句话来说：之后的每一项，只可能减去前一项才可能小于$10^9$

于是我们把前$63$项之内的拿出来暴力搞一搞
$63$项之后的，我们可以推公式推出来答案是多少

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;

int n,tot,vis[N],L[N],R[N],que[N];
LL f[N];

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

inline void insert(int w) {
	for (int i=w-1;i;i--) {
		if (abs(f[w]-f[i]) >= N) break;
		vis[abs(f[w]-f[i])] = 1;
	}
} 

inline int query() {
	for (int i=1;i;i++)
		if (!vis[i]) return i;
}

inline void Get_Ans(int w, int id) {
	for (int j=2;j;j++) {
		for (int i=1;i<j;i++) {
			if (f[j] - f[i] == w) {
				L[id] = i; R[id] = j;
				return;
			}
		}
	}
}

inline void query(int w) {
	for (int j=2;j;j++) {
		for (int i=1;i<j;i++) {
			if (f[j] - f[i] == w) {
				cout<<j<<' '<<i<<endl;
				return;
			}
		}
	}
}

int main() {
	f[1] = 1; f[2] = 2; vis[1] = 1;
	for (int i=3;i<=120;i++) { 
		if (i&1) f[i] = f[i-1] << 1;
		else f[i] = f[i-1] + query();
		insert(i);
	} 
	for (int j=2;j<=63;j++) {
		for (int i=1;i<j;i++) {
			if (f[j] - f[i] > 1e9) continue;
			que[++tot] = f[j] - f[i];
		}
	} 
	que[++tot] = (1e9) + 10;
	sort(que+1, que+1+tot);
	for (int i=1;i<tot;i++) Get_Ans(que[i], i); 
	for (int q=read(),x,p;q;q--) {
		x = read();
		p = lower_bound(que+1, que+1+tot, x) - que;
		if (que[p] == x) printf("%d %d\n",R[p], L[p]);
		else if (x <= 90) query(x);
		else printf("%lld %lld\n",(x-90-p+62)*2ll+120,(x-90-p+62)*2ll+119);
	}
	return 0;
}

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4712
神犇题解Ⅰ：http://www.cnblogs.com/clrs97/p/6006305.html
神犇题解Ⅱ：http://blog.csdn.net/lych_cys/article/details/53454323

解题报告

考虑每一个节点保存三个值

1. $w(i)$ 表示第i个点自己的权值
2. $f(i) = \sum\limits_{j \in son(i)} {d(j)} $
3. $d(i) = \min (w(i),f(i))$

显然 $d(i)$ 就是答案
于是我们只需要考虑维护 $f(i)$ 即可

考虑每一次修改操作
其一定是改变了到根节点的路径上连续一个区间的 $f(i)$
这个连续的区间满足 $f(i) + delta < w(i)$ 于是可以直接用树链剖分搞区间加就可以了

现在考虑复杂度：

因为 $f(i)$ 是不减的，所以如果一个点的 $f(i)$ 大于了 $w(i)$ 那么便会一直大下去
初始每一个点会贡献一次暴力修改，每一次修改操作也会贡献一次暴力修改

于是均摊下来，单次操作的暴力修改次数就是 $O(1)$ 的了
于是总复杂度：$O((n+m)log^2n)$