[NOIP模拟赛] 2021.11.16
T1
对所有长度大于等于3的子区间计算长高成山峰的花费和，一个区间长高成山峰的花费等于每个数字增大的花费和。
DDG的牛逼单调栈，危黑灵永远游荡在我们周围！
枚举的是山峰，算贡献只算到这个山峰的。
极短代码
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 1000005;
const int MOD = 1e9+7;
int n,ans;
int a[MAXN];
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int s[MAXN],tl;
int main()
{
// freopen("mountain.in","r",stdin);
// freopen("mountain.out","w",stdout);
n = Read();
for(int i = 1;i <= n;++ i) a[i] = Read();
for(int i = 1;i <= n;++ i)
{
while(tl && a[i] >= a[s[tl]])
{
if(tl > 1) ans = (ans + (n-i+1ll) * (Min(a[i],a[s[tl-1]])-a[s[tl]]) % MOD * (i-s[tl-1]-1) % MOD * s[tl-1] % MOD) % MOD;
--tl;
}
s[++tl] = i;
}
Put(ans,'\n');
return 0;
}
//426406027
T2
赛时切了，是个比较简单的背包。
赛时代码
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 55;
const int MAXA = 505;
const int B = 51*500;
const int C = 500;
int n,m,ans;
int a[MAXN][MAXN];
int dp[2][B<<1|5],r[MAXN][MAXA<<1],c[MAXN][MAXA<<1];
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int main()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
n = Read(); m = Read();
for(int i = 0;i < n;++ i)
for(int j = 0;j < m;++ j)
a[i][j] = Read();
for(int i = 0;i < n;++ i)
for(int j = 0;j < m;++ j)
{
int to = (i-1+n)%n;
++r[i][a[i][j]-a[to][j]+C];
}
for(int i = 0;i < n;++ i)
for(int j = 0;j < m;++ j)
{
int to = (j-1+m)%m;
++c[j][a[i][j]-a[i][to]+C];
}
int L = B,R = B;
for(int i = 1;i < n;++ i)
{
bool now = i&1,to=now^1;
memset(dp[now],0,sizeof(dp[now]));
int M = 0;
for(int j = L;j <= R;++ j) M = Max(M,dp[to][j]);
for(int j = L;j <= R;++ j)
{
for(int kk = 0,k;kk < m;++ kk)
{
k = a[i][kk] - a[i-1][kk];
dp[now][j+k] = Max(dp[now][j+k],dp[to][j]+r[i][k+C]);
}
}
L -= 500; R += 500;
for(int j = L;j <= R;++ j) dp[now][j] = Max(dp[now][j],M);
}
int val = 0;
for(int i = L;i <= R;++ i) val = Max(val,dp[(n-1)&1][i]+((C-(i-B) >= 0 && C-(i-B) <= 1000) ? r[0][C-(i-B)] : 0));
ans += val;
//---
L = B,R = B;
memset(dp[0],0,sizeof(dp[0]));
for(int i = 1;i < m;++ i)
{
bool now = i&1,to=now^1;
memset(dp[now],0,sizeof(dp[now]));
int M = 0;
for(int j = L;j <= R;++ j) M = Max(M,dp[to][j]);
for(int j = L;j <= R;++ j)
{
for(int kk = 0,k;kk < n;++ kk)
{
k = a[kk][i] - a[kk][i-1];
dp[now][j+k] = Max(dp[now][j+k],dp[to][j]+c[i][k+C]);
}
}
L -= 500; R += 500;
for(int j = L;j <= R;++ j) dp[now][j] = Max(dp[now][j],M);
}
val = 0;
for(int i = L;i <= R;++ i) val = Max(val,dp[(m-1)&1][i]+((C-(i-B) >= 0 && C-(i-B) <= 1000) ? c[0][C-(i-B)] : 0));
ans += val;
Put(ans,'\n');
return 0;
}
/*
可以考虑 ri-1 和 ri 满足什么关系可以获得贡献
地球是个环，所以还是有关的，但是可以dp
这负数真的恶心至极
*/
T3
\，/不要正方形构造题。
考虑翻转调整字典序必定变小，所以直接费用流。
只需从左上到右下定义费用逐渐增大即可，因为费用流优先增广费用小的。
还可以暴力调整，但是复杂度劣一些。
T4
给定一些字符必须转换，可以多次进行，求最大保留字符种类。
差两点。
一点是没相当转化成匹配问题，一点是题面出锅打一半就觉得完全不可做。
其实就是字符去填空，缩点之后变成很多强连通分量。
一些是需要转化的，一些是可以内部消耗边的(有空的)。
需要转化的连向可以转到的点(可以也是需要转化的点)，最大匹配就是可以保留的最多的字符种类。
注意一些本来就没有的字符不要算到贡献里面。