YJQQQAQ's Blog

上午考试的题是某高校的寒假集训题。

T1 ：

     题意：$S_0 = '0',S_1 = '1',S_i = S_{i-1} + S_{i-2} (i > 1)$，求一个给定的串tmp在$S_n$中的出现次数，对P取模

     题解：$O(n \times m)$的做法是很简单的，暴力合并kmp,这里就是观察到当串的长度大于tmp的长度之后，两个间隔了一个串的串，开头M个字符和结尾M个字符是一样的，所以可以分两类，每一次两步两步走的矩阵快速幂。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <memory.h>


using namespace std;

int n,m,MOD;

const int MAXN = 60010;

char s[50][MAXN];
char tmp[MAXN];
char L[2][MAXN],R[2][MAXN],Mid[2][MAXN];
int ans1,ans2;
int delta[2],len[MAXN];

int fail[MAXN];
int Kmp(char *s1,char *s2) {
		int n = strlen(s1 + 1);
		int m = strlen(s2 + 1);
		memset(fail,0,sizeof fail);
		for (int i=2;i<=m;i++) {
				int last = fail[i - 1];
				while (last && (s2[last + 1] != s2[i])) last = fail[last];
				if (s2[last + 1] == s2[i]) fail[i] = last + 1;
				else fail[i] = 0;
		}
		int now = 0;
		int cnt = 0;
		for (int j=1;j<=n;j++) {
				while (now && (s2[now + 1] != s1[j])) now = fail[now];
				if (s2[now + 1] == s1[j]) now ++;
				if (now == m) cnt ++;
		}
		return cnt;
}


struct  Matrix {
		int w,h;
		int a[4][4];
		Matrix (int w_ = 0,int h_ = 0) {
				w = w_,h = h_;
				memset(a,0,sizeof a);
		}
		Matrix operator * (const Matrix ano) const {
				Matrix res = Matrix(ano.w,h);
				for (int i=1;i<=h;i++) {
						for (int j=1;j<=ano.w;j++) {
								for (int k=1;k<=w;k++) {
										res.a[i][j] += 1LL * a[i][k] % MOD * ano.a[k][j] % MOD;
										res.a[i][j] %= MOD;
								}
						}
				}
				return res;
		}
};

Matrix m0,m1,mat,ret;
void Init() {
		m0 = Matrix(3,3),m1 = Matrix(3,3);
		m0.a[1][1] = m0.a[1][2] = m0.a[2][1] = m0.a[3][3] = 1;
		m0.a[1][3] = delta[0];
		m1.a[1][1] = m1.a[1][2] = m1.a[2][1] = m1.a[3][3] = 1;
		m1.a[1][3] = delta[1];
		ret = Matrix(3,3);
		ret.a[1][1] = ret.a[2][2] = ret.a[3][3] = 1;
		mat = m1 * m0;
}

void Solve() {
		int times = n / 2;
		while (times) {
				if (times & 1) ret = ret * mat;
				mat = mat * mat;
				times >>= 1;
		}
		if (n & 1) ret = m0 * ret;
		Matrix M = Matrix(1,3);
		M.a[1][1] = ans2,M.a[2][1] = ans1,M.a[3][1] = 1;
		M = ret * M;
		printf("%d\n",M.a[1][1]);
		return ;
}
		
int main() {
		freopen("bugs.in","r",stdin);
		freopen("bugs.out","w",stdout);
		scanf("%d%d%d",&n,&m,&MOD);
		scanf("%s",tmp + 1);
		s[0][1] = '0';
		s[1][1] = '1';
		len[0] = len[1] = 1;
		int now = 1;
		while (len[now - 1] < (m > 1 ? m : m + 1)) {
				now ++;
				for (int i = 1;i <= len[now - 2];i ++) {
						s[now][i] = s[now - 2][i];
				}
				for (int i = 1;i <= len[now - 1];i ++) {
						s[now][i + len[now - 2]] = s[now - 1][i];
				}
				len[now] = len[now - 1] + len[now - 2];
		}
		ans1 = Kmp(s[now - 1],tmp) % MOD;
		ans2 = Kmp(s[now],tmp) % MOD;
		if (n <= now) {
				printf("%d\n",Kmp(s[n],tmp));
				return 0;
		}
		for (int i = 1;i <= m; i++) {
				L[0][i] = s[now - 1][i];
				L[1][i] = s[now][i];
				R[0][i] = s[now - 1][len[now - 1] - (m - i)];
				R[1][i] = s[now][len[now] - (m - i)];
		}
		for (int i=1;i<m;i++) {
				Mid[0][i] = R[0][i + 1];
				Mid[1][i] = R[1][i + 1];
		}
		for (int i = 1;i < m ;i ++) {
				Mid[0][i + m - 1] = L[1][i];
				Mid[1][i + m - 1] = L[0][i];
		}
		n -= now;
		delta[0] = Kmp(Mid[0],tmp) % MOD;
		delta[1] = Kmp(Mid[1],tmp) % MOD;
		Init();
		Solve();
}

 T2 ：

       题意：给定一个长度为$N$的序列，求出最长的一个区间$[L,R]$使得$A[L] \leq A[i] \leq A[R]$对于任意$L \leq i \leq R$均成立，输出区间长度，$N \leq 10^7$

       题解：单调栈裸题

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <memory.h>

