2022年蓝桥杯省赛 C/C++ A组题解

前言： NewOJ最新推出2022蓝桥杯省赛题目，数据均为管理员自行构造，仅供参考。

传送门：http://oj.ecustacm.cn/viewnews.php?id=1021。

注：本次 C + +   A C++ A C++ A组的题目题目质量很好，但是难度过大，线段树考点重复（也可能存在其他做法）。

题意： 一张纸上打印了 20 20 20行 22 22 22列共 440 440 440个二维码，至少需要裁多少次可以全部裁出。如下图， 2 2 2行 3 3 3列共需要裁 9 9 9次。

Tag： 模拟

难度： ☆

思路： 根据题意，首先需要额外裁剪 4 4 4次去除边界。每裁 1 1 1刀，可以使得纸张数目增加 1 1 1。 最终要变成 440 440 440个二维码，只需要裁剪 439 439 439次。总计 439 + 4 = 443 439+4=443 439+4=443次。

题意： 在 2 2 2行 4 4 4列的棋盘中，两人轮流操作，每次可选择在空位上放置 1 1 1个棋子，或者在同一行连续的两个空位上放置棋子。最后使得棋盘放满的人输掉。

先手存在 4 4 4种初始局面如下所示， O O O表示空， X X X表示已放置。每人均以最优策略放棋子。判断先手胜利（输出 V V V）还是后手胜利（输出 L L L）。

XOOO XXOO OXOO OXXO
OOOO OOOO OOOO OOOO

Tag： 博弈

难度： ☆☆☆

思路： 博弈题核心：

只能转移到必胜态的，均为必败态。

可以转移到必败态的，均为必胜态。

1. 首先确定最终的必败态：只剩下1个棋子的时候肯定是必败的。

   OXXX	XOXX
   XXXX	XXXX
   

2. 利用上述提到的核心，倒推出其他情况属于必败态还是必胜态。

3. 注意，给定的 4 4 4个局面为先手第一步的四种局面，对于此时局面为必胜态，表示的是后手胜。

#include
using namespace std;
///判断是否仅存在一个空格
bool check(string s)
{
    int tot = 0;
    for(auto x : s)if(x == 'O')
        tot++;
    return tot == 1;
}
mapSG;
bool dfs(string s)
{
    if(SG.count(s))
        return SG[s];
    if(check(s))
        return SG[s] = false;
    ///模拟放1个棋子
    for(int i = 0; i < s.size(); i++)if(s[i] == 'O')
    {
        string tmp = s;
        tmp[i] = 'X';
        if(dfs(tmp) == false)///可以到达必败态均为必胜态
            return SG[s] = true;
    }
    ///模拟放2个棋子
    for(int i = 0; i < s.size() - 1; i++)if(s[i] == 'O' && s[i + 1] == 'O' && i != 3)
    {
        string tmp = s;
        tmp[i] = tmp[i + 1] = 'X';
        if(dfs(tmp) == false)///可以到达必败态均为必胜态
            return SG[s] = true;
    }
    ///运行到此，说明只能转移到必胜态，此时为必败态
    return SG[s] = false;
}

int main()
{
    string s[] = {"XOOOOOOO", "XXOOOOOO", "OXOOOOOO", "OXXOOOOO"};
    for(int i = 0; i < 4; i++)
    {
        if(dfs(s[i]))cout<<"L";///此时为必胜态，说明后手面临的局面必胜，输出L
        else cout<<"V";
    }
    return 0;
}

题意： 给定数组 a a a，求 ∑ i = 1 n ∑ j = i + 1 n a i a j sum_{i=1}^nsum_{j=i+1}^n a_ia_j ∑i=1n​∑j=i+1n​ai​aj​。

Tag： 前缀和

难度： ☆☆

思路： 可以进行如下转换：
∑ i = 1 n ∑ j = i + 1 n a i a j = ∑ i = 1 n [ a i ∑ j = i + 1 n a j ] sum_{i=1}^nsum_{j=i+1}^n a_ia_j =sum_{i=1}^nleft[a_isum_{j=i+1}^na_jright] i=1∑n​j=i+1∑n​ai​aj​=i=1∑n​[ai​j=i+1∑n​aj​]
对于里面的求和，直接用前缀和优化：
∑ i = 1 n ∑ j = i + 1 n a i a j = ∑ i = 1 n [ a i ∑ j = i + 1 n a j ] = ∑ i = 1 n a i ( s u m [ n ] − s u m [ i ] ) sum_{i=1}^nsum_{j=i+1}^n a_ia_j =sum_{i=1}^nleft[a_isum_{j=i+1}^na_jright] =sum_{i=1}^n a_i(sum[n]-sum[i]) i=1∑n​j=i+1∑n​ai​aj​=i=1∑n​[ai​j=i+1∑n​aj​]=i=1∑n​ai​(sum[n]−sum[i])
预处理前缀和即可，时间复杂度 O ( n ) O(n) O(n)。

#include
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
ll a[maxn], sum[maxn];
int main()
{
    int n;
    ll ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) ///预处理前缀和
        cin >> a[i], sum[i] = sum[i - 1] + a[i];
    for(int i = 1; i <= n; i++) ///求和即可
        ans += a[i] * (sum[n] - sum[i]);
    cout< 
试题D: 选数异或 
题意： 给定数组
    
     
      
       
        a
       
      
      
       a
      
     
    a和整数
    
     
      
       
        x
       
      
      
       x
      
     
    x，
    
     
      
       
        m
       
      
      
       m
      
     
    m次询问，每次询问区间
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]是否存在两个数字使得异或值等于
    
     
      
       
        x
       
      
      
       x
      
     
    x。
 
Tag： 线段树、
    
     
      
       
        S
       
       
        T
       
      
      
       ST
      
     
    ST表
 
难度： ☆☆☆
 
思路： 由于给定
    
     
      
       
        x
       
      
      
       x
      
     
    x，对于区间
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]中的每个数字
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i]而言，只需要判断区间
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]中是否存在
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
       
        ⊕
       
       
        x
       
      
      
       a[i]oplus x
      
     
    a[i]⊕x。
 
暴力判断会超时，如何快速判断区间
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]而不是一个一个
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i]来判断？
 
对每个数字
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i]，找到它左边最近的
    
     
      
       
        a
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       a[j]
      
     
    a[j]，满足
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
       
        ⊕
       
       
        a
       
       
        [
       
       
        j
       
       
        ]
       
       
        =
       
       
        x
       
      
      
       a[i]oplus a[j]=x
      
     
    a[i]⊕a[j]=x，则
    
     
      
       
        <
       
       
        j
       
       
        ,
       
       
        i
       
       
        >
       
      
      
       
      
     
    二元组是一个合法解，其中
    
     
      
       
        j
       
       
        <
       
       
        i
       
      
      
       j 
 
 
