作者： 林 珂涵

聚龙DAY5（补

Posted on By 林 珂涵 聚龙DAY5（补无评论

1.容斥原理

A∪B∪C = A+B+C – A∩B – B∩C – C∩A + A∩B∩C
早上讲课讲了一些奇奇怪怪的东西，又简单又难的神奇物品

2.比赛

什么奇奇怪怪的东西啊
S组 15/400
第四题原本打了前10%，但是少了三个>,然后挂了

1.chess 棋
标程很神奇，竟然统计一下该数在二进制中1的数量就可以了
实在是太神奇了
代码如下

#include<bits/stdc++.h>//棋
using namespace std;
#define int long long
#define rep(i,l,n) for(int i=l;i<=n;i++)
int n,m,a[10];
signed main()
{
    cin>>n>>m;
    rep(i,1,m) cin>>a[i];
    int sum=2;
    a[++m]=1;a[++m]=n;
    sort(a+1,a+m+1);
    rep(i,2,m) sum+=__builtin_popcountll(a[i]-a[i-1])-1;
    //__builtin_popcountll是在二进制的该数中有几个1
    cout<<sum<<endl; 
    return 0;
}

3.J组

1.小H的字符串
以前打过一模一样的题目，好像是什么压缩字符串的，
2501 OJ 上有打过
2.小H的任务 什么奇怪的东西
3.小H的游戏
思路：用搜索与回溯，记录所花费时间
要与t相等
4.小H的宝箱
第一反应是排列组合
有点类似第一天的放球问题
但是计算阶乘会爆，取膜后答案不对
用这个只能拿30分，
但是感觉全排列也会炸

Read More “聚龙DAY5（补” »

训练日志

聚龙DAY3

Posted on By 林 珂涵 聚龙DAY3无评论

1.数论

1.整除关系
a|b 表示b mod a=0
若a|b且a|c，则a|(bx+cy)
最大公约数GCD(a,b) 辗转相除
最小公倍数LCM(a,b)
GCD(a,b)LCM(a,b)=ab
2.同余关系
a≡b(mod m) //a-b能被某个自然数m整除
等价于 a mod m=b mod m
3.同余关系的性质
若a≡b(mod m)
a+c ≡b+c(mod m)
ac ≡bc(mod m)
如果a≡b(mod m)，x≡y(mod m)，则a+x≡b+y(mod m)
如果a≡b(mod m)，x≡y(mod m)，则ax≡by(mod m)
若a mod p=x且a mod q=x,p和q互质，则a mod(pq)=x
如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m)
如果c和m不互质：
g=gcd(c,m)//最大公约数
a≡b(mod m/g)//c与m/g互质
a≡b（mod m/y)(c与m不一定互质)
4.辗转相除
求gcd(a,b)
Gcd(a,b)=gcd(a mod b, b)
Gcd(a,b) = gcd( a – b, b)
求ax+by=c的整数解
其中c|gcd(a,b)
我们不妨设c=gcd(a,b)（若不等最后答案乘以一个c/gcd(a,b)即可）
5.辗转相除（裴蜀定理）
若b=0那么x=1,y=0;
否则
考虑 ax+by=gcd(a,b）与 bx’+(a mod b) y’=gcd(a,b)解的关系
bx’+(a-b*(a/b))y’=gcd(a,b) 这里的除法为整除
ay’+b(x’-(a/b)y’)=gcd(a,b)
所以 x=y’ y=x’-(a/b)y’
就这样迭代下去就可以得出ax+by=gcd(a,b) 的一组解 要变换其他的解只需要
x+kb,y-ka即可
6.逆元
求0<=x<b的x满足 ax=1 (mod b)
gcd(a,b)=1
这样的x我们称为在mod b意义下的a的逆元
7.费马小定理 ap-1%p=1
8.剩下不会，下一个

2.比赛

今天比赛再创历史“新高”
直接爆0了（鬼知道我第一题怎么RE的
1.chicken 最小生成树（但炸了
2.dusk 实在是太“easy”了，简单到不想打了
（为什么连一个“NO”都没有，样例实在是太高明了
3.dog
打了暴力，但挂了
不是我说，它是怎么做到，插队往后插的啊
而且还是一个一个往后插的？
4.贪心，但是我不会；

Read More “聚龙DAY3” »

训练日志