XDOJ 1009&1010&1011 – fffasttime

1009

卡在1018不会写了，因为1018是1009的加强版，是1007的二阶加强版，非常困难。1009虽然比1008提高了很多，但还是可写的，只要把链表换成搞基一点的书局结构就行了(树状数组、线段树、……)。因为链表主要把时间花在模拟k次跳跃上了，于是只要知道某个区间有多少个数就可以直接跳过去，用树状数组维护区间上还剩几个人就行了。

```
 
```
```
#include <iostream>
```
```
#include <cstdio>
```
```
#include <cstdlib>
```
```
using namespace std;
```
```
 
```
```
struct L_tree
```
```
{
```
```
int l,r,s;
```
```
}tr[800001];
```
```
 
```
```
int n,sum=0,tn;
```
```
 
```
```
void Make(int l,int r,int p)
```
```
{
```
```
tr[p].l=l;
```
```
tr[p].r=r;
```
```
if (l==r)
```
```
tr[p].s=1;
```
```
else
```
```
{
```
```
Make(l,(l+r)/2,p+p);
```
```
Make((l+r)/2+1,r,p+p+1);
```
```
tr[p].s=tr[p+p].s+tr[p+p+1].s;
```
```
}
```
```
}
```
```
 
```
```
int Up(int q,int p)
```
```
{
```
```
tr[p].s--;
```
```
if (tr[p].l==tr[p].r)
```
```
{
```
```
tr[p].s=0;
```
```
return tr[p].l;
```
```
}
```
```
if (q<=tr[p+p].s)
```
```
return Up(q,p+p);
```
```
else
```
```
return Up(q-tr[p+p].s,p+p+1);
```
```
tr[p].s=tr[p+p].s+tr[p+p+1].s;
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
int i,j,pos,se,n,m;
```
```
se=pos=1;
```
```
cin>>n>>m;
```
```
Make(1,n,1);
```
```
for (i=1;i<=n;i++)
```
```
{
```
```
se=(se+m-1)%tr[1].s;
```
```
if (se==0)
```
```
se=tr[1].s;
```
```
pos=Up(se,1);
```
```
if (i<n) cout<<pos<<' ';
```
```
else cout<<pos<<'\n';
```
```
}
```
```
return 0;
```
```
}
```

1010 最优规则式

这道题看起来是数据结构题，但再仔细观察一下发现由于有(a<b<c<d)所以直接前后计算某个位置左边的最大值和右边的最大值，再枚举一下这个位置即可，复杂度O(n)直接过了。

1011 高斯函数和

据说是1029的前置题，但算法已经很难推了。计算完整的和我只想到sqrt(n)的算法，如下：暴力计算到第k个高斯函数的时候，如果k比较大，那整除的结果不会经常改变，对于这部分计算出相同连续的n整除k结果的数量即可。但对于k比较小的情况只能一个个计算。当k取sqrt(n)的时候最快，要计算O(sqrt(n))次。对于10^18的情况还是会超时。

由于题目只要求计算奇偶性，所以还要再搞搞。仔细观察一下之前计算的式子会发现计算前后两部分的算式几乎一样，提取出一部分会得到一个偶数减去一个余项，所以只要判断余项的奇偶性即可。这里我用double被坑了一下，因为10^18用long double精度才够。。。

发表评论 取消回复

发表评论取消回复