using namespace std;

int n;

const int MAXN = 10000010;

inline void read(int &a) {
		a = 0;char c = getchar();
		while (isspace(c)) c = getchar();
		do a = a * 10 + c - '0',c=  getchar();while (isdigit(c));
}
int a[MAXN];
int st[MAXN],tp = 0,pos[MAXN],M[MAXN];
int ans = 0 ;
int main() {
		freopen("array.in","r",stdin);
		freopen("array.out","w",stdout);
		read(n);
		for (register int i = 1;i <= n;i ++) {
				read(a[i]);
				int mini = a[i],p = i;
				while (tp && a[i] >= st[tp]) {	
						if (a[M[pos[tp]]] <= mini) mini = a[M[pos[tp]]],p = M[pos[tp]];
					    tp --;
				}
				st[++tp] = a[i],pos[tp] = i;
				M[i] = p;
				if (i - p + 1 > ans) ans = i - p + 1;
		}
		printf("%d\n",ans);
}

					

	

T3 ：

      题意：给定一个图，其中每个点属于某两个极大团，极大团总数不超过$M$,点数不超过$N$，问最大匹配

      题解：首先把每个点随便放， 然后观察得到可以把每个极大团当成一个点，一个点当成一条边，则此时的一条路径可以理解为把终点和起点里面点的奇偶性取反，此时只需要求生成树森林然后在树上打标记就好了。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <memory.h>
#include <vector>
#define lowbit(_x_) ((_x_) & (-(_x_)))
using namespace std;

int n,m;
const int MAXN = 100010;

int L[MAXN],R[MAXN],fa[MAXN];

int findfa(int x) {return fa[x ]== x ? x : fa[x] = findfa(fa[x]);}

struct Edge {
		int l,r,id,nxt;
} e[MAXN << 1];

int ecnt,hed[MAXN],due[MAXN];

void addedge(int l,int r,int id) {
		++ecnt,e[ecnt].l = l,e[ecnt].r =r ,e[ecnt].id = id,e[ecnt].nxt= hed[l],hed[l] = ecnt;
}

bool vis[MAXN];

int seq[MAXN],seq_id = 0,fid[MAXN];
int dep[MAXN];

void dfs(int x) {
		seq[++seq_id] = x;
		L[x] = seq_id;
		for (int i=hed[x];i;i=e[i].nxt) {
				int to = e[i].r;
				if (!vis[to]) {
						vis[to] = 1;
						dep[to] = dep[x] + 1;
						fid[to] = i;
						dfs(to);
				}
		}
		R[x] = seq_id;
}
int bel[MAXN << 1],ll[MAXN << 1],rr[MAXN << 1];
vector<int> G[MAXN];

int bit[MAXN];

void modify(int p) {for (;p <= n;p += lowbit(p)) bit[p] ^= 1;}
int query(int p) {int ans = 0;for (; p; p -= lowbit(p)) ans ^= bit[p];return ans;}

void Init() {
		for (int i=1;i<=n;i++) {
				if (!vis[i]) vis[i] = 1,dep[i] = 0,dfs(i);
		}
		for (int i=1;i<=n;i++) {
				if (due[i] & 1) G[findfa(i)].push_back(i);
		}
}

vector<int> In[MAXN];
void Solve() {
		for (int i=1;i<=n;i++) {
				for (int j=0;j<G[i].size();j ++,j ++) {
						if (G[i].size() - j - 1) modify(L[G[i][j]]),modify(L[G[i][j+1]]);
				}
		}
		for (int i=1;i<=n;i++) {
				int P = query(R[i]) ^ query(L[i] - 1);
				if (P) bel[e[fid[i]].id] ^= 1;
		}
		for (int i=1;i<=m;i++) {
				if (bel[i]) In[rr[i]].push_back(i);
				else In[ll[i]].push_back(i);
		}
		int ans =0 ;
		for (int i=1;i<=n;i++) ans += In[i].size() / 2;
		printf("%d\n",ans);
		for (int i=1;i<=n;i++) {
				for (int j=0;j<In[i].size();j += 2) {
						if (In[i].size() - j - 1) printf("%d %d\n",In[i][j],In[i][j+1]);
				}
		}
}

int main() {
		freopen("pair.in","r",stdin);
		freopen("pair.out","w",stdout);
		scanf("%d%d",&n,&m);
		for (int i = 1; i <= n; i ++) fa[i] = i;
		for (int i=1;i<=m;i++) {
				int l,r;
				scanf("%d%d",&l,&r);
				if (findfa(l) != findfa(r)) {
						fa[findfa(l)] = findfa(r);
						addedge(l,r,i);
						addedge(r,l,i);
				}
				ll[i] = l,rr[i] = r;
				due[l] ++;
		}
		Init();
		Solve();
}