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