| by XianKa | No comments

【线段树维护数列】CF-446C – DZY Loves Fibonacci Numbers

题意

给一段序列,长度小于3e5,给出多次(3e5)区间操作,每次在 [ l , r ] 依次从fib(1)加上斐波那契数列。
斐波那契数列即f[n] = f[n – 1] + f[n – 2]; 前5项为1,1,2,3,5;
比如[1,1,4,5,6]现在要求在[2,4]上增加,[1,1+1,4+1,5+2,6+3]

另外一个操作就是求区间和。
传送门

斐波那契数列的性质

1.fib[n] = fib[n+2]-fib[2]

这个性质由斐波那契数列的差分推出。
1,1,2,3,5,8,13,21…
..,0,1,1,2,3,5..,8..,13…
可以看出,斐波那契数列求差分以后还是一个斐波那契数列,而且每一位向后移动了两个位置。根据差分的性质:差分序列的N位前缀和即原序列的第N个数字。可以通过逆差分得到序列和。
所以如果想求斐波那契数列的和,也可求它的差分的和,反正都是一样的,但由于差分出来的斐波那契数列是往后移动了两位的。所以需要原序列也往后移动两位,即fib(n)=fib(n+2)-fib(2)

2.斐波那契数列的叠加还是斐波那契数列

这个性质很好理解。因为每个斐波纳妾数列都满足同样的齐次线性递推关系。多个斐波那契数列的每一项还是满足。

也可以通过多次差分的规律,看出逆差分即本性质。

3.类斐波那契数列的公式

形如
F(1)=a,F(2)=b,F(n)=F(n-1)+F(n-2)
的数列即类斐波那契数列。
这类数列可以转化为斐波那契数列相关的数列。即
F(n)=a\times fib(n-1)+b\times fib(n-2)
可以通过矩阵证明
\left[\begin{matrix} 1 & 1\end{matrix} \right] \times \left[\begin{matrix} 0 & 1\\ 1 & 1 \end{matrix} \right]^{n} = \left[\begin{matrix} fib_{n-1} & fib_{n}\end{matrix} \right]
初始值的不同相当于左边的矩阵每列有个系数

线段树维护序列

魔改lazy

由于斐波那契数列的性质3和2,可以对lazy标记的传递方式进行魔改。每个区间记录序列前两个,这样既可以推算出区间和,也可以推算出某项的值。

向下传递的时候不是简单的直接传值。需要把对应的F1和F2算出来。因为对于每个小区间而言,它的F1和F2不再是大区间的F1和F2,需要用性质3计算。

比如
【1,8】
【1,4】 【5,8】
【1,2】【3,4】【5,6】【7,8】
【1】【2】【3】【4】【5】【6】【7】【8】
现在更新【2,6】… Read the rest

Read More
| by XianKa | No comments

【并查集+离散化】POJ2528

2528:Mayor’s posters

本题很多都是用的线段树,但线段树客观来说代码长,容易写错,所以并查集其实更好

先把操作离线,由于只有靠后的操作才会对区间产生影响,所以说每个点最后一次覆盖的才是最后显示的颜色

把区间抽象成节点。每个区间有一个l和r,倒着操作。每次操作就合并所有操作的区间。

如果操作的左右端点的父亲不同,那么本次操作就是合法的,说明至少有一个段是没有被合并的。还可以被涂一次颜色。

否则不合法次数 ans + 1。

最后答案就是 n – ans 。相当于问有多少次合法合并(询问)。很明显可以转化为并查集的询问条件是否成立。由于操作只有1e4次,所以不同的点不会超过2e4个点。可以把区间进行离散化。

