雅里集训模拟赛
T1
考虑二分答案,矩阵变成0/1矩阵,之后变成一个是否存在子矩阵的可行性判断
考虑UOJ群中极其巧妙的把每一行所有一的对数都压起来,然后枚举下一行也压起来,直到出现重复的就GG
这个题就做完了
T2
考虑hash,首先你会发现k,b都很小,所以可以搜索出我们钦定那些b是要用于满足k的,而如果出现了搜索到的之外的就一定弃掉不要了,因为每个区间包含的信息是一定的所以这样一定不会算漏掉qwq
那么判断前后相等的区间就相当于前后区间做个前缀和后每个类型的元素的大小差值关系是一样的,这个显然可以预处理然后差分,就能hash起来了!
然后你会TLE,此时可以把搜索改为枚举子集
然后你会WA,你就需要双模hash
然后我只有90
T3
匹配深度最大不是长度最长...
考虑把从每个点到根的处理出来,从根到每个点的括号序列处理出来,然后做一个查询hash表类似的就能完成括号匹配
然后你需要计算最大匹配深度...
这个其实很简单,如果是up,我们钦定他放在左边,也就是要保证其栈顶一定为'(',然后考虑'('入栈过程
如果'('入栈后发现栈顶有')'二者就弹出,然后匹配深度不变
否则的话直接入栈,')'直接入栈
最后如果这个点可以算答案就一定栈顶不能为')'
其次我们考虑down,从根到每个点....就不需要我重复了吧?
然后如果我们放入'('就dep+1,如果放入')'就dep-1,对于up的最大深度就是已经匹配出的最大深度和当前dep取max,对于down就是已经匹配出的最大深度和当前-dep取max
主要是可能出现((((((()))))这样子的序列,导致过根处不是最大深度qwq
然后注意我们匹配的时候要做两遍,从前到后和从后到前,因为我们单方向匹配啊
code:
T1不够长就不放了
T2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pir pair<ll,ll>
const int MAXN = 2e5 + 7;
const int MAXP = 2e7 + 7;
const ll P = 1e9 + 9;
const ll P2 = 1e9 + 7;
struct rec {
ll x, y;
bool operator<(const rec &y)const {
return x < y.x;
}
} e[MAXN];
int n, k, Kd, ans;
int vis[MAXN], ncnt[MAXN];
// ll base[MAXN];
const int base1 = 19260817;
const int base2 = 20040623;
inline pir gethash() {
ll ret1 = 0, ret2 = 0;
for(int i = 1; i <= 8; ++i) {
// printf("%lld %lld?\n", i, ncnt[i] % P);
ret1 = (ret1 * base1 % P + ncnt[i] % P) % P;
// printf("%lld??\n", ret1);
ret2 = (ret2 * base2 % P2 + ncnt[i] % P2) % P2;
}
// printf("%lld %lld\n", ret1, ret2);
return make_pair(ret1, ret2);
}
int nxt[MAXN], home[MAXP], vl[MAXN], que[MAXN];
pir to[MAXN];
ll ccnt, T;
const int P1 = 19260817;
inline void ct(int x, pir z, int w) {
ccnt++;
nxt[ccnt] = home[x];
home[x] = ccnt;
to[ccnt] = z;
vl[ccnt] = w;
}
inline void ins(pir x, int w, int O) {
int qwq = x.fi % P1;
que[++T] = qwq;
for(int i = home[qwq]; i; i = nxt[i]) {
// ll qaq = to[i].fi, QAQ = to[i].se;
if(to[i].fi == x.fi && to[i].se == x.se) {
// puts("QAQ");
// printf("%lld?\n", to[i]);
ans = max(ans, O - vl[i]);
// to2[i] = min(to2[i], w);
return ;
}
}
ct(qwq, x, w);
}
int bitCount(int i) {
int count = 0;
while(i != 0) {
count++;
i = (i - 1)&i;
}
return count;
}
// ll a[MAXN], hve[MAXN];
inline void solve() {
// puts("");
// for(int i = 1; i <= 8; ++i)if(vis[i])printf("%lld ", i);
// puts("");
for(int i = 1; i <= n; ++i) {
if(vis[e[i].y]) {
ncnt[e[i].y]++;
int minx = 1e9;
for(int j = 1; j <= 8; ++j) {
if(vis[j])
minx = min(ncnt[j], minx);
}
if(minx > 0 && minx != 1e9)
for(int j = 1; j <= 8; ++j)
if(vis[j]) {
ncnt[j] -= minx;
}
// a[i] = gethash(i);
// printf("%lld %lld %lld\n", i, e[i].x, e[i].y);
// O = e[i].x;
ins(gethash(), e[i + 1].x, e[i].x);
// puts("");
} else {
for(int i = 1; i <= 8; ++i)ncnt[i] = 0;
for(int i = 1; i <= T; ++i) {
home[que[i]] = 0;
}
ccnt = T = 0;
}
}
for(int i = 1; i <= T; ++i)home[que[i]] = 0;
for(int i = 1; i <= 8; ++i)ncnt[i] = 0;
ccnt = T = 0;
return ;
}
signed main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) {
scanf("%lld%lld", &e[i].x, &e[i].y);
// if(!vis[e[i].y])++Kd;
// vis[e[i].y] = 1;
}
// base[1] = 19602817;
// base[2] = 17254079;
// base[3] = 19835728;
// base[4] = 12594667;
// base[5] = 19048659;
// base[6] = 12352678;
// base[7] = 45678401;
// base[8] = 12376456;
sort(e + 1, e + n + 1);
// vis[1] = 1;
// vis[2] = 1;
// vis[3] = 1;
// for(int i = 1; i <= n; ++i)if(vis[e[i].y])printf("%lld %lld??\n", i, e[i].x);
// solve();
// printf("%lld\n", ans);
// return 0;
// for(int i = 1; i <= 8; ++i)vis[i] = 0;
int S = (1 << 8) - 1;
for(int T = 0; T <= S; ++T) {
if(bitCount(T) < k) {
continue;
}
for(int k = 0; k < 8; ++k) {
if(T & (1 << k)) {
vis[k + 1] = 1;
} else vis[k + 1] = 0;
}
solve();
}
printf("%lld\n", ans);
return 0;
}
T3
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;
using std::min;
using namespace std;
const int MAXN = 2e5 + 7;
const int inf = 1e9 + 7;
int n, sum, a[MAXN];
int ccnt, home[MAXN], nxt[MAXN], to[MAXN];
inline void cuntu(int x, int y) {
ccnt++;
nxt[ccnt] = home[x];
home[x] = ccnt;
to[ccnt] = y;
}
inline void ct(int x, int y) {
cuntu(x, y);
cuntu(y, x);
}
int root;
int siz[MAXN], dp[MAXN], vis[MAXN], dwn[MAXN], up[MAXN], dep[MAXN], maxdep[MAXN];
int mp[MAXN], dep1[MAXN], maxdep1[MAXN];
inline void getroot(int u, int F) {
siz[u] = 1;
dp[u] = 0;
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(v == F || vis[v])continue;
getroot(v, u);
siz[u] += siz[v];
dp[u] = max(dp[u], siz[v]);
}
dp[u] = max(dp[u], sum - siz[u]);
if(dp[u] < dp[root])root = u;
return ;
}
int ans;
int rev[MAXN], tot;
// int que[MAXN], head, tail;
// int st[MAXN], tp;
// inline void getdis(int u, int F) {
// int tmp1 = tp, tmp2 = head, rc1 = st[tp], rc2 = que[head]; //back?
// if(a[u] == ')') {
// if(tp > 0 && st[tp] == '(') {
// tp--;
// rc1 = st[tp + 1];
// } else {
// st[++tp] = ')';
// }
// pre[u] = 0;//不行
// que[++head] = ')';//压入
// if(st[tp] != '(') {
// suf[u] = tp;//不行?c
// }
// } else {
// if(head > 0 && que[head] == ')') {
// head--;
// rc2 = que[head + 1];
// } else {
// que[++head] = '(';
// }
// suf[u] = 0;
// st[++tp] = '(';//不行的
// if(que[head] != ')')pre[u] = tp;
// }
// rev[++tot] = u;
// for(int i = home[u]; i; i = nxt[i]) {
// int v = to[i];
// if(v == F || vis[v])continue;
// dep[v] = dep[u] + 1;
// getdis(v, u);
// }
// tp = tmp1;
// head = tmp2;
// st[tp] = rc1;
// que[head] = rc2;//back
// }
int st[MAXN], tp;
inline void getdown(int u, int F) {
bool flg = 0;
if(a[u] == 0) {//a[u]==0是右括号
if(tp && st[tp] == 1) {
--tp;
}//有左括号
else {
st[++tp] = 0;
flg = 1;
}
dep[u] = dep[F] - 1;
} else {
flg = 1;
st[++tp] = 1;
dep[u] = dep[F] + 1;
}
maxdep[u] = max(maxdep[F], dep[u]);
// printf("%d %d\n", u, maxdep[u]);
if((st[tp] != 1 || !tp) && mp[tp] >= 0) {
ans = max(ans, max(maxdep[u] + tp, mp[tp]));
//qwq?
//tp表示向上的右括号个数
}
// rev[++tot] = u;
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(v == F || vis[v])continue;
getdown(v, u);
}
if(flg)tp--;
else st[++tp] = 1;
return ;
}
inline void getup(int u, int F) {
bool flg = 0;
if(a[u] == 1) {//左
if(tp && st[tp] == 0)--tp;
else {
st[++tp] = 1;
flg = 1;
}
dep1[u] = dep1[F] + 1;
} else {
flg = 1;
st[++tp] = 0;
dep1[u] = dep1[F] - 1;
}
maxdep1[u] = max(maxdep1[F], -dep1[u]);
//这里注意用符号,左括号代表正
//右括号代表负
// printf("%d %d\n", u, maxdep[u]);
if(st[tp] != 0 || !tp) {
// printf("")
mp[tp] = max(mp[tp], maxdep1[u] + tp);
//qwq?
}
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(v == F || vis[v])continue;
getup(v, u);
}
if(flg)tp--;
else st[++tp] = 0;
return ;
}
inline void doit(int u) {
tot = 0;
// printf("nroot is ->%d\n", u);
for(int i = 1; i <= sum; ++i)mp[i] = -inf;
mp[0] = 0;
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(vis[v])continue;
rev[++tot] = v;
// int tmp = tot + 1;
tp = 1;
st[tp] = a[u];
if(a[u])maxdep[u] = dep[u] = 1;
else maxdep[u] = dep[u] = -1;
getdown(v, u);
tp = maxdep1[u] = dep1[u] = 0;
getup(v, u);
}
for(int i = 1; i <= sum; ++i)mp[i] = -inf;
mp[0] = 0;
for(int j = tot; j >= 1; --j) {
int v = rev[j];
tp = 1;
st[tp] = a[u];
if(a[u])maxdep[u] = dep[u] = 1;
else maxdep[u] = dep[u] = -1;
getdown(v, u);
tp = maxdep1[u] = dep1[u] = 0;
getup(v, u);
}
}
inline void solve(int u) {
vis[u] = 1;
// printf("%d\n", u);
doit(u);
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(vis[v])continue;
root = 0;
dp[0] = n;
sum = siz[v];
getroot(v, 0);
solve(root);
}
return ;
}
char s[MAXN];
int main() {
// freopen("test.in", "r", stdin);
scanf("%d", &n);
for(int i = 2, x; i <= n; ++i) {
scanf("%d", &x);
ct(x, i);
}
for(int i = 1; i <= n; ++i) {
scanf("%s", s);
a[i] = s[0] == '(';
// printf("%d %c\n", i, s[0]);
}
root = 0;
dp[root] = n;
sum = n;
getroot(1, 0);
// printf("%d\n", root);
solve(root);
printf("%d\n", ans);
return 0;
}