• .Title|raw

    HDU 6209 The Intersection 分数二分


    题目大意求一个分数x,使得其分母不超过100000并且f(x)与g(x)在x处最接近。 题解首先很明确这是个二分的题目,不过分数怎么二分……。 首先我们二分出x3>k2的最小的整数x,然后这样进行分数二分: 首先设左端点分子为lz = x-1,分母为lm = 1,右端点分子为rz = x,分母为rm = 1. 二分的时候,我们取分子midz = lz + rz,分母midm = lm + rm。 判断是否小于当前差值最小值,如果是记录此时答案。 然后判断当前分数的三次方是否比k2大,如果是,区间右端点左移,否则区间左端点右移。 当分母midm > 100000的时候终止二分,输出答

  • .Title|raw

    The Preliminary Contest for ICPC Asia Xuzhou 2019 G.Colorful String PAM(回文自动机) + 可持久化线段树


    题目大意给出一个字符串,求出所有回文串的字符种类数之和。 题解考场上他们都有回文自动机的板子而我没有QAQ 首先对于一个子串,其对应一个子区间,这个子区间的数据的种类数的多少我们是可以用主席树来维护的,这是众所周知的。 具体维护方法: 从第1位置往后扫,如果之前出现过相同的数据,我们就在之前出现过的位置-1,在当前位置计数+1,然后把当前位置记录下来。 但是我们怎么求所有回文串的长度和数目?Manacher是不行的,效率太低了。 于是有一个神奇的PAM,也就是回文自动机。 回文自动机中,cnt[i]表示以i结尾的最长的回文串的数目,len[i]表示以i结尾的回文串的长度为多少,pos[i]表示

  • .Title|raw

    The 2019 Asia Nanchang First Round Online Programming Contest A.Enju With math problem 思维题 欧拉筛


    题目大意给出100个数,求问是否存在某个连续的100个φ值,使得两者一一相等。 1≤ai≤1.5*108 题解首先其实能想到的是KMP,但是无奈这个ai太大了,用欧拉筛没办法筛出来,而且时间也不够,因为还有多组数据。 但是能够预处理一些φ还是好的,这样能降低所有数据都需要暴力算φ带来的复杂度。 然后我们猜想,是不是这100个数里面一定会有一个数对应的φ恢复到φ-1的时候是素数,也即两个相邻素数一定相隔100以内?答案是否定的,这个可以通过打表来检查出来。 但是我们可以找到另一个问题,这100个数的φ-1中,要么就是有至少一个素数,要么就是有一个数为一个≤13的素数和一个大素数的乘积。 这样我们

  • .Title|raw

    The Preliminary Contest for ICPC Asia Xuzhou 2019 I.query 树状数组 二维偏序


    题目大意给定一个1---n的排列和m次询问,每次询问区间 [l,r]之间min(pi,pj) = gcd(pi,pj)的数对的个数。 题解一开始看到是数对问题还以为是莫队,不过话说回来莫队WA了而不是T是怎么回事…… 首先我们需要注意min(pi,pj) = gcd(pi,pj)可以转化为pi和pj互为因数和倍数的关系(这样可以做一点常数上面的优化,也更好判断总体的数对的个数)。 然后我们要知道,所有的数对个数大概是O(nlogn)级别的。 于是我们可以枚举每个数的倍数预处理出所有的数对的位置对(i,j),我们尽量让i比j大,这有利于下面的思路。 然后有没有发现这个位置对很像是二维平面上的坐标

  • .Title|raw

    2018 ACM/ICPC Asia Jiaozuo Regional K.Counting Failures on a Trie Trie 思维题 倍增 Hash


    题目大意给出一棵trie树和一个字符串,然后对于每一次询问l,r,在Trie树上对子串[l,r]进行匹配。如果在某个字符处失配,则重新跳回Trie树根节点并忽略这个字符继续匹配。 求问对于每一个询问,在匹配过程中会失配几次,且最终会到达哪个节点。 题解暴力搜索必然是n^2的,对于此题1e5还有多组数据的情况想都不要想。 而每一次失配我们都会重新回到起点。 于是我们可以用预处理从每个位置的下一个位置开始的子串第一次的失配位置是在原字符串中的哪个位置。由于在这个位置我们会失配回到起点然后再次从这个位置的下一个位置开始,所以应该可以想到这个失配过程是完全可以去倍增的!。我们可以用倍增来处理失配次数,

icontofig | 发布于 2019-09-12 00:20:26 | 阅读量 331 | 二分
发布于 2019-09-12 00:20:26 | 二分

题目大意