#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<stdio.h>
#include<iostream>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 10233;
pii q[100233 + 233];
int f[100233 + 233];
int ff(int x)
{
    if(f[x] == x) return x;
    return f[x] = ff(f[x]);
}
void uni(int u, int v)
{
    f[ff(u)] = ff(v);
}
int main()
{
    int tc,n;
    scanf("%d",&tc);
    for(int j = 1; j <= tc; j++)
    
Read the rest Read More
| by XianKa | No comments

【二分-贪心】问题集合

二分这类问题 通常需要猜结论乱搞,解决此类问题的方法,就是见多识广

Q1

题意是说一个船会随风飘动,风的方向有周期。船每天也可以选择往一个方向自由航行,效果和风叠加,类似矢量。问最少多少天能到目的地。

做法是二分天数。天数定了,船如果不动,终点就是定了的。再此基础上船还可以走 天数 这么多步。如果和目的地的距离小于这个步数就缩减天数。

单调性:对于mid天,如果能达到,那么大于mid天也肯定能达到,因为多出的天数船可以想办法每天抵消风的影响呆在原地。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
int n, dirx[maxn], diry[maxn], desx, desy,inix,iniy;
string s;
int main()
{
    cin >> inix >> iniy >> desx >> desy;
    if(inix == desx && iniy == desy)
    {cout<<0;return 0;}
    cin >> n >> s;
    for(int i = 1; i <= n; i++ )
    {
        if(s[i - 1] == 'U') diry[i] = 1;
        if(s[i - 1] == 'D') 
Read the rest Read More
| by XianKa | No comments

【斜率优化】cf311b Cats Transport

题目地址

题意是说有n座山,每座山之间距离不同为di,p个饲养员,m只猫。每只猫会在Hi座山上,在Ti时间等待饲养。饲养员只能从1走到n不能停留,问怎么规划饲养员的出发时间才能使得等待时间最少。饲养员的出发时间可以为负。

规定 sum 代表前缀和。

对于某只猫 i 来说。如果饲养员在时间 t 出发,他要走 sumD[i] 的距离,那么这只猫的等待时间 W = t + sumD[i] – T[i] 。由此如果设 A[i] = T[i] – sumD[i] 。那么饲养员从时间 t 出发每只猫 i 的等待时间就是 t – A[i]

把 A 从小到大排序,由于 t – A[i] 不能是负数,所以每个饲养员一定从最开始往后带走连续的若干只猫而且排序的数组中最后一只一定等待时间为 0 。

设 f[ i , j ] 为前 i 个饲养员带走了前 j 只猫。那么第 i 个饲养员肯定从 A[j] 时间出发,带走的猫等待时间为\sum_{p=k+1}^{j}A_j-A{p}=A_j \times(j-k)-sumA[j]+sumA[k]设其为C

那么f[i][j] = min(f[i – 1][k] + C);

i j k 三层循环,把 i 看作不变量,对 j k 做斜率优化。同时由于每次只用到了i – 1的状态,所以可以把 … Read the rest

Read More
| by XianKa | No comments

【斜率优化】牛客练习赛40D 小A与最大子段和

题目传送门
官方题解
题意是说找到一个连续子段,使得\sum_{i}^{j}a_i \times i最大,也就是说每个数要乘上自己在子段里的位置。

官方题解就是说,令f[i]表示前i个数字的答案。f_{i}=\max_{j=0}^{i-1} (\sum_{k=j+1}^{i}a_k \times {(k-j)})这样每个a就可以和自己对应的坐标相乘,而j又是固定的,所以可以直接用前缀和把题目简化掉。

要截距最大化,斜率不单调,维护整个上突壳,在上突壳上二分找左边斜率小于当前,右边斜率大于当前的点。注意答案的初始化要为负数,因为答案可能为负。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+233;
ll a[maxn],b[maxn],f[maxn];
int q[maxn];
int l=1,r=1;
int n;
int brf(int k)
{
    if(l == r) return q[l];
    int L=l,R=r;
    while(L<R)
    {
        int mid=(L+R)>>1;
        if(b[q[mid + 1]] * q[mid + 1] - a[q[mid + 1]] - b[q[mid]] * q[mid] + a[q[mid]] 
            >= b[k] * (q[mid + 1] - q[mid])) L = mid + 1;
        else R 
Read the rest Read More
| by XianKa | No comments

蓝桥杯 算法提高 周期字串

题目地址

题意就是让求整个字符串最小循环节的长度。字符串长度小于100。
可以直接上kmp。就算长度一千万也可以搞。
当i-nxt[i]能整除i的时候,i-nxt[i]就是最小循环节的长度

#include<bits/stdc++.h>
using namespace std;
char a[111];
int nxt[111];
int n;
void kmp()
{
    nxt[1]=0;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j>0 && a[i]!=a[j+1]) j=nxt[j];
        if(a[i]==a[j+1]) j++;
        nxt[i]=j;
    }
}
int main()
{
    scanf("%s",a+1);
    n=strlen(a+1);
    kmp();
    if(n%(n-nxt[n])==0) printf("%d",n-nxt[n]);
    else printf("%d",n);
}
Read the rest Read More
| by XianKa | No comments

蓝桥杯题库解题报告

蓝桥杯历届试题做题记录

解题报告 与 题解

标签(空格分隔): 做题记录


鉴于网上蓝桥杯的大多数题目几乎找不到很好的题解,甚至出现了很多错误的题解。所以抽时间做了一份结题报告。
按逆序编号,和蓝桥杯练习网站上一样。有一些题在本弱博客上写过就直接贴地址了。
本报告所有题目已经由本弱亲自提交并且AC,但不排除网站的测试数据会被增强,以前的AC思路不一定会再次适用,建议对解题思路有疑问的先将AC代码粘上去看结果。


[TOC]


PREV-55 小计算器

题解

模拟

具体题解见博客

可以先把所有进制转为十进制,方便计算,要输出的时候再转成要求的进制

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,char> eco;
map<char,ll> deco;
int k=10;
ll ans=0;
char num[99];
void init()
{
    for(ll i=0;i<=9;i++)
    {
        eco[i]=i+'0';
        deco[i+'0']=i;
    }
    for(ll i='A';i<='Z';i++)
    {
        eco[i-'A'+10]=i;
        deco[i]=i-'A'+10;
    }
}
ll getnum()
{
    ll tmp=1;
    ll ret=0;
    for(int i=strlen(num)-1;i>=0;i--)
    {
        ret+=tmp*deco[num[i]];
        tmp*=k;
    }
    return ret;
}
void pout(ll tnum)
{
    //cout<<tnum<<endl;
    if(tnum==0)
    {
        printf("0\n");
        return;
    
Read the rest Read More
| by XianKa | No comments

蓝桥杯历届试题 区间移位

http://lx.lanqiao.cn/problem.page?gpid=T451

题意是给定n<=10000个区间,保证总长度大于等于10000,有重叠,让求最大移动的最小值是多少。

首先这个问法就很二分,但是check的方法不好想。

wjjj随便猜了个结论就猜对了(%%%)。二分后按照b排序,优先选b小的。

因为二分出mid后,对于任意一个区间,只能在[a-mid,b+mid]里移动。所以最开始假设没有覆盖,当前点k=0,从左到右选出可以覆盖的区间,尽量往右放进行覆盖,覆盖完以后k移动到本次覆盖区间的最右边。在多个区间都可以覆盖当前点k的时候,b小的肯定在向右移动的时候不是最优解,因为它无论如何都比比它b大的移动得多。最后如果找不到方案可以覆盖完整个区间就说明答案太小,否则答案可能太大。至于小数,可以证明只会有0.5出现,因为最开始的区间都是整数,如果有一个区间移动了1/3那么必然有一个区间需要移动2/3。肯定不是最优解。既然只有0.5那直接把区间长度扩大一倍,规定只能移动整数距离,最后答案half就可以了。

在查找b的时候不能暴力找,否则会炸掉,可以用二分来找,但是注意标记已经用过的区间,我直接用了multiset方便删除用过的区间,复杂度都是logN。总复杂度Nlog²N

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-12;
const int N=20000;
vector<pii> ab;
int vis[10001];
multiset<pii> c2;
int line[10001]; 
int main()
{
    int n,a,b;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        a*=2;b*=2;
        c2.insert({b,a});
    }
    int l=0,r=N;
    while(r>l)
    {
        multiset<pii> c1(c2);
        int mid=(l+r)>>1;
        int now=0;
        while(1)
        {
            int flag=0;
            multiset<pii>::iterator it;
            for(it=c1.begin();it!=c1.end();it++)
            {
                pii tmp=*it;
                int tta=tmp.second,ttb=tmp.first;
                if(tta-mid <= now && ttb+mid >= now)
                {
                    flag=1;
                    int len=ttb-tta;
                    if(now<=tta+mid) 
Read the rest Read More
| by XianKa | No comments

【数论】CF1110C

http://codeforces.com/problemset/problem/1110/C

题意是给一个a让求一个0<b<a使得gcd(a ^ b , a & b) 要最大

  • 首先注意到a^b和a&b的每一位都是相反的,所以说很容易想到构造一个b使得b&a=0,这样答案就是a^b。构造方法就是把a的每一位1变成0,0变成1。
  • 对于a的每一位全是1的情况需要单独讨论。
  • 如果a的每一位都是1,任取一个b,可以得到a^b=a-b , a&b=b 这个结论。那么问题就变成了求gcd(a-b,b),也就是gcd(a,b)_max。
  • 对于求最大的gcd,把a分解质因数,除掉其中一个最小的质因子,就是答案。
  • 由于本题时间不紧,而且cf测评机都是香港记者,所以可以直接根号复杂度暴力分解。当然也可以预处理质数表
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int q,a;
int main()
{
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&a);
        //a=q;
        int res=0;
        for(int i=0;(1<<i)+res < a;i++)
        {
            if(!((1<<i)&a) ) 
                res+=(1<<i); 
            //cout<<res<<'-';
        }
        if(res) printf("%d\n",res^a);
        else
        {
            bool flag=true;
            for(int i=2;i*i<=a;i++) 
            {
                if(a%i==0)
                {
                    flag=false;
                    printf("%d\n",a/i);
                    break;
                }
            }
            if(flag) printf("1\n");
        }
    }
}
Read the rest Read More
| by XianKa | No comments

牛客19寒假R2I

https://ac.nowcoder.com/acm/contest/327/I

这题有点坑的就是,这题其实和本场比赛上一题一点关系都没有……

直接分解质因子以后暴力n²枚举就可以,下面来分析一下这么做的时间复杂度:

  • 对于每个数分解质因子,sqrt(n)的复杂度,打素数表可以更快。2000*20=40000
  • 对于每个数枚举其他数,由于分解的时候质因子是有序的,所以对两个数可以归并排序的方法线性合并质因子。
  • 小知识点:对于1e9以内的数,一般不同的质因子个数不超过10个
  • 所以对于合并的复杂度,不会超过o(20),2000*2000*20=80000000
  • 总复杂度小于1e8,且常数极小,可以接受
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,ans=0;
vector<pii> a[2002];
int main()
{
    scanf("%d",&n);
    for(int j=1;j<=n;j++)
    {
        int k;
        scanf("%d",&k);
        for(int i=2;i*i<=k;i++)
        {
            int res=0;
            if(k%i==0)
            {
                while(k%i==0)
                {
                    k/=i;
                    res++;
                }
                a[j].push_back(make_pair(i,res));
            }  
        }
        if(k>1) a[j].push_back(make_pair(k,1));
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            int l=0,r=0,tmp=1;
            auto &aa=a[i];
            auto &bb=a[j];
            while(l<aa.size() && r<bb.size())
            {
                if(aa[l].first<bb[r].first) tmp*=aa[l++].second+1;
                else if(aa[l].first>bb[r].first) tmp*=bb[r++].second+1;
                else tmp*=aa[l++].second+bb[r++].second+1;
            }
            while(l<aa.size()) tmp*=aa[l++].second+1;
            while(r<bb.size()) tmp*=bb[r++].second+1;
            if(tmp<=10) ans++;
        }
    }
    printf("%d\n",ans);
Read the rest Read More