P3406 海底高铁

差分（标记第i段经过几次）+前缀和（求出每段经过的次数）+贪心策略（选价格便宜的）

#include 
using namespace std;int n, m, p1, p2, cf[100005], a, b, c; 
long long sum, ans;
int main()
{cin >> n >> m;if(m > 0)cin >> p1;for(int i = 2; i <= m; i++){//标记 cin >> p2;if(p1 < p2) cf[p1]++, cf[p2]--;else cf[p2]++, cf[p1]--;p1 = p2; }for(int i = 1; i < n; i++){sum += cf[i];//求第i段经过的次数 cin >> a >> b >> c;if(sum) ans += min(sum * a, sum * b + c);}cout << ans << endl;return 0;
}

P2004 领地选择

"最大子矩阵和"：二维前缀和

#include 
using namespace std;int n, m, c, mp[1005][1005], qz[1005][1005];
int sum[1005][1005], fx, fy;
int main()
{cin >> n >> m >> c;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> mp[i][j];qz[i][j] = qz[i][j - 1] + mp[i][j];//第i行前缀和 sum[i][j] = sum[i - 1][j] + qz[i][j];//子矩阵和 } } int maxn = -1e9, num;for(int x = 1; x <= n-c+1; x++){for(int y = 1; y <= m-c+1; y++){num = sum[x+c-1][y+c-1] + sum[x-1][y-1] - sum[x-1][y+c-1] - sum[x+c-1][y-1];if(num > maxn) fx = x, fy = y, maxn = num;} }cout << fx << " " << fy << endl; return 0;
}

P2671 [NOIP2015 普及组] 求和

∵y−x=z−y

∴x+z=2y

又，2y 是偶数，所以 x, z 同奇偶。

由于不同颜色的 x,z 肯定不会产生分数，所以我们可以先把这个「狭长的纸带」按照颜色分类，最后把每种颜色产生的分数加起来即可。

然后不同奇偶性的 x,z 也不会产生分数，所以把每个颜色种类按照奇偶性再分个类，最后把奇数产生的分数和偶数产生的分数加起来即可。

设一个分组里有k个数，这个分组中的数分别是x[1],x[2]……x[k]，下标分别是y[1],y[2]……y[k]

ans = (x[1] + x[2]) * (y[1] + y[2]) + (x[1] + x[3]) * (y[1] + y[3]) + ... + (x[1] + x[k]) * (y[1] + y[k])

+(x[2] + x[3]) * (y[2] + y[3]) + (x[2] + x[4]) * (y[2] + y[4]) + ... + (x[2] + x[k]) * (y[2] + y[k])

+...

+(x[k - 1] + x[k]) * (y[k - 1] + y[k])

化简得：

ans = x[1] * (y[1]+y[2]+y[1]+y[3]+……+y[1]+y[k]) // (2~k) k - 1 个y[1]

+ x[2] * (y[1]+y[2]+y[2]+y[3]+……+y[2]+y[k]) // k - 1 个y[2]

+……

+ x[k] * (y[1]+y[k]+y[2]+y[k]+……+y[k-1]+y[k]) // k - 1 个y[k]

最终得：

ans = x[1] * (y[1] * (k - 2) + y[1] + y[2] +……+ y[k])

+ x[2] * (y[2] * (k - 2) + y[1] + y[2] +……+ y[k])

+……

+ x[k] * (y[k] * (k - 2) + y[1] + y[2] +……+ y[k])

前缀和：y[1] + y[2] +……+ y[k]

#include 
using namespace std;int n, m, color[100005],number[100005], mod = 10007;
long long s[100005][2], sum[100005][2], ans;
int main()
{cin >> n >> m;for(int i = 1; i <= n; i++) cin >> number[i];for(int i = 1; i <= n; i++){cin >> color[i];s[color[i]][i % 2]++ ;//按颜色和奇偶数分组,每组s[][](k)个值sum[color[i]][i % 2] = (sum[color[i]][i % 2] + number[i]) % mod; //前缀和}for(int i = 1; i <= n; i++)ans = (ans + i * ((s[color[i]][i % 2] - 2) * number[i] % mod + sum[color[i]][i % 2])) % mod;cout << ans << endl;return 0;
}