杭电多校第四场 1005 Equal Sentences 题解

题目大意

把一个单词串定义为与原本单词串s几乎相等，当且仅当单词串只是由原本单词串相邻的单词交换所形成的，求原本单词串有多少个几乎相等的单词串。

解题思路

服了这翻译。

我看题看了半天没看懂。

直接跳了。

结果发现这个题目就是简单的dp。。

定义dp[i]为从第一个单词到第i个单词所形成的单词串有多少几乎相等的单词串。

如果第i个单词与第i-1个单词相同，则不需要交换，$dp[i] = dp[i-1]$。

如果第i个单词与第i-1个单词不相同，则不交换时贡献为$dp[i-1]$，交换时贡献为$dp[i-2]$，所以状态转移为$dp[i] = dp[i-1]+dp[i-2]$。

注意初始化$dp[0]=dp[1]=1$。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 5, mod = 1e9+7;
int dp[N];
string s[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) cin >> s[i];
		dp[0] = dp[1] = 1;
		for (int i = 2; i <= n; i++) {
			if (s[i] == s[i - 1])	dp[i] = dp[i - 1];
			else dp[i] = (dp[i - 1] + dp[i - 2])%mod;
		}
		cout << dp[n]%mod  << endl;
	}
	return 0;
}