比赛链接
比赛链接：Tasks - Monoxer Programming Contest 2022（AtCoder Beginner Contest 238）
这一次只做了三题，额，跟我状态有关，本来打着玩玩的，第四题的位运算没做出来。。。就放弃了，EF都看都没看，我的锅。。
A(签到)
输入$n(1\leq n\leq 10^9)$，如果$2^n>n^2$，就输出Yes，否则输出No
这个解只有$2,3,4$，注意判断时候$1$也不满足，wa了一发。。
B.Pizza(模拟)
挺有意思的，一个360°的披萨，一开始切一刀然后转$A_i$再切一刀，问最大的那一块是多少。
直接模拟，数据不大，开一个360°的数组模拟每一度有没有被刀
C.digitnum(数学)
定义f(x)表示不大于x的正整数有多少个跟x同位的数，比如f(9)=9，从1到9；f(39)=30，是从10开始一直到39
读入$n(1<n<10^{18})$，求$ans=f(1)+f(2)+\dots +f(n)$
不难发现每次就是计算等差数列，比如1位的时候是1...9，两位的时候就是10...99，假如n是一个3位数，那么就是100...x，实际上同减去99得到f(i)，变成了1...x-99，同样是计算等差数列，题目不难，就是数据很大，1e18的数据让我很头疼，总结如下：
unsigned long long的范围是long long的两倍，无符号，也就是最开始的那一位用来表示数字，也就是乘以2
__int128范围是$-2^{127} \thicksim 2^{127}-1$，大概是1e38
注意输出，没有关于输出__int128的库，cin和printf都没有，所以需要手写
这里不需要读入，我就手写print
inline void print(__int128 x)
{
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
总结后发现
最后查找题解和讨论之后，了解到一个定义——三角数：1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78,..n(n+1)/2。也就是我上面要求的等差数列，现在因为数据范围的问题导致很大。求n(n+1)/2的时候可以通过先取余然后相乘，除法用乘法逆元，最终ac
正解是这样可以的：
long long triangular_number(long long x){
x%=mod;
long long res=x;
res*=(x+1);res%=mod;
res*=inv2;res%=mod;
return res;
}
D.AND and SUM(位运算)
给出$a,s$，问是否有解满足
· $ x \ AND\ y = a $
· $ x + y = s $
我们需要一个十分重要的公式，我以前见过，但是忘了。。
$x\& y + x| y = x+y$
所以我们能得到与和或的关系，因为这两个运算不会进位
对于D，显然x和y的二进制位中都包含a，除a外的其他位不重合，于是可以把这些多出来的位全部移到x，此时y=a，则x=s-a，判断x>=0且x&y=a即可
这里重新写一篇题解，就写在这里了
总结
做题就是总结，每次收获一点就是最大的收获，希望下次努力克服，保证至少四题
文章评论