1. 负进制数
[P1017 NOIP2000 提高组] 进制转换 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
所谓负进制数，就是进制数为负数的一种实数表示法。
例如，-15(十进制)相当于110001(-2进制),并且它可以被表示为2的幂级数的和数:
110001=1(-2)5+1*(-2)4+0(-2)3+0*(-2)2+0(-2)^1 +1(-2)^0
我们对于给定的一个数，求它关于进制x（一个负数）的进制表示，要怎么做呢？
首先，应该了解如何将10进制转换成n进制，这里需要用短除法。将10进制数取余n，其商再继续取余直到该数被除至0，依次得到的余数倒序即为该10进制数的n进制表示。如果将10进制转换为-n进制呢？方法基本一样，只不过要注意的是要使其余数>=0，绝对不能为负数。举个例子，将10进制数15转换成-2进制：
- -15 - 8*(-2) = 1
- 8 - (-4)*(-2)=0
- -4-2*(-2)=0
- 2-(-1)*(-2)=0
- -1-1*(-2)=1
- 1不用做处理直接多一位1 然后被除数=0 因为进制是负数
我们要保证 这个 除数 × 商 + 余数 = 被除数
在C++里，-15%-2=-1，-15/-2=7,而7*-2+（-1）=-15
但是因为我们是不断取余数倒序为转换结果，所以余数不能出现负数。
所以我们只需要将商+1，余数-除数即可，因为余数（绝对值）一定小于除数，所以这样就可以将余数装换为正数
证明：（商+1）×除数+（余数-除数）= 商×除数+除数+余数-除数=商×除数+余数=被除数
我们将mod改写一下，其他部分和正数进制转化是相同的。
int MOD(int &n,int a,int b){
if(a<0 && a%b!=0){
n = a/b+1; //这个n其实是每一次运算的商，下一次运算的被除数。
return a-(a/b+1)*b;
}
n=a/b;
return a%b;
}
2. set 和 unordered_set
P3913 车的攻击 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
方法简单，但是当你使用set去重的时候，要注意：
如果你的方法不需要用到set的自动排序的功能，推荐使用unordered_set，具体表现是插入速度更快。
有时候就卡你一手tle。所以还是要拓宽知识面。
然后该开longlong的时候要看清楚数据范围。不要忘记。
void solve(){
LL n,k;
cin>>n>>k;
unordered_set<LL>s1,s2;
for(int i=1;i<=k;i++){
LL x,y;
cin>>x>>y;
s1.insert(x);
s2.insert(y);
}
int len1 = s1.size();
int len2 = s2.size();
cout<<1LL*len1*n + 1LL*abs(n-len1)*len2;
}
3. 其他
3.1 最大公约数和最小公倍数问题
[P1029 NOIP2001 普及组] 最大公约数和最小公倍数问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
tips:如果你想要使用标准库中的gcd ：std::__gcd(int a,int b); //如果你要longlong类型的就把参数类型改一下。
LL gcd(LL a,LL b){ //最好记一下
return b?gcd(b,a%b):a;
}
void solve(){
int x,y;
cin>>x>>y;
LL tmp = x*y;
int sum=0;
int cnt=0;
for(LL i=1;i*i<=tmp;i++){
if(tmp % i ==0){
LL j = tmp / i;
if(gcd(i,j)==x) {
// debug(i)debug(j)
sum++;
if(i==j) cnt++;
}
}
else continue;
}
cout<<1LL*sum*2-cnt<<endl;
}
dont forget the LL
今天内容不是很多，因为打的都是宝宝巴士
总之有收获的我都会发。