contest hit The 34th ACM/ICPC Asia Regional Harbin Preliminary
9.13的哈尔滨网络赛…
The 34th ACM/ICPC Asia Regional Harbin Preliminary
这个在哪里可以继续做题呢?
数模和网络赛严重撞车…唉…还撞上2天网络赛挤在一起的这周…
然后不知道在哪里还能看题和交题…已经记不清楚题目了…
而且做的也不太好…
队伍排名80多…一共10题,出了4题,分别是BCDJ…有一题是最后四分钟1A的…真是全身发抖的感觉…
一开始J题很多人过…感觉是个约瑟夫环的变形…不过怎么都想不出怎么做…
然后看到B题…树长的好快…节点最多m个孩子节点,没满的话每单位时间可以长出一个,问n<=2^128个单位时间后树有多少节点
是个菲波那契数列的变形…构造个转移矩阵…m+1阶的…然后二分,还有高精度
高精度没写好,结果错了2次…最后AC了…
然后sky想了个二分+树状数组来做J题的方法…然后过了
然后yq做了C题…一个KM…过了
接着想H题…菲波那契数列那题…话说出题人是菲波那契数列控么…
但是sky想了几个公式,结果还是WA到死…
还剩30分钟的时候准备写D题…如果规模小到100的话我会用高斯消元搞掉…可是规模有10000…
我本想用高斯消元先写个小数据找找规律的…可是完全找不出…都是小数点后好多位都还没规律的…
没办法…画了个矩阵大概的样子给yq…yq冒出来一句什么追赶法…然后去找书,也没找到什么结果…
然后我就YY了个算法…因为矩阵只有对角线和对角线上面和下面一共三个斜线上有非零值…
我就从上到下扫一遍,下面一行减去上面一行乘以一个系数,使得下面一行对角线左边的数消掉为0
然后从下往上扫一遍,上面一行减去下面一行乘以一个系数,使得下面一行对角线右边的数消掉为0
这是矩阵除了主对角线和增广的那一列,其他都是0了,于是就把每个变量值解出来
此时只剩4分钟…全身发抖,测几组数据时连输入数据都输不对了…然后交掉…1A…顿时人软掉了…
简述:
A: 不记得了
B: 和前m项有关的菲波那契数列,转移矩阵,高精度
C: 排列数差异,KM
D: 博弈,数学期望,解线性方程组,根据方程组的特性弄个专门算法
E: 不记得了
F: 不记得了
G: 不记得了
H: 前两项乘以系数的菲波那契数列,不会
I: 不记得了
J: 约瑟夫问题变种,每次间隔人数不同,不知有没有公式,我们用的是树状数组+二分
下面是D题代码,没有详述: