上午考试的题是某高校的寒假集训题。
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(); }