总分 40分
T1： 0分
T2： 0分
T3： 20分
T4： 20分
对于T1
题意：
Aliemo 有两个数 a,b ，但是他想考考你，所以他想给你另外两个数 x,y。
a+b 的值为 x ,a&b 的值为 y，首先需要判断能否有一组 a,b 满足当前的情况，如果有，那么求出
a xor b，否则输出 −1 （其中 a,b > 0 ）
输入：
第一行为一个正整数 T，表示组数。
接下来 T 行，每一行有两个整数 x,y。
输出：
对于每一组数据，按题意输出 a xor b 或者 −1
解题思路：
对于两个数，a,b;
异或可以看做不进位加法，a&b也就是只有在都是一的时候才是1
a+b=((a&b)<<1) + a^b;
所以，答案就是x-2*y, &的时候取得是相同的位，而a+b取得是不同的位，所以在进行判别的时候先将 a+b 和 a&b 这个 &一下，如果&为零，那就是真，否则就是是假
考试暴力代码（期望得分 30分，实际得分 0分）：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int a,b;
signed main()
{
int t=read();
while(t--)
{
int flag=0;
a=read(),b=read();
int pos1=-1,pos2=-1;
for(int i=0;i<=a;i++)
{
for(int j=0;j<=a;j++)
{
if(i+j==a && (i&j)==b)
{
flag=1;
pos1=i;
pos2=j;
break;
}
}
if(flag) break;
}
if(flag) cout<<(pos1^pos2)<<endl;
else cout<<"-1"<<endl;
}
return 0;
}
根据讲完之后代码：
#include <bits/stdc++.h>
using namespace std;
long long x,y;
int main()
{
long long t;
scanf("%lld",&t);
while(t--)
{
scanf("%lld %lld",&x,&y);
long long ans=x-2*y;
if( (ans&y)==0 )
{
printf("%lld",x-2*y);
}
else
{
printf("-1");
}
}
return 0;
}
T2 :游戏
题目：
luckyblock 又开始和社团的萌妹子玩游戏了。
在今天的游戏中，luckyblock 将会得到一个 n × m 且全为小写字母的矩阵，他可以从矩阵中任选
一块正方形，但必须保证该正方形中任意一类小写字母个数之和不能超过 k，换而言之，在该正方形
中， ‘a’字符个数不能超过 k ， ‘b’字符个数不能超过 k，...， ‘z’字符个数不能超过 k。
luckyblock 现在想知道，以 (i,j) 为左上角且符合以上要求的正方形中，边长最大的是多少？
输入：
第一行三个正整数 n,m,k，
接下来 n 行，每行 m 个小写字母。
输出：
输出 n 行，每行 m 个数字。其中第 i 行第 j 个数字表示，以 (i,j) 为左上角且符合题目要求的正
方形的最大边长。
解题思路：
O(\(n_^2\))的枚举每一个点，然后二分一下边长，利用二维前缀和进行字符的判别
在进行二分的时候，注意边界
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int map[302][302][26];
int sum[302][302][27];
int ans[302][302];
int k,n,m;
bool check(int l,int r,int mid)
{
int flag=0;
for(int i=1;i<=26;i++)
{
int sum_=sum[l + mid - 1][r + mid - 1][i]-sum[ l + mid - 1 ][ r - 1][ i ]- sum[ l- 1][r + mid - 1][i]+sum[ l - 1][ r - 1][i];
if(sum_>k)
{
flag=1;
}
}
if(flag==0) return true;
else return false;
}
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++)//求出前缀和
{
for(int j=1;j<=m;j++)
{
char c;
cin>>c;
map[i][j][c-'a'+1]=1;
for(int k=1;k<=26;k++)
{
sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+map[i][j][k];
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int l=0,r=min(n-i+1,m-j+1);//边长
while(l<=r)
{
int mid=l+r>>1;
if(check(i,j,mid))
{
l=mid+1;
}
else
{
r=mid-1;
}
}
cout<<r<<" ";
}
cout<<endl;
}
return 0;
}
T3：或和异或
题目：
loceaner 最近在研究位运算，它研究的主要有两个：or 和 xor。 （C 语言中对于 | 和∧�
为了更好的了解这两个运算符，loceaner 找来了一个 2 n 长度的数组。它第一次先对所有相邻两个
数执行 or 操作，得到一个 2 n−1 长度的数组。也就是说，一开始时数组为 a[1],a[2],…,a[2 n ]，执行完第
一次操作后，会得到 a[1] or a[2],a[3] or a[4],…,a[2 n − 1] or a[2 n ]。
第二次操作，loceaner 会将所有相邻两个数执行 xor 操作，得到一个 2 n−2 长度的数组，假如第一
次操作后的数组是 b[1],b[2],⋯,b[2 n−1 ]，那么执行完这次操作后会变成 b[1] xor b[2], b[3] xor b[4] ,⋯,
b[2 n−1 − 1] xor b[2 n−1 ]。
第三次操作，loceaner 仍然将执行 or 操作，第四次 loceaner 执行 xor 操作。如此交替进行。
最终这 2 n 个数一定会变成 1 个数。loceaner 想知道最终这个数是多少。
为了让这个游戏更好玩，loceaner 还会执行 Q 次修改操作。每次修改原先的 2 n 长度的数组中的
某一个数，对于每次修改操作，你需要输出 n 次操作后（最后一定只剩下唯一一个数）剩下的那个数
是多少。
输入：
第一行两个数 n ，Q。
接下来一行 2 n 个数 a i 表示一开始的数组。
接下来 Q 行，每行两个数 $x_i$,$y_i$，表示 loceaner 这次的修改操作是将 a[$x_i$] 改成 $y_i$。
输出：
Q 行，表示每次修改操作后执行 n 次操作后剩下的那个数的值。�
输入样例：
2 4
1 6 3 5
1 4
3 4
1 2
1 2
输出样例：
1
3
3
3
样例说明：
第一次修改，4,6,3,5->6,7->1
第二次修改，4,6,4,5->6,5->3
第三次修改，2,6,4,5->6,5->3
第四次修改，2,6,4,5->6,5->3
数据范围：
对于 30% 的数据 n ≤ 17 ，Q = 1。
对于另外 20% 的数据 n ≤ 10 ，Q ≤ 1000 。
对于再另外 30% 的数据 n ≤ 12 ，Q ≤ 100000。
对于 100% 的数据 1 ≤ n ≤ 17，1 ≤ Q ≤$10_^5$ ，1 ≤$x_i$≤ $2_^n$ ，0 ≤ $y_i$<$2_^30$ ，0 ≤$a_i$<$2_^30$
解题思路：
进行手画一次图之后，就会发现，它就是一个倒着的线段树，然后直接建树就可以了，然后对于每一次修改就是单点修改
我一开始就是修改一次建一次树，然后就起飞了，只有20分
正解代码（和我的差不了多少）：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
const int maxn=1000000;
struct node
{
int left,right,now,sum;
};
node tree[maxn<<2];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar(); }
return x*f;
}
void pushdown(int now)
{
if(tree[now].now%2==1)
{
tree[now].sum=(tree[now<<1].sum|tree[now<<1|1].sum);
}
else
{
tree[now].sum=(tree[now<<1].sum ^ tree[now<<1|1].sum);
}
return ;
}
void build(int now,int left,int right)
{
tree[now].left=left;
tree[now].right=right;
if(left==right)
{
tree[now].sum=read();
tree[now].now=0;
return;
}
int mid=left+right>>1;
build(now<<1,left,mid);
build(now<<1|1,mid+1,right);
tree[now].now=tree[now<<1].now+1;
pushdown(now);
}
void updata(int now,int left,int right,int val,int k)
{
if(left==right)
{
tree[now].sum=val;
tree[now].now=1;
return ;
}
int mid=(left+right)>>1;
if(k<=mid)
{
updata(now<<1,left,mid,val,k);
}
else
{
updata(now<<1|1,mid+1,right,val,k);
}
pushdown(now);
}
int main()
{
int n=read();
int t=read();
build(1,1,(1<<n));
while(t--)
{
int a=read(),b=read();
updata(1,1,(1<<n),b,a);
//for(int i=1;i<=(1<<n);i++)
printf("%d\n",tree[1].sum);
}
return 0;
}
T4 链接
题目：
Kersen 来到了一片森林， 森林中有一些树和连接两棵树的无向道路， 保证这些道路能把森林连通。
Kersen 对这片森林做了一些考察，有了两个奇怪的发现：
- 森林中的树总共分为两种，不妨记为 0 型树和 1 型树。
- 这些道路的长度都是 2 的整数次幂且互不相同，第 i 条道路的长度为 2 i 。
Kersen 又发现了这片森林的一个神奇之处，任何两棵类型不同的树之间都可以构成一组链接，这
一对链接的能量值为两棵树之间的最短路。
好奇的 Kersen 想知道这片森林所有链接的能量值之和，请你来帮帮他。
输入：
输入第一行包含两个整数 n,m ，表示森林中树的数量和无向道路的数量。
接下来一行包含 n 个整数 a 1 ,a 2 ,...,a n (ai = 0or1)，表示每一棵树的类型。
接下来 m 行，第 i 行表示第 i 条无向道路，包含两个整数 $ u_i $ ,$ v_i $ (1 ≤ $u_^i$,$v_^i$≤ n) 表示第 i 条无向
道路连接的树的编号，并且它的长度为 $2^i$。
输出：
输出一个整数，所有链接能量值之和对 10 9 + 7 取模的结果
输入样例：
3 2
0 1 0
3 1
1 2
输出样例
10
解题思路:
首先，我们的数学知识帮助了我们， $\sum_2^i$是要小于 $ 2^i $,所以第 i条边是一定比