为什么一定是左边最近合法位置而不是右边最近？
 
 
二者是一样的，因为i找到的左边最近合法位置是
     
      
       
        
         j
        
       
       
        j
       
      
     j，
     
      
       
        
         j
        
       
       
        j
       
      
     j找到的右边最近是
     
      
       
        
         i
        
       
       
        i
       
      
     i。
 
 
对于每个
    
     
      
       
        i
       
      
      
       i
      
     
    i，都找到左边最近合法的
    
     
      
       
        j
       
      
      
       j
      
     
    j，记为
    
     
      
       
        L
       
       
        e
       
       
        f
       
       
        t
       
       
        [
       
       
        i
       
       
        ]
       
       
        =
       
       
        j
       
      
      
       Left[i]=j
      
     
    Left[i]=j，满足
    
     
      
       
        j
       
       
        <
       
       
        i
       
       
        ,
       
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
       
        ⊕
       
       
        a
       
       
        [
       
       
        j
       
       
        ]
       
       
        =
       
       
        x
       
      
      
       j 
那么对于询问
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]中是否存在两个数字异或值等于
    
     
      
       
        x
       
      
      
       x
      
     
    x，等价于询问
     
      
       
        
         [
        
        
         l
        
        
         ,
        
        
         r
        
        
         ]
        
       
       
        [l,r]
       
      
     [l,r]中是否存在一个
     
      
       
        
         i
        
       
       
        i
       
      
     i满足：
     
      
       
        
         l
        
        
         ≤
        
        
         i
        
        
         ≤
        
        
         r
        
        
         ,
        
        
         l
        
        
         ≤
        
        
         L
        
        
         e
        
        
         f
        
        
         t
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        lle i le r,lle Left[i]
       
      
     l≤i≤r,l≤Left[i]。
 
存在一个
    
     
      
       
        i
       
      
      
       i
      
     
    i即可满足条件，相当于最大的
    
     
      
       
        L
       
       
        e
       
       
        f
       
       
        t
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       Left[i]
      
     
    Left[i]大于
    
     
      
       
        l
       
      
      
       l
      
     
    l即可，即
    
     
      
       
        l
       
       
        ≤
       
       
        M
       
       
        a
       
       
        x
       
       
        {
       
       
        L
       
       
        e
       
       
        f
       
       
        t
       
       
        [
       
       
        i
       
       
        ]
       
       
        ∣
       
       
        l
       
       
        ≤
       
       
        i
       
       
        ≤
       
       
        r
       
       
        }
       
      
      
       l le Max{Left[i]|lle i le r}
      
     
    l≤Max{Left[i]∣l≤i≤r}。
 
问题转换成：求区间最大值问题，使用线段树或者
    
     
      
       
        S
       
       
        T
       
      
      
       ST
      
     
    ST表即可。
 
那如何快速得到
    
     
      
       
        L
       
       
        e
       
       
        f
       
       
        t
       
      
      
       Left
      
     
    Left数组？从左往右遍历时，利用
    
     
      
       
        p
       
       
        o
       
       
        s
       
       
        [
       
       
        x
       
       
        ]
       
      
      
       pos[x]
      
     
    pos[x]记录数字
    
     
      
       
        x
       
      
      
       x
      
     
    x上一次出现的位置，那么
    
     
      
       
        L
       
       
        e
       
       
        f
       
       
        t
       
       
        [
       
       
        i
       
       
        ]
       
       
        =
       
       
        p
       
       
        o
       
       
        s
       
       
        [
       
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
       
        ⊕
       
       
        x
       
       
        ]
       
      
      
       Left[i]=pos[a[i]oplus x]
      
     
    Left[i]=pos[a[i]⊕x]。
 
注：本题也可使用莫队算法维护区间异或等于
    
     
      
       
        x
       
      
      
       x
      
     
    x的次数来求解。
 
#include
using namespace std;
const int maxn = 100000 + 10;
int tree[maxn << 2];
int Left[maxn], pos[(1 << 20) + 10];
int a[maxn], n, m, x;

//线段树模板
void build(int o, int l, int r)
{
    if(l == r)
    {
        tree[o] = Left[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    tree[o] = max(tree[o << 1], tree[o << 1 | 1]);
}
int query(int o, int l, int r, int L, int R)
{
    if(L <= l && r <= R)return tree[o];
    int mid = (l + r) >> 1;
    int ans = 0;
    if(L <= mid)ans = max(ans, query(o << 1, l, mid, L, R));
    if(R > mid)ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R));
    return ans;
}

int main()
{
    scanf("%d%d%d", &n, &m, &x);
    for(int i = 1; i <= n; i++) //预处理Left数组
    {
        scanf("%d", &a[i]);
        Left[i] = pos[a[i] ^ x];
        pos[a[i]] = i;
    }
    build(1, 1, n);//线段树建树
    while(m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        if(query(1, 1, n, l, r) >= l)//查询区间最值
            printf("yesn");
        else
            printf("non");
    }
    return 0;
}
 
试题E: 爬树的甲壳虫 
题意： 甲壳虫想要爬上高度为
    
     
      
       
        n
       
      
      
       n
      
     
    n的树，开始位于树根，高度为0，当它尝试从高度
    
     
      
       
        i
       
       
        −
       
       
        1
       
      
      
       i-1
      
     
    i−1爬到高度为
    
     
      
       
        i
       
      
      
       i
      
     
    i的位置时有
    
     
      
       
        
         P
        
        
         i
        
       
      
      
       P_i
      
     
    Pi​的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。
 
Tag： 期望
    
     
      
       
        D
       
       
        P
       
      
      
       DP
      
     
    DP、逆元
 
难度： ☆☆☆☆
 
