Day 4（补题）

1

算法讲解： 1.采用前缀和的思想可以优化代码，避免超时（一开始我的做法就是时间超时了） 2.在求解过程中需要去注意的一个点是最终求的是（t~t+1），最后求解的结果必须大于而不是大于等于！！！！ 代码演示： #include using namespace std; const int N = 5e4 + 10; int f[N]; int n, m; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { int x; cin >> x; f[i] = f[i - 1] + x; } while (m--) { int y; cin >> y; for (int i = 1; i <= n; i++) { if (f[i] > y) { cout << i << endl; break; } } } return 0; }

2

算法讲解： 1.根据题意可知以及经验可知，此题是一道bfs题（有求最小路径的倾向，并且边权为1）（bfs知识） 2.本体需要考虑的问题： （1）如何统计次数 1。使用unorder——map<string,int> 统计（map知识） （2）如何进行x->y 1.使用find和substr来解决 2.pos可能需要使用多次（string知识）（本题主要知识）

代码解释： #include #include #include <unordered_map> using namespace std; const int N = 10; string x[N], y[N]; int n;//统计一共出现过多少次规则 unordered_map<string, int> mp; string a,b; int bfs() { if (a == b) return 0;//剪枝二：如果一开始就相等，直接返回

queue<string> q;
q.push(a);
mp[a] = 0;

while (q.size())
{
	string st = q.front();
	q.pop();

	if (mp[st] >= 10) return -1;//剪枝一：如果已经超过10次，直接结束
	
	for (int i = 0; i < n; i++)
	{
		int pos = 0;
		while (st.find(x[i], pos) != -1)
		{
			pos = st.find(x[i], pos);
			string tmp = st.substr(0, pos) + y[i] + st.substr(pos + x[i].size());
			mp[tmp] = mp[st] + 1;
			q.push(tmp);
			if (tmp == b) return mp[tmp];
			pos++;
		}
	}
}
return -1;

} int main() { cin >> a >> b; while (cin >> x[n] >> y[n]) n++;//技巧一

int c=bfs();
if (c==-1)
{
	cout << "NO ANSWER!" << endl;
}
else
{
	cout << c << endl;
}
return 0;

}