2019广工赛补题
B:HDU 6462 人类史上最大最好的希望事件
斐波那契数列平方和加前缀和（或者斐波那契数列平方和等于fn*fn+1）
关键是取模比较坑。。。数学菜是原罪。。。
代码：
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const ll mod=192600817;
const int N=50050;
ll fp[N]={0,1},s[N]={0,1};
void solve()
{
for(int i=2;i<N;i++)
{
fp[i]=(fp[i-1]+fp[i-2])%mod;
s[i]=(fp[i]*fp[i])%mod;
s[i]=(s[i]+s[i-1]); //这里不能取模
}
}
ll abss(ll a)
{
if(a<0)a=-a;
return a;
}
int main()
{
int n;
solve();
while(~scanf("%d",&n))
{
while(n--)
{
int a,b,c,d;
ll ans=0;
scanf("%d%d%d%d",&a,&b,&c,&d);
int x=a*4+b+1,y=c*4+d+1;
if(y<x)
{
int te=y;y=x,x=te;
}
printf("%lld\n",(s[y]-s[x-1])%mod); //这里必须取模，绝对值不行。。。
}
}
return 0;
}
1010 HDU 6470 Count
矩阵快速幂。。。矩阵快速幂其实很好看出来，关键就是n立方有些人就不会处理（比如我这个菜鸡），实际上就是通过设置转移矩阵的系数使得每次i都会加一即可，会发现图上的i立方那一行算出来刚好是（i+1）立方，这其实也是整个矩阵快速幂应用的核心思想。。。
最终的矩阵如下图：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const long long mod=123456789;
struct matrix
{
long long m[6][6];
};
matrix mul(matrix x,matrix y)
{
matrix temp;
memset(temp.m,0,sizeof(temp.m));
for(int i=0;i<6;i++)
for(int j=0;j<6;j++)
for(int k=0;k<6;k++){temp.m[i][j]=(temp.m[i][j]+x.m[i][k]*y.m[k][j])%mod;}
return temp;
}
matrix mm(matrix x,ll s)
{
matrix res;
memset(res.m,0,sizeof(res.m));
for(int i=0;i<6;i++)res.m[i][i]=1;
while(s)
{
if(s&1)res=mul(res,x);
s>>=1;
x=mul(x,x);
}
return res;
}
int main()
{
int h;
scanf("%d",&h);
while(h--)
{
ll x;
cin >> x;
matrix ob={2,0,0,0,0,0,1,0,0,0,0,0,27,0,0,0,0,0,9,0,0,0,0,0,3,0,0,0,0,0,1,0,0,0,0,0};
matrix o={1,2,1,0,0,0,1,0,0,0,0,0,0,0,1,3,3,1,0,0,0,1,2,1,0,0,0,0,1,1,0,0,0,0,0,1};
o=mm(o,x-2);
o=mul(o,ob);
printf("%lld\n",o.m[0][0]%mod);
}
return 0;
}
8 HDU 6468 zyb的面试
首先我们应当了解我们自己是如何去寻找这个数的确切值的，一般而言，都是通过一层一层的判断，确定这个数属于哪个范围，然后再增加数位然后再去判断，这就比较符合“树”的思想，即我们通过逐层判断，最终确定该数的值。因此我们就可以比较自然的想到建立十叉树然后利用dfs来寻找该数。
官方的题解如下：
题目的难点就在于判断每一步是向左还是向下（暴力会TLE。。。）
好吧，后来又在网上看到大佬的代码，不建树也可以解，大概就是你可以直接在过程中把这个数算出来。。。 贴个链接吧。。。（https://blog.****.net/tianyizhicheng/article/details/88605227）
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e6+20;
int tree[N],n,d;
void build_tree(int now) //建树
{
for(int i=1;i<=10;i++)
{
if((now)*100+i<N)
{
tree[now*10+i]=now*10+i,build_tree(now*10+i);
}
else if(now*10+i<N)tree[now*10+i]=now*10+i;
}
}
int dfs(int k,int num,int deep)
{
//cout << tree[num] << endl;
int cnt; //算节点的孩子数
int mx = (tree[num]+1)*(int)pow(10,d-deep)-1;
//cout << mx << endl;
if((tree[num]+1)*(int)pow(10,d-deep)-1<=n)cnt=(int)(pow(10,d-deep+1)-1)/9;
else if(deep<d)
{
int temp = min(mx,n) - tree[num]*(int)pow(10,d-deep)+1;
//cout << temp << endl;
temp=max(temp,0);
cnt = (int)(pow(10,d-deep)-1)/9+temp;
}
else cnt=1;
//cout << tree[num] << ' ' << cnt << endl;
if(k==1)return tree[num];
if(k>cnt)return dfs(k-cnt,num+1,deep); //步数大于孩子数就可以向右走
else return dfs(k-1,num*10,deep+1); //否则向下走
}
int main()
{
build_tree(0);
//cout << tree[10] << endl;
/*for(int i=0;i<=1000;i++)
{
printf("%d ",tree[i]);
if(i%10==0)puts("");
}*/
int k,T;
cin >> T;
while(T--)
{
d=0;
scanf("%d%d",&n,&k);
int x=n;
while(x)x/=10,d++;
int fx = dfs(k,1,1);
printf("%d\n",fx);
}
return 0;
}
4 HDU 6464 免费送气球
线段树+离散化。
其实基本上就是纯的线段树题目，只不过在线段树的基础上做小小的修改，以及对输入做一些处理。
如何使用线段树呢？
事实上，线段树的每个节点上除了保存有子树的和以外，它还隐含了一个信息，就是坐标。
我们可以先把操作都读一遍，把所有的数据都存进一个数组，然后我们就可以排序离散化然后知道这些数据的相对大小关系，这样之后我们就知道了这些数据在插入线段树时的坐标，然后的操作就和基础的线段树一致了。
也可以不事先读入数据，每次从1-1e9二分来找相对位置。
取模可能要小心点，WA了一发。（建树的部分好像不能取模）
代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>PLL;
const int N = 1e5+10;
const ll mod =1000000007;
struct Op
{
int o;
ll f,s;
Op(){};
Op(int _o,ll _f,ll _s):o(_o),f(_f),s(_s){};
}O[N];
ll sorted[N]={0};
PLL tree[N*8];
void push_up(ll rt)
{
tree[rt].first=(tree[rt<<1].first + tree[rt<<1|1].first)%mod;
tree[rt].second = (tree[rt<<1].second + tree[rt<<1|1].second);
}
void update(ll lc,ll nu,ll l,ll r,ll rt)
{
if(l==r){tree[rt].first=(tree[rt].first+(sorted[lc]*nu)),tree[rt].second+=nu;return;}
ll mid = (l+r)>>1;
if(mid>=lc)update(lc,nu,l,mid,rt<<1);
else update(lc,nu,mid+1,r,rt<<1|1);
push_up(rt);
}
ll quary(ll lc,ll l,ll r,ll rt)
{
if(lc==0)return 0;
if(l==r)return (lc*(tree[rt].first/tree[rt].second))%mod;
ll mid = (r+l)>>1;
if(tree[rt<<1].second<=lc)return (tree[rt<<1].first+quary(lc-tree[rt<<1].second,mid+1,r,rt<<1|1))%mod;
else
{
return quary(lc,l,mid,rt<<1);
}
}
int main()
{
int Q;
ll cnt=0;
cin >> Q;
for(int i=0;i<Q;i++)
{
int t;
ll f,s;
scanf("%d%lld%lld",&t,&f,&s);
O[i]=Op(t,f,s);
if(t==1)
{
sorted[cnt++]=s;
}
}
sort(sorted,sorted+cnt);
for(int i=0;i<Q;i++)
{
if(O[i].o==1)
{
ll lc = lower_bound(sorted,sorted+cnt,O[i].s) - sorted ;
//cout << lc << endl;
update(lc,O[i].f,1,cnt,1);
}
else
{
ll a = quary(O[i].s,1,cnt,1);
//cout << a << endl;
ll b = quary(O[i].f-1,1,cnt,1);
//cout << b << endl;
printf("%lld\n",(a-b+mod)%mod); //加mod应该是防负数。。。
}
}
return 0;
}
9 HDU 6469 故事
这题采用的是倒推法。由于当打败的1级怪数量确定后，打怪的顺序就确定了（大到小有很多种走法，但小到大的走法是唯一的）。
而且这题的答案符合线性要求（打的怪越多，经验一定越多）。
所以我们可以二分打1级怪数量，然后判断能不能符合情况。
但这题的难点在于直接循环来做会超时(1e5*1e5)，所以需要合并一些链条，以及做适当的剪枝，具体看代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N =1e5+10;
int n,tot,ct[N]={0};
ll now,a[N];
int check(ll m)
{
ll ans=0,sum=n; //ans代表使用的体力，sum表示层数
for(int i=1;i<=tot;i++)
{
if(m==1)return(now-ans)>=(sum); //剪枝，当m==1时，我们直接判断剩下的体力够不够走完（不加TLE）
ans+=m*ct[i];
sum-=ct[i];
if(ans>now)return 0; //体力超过上限就失败
if(i<tot)m=m/a[i+1] + ((m%a[i+1])?1:0); //这里向上取整。
}
return 1;
}
int main()
{
int Q;
ll mx=1,ans=1;
cin >> n >> Q;
tot=1,ct[tot]=1;
scanf("%lld",&a[tot]);
for(int i=2;i<=n;i++) //合并。将生成1个低级怪的情况合并在一起，遇到时直接整条判断
{
ll x;
scanf("%lld",&x);
if(x==1)ct[tot]++;
else {a[++tot]=x,ct[tot]=1;}
}
while(Q--)
{
scanf("%lld",&now);
if(now<n){cout << 0 << endl;continue;}
ll r=(ll)1e9,l=0;
ll mid,ans;
while(r>=l)
{
mid =(r+l)>>1;
if(check(mid))ans=mid,l=mid+1;
else r= mid-1;
}
printf("%lld\n",ans*a[1]);
}
return 0;
}