思路： 
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       dp[i-1]
      
     
    dp[i−1]表示从高度
    
     
      
       
        i
       
       
        −
       
       
        1
       
      
      
       i-1
      
     
    i−1出发到顶部花费的期望时间。根据题意可以得到如下的状态转移方程：
 
     
      
       
        
         
          
           
            
             d
            
            
             p
            
            
             [
            
            
             i
            
            
             −
            
            
             1
            
            
             ]
            
           
          
         
         
          
           
            
            
             =
            
            
             
              P
             
             
              i
             
            
            
             ∗
            
            
             d
            
            
             p
            
            
             [
            
            
             0
            
            
             ]
            
            
             +
            
            
             (
            
            
             1
            
            
             −
            
            
             
              P
             
             
              i
             
            
            
             )
            
            
             d
            
            
             p
            
            
             [
            
            
             i
            
            
             ]
            
            
             +
            
            
             1
            
           
          
         
        
        
         
          
           
            
             d
            
            
             p
            
            
             [
            
            
             n
            
            
             ]
            
           
          
         
         
          
           
            
            
             =
            
            
             0
            
           
          
         
        
       
       
         begin{aligned} dp[i-1]&=P_i*dp[0]+(1-P_i)dp[i] + 1 \ dp[n]&=0 end{aligned} 
       
      
     dp[i−1]dp[n]​=Pi​∗dp[0]+(1−Pi​)dp[i]+1=0​
 利用递推式展开：
 
     
      
       
        
         
          
           
            
             d
            
            
             p
            
            
             [
            
            
             n
            
            
             ]
            
           
          
         
         
          
           
            
            
             =
            
            
             0
            
            
             ∗
            
            
             d
            
            
             p
            
            
             [
            
            
             0
            
            
             ]
            
            
             +
            
            
             0
            
            
             =
            
            
             a
            
            
             ∗
            
            
             d
            
            
             p
            
            
             [
            
            
             0
            
            
             ]
            
            
             +
            
            
             b
            
           
          
         
        
        
         
          
           
            
             d
            
            
             p
            
            
             [
            
            
             n
            
            
             −
            
            
             1
            
            
             ]
            
           
          
         
         
          
           
            
            
             =
            
            
             
              P
             
             
              n
             
            
            
             ∗
            
            
             d
            
            
             p
            
            
             [
            
            
             0
            
            
             ]
            
            
             +
            
            
             (
            
            
             1
            
            
             −
            
            
             
              P
             
             
              n
             
            
            
             )
            
            
             d
            
            
             p
            
            
             [
            
            
             n
            
            
             ]
            
            
             +
            
            
             1
            
           
          
         
        
        
         
          
           
            
             d
            
            
             p
            
            
             [
            
            
             n
            
            
             −
            
            
             2
            
            
             ]
            
           
          
         
         
          
           
            
            
             =
            
            
             
              P
             
             
              
               n
              
              
               −
              
              
               1
              
             
            
            
             ∗
            
            
             d
            
            
             p
            
            
             [
            
            
             0
            
            
             ]
            
            
             +
            
            
             (
            
            
             1
            
            
             −
            
            
             
              P
             
             
              
               n
              
              
               −
              
              
               1
              
             
            
            
             )
            
            
             d
            
            
             p
            
            
             [
            
            
             n
            
            
             −
            
            
             1
            
            
             ]
            
            
             +
            
            
             1
            
           
          
         
        
        
         
          
           
            
             .
            
            
             .
            
            
             .
            
           
          
         
        
        
         
          
           
            
             d
            
            
             p
            
            
             [
            
            
             0
            
            
             ]
            
           
          
         
         
          
           
            
            
             =
            
            
             
              P
             
             
              1
             
            
            
             d
            
            
             p
            
            
             [
            
            
             0
            
            
             ]
            
            
             +
            
            
             (
            
            
             1
            
            
             −
            
            
             
              P
             
             
              1
             
            
            
             )
            
            
             d
            
            
             p
            
            
             [
            
            
             1
            
            
             ]
            
            
             +
            
            
             1
            
           
          
         
        
       
       
         begin{aligned} dp[n]&=0*dp[0]+0=a*dp[0]+b \ dp[n-1]&=P_n * dp[0] + (1-P_n)dp[n] + 1 \ dp[n-2]&=P_{n-1} * dp[0] + (1-P_{n-1})dp[n-1] + 1 \ ... \ dp[0]&=P_1dp[0]+(1-P_1)dp[1]+1 end{aligned} 
       
      
     dp[n]dp[n−1]dp[n−2]...dp[0]​=0∗dp[0]+0=a∗dp[0]+b=Pn​∗dp[0]+(1−Pn​)dp[n]+1=Pn−1​∗dp[0]+(1−Pn−1​)dp[n−1]+1=P1​dp[0]+(1−P1​)dp[1]+1​
 维护两个变量
    
     
      
       
        a
       
       
        ,
       
       
        b
       
      
      
       a,b
      
     
    a,b，分别表示
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        0
       
       
        ]
       
      
      
       dp[0]
      
     
    dp[0]的系数和常数，初始均为0。
 
将
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        n
       
       
        ]
       
      
      
       dp[n]
      
     
    dp[n]代入
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        n
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       dp[n-1]
      
     
    dp[n−1]中，得到新的
    
     
      
       
        a
       
       
        ,
       
       
        b
       
      
      
       a,b
      
     
    a,b：
 
     
      
       
        
         
          
           
            a
           
          
         
         
          
           
            
            
             =
            
            
             
              P
             
             
              n
             
            
            
             +
            
            
             (
            
            
             1
            
            
             −
            
            
             
              P
             
             
              n
             
            
            
             )
            
            
             ∗
            
            
             a
            
           
          
         
        
        
         
          
           
            b
           
          
         
         
          
           
            
            
             =
            
            
             1
            
            
             +
            
            
             (
            
            
             1
            
            
             −
            
            
             
              P
             
             
              n
             
            
            
             )
            
            
             ∗
            
            
             b
            
           
          
         
        
       
       
         begin{aligned} a&=P_n+(1-P_n)*a \ b&=1+(1-P_n)*b end{aligned} 
       
      
     ab​=Pn​+(1−Pn​)∗a=1+(1−Pn​)∗b​
 最终可以得到：
 
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         0
        
        
         ]
        
        
         =
        
        
         a
        
        
         ∗
        
        
         d
        
        
         p
        
        
         [
        
        
         0
        
        
         ]
        
        
         +
        
        
         b
        
       
       
         dp[0]=a*dp[0]+b 
       
      
     dp[0]=a∗dp[0]+b
 遍历中全部使用模意义下的数字，求解
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        0
       
       
        ]
       
      
      
       dp[0]
      
     
    dp[0]的时候相当于求解：
 
     
      
       
        
         (
        
        
         a
        
        
         −
        
        
         1
        
        
         )
        
        
         d
        
        
         p
        
        
         [
        
        
         0
        
        
         ]
        
        
         +
        
        
         b
        
        
         ≡
        
        
         0
        
        
         %
        
        
         M
        
        
         O
        
        
         D
        
       
       
         (a-1)dp[0]+bequiv0% MOD 
       
      
     (a−1)dp[0]+b≡0%MOD
 利用扩展欧几里得求解
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        0
       
       
        ]
       
      
      
       dp[0]
      
     
    dp[0]即可。
 
注意：存在更优的做法，递推过程更复杂，但是不需要最后的扩展欧几里得。
 