求一个分数x,使得其分母不超过100000并且f(x)与g(x)在x处最接近。

题解

首先很明确这是个二分的题目,不过分数怎么二分……。

首先我们二分出x3>k2的最小的整数x,然后这样进行分数二分:

首先设左端点分子为lz = x-1,分母为lm = 1,右端点分子为rz = x,分母为rm = 1.

二分的时候,我们取分子midz = lz + rz,分母midm = lm + rm。

判断是否小于当前差值最小值,如果是记录此时答案。

然后判断当前分数的三次方是否比k2大,如果是,区间右端点左移,否则区间左端点右移。

当分母midm > 100000的时候终止二分,输出答案即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double u,v;
ll lz,rz,lm,rm;
ll val,k;
int t;
ll mz,mm;
const long double INF = 1e19;
long double _abs(long double x){
    return (x < 0) ? -x : x;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--){
        cin >> k;
        val = 0;
        ll l = 1,r = 1e5;
        while(l <= r){
            ll mid = (l + r) >> 1;
            if(mid * mid * mid  >= k * k){
                val = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        if(val * val * val == k * k){
            cout << val << "/1" << "\n";
            continue;
        }
        lm = rm
继续阅读
icontofig | 发布于 2019-09-11 08:47:43 | 阅读量 328 | 字符串 可持久化线段树
发布于 2019-09-11 08:47:43 | 字符串 可持久化线段树

题目大意

给出一个字符串,求出所有回文串的字符种类数之和。

题解

考场上他们都有回文自动机的板子而我没有QAQ

首先对于一个子串,其对应一个子区间,这个子区间的数据的种类数的多少我们是可以用主席树来维护的,这是众所周知的。

具体维护方法:

从第1位置往后扫,如果之前出现过相同的数据,我们就在之前出现过的位置-1,在当前位置计数+1,然后把当前位置记录下来。

但是我们怎么求所有回文串的长度和数目?Manacher是不行的,效率太低了。

于是有一个神奇的PAM,也就是回文自动机。

回文自动机中,cnt[i]表示以i结尾的最长的回文串的数目,len[i]表示以i结尾的回文串的长度为多少,pos[i]表示以i为结尾的回文串在原串的位置是哪里。

这样的PAM的时间复杂度是O(n*log(字符集大小))的

这样我们就很容易能够求得答案了。

最终答案是ans = n + Σ query(root[pos[i]],1,siz,pos[i]-len[i]+1,pos[i]) * cnt[i];

据说还有后缀自动机SAM的做法,这个我也不怎么会……所以就不写了,等以后学QAQ。

如果对回文自动机不了解的可以去找博客https://www.cnblogs.com/nbwzyzngyl/p/8260921.html

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
typedef long long ll;
struct seg{
    int ch[2];
    int val;
}tr[maxn*25];
int root[maxn];
char s[maxn];
int siz = 0;
struct PAM{
    int p,last,cur,n,S[maxn],len[maxn],pos[maxn],cnt[maxn],fail[maxn];
    int nt[maxn][26];
    int new_node(int l){
        for(int i = 0;i < 26;++i)
            nt[p][i] = 0;
        len[p] = l;
        cnt[p] = 0;
        return p++;
    }
    inline v
继续阅读
icontofig | 发布于 2019-09-11 08:23:30 | 阅读量 340 | 思维题 筛法
发布于 2019-09-11 08:23:30 | 思维题 筛法

题目大意

给出100个数,求问是否存在某个连续的100个φ值,使得两者一一相等。

1≤ai≤1.5*108

题解

首先其实能想到的是KMP,但是无奈这个ai太大了,用欧拉筛没办法筛出来,而且时间也不够,因为还有多组数据。

但是能够预处理一些φ还是好的,这样能降低所有数据都需要暴力算φ带来的复杂度。

然后我们猜想,是不是这100个数里面一定会有一个数对应的φ恢复到φ-1的时候是素数,也即两个相邻素数一定相隔100以内?
答案是否定的,这个可以通过打表来检查出来。

但是我们可以找到另一个问题,这100个数的φ-1中,要么就是有至少一个素数,要么就是有一个数为一个≤13的素数和一个大素数的乘积。

这样我们可以直接分开讨论,把所有可能的情况计入一个vector里面,最多出现1000种可能(实际上到不了),然后直接对于每一种可能暴力检索100个数是否符合要求即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7+5;
int phi[maxn];
int pr[maxn],np[maxn];
int cnt = 0;
void euler(){
    phi[1] = 1;
    for(int i = 2;i < maxn;++i){
        if(!np[i]){
            pr[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1;j <= cnt && i * pr[j] < maxn;++j){
            np[i*pr[j]] = 1;
            if(i % pr[j] == 0){
                phi[i*pr[j]] = phi[i] * pr[j];
                break;
            }
            else phi[i*pr[j]] = phi[i] * (pr[j] - 1);
        }
    }
    return;
}
int mx = 0,mi = 1e9;
int a[105];
int n;
int t;
int calc(int x){//暴力求解φ(x
继续阅读
icontofig | 发布于 2019-09-08 00:15:37 | 阅读量 281 | 树状数组 偏序
发布于 2019-09-08 00:15:37 | 树状数组 偏序

题目大意

给定一个1---n的排列和m次询问,每次询问区间 [l,r]之间min(pi,pj) = gcd(pi,pj)的数对的个数。

题解

一开始看到是数对问题还以为是莫队,不过话说回来莫队WA了而不是T是怎么回事……

首先我们需要注意min(pi,pj) = gcd(pi,pj)可以转化为pi和pj互为因数和倍数的关系(这样可以做一点常数上面的优化,也更好判断总体的数对的个数)。

然后我们要知道,所有的数对个数大概是O(nlogn)级别的。

于是我们可以枚举每个数的倍数预处理出所有的数对的位置对(i,j),我们尽量让i比j大,这有利于下面的思路。

然后有没有发现这个位置对很像是二维平面上的坐标啊……

欸,貌似询问也可以转化成二维坐标(r,l)啊……。

那如果我们都像上面把所有数对和询问都转化成二维坐标的话……那么就成了下面的经典二维偏序问题:

平面上有若干个点,求问横坐标小于等于r,纵坐标大于等于l的点的个数有多少。

于是我们对坐标按照横坐标排序,询问按照先r后l从小到大排序,然后横向扫一遍所有横坐标上的点,用树状数组维护当前扫过的所有点的个数。每一次询问的答案都是query(n) - query(l-1)。

非常经典的二维偏序问题,时间复杂度是O(nlogn),我还给想成了莫队,真的惭愧,果然还是练的太少……

代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int maxn = 1e5+5;
struct quest{
    int l,r,id;
    bool operator < (const quest &b)const{
        return (this->r == b.r) ? (this->l < b.l) : (this->r < b.r);
    }
}q[maxn];
int cnt = 0;
int a[maxn];
int c[maxn];
int ans[maxn];
int lowbit(int x){
    return x & -x;
}
struct point{
    int x,y;
    bool operator < (const point &b) const{
        return (this->x == b.x) ? (this->y
继续阅读
icontofig | 发布于 2019-09-06 22:19:42 | 阅读量 271 | Trie 思维题 hash
发布于 2019-09-06 22:19:42 | Trie 思维题 hash

题目大意

给出一棵trie树和一个字符串,然后对于每一次询问l,r,在Trie树上对子串[l,r]进行匹配。如果在某个字符处失配,则重新跳回Trie树根节点并忽略这个字符继续匹配。

求问对于每一个询问,在匹配过程中会失配几次,且最终会到达哪个节点。

题解

暴力搜索必然是n^2的,对于此题1e5还有多组数据的情况想都不要想。

而每一次失配我们都会重新回到起点。

于是我们可以用预处理从每个位置的下一个位置开始的子串第一次的失配位置是在原字符串中的哪个位置。由于在这个位置我们会失配回到起点然后再次从这个位置的下一个位置开始,所以应该可以想到这个失配过程是完全可以去倍增的!。我们可以用倍增来处理失配次数,然后最终位置可以直接通过一个map存储hash值对应的trie树位置进行查询。

然后考虑如何预处理。

首先我们应该能够想到,如果一个子串能够在trie树中成功匹配,那么它的前缀串也一定能够在trie树中成功匹配。

于是这个性质导致我们可以二分失配的长度,然后我们只需要查询当前二分产生的子串是否能在trie树中进行匹配就可以了。

hash想不被卡的话,感觉就是选一个奇怪点的质数作为base。取模倒是不至于,直接unsigned long long自然溢出就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef unsigned long long ll;
const ll base = 983;
ll h[maxn],bs[maxn];
struct trie{
    int id;
    int ch[26];
}tr[maxn];
int f[maxn][26];
string s;
int x;char c;
int len;
map<ll,int>mp;
int n,m,q,t;
int ql,qr;
void init(){
    bs[0] = 1;
    for(int i = 1;i < maxn;++i){
        bs[i] = bs[i-1] * base;
    }
    return;
}
ll get_hash(int l,int r){
    return h[r] - h[l] * bs[r - l];
}
void dfs(int
继续阅读
icontofig | 发布于 2019-09-04 15:41:58 | 阅读量 289 | LCA 树上差分
发布于 2019-09-04 15:41:58 | LCA 树上差分

题目大意

给定n个点的树,其中有m条路径被标记,求问有多少种方案能够使得取k条被标记的路径并且所取的k条路径至少有一个共同点。

题解

 首先此题标记的是m条路径,也就是说,路径上所有点都是被标记的。

如果我们仅考虑对于一个点,选出k条路径都有这一个共同点的话,很容易想到方案书是C(vis,k),其中vis表示这个点被多少条路径标记。

那么我们的问题就成了如何去求每个点的vis值。

对于每一个路径,我们肯定不能通过暴力扫一遍去统计vis值,这样肯定是TLE的。

于是我们就有一个经典的思路:树上差分。

我们找路径起点u和终点v的lca,假设为pos,我们稍微思考一下,就可以知道,我们应该在u的位置+1,v的位置+1,然后在pos的位置-1,pos的父节点位置-1(保证pos也被访问一次而其上的节点不被访问)。

之后我们只需要在从根节点dfs一次,然后向上回溯的过程中更新所有的点的vis值就可以了。

但是还没完,如果我们把所有节点的方案都加在一起,势必会有重复的方案。

我们考虑重复的方案会是什么样的。

如果两个点相邻,那么他们重复的方案数即为C(vise,k),其中vise为两点之间的边。

所以我们只需要再减去所有共同边上的方案数就可以了。

vise的值的统计和前面vis的统计差不多,也是利用树上差分的思想,不过我们要用点的位置表示其父亲到其的边,然后对每条路径,在u的位置+1,v的位置+1,lca的位置-2。要注意和上面点的位置的统计的区别。

时间复杂度为O((n+m)logn + 2*n)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 3e5+5;
int t;
ll fac[maxn];
int f[maxn][25];
int n,m;
void pre_lca(){
    for(int j = 1;j < 23;++j){
        for(int i = 1;i <= n;++i){
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
    return;
}
int dep[maxn];
int lca(int x,int y){
    if(d
继续阅读
icontofig | 发布于 2019-09-02 23:23:58 | 阅读量 479 | 思维题 扫描线 树状数组
发布于 2019-09-02 23:23:58 | 思维题 扫描线 树状数组

题目大意

每个点的数值是通过一个从中心最大值开始的蛇形矩阵确定的。其中有m个点上的权值可用,对于q个询问,输出左下角为(x1,y1),右上角为(x2,y2)的矩阵区域内所有可用点的权值经过处理后的和。

处理的方法是,将原权值所有数位上的数相加。

题解

此题估计是模仿NOIP2014普及组T3的蛇形矩阵出的规律题目。

首先n为奇数,n*n为奇数,地图大小为 一定为奇数,所以

x = x − n/2 − 1
y = y  - n /2 - 1;
t = max(abs(x),abs(y)); //确定该点在第几圈螺旋
 if(x >= y)ans = n ∗ n −4∗ t ∗ t −2∗ t − x − y;//在向右与向上的路线上

else ans = n ∗ n −4∗ t ∗ t +2∗ t + x + y;//在向左与向下的路线上

(下面这部分代码是队友写的,我不是很清楚他的思路)

这样我们就可以O(m)的预处理所有的可用点的权值了。

对于每一次询问,都是一个矩形区域。

我们考虑二维前缀和,其答案相当于ans(x2,y2) - ans(x2,y1-1) - ans(x1-1,y2) + ans(x-1,y-1),其中ans(x,y)代表1——x,1——y矩形区域中所有值的和。

但是二维显然会爆空间,所以我们考虑如何降维。

我们可以将一个询问拆解成4个,用flag为1或-1标记此次询问的前缀和是要加还是减。

之后我们可以运用扫描线的方法,先按照x排序,然后对y进行映射,用树状数组维护映射后y上的值。用一条竖直的扫描线不断向右扫,遇到一个询问点就查询一次。

但是这样我们使用扫描线是要将所有的点当作修改操作的,而不能提前加入树状数组,否则答案会出问题。

所以我们将所有的m个点和4*q个询问加入操作合集,查询flag为-1或1,修改flag为2,按照先x、次先y、再次先修改的顺序排序,用一条平行于y轴的线从左向右扫过整个横坐标区间,用树状数组维护当前投影到y轴上的值。每当遇到修改操作,直接update树状数组中的值进行维护,遇到查询操作直接从树状数组中查询。

理论时间复杂度为O((m+4*q)log(m+4*q));

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cal(int x, int y, int n
继续阅读
icontofig | 发布于 2019-08-29 22:27:27 | 阅读量 405 | 博弈论 记忆化搜索
发布于 2019-08-29 22:27:27 | 博弈论 记忆化搜索

Description

In a world where ordinary people cannot reach, a boy named "Koutarou" and a girl named "Sena" are playing a video game. The game system of this video game is quite unique: in the process of playing this game, you need to constantly face the choice, each time you choose the game will provide 1−3 options, the player can only choose one of them. Each option has an effect on a "score" parameter in the game. Some options will increase the score, some options will reduce the score, and some options will change the score to a value multiplied by −1 .

That is, if there are three options in a selection, the score will be increased by 1, decreased by 1, or multiplied by −1. The score before the selection is 888. Then selecting option 1 will make the score become 9, and selecting option 2 will make the score 7 and select option 3 to make the score −8. Note that the score has an upper limit of 100 and a lower limit of −100. If the score is 99 at this time, an option that makes the score

继续阅读
icontofig | 发布于 2019-08-29 22:08:21 | 阅读量 410 | 线段树
发布于 2019-08-29 22:08:21 | 线段树

题目大意

给定一个序列,有两个操作:

1.询问l---r之间所有数按题目中格式公式的计算求和。

2.更改序列某个位置的值。

题解

其实这题还是蛮简单的……我零基础的队友30s就像出来了(比我快了一些)

这题直接维护区间和是不行的,我们看到询问的操作中的公式跟数的位置和询问区间长度都有关系。

那么我们现在要想的就是如何让区间和与数的位置变成无关的式子。

注意到对于位置 i,有n - i + 1 - n - r,即为我们要求的区间中 位置 i的数字对应的位置系数。

所以我们可以用线段树维护两个值,一个表示 a[i]*(n-i+1)的和,另一个表示a[i]的和。

询问的时候用前一个值对应的区间询问减去后一个值对应的区间询问的(n-r)倍就是我们需要询问的东西了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
struct tree{
	ll sum1,sum2;
	int l,r;
}tr[maxn<<2];
ll a[maxn];
int n,q;
void push_up(int now){
	tr[now].sum1 = tr[now<<1].sum1 + tr[now<<1|1].sum1;
	tr[now].sum2 = tr[now<<1].sum2 + tr[now<<1|1].sum2;
	return;
}
void build(int now,int l,int r){
	tr[now].l = l;
	tr[now].r = r;
	tr[now].sum1 = tr[now].sum2 = 0;
	if(l == r){
		tr[now].sum1 = a[l];
		tr[now].sum2 = a[l] * (n - l + 1);
		return;
	}
	int mid = (l + r) >> 1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	push_up(now);
	return;
}
void update(int now,int pos){
	if(tr[now].l == tr[now].r){
		tr[now].sum1 = a[pos];
		t
继续阅读
icontofig | 发布于 2019-08-27 20:06:53 | 阅读量 470 | 思维题
发布于 2019-08-27 20:06:53 | 思维题

题目大意

n个人围成一圈,从1号开始报数,报到k的人出圈,然后再从下一个人开始新一轮报数。问经过第m个出圈的人最开始的编号是多少。

题解

经典约瑟夫问题,想必大家都知道递推式吧……

f(n,m) = (f(n-1,m-1) + k) % n

好了就是这样,至于具体证明貌似说刘汝佳的白书上有?

但是我们注意到此题数据范围真的是太大了,我们不能使用O(m)的做法了……

不,并不是不能用,只是当m小于等于k的时候我们可以这么做(这时候m的范围只有2x106),但是如果是k小于等于m的时候我们就要另作讨论了。

首先如果k = 1,那我们直接输出m就好,因为题目保证n ≥ m;

但是如果k > 1……

我们注意到,如果k比较小,远小于n-m的话,我们可能进行d轮都轮不完一圈,所以我们考虑可以用乘法跳项的思想来加速递推式的推进。

最终的复杂度不是很清楚是多少,但是由于使用了乘法来加速,所以我们中间实际上跳过了很多不必要取模的项,整体复杂度就比较低了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k;
int t;
ll d,now,a;
ll ans = 0;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    int cas = 0;
    while(t--){
        cas++;
        ans = 0;
        cin >> n >> m >> k;
        ll ans = (k - 1) % (n - m + 1) + 1;
        if(k == 1){
            ans = m;
        }
        else if(k >= m){
            for(ll i = 2;i <= m;++i)
                ans = (ans + k - 1) % (n - m + i) + 1;
        }
        else{
            now = 1,a = n - m;
            while(now < m){
           
继续阅读