千题目标Category

【差分约束/tarjan缩点】BZOJ2330 银河

传送门

题目的五个条件转化为差分约束的不等式
再加：

  • 设d[0] = 0; d[i] – d[0] = 1 每个星球最低为1亮度
  • 再从0一个点往所有点连1的有向边

题目可能出现无解的情况，差分约束的图出现正环即无解。

但是题目数据量很大，直接在跑最长路的时候用spfa判正环会超时

先tarjan缩点。同一个强连通分量里面如果边权之和为正那么肯定存在正环直接无解。复杂度O(N)

最后把缩点后的图重新建图，是一个有向无环图，可以直接跑最长路。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 233;
int n, m;
int h[maxn], e[maxn], val[maxn], pre[maxn], cnt;
int hc[maxn], ec[maxn], valc[maxn], prec[maxn], cntc;
void add(int u, int v, int w)
{
    e[++cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt;
}
void addc(int u, int v, int w)
{
    ec[++cntc] = v;
… Read the rest

【差分约束/数据结构优化贪心】poj1201 区间

传送门

这个题目有两种做法

差分约束

设s [ i ]表示前i个里面取数的个数
* s[b] – s[a – 1] = ci
* s[k] – s[k – 1] = 0 (任何k要比k-1取得多)
* s[k] – s[k – 1] <= 1 (任何数只能取一次)

然后建图跑，从第一个点开始跑最长路。
注意最后只能用spfa来跑，因为djistra无法处理反边权的情况。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 233;
int h[maxn], e[maxn], pre[maxn], val[maxn], cnt;
void add(int u, int v, int w)
{
    e[++cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt; 
}
int dis[maxn], vis[maxn];
void dji()
{
    memset(dis,
… Read the rest

【CDQ分治】HDU1520-Tunnel Warfare

题目传送门

离线分治大法好啊！！

题意

区间有n<=50000个点，m<=50000次操作。一开始所有点都是相连的。有三种操作。1 断开某个点。2 恢复上次断开的点。 3 查询某个点属于的线段的长度。

这个题本来是在集训队的线段树作业里。今天学了CDQ分治突发奇想好像可以做…..然后就做了。虽然当时我也是用set做的

思路源于set的在线算法。

set本质平衡树。每次读到一次断开操作，在平衡树中加入这个节点。查询的时候在平衡树里查找第一个比它大的和第一个比它小的数字。其差值就是答案。

恢复操作需要用一个栈存起来。然后从平衡树里删除这个值。总复杂度NlogN,其中N指的操作总数

这里有个坑点。断开操作可能会有重复。比如先断开 3 再断开 4 然后再断开 3 。虽然对查询操作没有影响，但是恢复操作的时候第一个恢复的是 3 这个点…..我因为这个WA了好久

但是虽然STL里面有set，但如果不能用STL或者不会写平衡树怎么办呢。

重点来了：CDQ分治

CDQ分治是一种基于时间分治的离线算法。其核心思想就是基于前面的操作会对后面的查询造成影响。所以可以把查询离线，根据时间顺序，计算修改操作对之后每个查询的影响。

然而这题有点特别就是有撤销操作。每次修改对后面询问的影响都可能被撤销。如果单单按照操作顺序作为时间分治，还需要用到可持久化的数据结构。

但是换个思路。既然每个操作有撤销，那么就考虑每个操作的”存活时间”。

每个操作在撤销之前对其间的询问都会造成影响。考虑每个操作的存活时间，把询问根据存活时间分治。

比如”DDDRQDQ”，其中第三个D的存活时间为0，因为它没有对任何询问造成影响。第一、二个询问的存活时间都为2，考虑其出生时间，记为[1,2]，最后一个D则是[2,2]。

接下来把相应的询问安排到相应的区间。有点类似于线段树的感觉。在每个断开操作造成影响的询问操作的区间加上它。

在每个区间分治的时候把修改和询问一起排序。因为CDQ分治的正确性，修改一定会对只后的询问造成影响，所以可以把坐标排序。然后从左往右，从右往左扫一次。依次找出每个询问最近的修改就可以啦。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 233;
struct dt{
    int x,l,r;
}a[maxn];
int n,m,q[maxn],ansl[maxn],ansr[maxn],vis[maxn];
pair<int,int> b[maxn];
vector<int> g[maxn * 4];
void cg(int k, int l, int r,int x,int y,int id)
{
    if(x > y) return;
    if(l > r || l > y ||
… Read the rest

【莫比乌斯反演】牛客练习赛40E-小D的lemon

本题细节极多。WA题自闭两开花

传送门

解题方法打字太难了。手写算了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 250025;
ll p = 1e9 + 7;
ll primes[maxn], mu[maxn], g[maxn], f[maxn], invg[maxn], inv[maxn], s[maxn], cnt;
bool st[maxn];
ll ksm(ll n, ll m)
{
    ll res = 1;
    while(m)
    {
        if(m & 1LL) res = (res * n) % p;
        n = (n * n) % p;
        m >>= 1LL;
    }
    return res;
}
void get_primes(int n)
{
    mu[1] = 1; f[1] = 1; invg[1]
… Read the rest

【线段树维护数列】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

【并查集+离散化】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

【斜率优化】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

【斜率优化】牛客练习赛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

蓝桥杯 算法提高 周期字串

题目地址

题意就是让求整个字符串最小循环节的长度。字符串长度小于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

蓝桥杯题库解题报告

蓝桥杯历届试题做题记录

解题报告 与 题解

标签（空格分隔）： 做题记录

鉴于网上蓝桥杯的大多数题目几乎找不到很好的题解，甚至出现了很多错误的题解。所以抽时间做了一份结题报告。
按逆序编号，和蓝桥杯练习网站上一样。有一些题在本弱博客上写过就直接贴地址了。
本报告所有题目已经由本弱亲自提交并且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