#include
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int MOD = 998244353;
ll x[maxn], y[maxn];
ll ksm(ll a, ll b, ll m)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)ans = ans * a % m;
        b >>= 1;
        a = a * a % m;
    }
    return ans;
}
ll inv(ll x)
{
    return ksm(x, MOD - 2, MOD);
}
ll extgcd(ll a, ll b, ll&x, ll&y)//ax+by = gcd(a, b)的解。返回值为gcd
{
    ll d = a;
    if(b)
    {
       d = extgcd(b, a % b, y, x);
       y -= (a / b) * x;
    }
    else x = 1, y = 0;
    return d;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];
        ll g = __gcd(x[i], y[i]);
        x[i] = x[i] / g;
        y[i] = y[i] / g;
    }
    ll a = 0, b = 0;
    for(int i = n; i >= 1; i--)
    {
        ll p = x[i] * inv(y[i]) % MOD, p_1 = (y[i] - x[i]) * inv(y[i]) % MOD;
        a = (p + p_1 * a) % MOD;
        b = (1 + p_1 * b) % MOD;
    }
    ///cout< 
试题F: 青蛙过河 
题意： 小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降1，当石头的高度下降到0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到0 是允许的）。
 
小青蛙一共需要去学校上
    
     
      
       
        x
       
      
      
       x
      
     
    x天课，所以它需要往返
    
     
      
       
        2
       
       
        x
       
      
      
       2x
      
     
    2x次。当小青蛙具有一个跳跃能力
    
     
      
       
        y
       
      
      
       y
      
     
    y时，它能跳不超过
    
     
      
       
        y
       
      
      
       y
      
     
    y的距离。请问小青蛙的跳跃能力至少是多少才能用这些石头上完
    
     
      
       
        x
       
      
      
       x
      
     
    x次课。
 
Tag： 二分答案、贪心
 
难度： ☆☆☆☆
 
思路： 往返累计
    
     
      
       
        2
       
       
        x
       
      
      
       2x
      
     
    2x次相当于单向走
    
     
      
       
        2
       
       
        x
       
      
      
       2x
      
     
    2x次。跳跃能力越大，越能保证可以通过
    
     
      
       
        2
       
       
        x
       
      
      
       2x
      
     
    2x次。因此可以使用二分答案，找到一个最小的满足条件的跳跃能力。
 
假设跳跃能力为
    
     
      
       
        m
       
       
        i
       
       
        d
       
      
      
       mid
      
     
    mid，一种思想是每次能跳多远跳多远，然后去模拟判断
    
     
      
       
        m
       
       
        i
       
       
        d
       
      
      
       mid
      
     
    mid是否合法，做法比较复杂，暂不展开。
 
另一种想法是判断每个长度为
    
     
      
       
        m
       
       
        i
       
       
        d
       
      
      
       mid
      
     
    mid的区间之和是否大于等于
    
     
      
       
        2
       
       
        x
       
      
      
       2x
      
     
    2x，如果每个区间和都大于
    
     
      
       
        2
       
       
        x
       
      
      
       2x
      
     
    2x，肯定可以保证构造出一组解通过
    
     
      
       
        2
       
       
        x
       
      
      
       2x
      
     
    2x次。反过来是否成立可以自行思考一下。
 
参考：https://www.zhihu.com/question/525176453/answer/2433729894。
 
#include
using namespace std;
const int maxn = 1e5 + 10;
template 
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}
int h[maxn], sum[maxn];
int n, x;
//判断所有长度为mid的区间之和是否大于等于2x
bool check(int mid)
{
    for(int i = 1; i + mid - 1 <= n; i++)
        if(sum[i + mid - 1] - sum[i - 1] < 2 * x)return false;
    return true;
}
int main()
{
    read(n); read(x);
    for(int i = 1; i <= n - 1; i++)//预处理前缀和
        read(h[i]), sum[i] = sum[i - 1] + h[i];
    sum[n] = 1e9 + 7;
    int left = 1, right = n, ans = n;
    while(left <= right)//二分答案
    {
        int mid = (left + right) >> 1;
        if(check(mid))
            ans = mid, right = mid - 1;//求最小合法解
        else
            left = mid + 1;
    }
    cout< 
试题G: 最长不下降子序列 
题意： 给定数组
    
     
      
       
        a
       
      
      
       a
      
     
    a，可以修改连续的
    
     
      
       
        K
       
      
      
       K
      
     
    K个数字变成一个相同值。请计算修改后的最长不下降子序列长度。
 
Tag： 动态规划、线段树
 
难度： ☆☆☆☆☆
 
思路： 最长不下降子序列是经典的动态规划问题。本题只和数字大小有关，与数值无关，因此，先对数组进行离散化。
 
记
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       dp[i]
      
     
    dp[i]表示以
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i]结尾的最长不下降子序列长度，对于修改连续的
    
     
      
       
        K
       
      
      
       K
      
     
    K个数字变成同一值，最好修改成与前面一样的数字，即：
 
修改
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        −
       
       
        k
       
       
        +
       
       
        1
       
       
        ]
       
       
        ,
       
       
        .
       
       
        .
       
       
        .
       
       
        ,
       
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i-k+1],...,a[i]
      
     
    a[i−k+1],...,a[i]均修改成
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        −
       
       
        k
       
       
        ]
       
      
      
       a[i-k]
      
     
    a[i−k]，此时的最长上升子序列可以看成3段：
 

     
      
       
        
         [
        
        
         1
        
        
         ,
        
        
         i
        
        
         −
        
        
         k
        
        
         ]
        
       
       
        [1,i-k]
       
      
     [1,i−k]：长度为
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         −
        
        
         k
        
        
         ]
        
       
       
        dp[i-k]
       
      
     dp[i−k]

     
      
       
        
         [
        
        
         i
        
        
         −
        
        
         k
        
        
         +
        
        
         1
        
        
         ,
        
        
         .
        
        
         .
        
        
         .
        
        
         ,
        
        
         i
        
        
         −
        
        
         1
        
        
         ]
        
       
       
        [i-k+1,...,i-1]
       
      
     [i−k+1,...,i−1]：长度为
     
      
       
        
         k
        
        
         −
        
        
         1
        
       
       
        k-1
       
      
     k−1

     
      
       
        
         [
        
        
         i
        
        
         ,
        
        
         i
        
        
         +
        
        
         1...
        
        
         n
        
        
         ]
        
       
       
        [i,i+1...n]
       
      
     [i,i+1...n]：
     
      
       
        
         a
        
        
         [
        
        
         i
        
        
         ]
        
        
         ,
        
        
         a
        
        
         [
        
        
         i
        
        
         +
        
        
         1
        
        
         ]
        
        
         ,
        
        
         .
        
        
         .
        
        
         .
        
        
         ,
        
        
         a
        
        
         [
        
        
         n
        
        
         ]
        
       
       
        a[i],a[i+1],...,a[n]
       
      
     a[i],a[i+1],...,a[n]中，以
     
      
       
        
         a
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        a[i]
       
      
     a[i]开头的最长上升子序列，注意此时的
     
      
       
        
         a
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        a[i]
       
      
     a[i]的值应该等于
     
      
       
        
         a
        
        
         [
        
        
         i
        
        
         −
        
        
         k
        
        
         ]
        
       
       
        a[i-k]
       
      
     a[i−k]
 
