Bupt summer training for 2013_String

A - Crazy Search(POJ 1200)

解題思路：

還有什麼比離散化之後直接hash解決簡單粗暴的呢？

#include <algorithm>

#include <iostream>

#include <iomanip>

#include <cstring>

#include <climits>

#include <complex>

#include <fstream>

#include <cassert>

#include <cstdio>

#include <bitset>

#include <vector>

#include <deque>

#include <queue>

#include <stack>

#include <ctime>

#include <set>

#include <map>

#include <cmath>

#define eps 1e-9

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

typedef pair<ll, ll> pll;

typedef complex<ld> point;

typedef pair<int, int> pii;

typedef pair<pii, int> piii;

template<class T>

inline bool read(T &n)

{

T x = 0, tmp = 1; char c = getchar();

while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();

if(c == EOF) return false;

if(c == '-') c = getchar(), tmp = -1;

while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();

n = x*tmp;

return true;

}

template <class T>

inline void write(T n)

{

if(n < 0)

{

putchar('-');

n = -n;

}

int len = 0,data[20];

while(n)

{

data[len++] = n%10;

n /= 10;

}

if(!len) data[len++] = 0;

while(len--) putchar(data[len]+48);

}

//-----------------------------------

const int MAXN=16000010;

const int MOD=100007;

char str[MAXN];

bool hash[10000000];

int ansi[256];

int main()

