danihao123's Blog

点双开坑……

考虑每个点双。如果一个点双有一个（全局的）割点，那么必须要在该点双的一个非割点处建一个出口（否则割掉这个割点会出事）。如果一个点双的割点多于一个，那么其实并没有必要在这里建出口，因为不管割掉那个点，这个点双里面的点总有办法走到一个只有一个割点的点双里。

有一种特殊情况……就是整个图是点双联通的，这样的话随便找两个点建出口就行了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <map>
const int maxn = 100005;
std::vector<int> G[maxn];
int n;
void clear_graph() {
  for(int i = 1; i <= 100000; i ++) {
    G[i].clear();
  }
}
void add_edge(int u, int v) {
  G[u].push_back(v); G[v].push_back(u);
}

std::map<int, int> ma;
int sz;
int trace(int x) {
  if(ma.count(x)) {
    return ma[x];
  } else {
    ma[x] = ++ sz;
    return sz;
  }
}

using Edge = std::pair<int, int>;
int dcnt, bcc_cnt;
int pre[maxn];
bool is_cut[maxn]; int bccno[maxn];
std::vector<int> bcc[maxn];

std::stack<Edge> S;
int dfs(int x, int fa = -1) {
  pre[x] = ++ dcnt; int low = pre[x];
  int cld = 0;
  for(auto v : G[x]) {
    Edge e = std::make_pair(x, v);
    if(!pre[v]) {
      S.push(e); cld ++;
      int lowv = dfs(v, x);
      low = std::min(low, lowv);
      if(lowv >= pre[x]) {
        is_cut[x] = true;
        bcc_cnt ++; bcc[bcc_cnt].clear();
        while(true) {
          Edge ee = S.top(); S.pop();
          int f = ee.first, g = ee.second;
          if(bccno[f] != bcc_cnt) {
            bccno[f] = bcc_cnt; bcc[bcc_cnt].push_back(f);
          }
          if(bccno[g] != bcc_cnt) {
            bccno[g] = bcc_cnt; bcc[bcc_cnt].push_back(g);
          }
          if(f == x && g == v) break;
        }
      }
    } else if(pre[v] < pre[x] && v != fa) {
      S.push(e); low = std::min(low, pre[v]);
    }
  }
  if(fa < 0 && cld == 1) is_cut[x] = false;
  return low;
}
void calc_bcc() {
  std::fill(pre, pre + 1 + sz, 0);
  std::fill(is_cut, is_cut + 1 + sz, false);
  std::fill(bccno, bccno + 1 + sz, 0);
  dcnt = bcc_cnt = 0;
  for(int i = 1; i <= sz; i ++) {
    if(!pre[i]) dfs(i);
  }
}

using ll = long long;
int main() {
  int cs = 0;
  while(scanf("%d", &n) == 1) {
    if(n == 0) break;
    cs ++; sz = 0; ma.clear();
    clear_graph();
    for(int i = 1; i <= n; i ++) {
      int u, v; scanf("%d%d", &u, &v);
      u = trace(u); v = trace(v);
      add_edge(u, v);
    }
    calc_bcc();
    ll a1 = 0, a2 = 1LL;
    for(int i = 1; i <= bcc_cnt; i ++) {
      int cnum = 0;
      for(auto x : bcc[i]) {
        if(is_cut[x]) cnum ++;
      }
      if(cnum == 1) {
        a1 ++;
        a2 *= (ll(bcc[i].size() - 1));
      }
    }
    if(bcc_cnt == 1) {
      a1 = 2; ll s = bcc[1].size();
      a2 = s * (s - 1LL) / 2LL;
    }
    printf("Case %d: %lld %lld\n", cs, a1, a2);
  }
  return 0;
}

Trie第一题……

首先，容我吐槽一下UVa这个OJ，速度特别感人（同学们可以实践一下）。

这个题最容易想到的是[tex]O(n^2)[/tex]的DP——对于[tex]S[i\ldots n][/tex]，枚举其前缀查是否为单词，然后转移。但是啊……对于[tex]n\le 300000[/tex]这种方法肯定会T飞。

然后我们可以考虑使用Trie优化DP。对于每个[tex]S[i\ldots n][/tex]，在前缀树中查找之，就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100，所以查找会很快辣~

代码：

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=300005;
const int maxW=4005,maxL=105;
const int MOD=20071027;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int n;
vector<int> AnsList;
namespace Trie{
	const int maxnode=400005;
	const int sigma_siz=26;
	int Tree[maxnode][sigma_siz];
	int val[maxnode];
	int siz;
	inline int idx(char c){
		return c-'a';
	}
	inline void InitTrie(){
		siz=0;
		val[0]=0;
		CL_ARR(Tree[0],0);
	}
	void Insert(char *s,int v){
		register int u=0,n=strlen(s);
		register int i,c;
		REP(i,n){
			c=idx(s[i]);
			if(!Tree[u][c]){
				siz++;
				Tree[u][c]=siz;
				val[siz]=0;
				CL_ARR(Tree[siz],0);
			}
			u=Tree[u][c];
		}
		val[u]=v;
	}
	void Query(char *s,int len){
		register int i,c,u=0;
		AnsList.clear();
		REP(i,len){
			if(!s[i])
				break;
			c=idx(s[i]);
			if(!Tree[u][c])
				break;
			u=Tree[u][c];
			if(val[u])
				AnsList.push_back(val[u]);
		}
	}
};

char Text[maxn];
int len[maxW];
char buf[maxL];
int d[maxn];
int main(){
	register int i,j,Case=0;
	int m;
	while(scanf("%s%d",Text,&m)==2){
		Case++;
		n=strlen(Text);
		Trie::InitTrie();
		REP_B(i,m){
			scanf("%s",buf);
			len[i]=strlen(buf);
			Trie::Insert(buf,i);
		}
		d[n]=1;
		DREP(i,n){
			d[i]=0;
			Trie::Query(Text+i,n-i);
			REP(j,AnsList.size()){
				d[i]=(d[i]+d[i+len[AnsList[j]]])%MOD;
			}
		}
		printf("Case %d: %d\n",Case,d[0]);
	}
	return 0;
}