智力体验(?)
欢迎来到今天的智力体验。这意味着您将重新定义您的智力。
CF原题大赏
学习取模
题面
原题：
传送门：Problem - 1562A - Codeforces
You are given two integers $l$ and $r$, $l≤r$. Find the largest possible value of amodbamodb over all pairs $(a,b)$ of integers for which $r≥a≥b≥l$.
As a reminder, $a mod b$ is a remainder we get when dividing $a$ by $b$. For example, $26mod8=2$.
题目大意：
给您一个范围l和r，使得a和b在l到r的范围中且a mod b最大，输出该a mod b的值。
解题
- 对于任意的一个数
a，要使a mod b尽可能大，容易得到b的值应为a÷2+1。 - 而现在
b的范围已知，即b可以根据a的取值自由选择，那么应让a的取值尽量大，a mod b才会最大。
由上可知，我们需要对l和r的情况进行讨论。
- 当
(r/2+1)≥l时，可以使得a取到最大值r，而b也可以取到a÷2+1的理想值。 - 当
(r/2+1)＜l时，a可以是最大值r，但b能取到的最优解为l。此时答案为r mod l。
示例代码
#include
<bits tdc++.h="">
using namespace std;
int t;
int l,r;
int main(){
cin>>t;
while(t--){
cin>>l>>r;
if((r/2+1)>=l){
cout<<((r-1)/2)<
<endl; }else{="" cout<<r%l<<endl;="" }="" return="" 0;="" <="" re="">
学习异或
好奇的宝宝
Bob又在搞事情了。
题面
原题
Alice gave Bob two integers aa and bb (a>0a>0 and b≥0b≥0). Being a curious boy, Bob wrote down an array of non-negative integers with MEXMEX value of all elements equal to aa and XORXOR value of all elements equal to bb.
What is the shortest possible length of the array Bob wrote?
Recall that the MEXMEX (Minimum EXcluded) of an array is the minimum non-negative integer that does not belong to the array and the XORXOR of an array is the bitwise XOR of all the elements of the array.
大意
给两个数a，b，表示在一个集合${0,1, ... , a-1, ... , x}$中，有x-任意元素=b的存在。
a为EXcluded数，意思是在这个集合中，最小的不存在的非负数为a。并且在这个集合中，一定有两个数之差为b，输出这个集合最少有几个数。
补充
- 如果
a^b=c，则a^c=b。
a^(a+1)^(a+2)^(a+3)=0 (a为4的倍数) ，证明过程可参考二进制，末两位分别为00，01，10，11。
解题
这题需要对多种情况进行分类讨论，根据补充2发现，其规律为4个一循环。
示例代码
#include
<bits tdc++.h="">
using namespace std;
int t;
int a,b;
int main(){
cin>>t;
while(t--){
int ans=0;
cin>>a>>b;
switch (a%4)
{
case 1:
ans=a-1;
break;
case 2:
ans=1;
break;
case 3:
ans=a;
break;
default:
ans=0;
break;
}
if(ans==b)cout<
<a<<endl; else="" if((b^ans)!="a)cout<<a+1<<endl;" cout<<a+2<<endl;="" }="" return="" 0;="" }<="" re="">
学习加法
题面
原题
传送门：Problem - 1567C - Codeforces
Alice has just learned addition. However, she hasn't learned the concept of "carrying" fully — instead of carrying to the next column, she carries to the column two columns to the left.
For example, the regular way to evaluate the sum 2039+29762039+2976 would be as shown:
However, Alice evaluates it as shown:
In particular, this is what she does:
- add 99 and 66 to make 1515, and carry the 11 to the column two columns to the left, i. e. to the column "00 99";
- add 33 and 77 to make 1010 and carry the 11 to the column two columns to the left, i. e. to the column "22 22";
- add 11, 00, and 99 to make 1010 and carry the 11 to the column two columns to the left, i. e. to the column above the plus sign;
- add 11, 22 and 22 to make 55;
- add 11 to make 11.
Thus, she ends up with the incorrect result of 1500515005.
Alice comes up to Bob and says that she has added two numbers to get a result of nn. However, Bob knows that Alice adds in her own way. Help Bob find the number of ordered pairs of positive integers such that when Alice adds them, she will get a result of nn. Note that pairs (a,b)(a,b) and (b,a)(b,a) are considered different if a≠ba≠b.
大意
爱丽丝刚刚学会了加法。然而，她还没有完全学会 "携带 "的概念--她不是携带到下一列，而是携带到左边两列的列。
例如，评估2039+2976的常规方法是如图所示。
然而，爱丽丝是按照图中的方式进行评估的。
具体来说，她是这样做的。
将9和6相加为15，并将1带到左边两列，即 "0 9 "列。
加3和7得10，并把1带到左边两列，即 "2 2 "列。
加1、0和9组成10，并将1带到左边两列，即加号上面的那一列。
加1，2和2组成5。
加1为1。
因此，她最后得到的结果是不正确的15005。
爱丽丝走过来对鲍勃说，她把两个数字相加得到的结果是n，但是，鲍勃知道爱丽丝是用自己的方式加的。请帮助鲍勃找出有秩序的正整数对，使爱丽丝将它们相加后得到的结果是n。请注意，如果a≠b，则成对的(a,b)和(b,a)被视为不同。
输入
输入由多个测试案例组成。第一行包含一个整数t（1≤t≤1000）--测试案例的数量。测试用例的描述如下。
每个测试用例的唯一一行包含一个整数n（2≤n≤109）--Alice给Bob看的数字。
输出
对于每个测试用例，输出一个整数 - 有序的正整数对的数量，以便当Alice将它们相加时，她将得到一个n的结果。
—— 通过 www.DeepL.com/Translator 翻译
解题
本题可思考Alice的加法方式和正常进位的加法方式。
Alice将个位的进位进到了百位，百位的进到了万位……反过来，十位的进到千位，如是往复。
不难发现，将互不相关的奇数位和偶数位分别提出来组成新的正常进位的数字，利用排列组合的原理即可求出最终答案。
对于自然数n，使得a+b=n (a,b为正整数)的方案数为n-1种。
通过比较发现，当A的奇偶都为0，且B的奇偶都为0时，应该将答案减去这两个舍去的情况。
示例代码
#include
<bits tdc++.h="">
using namespace std;
int t;
string n;
int num1,num2;
int main(){
cin>>t;
while (t--){
cin>>n;
num1=num2=0;
for(int i=0;i
<n.length();i++){ if(i%2="=0)" num1="num1*10+n[i]-'0';" else="" num2="num2*10+n[i]-'0';" }="" cout<<"="">
"<
<num1<<" "<<num2<<endl;="" cout<<(num1+1)*(num2+1)-2<<endl;="" }="" return="" 0;="" }<="" re="">
</num1<<">
</n.length();i++){>
</bits>
</a<<endl;>
</bits>
</endl;>
</bits>