为了求出
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       dp[i]
      
     
    dp[i]，利用权值线段树求出
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        1
       
       
        ]
       
       
        ,
       
       
        .
       
       
        .
       
       
        .
       
       
        ,
       
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       dp[1],...,dp[i-1]
      
     
    dp[1],...,dp[i−1]中最大的数字
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       dp[j]
      
     
    dp[j]，同时保证
    
     
      
       
        a
       
       
        [
       
       
        j
       
       
        ]
       
       
        ≤
       
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[j]le a[i]
      
     
    a[j]≤a[i]。
 
具体做法为：对
    
     
      
       
        a
       
      
      
       a
      
     
    a数组离散化后，从左往右遍历
    
     
      
       
        a
       
      
      
       a
      
     
    a数组，将
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i]看作线段树的第
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i]位，
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       dp[i]
      
     
    dp[i]为线段树维护的值（线段树维护最大值），查询线段树区间
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
       
        ]
       
      
      
       [1,a[i]]
      
     
    [1,a[i]]的最大值即可。
 
类似的，反向遍历，每次查询
    
     
      
       
        [
       
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
       
        ,
       
       
        n
       
       
        ]
       
      
      
       [a[i],n]
      
     
    [a[i],n]的最大值，就可以维护以
    
     
      
       
        x
       
      
      
       x
      
     
    x开头的最长上升子序列，这样，最后暴力枚举每一段
    
     
      
       
        K
       
      
      
       K
      
     
    K即可。
 
#include
using namespace std;
const int maxn = 1e5 + 10;
template 
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}
int a[maxn], b[maxn];
int dp[maxn];
///dp[i]表示以i结尾的最长上升子序列

///权值线段树，维护dp数组
int tree[maxn << 2];
void build(int o, int l, int r)
{
    tree[o] = 0;
    if(l == r)return;
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
}
void update(int o, int l, int r, int x, int val)
{
    if(l == r)
    {
        tree[o] = max(tree[o], val);
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)update(o << 1, l, mid, x, val);
    else update(o << 1 | 1, mid + 1, r, x, val);
    tree[o] = max(tree[o << 1], tree[o << 1 | 1]);
}
int query(int o, int l, int r, int L, int R)
{
    if(L <= l && r <= R)
        return tree[o];
    int mid = (l + r) >> 1;
    int ans = 0;
    if(L <= mid)ans = max(ans, query(o << 1, l, mid, L, R));
    if(R > mid)ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R));
    return ans;
}

int main()
{
    int n, k, tot = 0;
    read(n); read(k);
    for(int i = 1; i <= n; i++)read(a[i]), b[++tot] = a[i];
    if(n == k)
    {
        cout<
        ///dp[i] = max(dp[j]) 满足j=1...i-1 && a[j] <= a[i]
        dp[i] = query(1, 1, tot, 1, a[i]) + 1;
        update(1, 1, tot, a[i], dp[i]);
    }
    ///重新清空
    build(1, 1, tot);
    for(int i = n; i > k; i--)///从后往前遍历a，放入权值线段树中
    {
        ///a[i-k+1] ... a[i]相等 均等于a[i-k]
        ///最后一段要注意：查询的是[a[i-k],tot]中的最大值
        ans = max(ans, dp[i - k] + k - 1 + query(1, 1, tot, a[i - k], tot) + 1);
        int tmp = query(1, 1, tot, a[i], tot) + 1; ///以a[i]开始的最长上升子序列长度
        ans = max(ans, tmp + k);
        ///插入的是a[i]
        update(1, 1, tot, a[i], tmp);
    }
    cout< 
试题H: 扫描游戏 
题意： 有一根围绕原点
    
     
      
       
        O
       
      
      
       O
      
     
    O顺时针旋转的棒
    
     
      
       
        O
       
       
        A
       
      
      
       OA
      
     
    OA，初始时指向正上方（
    
     
      
       
        Y
       
      
      
       Y
      
     
    Y 轴正向）。在平面中有若干物件，第
    
     
      
       
        i
       
      
      
       i
      
     
    i个物件的坐标为
    
     
      
       
        (
       
       
        x
       
       
        i
       
       
        ,
       
       
        y
       
       
        i
       
       
        )
       
      
      
       (xi, yi)
      
     
    (xi,yi) ，价值为
    
     
      
       
        z
       
       
        i
       
      
      
       zi
      
     
    zi。当棒扫到某个物件时，棒的长度会瞬间增长
    
     
      
       
        z
       
       
        i
       
      
      
       zi
      
     
    zi，且物件瞬间消失（棒的顶端恰好碰到物件也视为扫到），如果此时增长完的棒又额外碰到了其他物件，也按上述方式消去（它和上述那个点视为同时消失）。
 
如果将物件按照消失的时间排序，则每个物件有一个排名，同时消失的物件排名相同，请输出每个物件的排名，如果物件永远不会消失则输出
    
     
      
       
        −
       
       
        1
       
      
      
       -1
      
     
    −1。
 
Tag： 计算几何、线段树
 
难度： ☆☆☆☆☆
 
思路： 首先进行极角排序，按照顺时针排序。具体可以利用象限+叉积来排序。
 
初始时棒长度为
    
     
      
       
        L
       
      
      
       L
      
     
    L，每次需要找到顺时针第一个小于等于
    
     
      
       
        L
       
      
      
       L
      
     
    L的点即可。
 
可以利用线段树维护每个点到原点的距离
    
     
      
       
        
         x
        
        
         i
        
        
         2
        
       
       
        +
       
       
        
         y
        
        
         i
        
        
         2
        
       
      
      
       x_i^2+y_i^2
      
     
    xi2​+yi2​，要找的是下一个小于等于
    
     
      
       
        
         L
        
        
         2
        
       
      
      
       L^2
      
     
    L2的点，因此维护最小值。
 
假设之前位置为
    
     
      
       
        l
       
       
        a
       
       
        s
       
       
        t
       
      
      
       last
      
     
    last（初始为0），每次利用线段树查找区间
    
     
      
       
        [
       
       
        l
       
       
        a
       
       
        s
       
       
        t
       
       
        +
       
       
        1
       
       
        ,
       
       
        n
       
       
        ]
       
      
      
       [last+1,n]
      
     
    [last+1,n]中从左往右第一个小于等于
    
     
      
       
        
         L
        
        
         2
        
       
      
      
       L^2
      
     
    L2的数字，如果没有找到则查找区间
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        l
       
       
        a
       
       
        s
       
       
        t
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       [1,last-1]
      
     
    [1,last−1]中从左往右第一个小于等于
    
     
      
       
        
         L
        
        
         2
        
       
      
      
       L^2
      
     
    L2的数字（顺时针一圈）。
 
如果没找到则终止。
 
如果找到了，下标记为
    
     
      
       
        i
       
       
        d
       
       
        x
       
      
      
       idx
      
     
    idx。棒长
    
     
      
       
        L
       
      
      
       L
      
     
    L增加
    
     
      
       
        
         z
        
        
         
          i
         
         
          d
         
         
          x
         
        
       
      
      
       z_{idx}
      
     
    zidx​，记录一下当前第
    
     
      
       
        i
       
       
        d
       
       
        x
       
      
      
       idx
      
     
    idx个点的答案。注意特判一下，如果当前点和先前点夹角为0，则排名是一样的。
 
代码中由于
    
     
      
       
        L
       
      
      
       L
      
     
    L不断增加，
    
     
      
       
        
         L
        
        
         2
        
       
      
      
       L^2
      
     
    L2会超过
    
     
      
       
        l
       
       
        o
       
       
        n
       
       
        g
       
       
         
       
       
        l
       
       
        o
       
       
        n
       
       
        g
       
      
      
       long long
      
     
    long long，可以在代码中维护距离而不是距离的平方，也可以使用
    
     
      
       
        _
       
       
        _
       
       
        i
       
       
        n
       
       
        t
       
       
        128
       
      
      
       __int128
      
     
    __int128来维护变量
    
     
      
       
        
         L
        
        
         2
        
       
      
      
       L^2
      
     
    L2。
 
#include
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;
const int maxn = 2e5 + 10;
template 
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x = x * w;
}
struct point
{
    ll x, y, z;
    int id;
}a[maxn];
ll n;
__int128 L;

