2022-07-18 至 2022-07-25 记录

题目大意：给定n*m方阵，每个格点上有1或-1。每次只能向右移动一步或者向下移动一步。问是否存在从起始点(1,1)到(n,m)一条和为0的路径。
思路：
关键在于充分利用方阵上的-1,1，增量时仅会造成很小变化，可能在变化的途中达到目标值。（先找到某个范围）

从起点到终点走的格点数是固定的，都是n+m-1。因此n+m-1为奇数时，不可能达成目标。而n+m-1为偶数时，由于奇+奇=偶，奇-奇=偶，因此到达(n,m)点的所有路径和都为偶数。
使用dp容易求得路径和的最大值和最小值(必要条件)。如果[最小值，最大值]包含0，则最终答案包含0。这是因为可以移动每次上下水平向右移动的步骤使得路径和变为最大值。使用方阵上的-1，1的条件，每次移动改变路径和-2或2。于是一定某次移动后路径和变为0
反思：这种思想以前是遇到过的，见那个很妙的滑动窗口均值的题(juju and binary string 2800)。
另一种思路：运用bitset dp记录和。

#include 
using namespace std;
vector vis;


int main()
{
    int t; cin>>t;
    for(int i  =0 ;i
        int n,m;
        scanf("%d %d",&n,&m);
        int d[n][m];
        for(int  k = 0;kprintf("NOn");continue;}
        int dpmin[n][m],dpmax[n][m];
        dpmin[0][0]=dpmax[0][0]=d[0][0];
        for(int i = 0;i
            for(int j = 0;j
                if(i==0&&j==0) continue;
                int a = INT_MIN;  //用于更新最大值
                int b = INT_MAX;  //用于更新最小值
                if(i-1>=0) {a = max(a,dpmax[i-1][j]); b = min(b,dpmin[i-1][j]);}
                if(j-1>=0) {a = max(a,dpmax[i][j-1]);    b = min(b,dpmin[i][j-1]);}
                dpmax[i][j] = a + d[i][j];
                dpmin[i][j] = b + d[i][j];
            }
        }
        if(dpmin[n-1][m-1]<=0 && dpmax[n-1][m-1]>=0) printf("YESn"); else printf("NOn");
    }
    system("pause");
}

题目大意：
给定数组a，判断是否存在一个连续子数组，使得其最大值大于等于其和。
思路：
和leetcode某次周赛类似(threhold那道题)，以每个点作为最大值划分解空间。设当前点下标为i,左边连续最后一个小于等于a[i]的数下标为x，右边连续最后一个小于等于a[i]的数的下标为y（采用单调栈 O ( n ) O(n) O(n)做出）。
然后判断 a [ u : i ] , 其中 x ≤ u ≤ i − 1 a[u:i],其中x leq u leq i - 1 a[u:i],其中x≤u≤i−1和 a [ i : o ] , 其中 i + 1 ≤ o ≤ y a[i:o],其中i+1 leq o leq y a[i:o],其中i+1≤o≤y这一系列子数组和是否至少有一个大于 a i a_i ai​即可，这可以使用前缀和，后缀和+线段树在 O ( n log ⁡ n ) O(n log n) O(nlogn)内实现。

#include 
using namespace std;
typedef long long ll;
ll pretree[9500001];
ll suftree[9500001];


void build(int s, int t, int p,ll d[]) {
  // 对 [s,t] 区间建立线段树,当前根的编号为 p
  if (s == t) {
    d[p] = -1e18;
    return;
  }
  int m = s + ((t - s) >> 1);
  // 移位运算符的优先级小于加减法，所以加上括号
  // 如果写成 (s + t) >> 1 可能会超出 int 范围
  build(s, m, p * 2,d), build(m + 1, t, p * 2 + 1,d);
  // 递归对左右区间建树
  d[p] = -1e18;
}


ll query(int l, int r, int s, int t, int p,ll d[]) {
  // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
 // if(r < l) return LONG_LONG_MIN + 1e18;
  if (l <= s && t <= r)
    return d[p];  // 当前区间为询问区间的子集时直接返回当前区间的和
  int m = s + ((t - s) >> 1);
  ll ans = LONG_LONG_MIN;
  if (l <= m) ans = max(ans,query(l, r, s, m, p * 2,d));
  // 如果左儿子代表的区间 [l, m] 与询问区间有交集, 则递归查询左儿子
  if (r > m) ans = max(ans,query(l, r, m + 1, t, p * 2 + 1,d));
  // 如果右儿子代表的区间 [m + 1, r] 与询问区间有交集, 则递归查询右儿子
  return ans;
}

// C++ Version
void update(int index,ll c, int s, int t, int p, ll d[]) {
  if (s == t && s== index) {
    d[p] = max(d[p],(ll)c);
    return;
  } 
  int m = s + ((t - s) >> 1);
  if(index <= m) update(index,c,s,m,2*p,d);
  else update(index,c,m+1,t,2*p+1,d);
  d[p] = max(d[p*2],d[p*2+1]);
}



