题意：   给出      m    m   m 个只由      A   ,   T   ,   C   ,   G    A,T,C,G   A,T,C,G 组成的字符串（每个的长度不大于      10    10   10），求一个长度为      n    n   n 且也只由      A   ,   T   ,   C   ,   G    A,T,C,G   A,T,C,G 组成但不包含之前所给的      m    m   m个字符串的序列的种类数。 思路：   借助离散数学中可达矩阵的概念。先把m个字符串建立成AC自动机中的字典树，同时对于字符串的结尾节点，进行标记。一个节...

题意：   给出一个      n    n   n 个数的数组和一个      t    t   t，要求出满足      ∑    i   =   l    r     a   i    <   t    \sum_{i=l}^{r}{a_i}<t   ∑i=lr​ai​<t 的      l    l   l和      r    r   r 的对数。 数据范围：     1   ≤   n   ≤   200   ,   000   ,   ∣   t   ∣   ≤   2   ⋅   1    0   14    ,   ∣    a   i    ∣   ≤  ...

题意：   给一个有向图，删除每一条边的代价是边的长度，要求花费最小的代价，使得      1   →   n    1\to n   1→n最短路变长,求该最小花费。 思路：   要使得最短路变长，那么删除的边一定要破坏原来的最短路。即要先把所有最短路的所有边找出来，通过删除某几条边，使得所有的最短路无效。   如何把最短路的所有边全部找出呢？以      d   i   s   1   [   i   ]    dis1[i]   dis1[i] 表示原图中，     1    1   1 号节点到其余节点的最短距离；以      d   i   s   2   [   i   ]    ...

毒瘤题 题意：      T    T   T 次询问，每次给定      n   ,   m    n,m   n,m ，求：     (    ∑    i   =   1    n      ∑    j   =   1    m     φ   (   i   j   )     )     m   o   d     998244353    (\sum_{i=1}^{n}{\sum_{j=1}^{m}{\varphi(ij)}})\;mod\;998244353   (∑i=1n​∑j=1m​φ(ij))mod998244353 的值。 数据范围：     1   ≤   T   ...

一.莫比乌斯函数： 1.定义：      μ   (   d   )   =    {     <mstyle displaystyle="false" scriptlevel="0">   1   ,   </mstyle>   <mstyle displaystyle="false" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="0">  d   =  ...

定义：        A   h   o   –   C   o   r   a   s   i   c   k    Aho–Corasick   Aho–Corasick 算法是由      A   l   f   r   e   d   V   .   A   h   o    Alfred V. Aho   AlfredV.Aho 和      M   a   r   g   a   r   e   t   J   .   C   o   r   a   s   i   c   k    Margaret J.Corasick   MargaretJ.Corasick 发明的字符串搜索...

题意：   首先给一棵      n    n   n 个点的树，然后有      q    q   q 次的询问，每次询问会向树上点      x    x   x 和      y    y   y 之间增加一条边（保证增加的边之前不存在），然后问点      a    a   a 和      b    b   b 之间是否存在一条路径长度为      k    k   k 的路径。每次询问相互独立，即每次增加的边在下一次的询问中不存在。 数据范围：      3   ≤   n   ≤   1    0   5    ,   1   ≤   q   ≤   1    0   5    ...

题解 A.配对： 贪心，倒序配对。  #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; const double eps=1e-6; priority_queue<int,vector<int>,greater<int> >que; int a[N],b[N]; int main() { int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i...

核心代码（求next数组和extend数组）： const int N=5e4+5; char s1[N],s2[N]; int nxt[N],extend[N]; void getNext(char s[])//模式串 { int ls=strlen(s),i=0; nxt[0]=ls; while(i<ls&&s[i]==s[i+1]) i++; nxt[1]=i; int k=1;//已知的最大匹配的开始位置 for(int i=2;i<ls;i++) { int len=k+nxt[k];//已知的最大匹配的结束位置 nxt[i]=min(nxt[i-k],...

1.hdu 3400 题意：   在二维平面中有两个线带，有两个段      A   B    AB   AB 和      C   D    CD   CD，     l   x   h   g   w    lxhgw   lxhgw在      A   B    AB   AB 上的速度是      p    p   p，     C   D    CD   CD 上是     q    q   q，他可以以速度      r    r   r 在平面上的其他区域移动。从      A    A   A 到      D    D   D 需要多长时间？ 思路：   如果不考虑速度，两点...

题解 <mark>B.牛牛战队的比赛地</mark>：【三分】    要求最大距离的最小值     →    \rightarrow   → 三分。   三分用于单峰函数求最值，又因为是对浮点数进行三分，可以通过限定三分的次数来达到一定的精度要求。 #include <bits/stdc++.h> using namespace std; const int N=1e5+5; typedef long long ll; ll x[N],y[N]; int n; double check(double xx) { double res=0; for(int i...

定义函数：     f   (   x   ,   y   )   =   (   x   ∣   y   )   −   y    f(x,y)=(x|y)-y   f(x,y)=(x∣y)−y   给出数组      a    a   a，要求求出使得      f   (   f   (   …   f   (   f   (    a   1    ,    a   2    )   ,    a   3    )   ,   …    a    n   −   1     )   ,    a   n    )    f(f(…f(f(a_1,a_2),a_3),…a_{n−1}),...

操作: D：单点修改； Q：查询该点所在的最大连续区间长度； R：把最近一次删除的点还原；   我一开始的思路是：对于最长连续区间长度的查询，用的是set来存储之前被删除的点（目的是让点排好序），用数组模拟一下栈按删除顺序存点，对于当前要查找的点，利用二分查找找到set中第一个大于等于该位置的点，和前一个点作差，直接求出。 #include <bits/stdc++.h> using namespace std; const int N=5e4+5; int a[N]; set<int>st; int n,m,cnt; int main() { int p; set&l...

题目 题解 G.音乐鉴赏【概率】：  还没有做过概率题，感觉都被以前的概率题吓怕了。主要是推公式： 设期末分数占比为：     x    x   x，期末分数为：     y    y   y，平时分数：     s   c   o   r   e    score   score 那么最终的分数为优秀：      s   c   o   r   e   ∗   (   1   −   x   )   +   y   ∗   x   ≥   90    score*(1-x)+y*x\geq 90   score∗(1−x)+y∗x≥90 化简得：      y   ≥     90   − ...