int Quadrant(point a)
{
    if(a.x >= 0 && a.y > 0)return 1;///y的正半轴放到第一象限
    if(a.x > 0 && a.y <= 0)return 2;///x的正半轴放到第二象限
    if(a.x <= 0 && a.y < 0)return 3;
    return 4;
}
ll cross(point a, point b)
{
    return a.x * b.y - a.y * b.x;
}
bool cmp(point a, point b)
{
    if(Quadrant(a) == Quadrant(b))
    {
        if(cross(a, b) == 0)
            return a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;
        else
           return cross(a, b) < 0;
    }
    else
        return Quadrant(a) < Quadrant(b);
}

__int128 mi[maxn << 2];
void push_up(int o)
{
    mi[o] = min(mi[o << 1], mi[o << 1 | 1]);
}
void build(int o, int l, int r)
{
    if(l == r)
    {
        mi[o] = a[l].x * a[l].x + a[l].y * a[l].y;
        return ;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    push_up(o);
}

void update(int o, int l, int r, int x, __int128 val)
{
    if(l == r)
    {
        mi[o] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)update(o << 1, l, mid, x, val);
    else update(o << 1 | 1, mid + 1, r, x, val);
    push_up(o);
}

///找右边第一个小于等于z^2的数字
ll idx;
bool query(int o, int l, int r, int L, int R, __int128 z)
{
    if(L > R)return false;
    if(l == r)
    {
        idx = l;
        return mi[o] <= z;
    }
    int mid = (l + r) >> 1;
    if(L <= mid)
    {
        if((mi[o << 1] <= z) && query(o << 1, l, mid, L, R, z))
            return true;
    }
    if(R > mid)
    {
        if((mi[o << 1 | 1] <= z) && query(o << 1 | 1, mid + 1, r, L, R, z))
            return true;
    }
    return false;
}
int ans[maxn];

int main()
{
    read(n);read(L);
    for(int i = 1; i <= n; i++)
    {
        read(a[i].x);read(a[i].y);read(a[i].z);
        a[i].id = i;
        ans[i] = -1;
    }
    sort(a + 1, a + 1 + n, cmp);
    build(1, 1, n);
    int cnt = 0;
    int lastcnt = 0;
    int last = 0;  ///上一个位置
    while(true)
    {
        bool ok = query(1, 1, n, last + 1, n, L * L);
        if(ok)L = L + a[idx].z;
        else
        {
            ok = query(1, 1, n, 1, last - 1, L * L);
            if(ok)L = L + a[idx].z;
            else break;
        }
        update(1, 1, n, idx, 1e32);
        if(last)
        {
            if(Quadrant(a[last]) == Quadrant(a[idx]) && cross(a[last], a[idx]) == 0)
                ans[a[idx].id] = lastcnt, ++cnt;
            else
                ans[a[idx].id] = ++cnt, lastcnt = cnt;
        }
        else
            ans[a[idx].id] = ++cnt, lastcnt = cnt;
        last = idx;
    }
    for(int i = 1; i <= n; i++)
    {
        cout< 
试题I: 数的拆分 
题意： 判断数字
    
     
      
       
        a
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         18
        
       
      
      
       a le 10^{18}
      
     
    a≤1018能否表示成
    
     
      
       
        
         x
        
        
         1
        
        
         
          y
         
         
          1
         
        
       
       
        
         x
        
        
         2
        
        
         
          y
         
         
          2
         
        
       
      
      
       x_1^{y_1}x_2^{y_2}
      
     
    x1y1​​x2y2​​的形式，其中
    
     
      
       
        
         x
        
        
         1
        
       
       
        ,
       
       
        
         x
        
        
         2
        
       
      
      
       x_1,x_2
      
     
    x1​,x2​为正整数，
    
     
      
       
        
         y
        
        
         1
        
       
       
        ,
       
       
        
         y
        
        
         2
        
       
      
      
       y_1,y_2
      
     
    y1​,y2​为大于等于
    
     
      
       
        2
       
      
      
       2
      
     
    2的正整数。
    
     
      
       
        T
       
       
        ≤
       
       
        100000
       
      
      
       T le 100000
      
     
    T≤100000次询问。
 
Tag： 数论
 
难度： ☆☆☆☆☆
 
思路： 首先考虑将
    
     
      
       
        a
       
      
      
       a
      
     
    a进行素因子分解
    
     
      
       
        
         p
        
        
         1
        
        
         
          q
         
         
          1
         
        
       
       
        
         p
        
        
         2
        
        
         
          q
         
         
          2
         
        
       
       
        ⋅
       
       
        .
       
       
        .
       
       
        .
       
       
        ⋅
       
       
        
         p
        
        
         k
        
        
         
          q
         
         
          k
         
        
       
      
      
       p_1^{q_1}p_2^{q_2}cdot ...cdot p_k^{q_k}
      
     
    p1q1​​p2q2​​⋅...⋅pkqk​​，首先要满足
    
     
      
       
        
         q
        
        
         i
        
       
       
        ≥
       
       
        2
       
      
      
       q_ige 2
      
     
    qi​≥2。
 

    
     
      
       
        ∀
       
       
        
         q
        
        
         i
        
       
       
        ≥
       
       
        2
       
      
      
       forall q_i ge 2
      
     
    ∀qi​≥2，要拆分成
    
     
      
       
        
         k
        
        
         1
        
       
       
        ∗
       
       
        
         y
        
        
         1
        
       
       
        +
       
       
        
         k
        
        
         2
        
       
       
        ∗
       
       
        
         y
        
        
         2
        
       
       
        =
       
       
        
         q
        
        
         i
        
       
      
      
       k_1*y_1+k_2*y_2=q_i
      
     
    k1​∗y1​+k2​∗y2​=qi​，
    
     
      
       
        
         k
        
        
         1
        
       
       
        ,
       
       
        
         k
        
        
         2
        
       
       
        ≥
       
       
        0
       
       
        ,
       
       
        
         y
        
        
         1
        
       
       
        ,
       
       
        
         y
        
        
         2
        
       
       
        ≥
       
       
        2
       
      
      
       k_1,k_2 ge 0,y_1,y_2ge 2
      
     
    k1​,k2​≥0,y1​,y2​≥2。
 

    
     
      
       
        
         y
        
        
         1
        
       
       
        =
       
       
        2
       
       
        ,
       
       
        
         y
        
        
         2
        
       
       
        =
       
       
        3
       
      
      
       y_1=2,y_2=3
      
     
    y1​=2,y2​=3可以保证所有的
    
     
      
       
        
         q
        
        
         i
        
       
       
        ≥
       
       
        2
       
      
      
       q_i ge 2
      
     
    qi​≥2均有非负整数解。
 
 
 

     
      
       
        
         2
        
        
         
          k
         
         
          1
         
        
        
         +
        
        
         3
        
        
         
          k
         
         
          2
         
        
        
         =
        
        
         k
        
       
       
        2k_1+3k_2=k
       
      
     2k1​+3k2​=k对于
     
      
       
        
         ∀
        
        
         k
        
        
         >
        
        
         1
        
       
       
        forall k > 1
       
      
     ∀k>1均有非负整数解：
 
 
1、
     
      
       
        
         k
        
        
         %
        
        
         3
        
        
         =
        
        
         =
        
        
         0
        
       
       
        k%3==0
       
      
     k%3==0：
     
      
       
        
         
          k
         
         
          1
         
        
        
         =
        
        
         0
        
        
         ,
        
        
         
          k
         
         
          2
         
        
        
         =
        
        
         
          k
         
         
          3
         
        
       
       
        k_1=0,k_2=frac{k}{3}
       
      
     k1​=0,k2​=3k​
 
 
2、
     
      
       
        
         k
        
        
         %
        
        
         3
        
        
         =
        
        
         =
        
        
         1
        
       
       
        k%3==1
       
      
     k%3==1：
     
      
       
        
         
          k
         
         
          1
         
        
        
         =
        
        
         2
        
        
         ,
        
        
         
          k
         
         
          2
         
        
        
         =
        
        
         
          
           k
          
          
           −
          
          
           4
          
         
         
          3
         
        
       
       
        k_1=2,k_2=frac{k-4}{3}
       
      
     k1​=2,k2​=3k−4​
 
 
3、
     
      
       
        
         k
        
        
         %
        
        
         3
        
        
         =
        
        
         =
        
        
         2
        
       
       
        k%3==2
       
      
     k%3==2：
     
      
       
        
         
          k
         
         
          1
         
        
        
         =
        
        
         1
        
        
         ,
        
        
         
          k
         
         
          2
         
        
        
         =
        
        
         
          
           k
          
          
           −
          
          
           2
          
         
         
          3
         
        
       
       
        k_1=1,k_2=frac{k-2}{3}
       
      
     k1​=1,k2​=3k−2​
 
 
所以问题变成数字
    
     
      
       
        a
       
      
      
       a
      
     
    a能否变成
    
     
      
       
        
         x
        
        
         1
        
        
         2
        
       
       
        
         x
        
        
         2
        
        
         3
        
       
      
      
       x_1^2x_2^3
      
     
    x12​x23​。
 
对于
    
     
      
       
        a
       
       
        =
       
       
        
         p
        
        
         1
        
        
         
          q
         
         
          1
         
        
       
       
        
         p
        
        
         2
        
        
         
          q
         
         
          2
         
        
       
       
        ⋅
       
       
        .
       
       
        .
       
       
        .
       
       
        ⋅
       
       
        
         p
        
        
         k
        
        
         
          q
         
         
          k
         
        
       
      
      
       a=p_1^{q_1}p_2^{q_2}cdot ...cdot p_k^{q_k}
      
     
    a=p1q1​​p2q2​​⋅...⋅pkqk​​，只需要检测每个
    
     
      
       
        
         q
        
        
         i
        
       
      
      
       q_i
      
     
    qi​是否大于等于
    
     
      
       
        2
       
      
      
       2
      
     
    2即可，只要大于等于
    
     
      
       
        2
       
      
      
       2
      
     
    2就可以按照对应的
    
     
      
       
        
         k
        
        
         1
        
       
       
        ,
       
       
        
         k
        
        
         2
        
       
      
      
       k_1,k_2
      
     
    k1​,k2​分配到
    
     
      
       
        
         x
        
        
         1
        
       
       
        ,
       
       
        
         x
        
        
         2
        
       
      
      
       x_1,x_2
      
     
    x1​,x2​里面。
 
由于
    
     
      
       
        a
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         18
        
       
      
      
       ale 10^{18}
      
     
    a≤1018，所以
    
     
      
       
        
         x
        
        
         1
        
        
         2
        
       
       
        
         x
        
        
         2
        
        
         3
        
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         18
        
       
      
      
       x_1^2x_2^3le 10^{18}
      
     
    x12​x23​≤1018。如果素因子
    
     
      
       
        p
       
       
        >
       
       
        4000
       
      
      
       p>4000
      
     
    p>4000，则
    
     
      
       
        
         p
        
        
         5
        
       
       
        ≥
       
       
        1
       
       
        
         0
        
        
         18
        
       
      
      
       p^5ge 10^{18}
      
     
    p5≥1018。所以只需要暴力判断
    
     
      
       
        4000
       
      
      
       4000
      
     
    4000以内的素因子，对于大于
    
     
      
       
        4000
       
      
      
       4000
      
     
    4000的
    
     
      
       
        p
       
      
      
       p
      
     
    p，指数只可能是
    
     
      
       
        2
       
       
        ,
       
       
        3
       
       
        ,
       
       
        4
       
      
      
       2,3,4
      
     
    2,3,4，即判断一下是否为平方数或者立方数即可。
 
时间复杂度
    
     
      
       
        O
       
       
        (
       
       
        T
       
       
        ∗
       
       
        550
       
       
        )
       
      
      
       O(T*550)
      
     
    O(T∗550)，
    
     
      
       
        550
       
      
      
       550
      
     
    550为
    
     
      
       
        4000
       
      
      
       4000
      
     
    4000以内素数数量。
 
#include
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
template 
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}

bool not_prime[4010];
int prime[4010], tot;
void init(int n)
{
    for(int i = 2; i <= n; i++)if(!not_prime[i])
    {
        prime[++tot] = i;
        for(int j = i + i; j <= n; j += i)
            not_prime[j] = 1;
    }
}
inline bool check(ll x)
{
    ///检查平方数
    ll y = pow(x, 0.5);
    if(y * y == x || (y + 1) * (y + 1) == x)
        return true;
    ///检查立方数
    y = pow(x, 1.0 / 3);
    if(y * y * y == x || (y + 1) * (y + 1) * (y + 1) == x || (y + 2) * (y + 2) * (y + 2) == x)
        return true;
    return false;
}
int main()
{
    init(4000);
    int T;
    read(T);
    while(T--)
    {
        ll x;
        read(x);
        if(check(x))
        {
            puts("yes");
            continue;
        }
        bool flag = true;
        for(int i = 1; i <= tot; i++)if(x % prime[i] == 0){
            int now = 0;
            while(x % prime[i] == 0)
            {
                now++;
                x /= prime[i] ;
            }
            ///cout<
                flag = false;
                break;
            }
        }
        if(flag & check(x))
        {
            puts("yes");
            continue;
        }
        else
        {
            puts("no");
        }
    }
    return 0;
}
 
试题J: 推导部分和 
题意： 对于数列
    
     
      
       
        a
       
      
      
       a
      
     
    a，已知部分区间和，询问若干次区间和。
 
Tag： 并查集、搜索
 
难度： ☆☆☆☆
 
思路： 对于已知的区间
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]的和为
    
     
      
       
        s
       
      
      
       s
      
     
    s，用前缀和
    
     
      
       
        s
       
       
        u
       
       
        m
       
       
        [
       
       
        r
       
       
        ]
       
       
        −
       
       
        s
       
       
        u
       
       
        m
       
       
        [
       
       
        l
       
       
        −
       
       
        1
       
       
        ]
       
       
        =
       
       
        s
       
      
      
       sum[r]-sum[l-1]=s
      
     
    sum[r]−sum[l−1]=s表示，根据差分约束建图准则，相当于点
    
     
      
       
        l
       
       
        −
       
       
        1
       
      
      
       l-1
      
     
    l−1到点
    
     
      
       
        r
       
      
      
       r
      
     
    r长度为
    
     
      
       
        s
       
      
      
       s
      
     
    s，
    
     
      
       
        r
       
      
      
       r
      
     
    r到
    
     
      
       
        l
       
       
        −
       
       
        1
       
      
      
       l-1
      
     
    l−1长度为
    
     
      
       
        −
       
       
        s
       
      
      
       -s
      
     
    −s。
 
