A
解法一(官方解法):
要求每段的二进制或都相同,那么如果整个序列中存在某个数的第 \(i\) 位为 \(1\),那么整个序列的每一段长
度为 \(k\) 的连续子序列中都至少有一个数的第 \(i\) 位为 \(1\)。
我们可以对每一位单独求一个满足条件的最小的 \(k\),然后所有位的 \(k\) 的最大值就是答
案。
对于每一位,其序列都形如 00010110001... 这样的二进制串,要求每连续 \(k\) 个位置都至少包含一个 \(1\)。
这是一个很经典的问题,可以用双指针或滑动窗口等方法来实现。
解法二:
注意到或运算本质上和加法是差不多的,都有单调性,所以可以用线段树+二分求解,其中把线段树中所有的 + 变为 | 即可。
bool mst;
int n,m;
#define ls (p<<1)
#define rs (p<<1|1)
#define int long long
const int N = 5000005;
int a[N];
struct point
{int sum,lazy;
}t[N*4];
struct segtree
{void push_up(int p){t[p].sum = t[ls].sum|t[rs].sum;}void build(int p,int l,int r){if(l==r){t[p].sum = a[l];return;}int mid = (l+r)/2;build(ls,l,mid);build(rs,mid+1,r);push_up(p);}int get(int p,int L,int R,int l,int r){if(L<=l&&r<=R)return t[p].sum;int ans = 0;int mid = (l+r)/2;if(L<=mid)ans |= get(ls,L,R,l,mid);if(R>mid)ans |= get(rs,L,R,mid+1,r);return ans;}
}bird;
bool check(int x)
{int c1,c2;int i;for(i=1;i<=n-x+1;i++){c2 = c1;c1 = bird.get(1,i,i+x-1,1,n);if(~-i&&c1!=c2)return 0;}return 1;
}
bool men;
void solve()
{cin>>n;int i;for(i=1;i<=n;i++)cin>>a[i];bird.build(1,1,n);int l,r;l = 1,r = n;while(l<r){int mid = (l+r)/2;if(check(mid))r = mid;elsel = mid+1;}cout<<r<<endl;return;
}
B
解法一(官方解法):
代码很简单,不给了。
解法二:
可以将上述做法简化,把 dfs 换成递推的过程就可以了。
void solve()
{cin>>n>>k;int i;for(i=1;i<n;i++){int u,v;cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}int s = k;int j;for(i=1;i<=n;i++)for(j=2;j<=e[i].size();j++)s *= k-j,s %= mod;s *= k-1,s %= mod;cout<<s%mod<<endl;return;
}
C
void solve()
{queue<int> q[50];map<int,bool> ma;cin>>n>>m;cin>>s+1>>t+1;int i,j;for(i=1;i<=n;i++)ma[s[i]-'a'+1] = 1,q[s[i]-'a'+1].push(i);for(i=1;i<=m;i++){if(q[t[i]-'a'+1].empty()){NOreturn;}int j;for(j=1;j<=t[i]-'a'+1;j++)while(q[j].size()&&q[j].front()<q[t[i]-'a'+1].front())q[j].pop();q[t[i]-'a'+1].pop();}YESreturn;
}