A. Mahmoud and Ehab and the MEX
题意：略。
解法：让x没有出现,以及0..x-1都出现就可以了。
#include <bits/stdc++.h>
using namespace std;
int n, x;
bool vis[110];
int main(){
scanf("%d%d",&n,&x);
for(int i=1;i<=n;i++){
int y;
scanf("%d",&y);
vis[y]=1;
}
if(x==0&&vis[0]){
printf("1\n");
return 0;
}
int ans = 0;
for(int i=0; i<x; i++){
if(!vis[i]) ans++;
}
ans += (vis[x]!=0);
printf("%d\n", ans);
}B. Mahmoud and Ehab and the bipartiteness
题意：要把所有的点分成两个集合，那么最多的情况就是一个集合中所有的点都连接另一个集合中所有的点
解法：那么当我们从一个点开始DFS的时候，奇数次的时候扫的点属于一个集合，偶数次的点属于另一个集合，这样的话，就能找出最多的边数，减去现在已有的边数就能得到答案
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
vector <int> G[maxn];
typedef long long LL;
bool vis[maxn];
LL num0,num1;
int n;
void dfs(int x, int len){
for(int i=0; i<G[x].size(); i++){
int v=G[x][i];
if(!vis[v]){
vis[v]=1;
if(len&1) num0++;
else num1++;
dfs(v, len+1);
}
}
}
int main(){
scanf("%d", &n);
for(int i=1; i<n; i++){
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
vis[1]=1;
num0=1;
dfs(1,0);
printf("%lld\n", num0*num1-n+1);
return 0;
}C. Mahmoud and Ehab and the xor
题意：给你一个数X问你能不能分解成N个数，使得这N个数的异或和为X
解法：脑洞，重点就是抓住异或的性质，两个相同的数异或等于0，任何数异或0结果都不变。意思就是例如 3^4^5^3^4^5^6=6 。然后这道题就很简单了。假设我们要使最后的结果为X，大小为4，那么我们可以 a^b^c^(a^b^c)^x=x，其中四个数分别为，a,b,c,(a^b^c)。但是a^b^c可能等于a,b,c中的一个数，所以我们要用一些足够特殊的数完成这个操作
#include <bits/stdc++.h>
using namespace std;
int n,x;
int main(){
scanf("%d%d",&n,&x);
if(n==1){
puts("YES");
printf("%d\n", x);
return 0;
}
if(n==2){
if(x==0){
puts("NO");
}else{
puts("YES");
printf("%d %d\n", 0, x);
}
return 0;
}
int temp = 0, a = 1<<18, b = 1<<19;
puts("YES");
for(int i=1; i<=n-3; i++){
printf("%d ", i);
temp ^= i;
}
printf("%d %d %d\n", a, b, (a^b^temp^x));
return 0;
}D. Mahmoud and Ehab and the binary string
题意：交互式，要求寻找二进制串里0和1的任意一个位置，串长给定。
解法：二分法。直接找相邻的01串或者10串，具体查找方法是先将所有串赋值为0这样就能得到1的总个数，然后将所要求的区间全赋值为1其他赋值为0。设num1为总的1的个数反馈的值其实就是表示L～R之间0的个数，然后只要满足(设返回的数为now)只要满足num1-now<(R-L+1)&&num1-now>-(R-L+1)就二分到这个区间因为这个区间能够确保既有0又有1然后知道L与R就相差1就行，之后确定0，1位置就简单了就是在L，R两个位置里找。
#include <bits/stdc++.h>
using namespace std;
int n, black=0;
bool check(int L, int R){
printf("? ");
for(int i=1; i<L; i++){
printf("0");
}
for(int i=L; i<=R; i++){
printf("1");
}
for(int i=R+1; i<=n; i++){
printf("0");
}
puts("");
fflush(stdout);
int req;
scanf("%d", &req);
if(black-(R-L+1)<req && req<black+(R-L+1)) return 1;
else return 0;
}
int main()
{
scanf("%d", &n);
printf("? ");
for(int i=1; i<=n; i++){
printf("0");
}
puts("");
fflush(stdout);
scanf("%d", &black);
int L=1, R=n;
while(R-L>=2){
int mid=(L+R)/2;
if(check(mid,R)){
L=mid;
}
else{
R=mid;
}
}
printf("? ");
for(int i=1; i<L; i++) printf("0");
printf("1");
for(int i=L+1; i<=n; i++) printf("0");
puts("");
fflush(stdout);
int req;
scanf("%d", &req);
printf("! ");
if(req<black){
printf("%d %d\n", R,L);
}else{
printf("%d %d\n", L,R);
}
fflush(stdout);
return 0;
}E. Mahmoud and Ehab and the function
题意：计算题上给出的公式。
解法：http://m.blog.csdn.net/HowardEmily/article/details/78084385 之前一直在想怎么用数据结构维护a[i]*(-1)^(i-1)这个东西。
可以观察到无论j怎么变化对于a数组的元素都是奇数为加,偶数为减.这个的和我们是可以提前维护好的,修改的时候由于整个区间（l,r）都增加x,所以只需要统计区间长度奇偶性就可以了.（要么只增加一个要么不增加）.
然后我们观察b数组,发现b数组最多也是n个元素,并且j最大为m-n.所以我们可以预处理j为0，1,2,3,…m-n的所有的和,存起来然后二分一下求最小值即可.（因为是套绝对值所以值越接近越好）.
怎么样预处理呢？可以想到对于每个不同j对应只是b数组中的起点不同,这个过程可以类似尺取一样，初始当j为0，第i个数,若i为奇数为+否则-. j每增加1,要把第一个元素的值减掉,然后正好全部变号了,这个过程每次乘以个-1即可.新加进来的数因为是第n个就取决于n的奇偶性了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
LL n, m, q, a[maxn], b[maxn];
vector <LL> v;
int main(){
scanf("%lld%lld%lld", &n,&m,&q);
LL suma = 0, sumb = 0 ;
v.push_back(-1e18);
v.push_back(1e18);
for(int i=1; i<=n; i++){
scanf("%lld", &a[i]);
if(i&1) suma += a[i];
else suma -= a[i];
}
for(int i=1; i<=m; i++){
scanf("%lld", &b[i]);
}
for(int i=1; i<=n; i++){
if(i&1) sumb += b[i];
else sumb -= b[i];
}
v.push_back(sumb);
for(int i=n+1; i<=m; i++){
sumb -= b[i-n];
sumb *= -1;
if(n&1) sumb += b[i];
else sumb -= b[i];
v.push_back(sumb);
}
sort(v.begin(),v.end());
int pos = lower_bound(v.begin(), v.end(), suma) - v.begin();
printf("%lld\n", min(abs(suma-v[pos]), abs(suma-v[pos-1])));
while(q--)
{
int l,r;
LL x;
scanf("%d%d%lld", &l,&r,&x);
if((r-l+1)&1){
if(l&1) suma += x;
else suma -= x;
}
pos = lower_bound(v.begin(), v.end(), suma) - v.begin();
printf("%lld\n", min(abs(suma-v[pos]), abs(suma-v[pos-1])));
}
return 0;
}F. Mahmoud and Ehab and the final stage
题意：n个字符串，支持修改一个位置上的字符串和查询一个区间的子区间中长度乘LCP的最大值，输入字符数和询问数不超过10^5。
解法：http://www.bubuko.com/infodetail-2316288.html
求出相邻的LCP长度，区间LCP等于区间最小值，查询分几种情况考虑，一种只有一个串，线段树维护长度最大值即可；若有若干个串，设一个阈值k，若答案的LCP<=k，对于小等k的每一个i，若一个位置的相邻LCP大等i，设为1，否则设为0，即求区间最长连续1，每种i开一棵线段树维护即可；若LCP>k，我们把相邻LCP长度超过k的位置存进set，查询的时候拿出来，直接建笛卡尔树计算答案，由于字符总数有限，这样的位置不会超过L/k个。总时间复杂度为O(nklogn+nL/k)，适当调整k，时间复杂度为O(n(nlogn)^0.5)。
搞了好久没懂如何用笛卡尔树计算这个答案，真心弱鸡。
京公网安备 11010502036488号