建好图之后，每次询问一个区间
    
     
      
       
        [
       
       
        q
       
       
        l
       
       
        ,
       
       
        q
       
       
        r
       
       
        ]
       
      
      
       [ql,qr]
      
     
    [ql,qr]的和，相当于询问
    
     
      
       
        s
       
       
        u
       
       
        m
       
       
        [
       
       
        q
       
       
        r
       
       
        ]
       
       
        −
       
       
        s
       
       
        u
       
       
        m
       
       
        [
       
       
        q
       
       
        l
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       sum[qr]-sum[ql-1]
      
     
    sum[qr]−sum[ql−1]的值。
 
首先要保证
    
     
      
       
        q
       
       
        l
       
       
        −
       
       
        1
       
      
      
       ql-1
      
     
    ql−1和
    
     
      
       
        q
       
       
        r
       
      
      
       qr
      
     
    qr在同一个连通块中，其次每个连通块只需要随便一个点初始化为
    
     
      
       
        0
       
      
      
       0
      
     
    0，然后按照边长扩展即可。这是由于等号，不管怎么走，相对差值是不变的。
 
代码中
    
     
      
       
        d
       
       
        f
       
       
        s
       
      
      
       dfs
      
     
    dfs和
    
     
      
       
        b
       
       
        f
       
       
        s
       
      
      
       bfs
      
     
    bfs均可以。
 
#include
using namespace std;
typedef long long ll;
template 
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x = x * w;
}
const int maxn = 1e5 + 10;
const ll INF = -1e13;
int n, m, q;
struct edge
{
    int v; ll w;
    edge(){}
    edge(int v, ll w):v(v), w(w){}
};
vectorMap[maxn];
ll sum[maxn];
bool vis[maxn];
void dfs(int u, ll d)
{
    vis[u] = 1;
    sum[u] = d;
    ///cout<
        int v = x.v; ll w = x.w;
        if(vis[v])continue;
        dfs(v, d + w);
    }
}
queue >Q;
void bfs(int u, ll d)
{
    vis[u] = 1;
    sum[u] = d;
    Q.push(make_pair(u, d));
    while(!Q.empty())
    {
        auto now = Q.front();
        Q.pop();
        int u = now.first; ll d = now.second;
        for(auto x : Map[u])
        {
            int v = x.v; ll w = x.w;
            if(vis[v])continue;
            vis[v] = 1;
            sum[v] = d + w;
            Q.push(make_pair(v, d + w));
        }
    }
}
int f[maxn];
int Find(int x)
{
    return x == f[x] ? x : f[x] = Find(f[x]);
}
int main()
{
    read(n);read(m);read(q);
    for(int i = 0; i <= n; i++)f[i] = i;
    for(int i = 1; i <= m; i++)
    {
        int l, r; ll s;
        read(l);read(r);read(s);
        ///cout<
        int l, r;
        read(l), read(r);
        --l;
        if(Find(l) != Find(r))puts("UNKNOWN");
        else printf("%lldn", sum[r] - sum[l]);
    }
    return 0;
}