{

int n,nc;

while(read(n)&&read(nc))

{

int ans=0;

gets(str);

memset(hash,0,sizeof(hash));

memset(ansi,0,sizeof(ansi));

int len=strlen(str);

for(int i=0;i<len;i++)

ansi[str[i]]=1;

int cnt=0;

for(int i=0;i<256;i++)

if(ansi[i])

ansi[i]=cnt++;

for(int i=0;i<len-n+1;i++)

{

ull sum=0;

for(int j=i;j<i+n;j++)

sum=sum*nc+ansi[str[j]];

if(!hash[sum])

{

ans++;

hash[sum]=true;

}

write(ans);

putchar('\n');

}

return 0;

}

B - Power Strings

利用KMP的失配函數，将自己作為模闆鍊進行比對

然後根據失配數組的性質計算出向前移動幾位數字使得字元串比對

則移動的數字就是循環節

#include <algorithm>

#include <iostream>

include <cstring>

#include <iomanip>

##include <climits>

#include <complex>

include <cstdio>

#include <fstream>

#include <cassert>

#include <bitset>

#include <vector>

#include <deque>

nclude <set>

#in

#include <queue>

#include <stack>

#include <ctime>

iclude <map>

#include <cmath>

#define EPS 1e-10

namespace std;

temp

#define INF 0x3f3f3f3f

#define ll __int64

usin

glate<class T>

inline bool read(T &n)

{

;

while((c < '0' || c > '9') && c !=

T x = 0, tmp = 1; char c = getchar(

)'-' && c != EOF) c = getchar();

if(c == EOF) return false;

c <= '9') x *= 10, x += (c - '0'),c = get

if(c == '-') c = getchar(), tmp = -1;

while(c >= '0' &&

char();

n = x*tmp;

return true;

}

-----------------------------const int MAXN=10000010; char str[MAXN]; -----------------------------

const int MAXN=10000010;

char str[MAXN];

//-----------------------------------------

int next[MAXN];

int getFail()

{

next[0]=next[1]=0;

int n=strlen(str);

for(int i=1;i<n;i++)

{

xt[n]>0&&n%(n-next

int j=next[i];

while(j&&str[i]!=str[j])

j=next[j];

next[i+1]=str[i]==str[j]?j+1:0;

}

if(n

e[n])==0)

return n/(n-next[n]);

else

return 1;

}

int main()

{

while(scanf("%s",str)!=EOF)

{

if(str[0] == '.')

continue;

printf("%d\n",getFail());

}

return 0;

}

C - Colored Sticks

Trie樹+并查集+歐拉回路

将所有出現過的字元串插入Trie樹，并傳回編号

将所有顔色的編号用并查集維護起來，并且記錄編号的入度

最後檢視有多少點不在并查集中，以及歐拉回路的入度奇偶性

#include <algorithm>

#include <iostream>

#include <iomanip>

#include <cstring>

#include <climits>

#include <complex>

#include <fstream>

#include <cassert>

#include <cstdio>

#include <bitset>

#include <vector>

#include <deque>

#include <queue>

#include <stack>

#include <ctime>

#include <set>

#include <map>

#include <cmath>

#define CLR(x,y) memset(x,y,sizeof(x))

#define eps 1e-9

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

typedef long double ld;

typedef pair<ll, ll> pll;

typedef complex<ld> point;

typedef pair<int, int> pii;

typedef pair<pii, int> piii;

template<class T>

inline bool read(T &n)

{

T x = 0, tmp = 1; char c = getchar();

while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();

if(c == EOF) return false;

if(c == '-') c = getchar(), tmp = -1;

while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();

n = x*tmp;

return true;

}

template <class T>

inline void write(T n)

{

if(n < 0)

{

putchar('-');

n = -n;

}

int len = 0,data[20];

while(n)

{

data[len++] = n%10;

n /= 10;

}

if(!len) data[len++] = 0;

while(len--) putchar(data[len]+48);

}

//-----------------------------------

const int MAXN=500005;

struct Trie

{

int child[MAXN*10][26],root;

int flag[MAXN*10];

int sz;

int idx(char c) { return c-'a'; }

Trie()

{

root=sz=1;CLR(child[1],0);flag[1]=0;

}

void insert(const char *str,const int v)

{

int *cur=&root;

for(const char *p=str;*p;p++)

{

cur=&child[*cur][idx(*p)];

if(*cur==0)

{

*cur=++sz;

CLR(child[sz],0);

flag[*cur]=0;

}

flag[*cur]=v;

}

int find(const char *str)

{

int *cur=&root;

for(const char *p=str;*p && *cur;p++)

cur=&child[*cur][idx(*p)];

if(*cur==0)

return 0;

return flag[*cur];

}

}trie;

int fa[MAXN];

int find_fa(int x)

{

if(fa[x]==x)

return x;

else

return fa[x]=find_fa(fa[x]);

}

void Merge(int x,int y)

{

int xx=find_fa(x),yy=find_fa(y);

fa[xx]=yy;

}

char a[20],b[20];

int deg[MAXN];

void init()

{

for(int i=1;i<MAXN;i++)

fa[i]=i,deg[i]=0;

}

bool check(int cnt)

{

int euler=0;

int father=0,fath=find_fa(1);

for(int i=1;i<cnt;i++)

{

euler+=(deg[i]&1);

father+=( find_fa(i)!=fath );

}

return father || euler>2;

}

int main()

{

// freopen("data.txt","r",stdin);

int cnt=1;

init();

while(scanf("%s %s",a,b)!=EOF)

{

int s=trie.find(a);

if(!s)

{

trie.insert(a,cnt);

s=cnt++;

}

int t=trie.find(b);

if(!t)

{

trie.insert(b,cnt);

t=cnt++;

}

if(find_fa(s)!=find_fa(t))

Merge(s,t);

deg[s]++;

deg[t]++;

}

if(check(cnt))

puts("Impossible");

else

puts("Possible");

return 0;

}

D - DNA repair

解題思路以及見：http://blog.csdn.net/u013007900/article/details/38490739

E - Kindergarten

這題和字元串沒啥關系吧？

本題是要求圖中的最大完全子圖（最大團）中頂點的個數（最大團的規模或稱為最大完全數）。普通圖的最大團則是一個NP問題，目測是要暴力枚舉。

由于原圖的補圖是一個二分圖，其最大完全數等價于其補圖的最大獨立集中元素的個數，于是可以根據二分圖的性質求出這個最大獨立集。

定理：

二分圖最大獨立集=頂點數 - 二分圖最大比對

最大完全數 = 原圖補圖的最大獨立集的規模

概念：

最大完全子圖：每個點都兩兩相連，共有 n * ( n-1 ) / 2 條邊，又稱為最大團

最大完全數：圖中最大完全子圖的頂點個數，又稱為最大團的規模

獨立集：圖中任意兩個頂點都不相連的頂點集合，可以了解為孤立點的集合

補圖：原來圖連邊的不連，不連邊的連邊，形成的新圖稱為補圖

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define CLR(x,y) memset(x,y,sizeof(x))
#define eps 1e-9
#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;

template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1; char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
template <class T>
inline void write(T n)
{
    if(n < 0)
    {
        putchar('-');
        n = -n;
    }
    int len = 0,data[20];
    while(n)
    {
        data[len++] = n%10;
        n /= 10;
    }
    if(!len) data[len++] = 0;
    while(len--) putchar(data[len]+48);
}
//-----------------------------------

const int MAXN=210;

bool mapp[MAXN][MAXN];
int from[MAXN],G,B,m;
bool used[MAXN];

bool match(int x)
{
	for(int i=1;i<=B;i++)
		if(mapp[x][i] && !used[i])
		{
			used[i]=true;
			if(from[i]==-1 || match(from[i]))
			{
				from[i]=x;
				return true;
			}
		}
	return false;
}

int hungry()
{
	int tot=0;
	CLR(from,-1);
	for(int i=1;i<=G;i++)
	{
		CLR(used,0);
		if(match(i))
			tot++;
	}
	return tot;
}


int main()
{
    freopen("data.txt","r",stdin);
    int Cas=1;
	while(read(G)&&read(B)&&read(m)&&G&&B&&m)
	{
	    for(int i=1;i<=G;i++)
            for(int j=1;j<=B;j++)
                mapp[i][j]=true;
		int u,v;
		for(int i=0;i<m;i++)
		{
			read(u),read(v);
			mapp[u][v]=false;
		}
		printf("Case %d: %d\n",Cas++,B+G-hungry());
	}
	return 0;
}

Trie樹+并查集+歐拉回路

将所有出現過的字元串插入Trie樹，并傳回編号

将所有顔色的編号用并查集維護起來，并且記錄編号的入度

最後檢視有多少點不在并查集中，以及歐拉回路的入度奇偶性

Bupt summer training for 2013_String

繼續閱讀

如何下載下傳blob:https://www.bilibili.com/的視訊

BZOJ3643 Phi的反函數（數論+搜尋）

leetcode_17.Letter Combinations of a Phone Number

HDU 1286 找新朋友（歐拉函數模闆）

hdu 1286 找新朋友（歐拉函數）

哈理工oj Touring （最短路 dij算法鄰接表 + 隊列）

HDU 1286 找新朋友(歐拉函數)找新朋友

HDU 5119 Happy Matt Friends（dp） Happy Matt Friends

CF-346 D. Robot Control(反向建圖spfa)

ACMer成長之路

pat（B）1009. 說反話（逆疊代器）

關于多項式的一點研究及其在ACM競賽中的應用關于多項式的一點研究及其在ACM競賽中的應用

codeforces 838D D. Airplane Arrangements 構造法推公式

HDU Reorder the Books

POJ 1284 Primitive Roots (歐拉函數&原根定理)

hdu 4741 Save Labman No.004（計算幾何） Save Labman No.004