数学　

等差数列，公差是０的时候特判

#include 
     
      typedef long long ll;const int N = 1e5 + 5;int main() {    int a, b, c;    scanf ("%d%d%d", &a, &b, &c);    bool flag = true;    if (c == 0) {        if (a == b) {            flag = true;        } else {            flag = false;        }    } else {        int d = (b - a) / c;        if (d >= 0 && (b - a) % c == 0) {            flag = true;        } else {            flag = false;        }    }    if (flag) {        puts ("YES");    } else {        puts ("NO");    }    return 0;}
     

数学　

题意：３＊３的矩阵，已经填了ａ，ｂ，ｃ，ｄ四个数字，问填完数后四个２＊２的子矩阵的和相等的方案数，所有数字范围在[1, n].

分析：蛮有意思的题目，很明显中心的数字是公有的，？从上到下从左到右设为x1,x2,x3,x4x5，那么满足x1+a+b=x4+b+d -> x4 = x1 + (a  - d)，x2=x1+(b-c), x5=x1+(a+b-c-d)，因为x2, x4, x5范围在[1, n]，能得到一个x1的最小可行区间，然后＊x３的可行区间（ｎ）．当然Ｏ（ｎ）枚举也可以．

#include 
     
      typedef long long ll;const int N = 1e5 + 5;int main() {    int n, a, b, c, d;    scanf ("%d%d%d%d%d", &n, &a, &b, &c, &d);    int d1 = a - d, d2 = b - c, d3 = a + b - c - d;    int l = 1, r = n;    l = std::max (l, 1 - d1);    r = std::min (r, n - d1);    l = std::max (l, 1 - d2);    r = std::min (r, n - d2);    l = std::max (l, 1 - d3);    r = std::min (r, n - d3);    if (l <= r) {        long long ans = 1ll * (r - l + 1) * n;        std::cout << ans << '\n';    } else {        puts ("0");    }    return 0;}
     

数学　

题意：ｎ个数字有正有负，总和０，相邻数字可以分配，问最小操作数使得所有数字变成０．

分析：如果一段长度为Ｌ数字总和为０，最多Ｌ－１次可以使得每个数字为０．将ｎ个数字分成ｍ段都是０的，那么答案是ｎ－ｍ，所以求cnt[k]最大，表示ｍ最大（最后一组为－ｋ＋ｋ）．

#include 
     
      int main() {	std::ios::sync_with_stdio (false);	std::cin.tie (0);	std::map
      
        mp;	int n;	std::cin >> n;	long long sum = 0;	int mx = 0;	for (int i=0; i
       
        > x;		sum += x;		mp[sum]++;		mx = std::max (mx, mp[sum]);	}	std::cout << n - mx << '\n';	return 0;}
       
      
     

set　

题意：按照BST建一棵树二叉树，问当前插入的点的父节点．

分析：set模拟平衡树，lower_bound查找位置．

#include 
     
      const int N = 1e5 + 5;std::set
      
        st;std::map
       
         left, right;int main() {    int n, x;    scanf ("%d", &n);    scanf ("%d", &x);    st.insert (x);    int ans;    for (int i=0; i
       
      
     

DP 

题意：第i个车站能到[i+1, a[i]]的位置，p(i, j)表示从ｉ到ｊ最少搭几次车．求

分析：定义dp[i]表示的最小搭车数，从[i+1, n]中a[m]最大的dp[m]转移来，．．．

#include 
     
      const int N = 1e5 + 5;int a[N];long long dp[N];std::pair
      
        mx[N][20];int n;void init_ST() {    for (int i=0; i
       
        =0; --i) {        int p = query_max (i + 1, a[i]);        dp[i] = dp[p] - (a[i] - p) + n - i - 1;        ans += dp[i];    }    printf ("%I64d\n", ans);    return 0;}