分类目录归档:搜索

洛谷P1019 单词接龙

预处理单词i连接单词j的最小重叠部分,然后dfs即可.

code:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int ex[25][25];
string s[25];
int n;
void pre() {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int len1 = s[i].length();
      int len2 = s[j].length();
      for (int k = 1; k <= len1 - 1; ++k) {
        int m = 0;
        for (; m < len2 - 1 && m < k; ++m) {
          if (s[i][len1 - k + m] != s[j][m]) {
            break;
          }
        }
        if (m == k && m < len2 - 1) {
          ex[i][j] = k;
          break;
        }
      }
    }
  }
}
int vis[25];
int ans;

void dfs(int i, int len) {
  vis[i]++;
  // cout<<i<<endl;
  int j = 0;
  for (j = 0; j < n; ++j) {
    if (ex[i][j] && vis[j] < 2) {
      dfs(j, len + s[j].length() - ex[i][j]);
      vis[j]--;
    }
  }
  if (j == n) ans = max(ans, len);
}

int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> s[i];
  }
  char a;
  cin >> a;
  pre();
  for (int i = 0; i < n; ++i) {
    if (s[i][0] == a) {
      dfs(i, s[i].length());
      vis[i]--;
    }
  }
  cout << ans << endl;
  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}

ZOJ 3983 -Crusaders Quest

题目链接:ZOJ-3983

记录连续字母块的首尾位置,暴力枚举删除位置,更新最大值。

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int res;

void dfs(string s, int ans) {
  if (s.size() == 0) {
    res = max(ans, res);
    return;
  }
  vector<int> index;
  index.push_back(0);
  int j = 0;
  int i = 1;
  for (i = 1; s[i]; i++) {
    if (s[i] != s[j]) {
      index.push_back(i);
      j = i;
    }
  }
  index.push_back(i);
  vector<int>::iterator it = index.begin();
  string t=s;
  while ((it+1) != index.end()) {
    s.erase(s.begin() + *it, s.begin() + *(it + 1));
    if (*(it + 1) - *it == 3) {
      dfs(s, ans + 1);
    } else {
      dfs(s, ans);
    }
    ++it;
    s=t;
  }
}

int main() {
  int T;
  cin >> T;
  int kase = 0;
  while (T--) {
    string s;
    cin >> s;
    res = 0;
    dfs(s, 0);
    cout << res << endl;
  }
  return 0;
}