int main()
{
    int t;
    scanf("%d",&t);
    for(int i = 0;i
        int n; scanf("%d",&n);
        int a[n];
        for(int  k = 0;k=0;k--) suf[k] = suf[k+1]+a[k];
        //找左侧第一个大于自身元素的index 
        int l[n];
        //找右侧第一个大于自身元素的index
        int r[n];
        stack s;    //当前元素的Index
        l[0] = -1;  
        s.push(0);
        for(int k = 1;k
            while(!s.empty() && a[s.top()] <= a[k]) 
                s.pop();
            if(!s.empty()) {l[k]=s.top();} else l[k]=-1;
            s.push(k);
        }
        while(!s.empty()) s.pop();
        r[n-1] = n; s.push(n-1);
        for(int k =  n-2;k>=0;k--)
        {

            while(!s.empty() && a[s.top()] <= a[k]) 
                s.pop();
            if(!s.empty()) {r[k]=s.top();} else r[k] = n;
            s.push(k);
        }
        // for(int k  = 0;k
            update(k+1,suf[k],1,n,1,suftree);
            update(k+1,pre[k],1,n,1,pretree);
        }
        bool f = true;
        for(int k = 0;k< n;k++)
        {
            int l_ = l[k] + 1,r_  = r[k] - 1;
            ll tmp = LONG_LONG_MIN;
            if(r_ >= k + 1) tmp = max(tmp,query(k+2,r_+1,1,n,1,pretree));
            ll pre_; if(k-1>=0) pre_= pre[k-1]; else pre_ = 0;
            if(tmp != LONG_LONG_MIN && tmp - pre_ > a[k]) {f = false;break;}
            tmp = LONG_LONG_MIN;
            if(k-1>=l_) tmp = max(tmp,query(l_+1,k,1,n,1,suftree));
            ll suf_; if(k+1 a[k]) {f =  false;break;}
        }
        if(!f) printf("NOn"); else printf("YESn");
    }
    system("pause");
    return 0;
}

题目大意：给定含n个整数(n为偶数)的数组a,给定一个整数k。将a中元素两个分为一组(记作 a i , a j a_i,a_j ai​,aj​),求使得 ⌊ a i + a j k ⌋ lfloor frac{a_i+a_j}{k} rfloor ⌊kai​+aj​​⌋总和最大的分组方案对应的总和。
思路：
⌊ a i + a j k ⌋ = a i + a j − ( a i + a j ) % k k lfloor frac{a_i+a_j}{k} rfloor = frac{a_i + a_j - (a_i + a_j)%k}{k} ⌊kai​+aj​​⌋=kai​+aj​−(ai​+aj​)%k​且等式右侧分子是k的倍数。于是总和为：
∑ i , j a i + a j − ( a i + a j ) % k k = ∑ i a i − ∑ i , j ( a i + a j ) % k k Δ sum_{i,j} frac{a_i + a_j - (a_i + a_j)%k}{k} = frac{sum_i a_i - sum_{i,j}(a_i + a_j)% k}{k} quad Delta i,j∑​kai​+aj​−(ai​+aj​)%k​=k∑i​ai​−∑i,j​(ai​+aj​)%k​Δ
而 ( a i + a j ) % k = ( a i % k + a j % k ) % k (a_i + a_j) % k = (a_i % k + a_j % k) % k (ai​+aj​)%k=(ai​%k+aj​%k)%k。而 a i % k ∈ [ 0 , k − 1 ] a_i % k in [0,k-1] ai​%k∈[0,k−1]同理对 a j a_j aj​.于是当 a i % k + a j % k ≥ k a_i % k + a_j % k geq k ai​%k+aj​%k≥k时， ( a i + a j ) % k = ( a i % k + a j % k ) % k = a i % k + a j % k − k (a_i + a_j) % k = (a_i % k + a_j % k) % k = a_i % k + a_j % k - k (ai​+aj​)%k=(ai​%k+aj​%k)%k=ai​%k+aj​%k−k,否则 ( a i + a j ) % k = ( a i % k + a j % k ) % k = a i % k + a j % k (a_i + a_j) % k = (a_i % k + a_j % k) % k = a_i % k + a_j % k (ai​+aj​)%k=(ai​%k+aj​%k)%k=ai​%k+aj​%k。由 Δ Delta Δ式的形式可知要使得 a i % k + a j % k ≥ k a_i %k + a_j %k geq k ai​%k+aj​%k≥k的配对数尽可能多。设数组b满足 b i = a i % k b_i = a_i % k bi​=ai​%k，将b排序。采用双指针贪心。l最初指向b第一个,r最初指向b的最后一个。l不断增加到第一个使得 b [ l ] + b [ r ] ≥ k b[l]+b[r] geq k b[l]+b[r]≥k的为止，计数器加1。然后l++,r–,递归进行下一轮匹配。由于最初r指向最大值,因此首轮迭代l不停止的地方的元素一定不能和其余任何元素构成和大于等于k的对。容易证明一定存在最优解存在第一轮迭代得出的对。并且最优子结构显然成立。

#include 
using namespace std;
typedef long long ll;

int main()
{
    int t;
    scanf("%d",&t);
    for(int i = 0;i
        int n; scanf("%d",&n);
        int k; scanf("%d",&k);
        int a[n];
        int b[n];
        ll sum = 0,sum_ = 0;
        for(int q = 0;qscanf("%d",&a[q]); sum += (ll)a[q]; b[q] = a[q]%k;sum_ += b[q];}
        sort(b,b+n);
        int l   =   0,r  = n - 1,u = 0;
        while(l < r)
        {
            while(l