训练笔记

Tiork蜡笔小新 · 2020-10-07 12:11:38 · 个人记录

1：疯子坐飞机问题

飞机上有100个座位，按顺序从1到100编号。有100个乘客，他们分别拿到了从1号到100号的座位，他们按号码顺序登机并应当对号入座，如果他们发现对应号座位被别人坐了，他会在剩下空的座位随便挑一个坐。现在假如1号乘客疯了 -_-! (其他人没疯)，他会在100个座位中随机坐一个座位。那么第100人正确坐自己座位的概率是多少？

答案：恒为1/2

2：比值排序问题，a/b 与 c/d 化为 ad 与 cb

3: 约瑟夫环，n个人k号死亡，赢家递推公式：

f(N,M)=(f(N−1,M)+M)%N

n个人，k人死，第m个死的，递推公式：

A(n,m)=(A(n−1,m−1)+k)%n

4：__int128数据类型，占用16个字节，可存下1e35大小的数，输入输出：

inline __int128 read(){
    __int128 ans=0,w=1;
    register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') ans=ans*10+(ch^48),ch=getchar();
    return ans*w;
}
inline print(__int128 x)
{
    if(!x) cout<<0;
    stack<int>st;
    while(x) st.push(x%10) ,x/=10;
    while(st.size()) cout<<st.top(),st.pop();
    cout<<endl;
}

5：遇到大于__int128的加法。用两个数代替一个数。

打表找规律是ACM重要的思维。