（之前的就暂时不补了就从以后的开始记）
8.12
CF1606C Banknotes
题目分析：
显然第 \(i\) 种货币可以用来组成 \(a_{i+1} - a_{i}\) 位，为了使得 \(k\) 最小，显然从低到高位依次填补是最优的。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100;
int a[MAXN],ans[MAXN],pre[MAXN];
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
for(int i=1; i<=10; i++) pre[i] = pre[i-1] * 10 + 9;
int t;
scanf("%lld",&t);
while(t--){
int n,k;
int tot = 0;
scanf("%lld%lld",&n,&k);k++;
for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
for(int i=1; i<n; i++){
if(pre[a[i+1] - a[i]] <= k) k -= pre[a[i+1]-a[i]],ans[++tot] = pre[a[i+1]-a[i]];
else if(k) ans[++tot] = k,k=0;
}
if(k) ans[++tot] = k;
for(int i=tot; i>=1; i--)
printf("%lld",ans[i]);
printf("\n");
}
return 0;
}
总结：
做了一道大水题，水题数+1
*CF1606D Red-Blue Matrix
题目分析：
我们考虑如果只有一列的情况，那么我们将这一列的元素从大到小排序之后，显然我们的红色行是下面连续的一段。
那么我们就考虑将我们的矩阵按第一列排序，显然因为第一列的限制，我们的红色行也只能是下面连续的一段，然后就直接枚举选哪一段，以及左右矩阵的分割点是哪个就好了。
可以预处理出来矩阵的各个部分的最大值与最小值就可以实现 \(O(1)\) 的复杂度判断是否合法。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
vector<int> a[MAXN];
vector<int> p1[MAXN],p2[MAXN],p3[MAXN],p4[MAXN];
int n,m;
int p[MAXN];
char ans[MAXN];
bool flag[MAXN];
bool cmp(int l,int r){
return a[l][1] < a[r][1];
}
void work(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n+1;i++){
p1[i].clear();p2[i].clear();p3[i].clear();p4[i].clear();a[i].clear();
p1[i].resize(m+5,0);p2[i].resize(m+5,(int)1e6);p3[i].resize(m+5,(int)1e6);p4[i].resize(m+5,0);a[i].resize(m+5,0);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
for(int i=0; i<=n+1; i++) p[i] = i,flag[i] = false;
sort(p+1,p+1+n,cmp);
for(int i=1;i<=n;i++) //左上角到左下角的最大值
for(int j=1;j<=m;j++){
p1[p[i]][j]=a[p[i]][j];
p1[p[i]][j]=max(p1[p[i]][j],p1[p[i-1]][j]);
p1[p[i]][j]=max(p1[p[i]][j],p1[p[i]][j-1]);
}
for(int i=1;i<=n;i++) //左下角到右上角的左小指
for(int j=m;j>=1;j--){
p2[p[i]][j]=a[p[i]][j];
p2[p[i]][j]=min(p2[p[i]][j],p2[p[i-1]][j]);
p2[p[i]][j]=min(p2[p[i]][j],p2[p[i]][j+1]);
}
for(int i=n;i>=1;i--) //右上角到左下角的最小值
for(int j=1;j<=m;j++){
p3[p[i]][j]=a[p[i]][j];
p3[p[i]][j]=min(p3[p[i]][j],p3[p[i+1]][j]);
p3[p[i]][j]=min(p3[p[i]][j],p3[p[i]][j-1]);
}
for(int i=n;i>=1;i--) //右下角到左上角的最大值
for(int j=m;j>=1;j--){
p4[p[i]][j]=a[p[i]][j];
p4[p[i]][j]=max(p4[p[i]][j],p4[p[i+1]][j]);
p4[p[i]][j]=max(p4[p[i]][j],p4[p[i]][j+1]);
}
for(int i=2; i<=n; i++){
for(int j=1;j<=m-1;j++){
if(p3[p[i]][j]>p1[p[i-1]][j]&&p2[p[i-1]][j+1]>p4[p[i]][j+1]){
for(int k=n;k>=i;k--) flag[p[k]] = true;
printf("YES\n");
for(int k=1;k<=n;k++){
if(flag[k]) printf("R");
else printf("B");
}
printf(" %d\n",j);
return;
}
}
}
printf("NO\n");
}
int main(){
int t;
scanf("%d",&t);
while(t--){
work();
}
return 0;
}
总结：
考虑解决小的问题，并由小的问题推广到大问题，有利于发现题目性质。并且要善于观察数据范围。
*CF1606E Arena
题目分析：
我们读完题之后会发现英雄能不能全部干掉与最大值密切相关，那么我们就可以考虑设 \(f(i,j)\)，表示有 \(i\) 个英雄，最大血量为 \(j\) 的最后全部被干掉的方案数。
转移也是相当显然的：
也就是我们直接枚举这一轮剩下多少人，显然剩下的最大值就是 \(j-(i-1)\)，而这一轮干掉的 \(i-k\) 个人显然血量为 \([1,i-1]\) 均可。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 505;
const int MOD = 998244353;
int dp[MAXN][MAXN],c[MAXN][MAXN],pre[MAXN][MAXN];
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = (res * a)%MOD;
a = (a * a)%MOD;
b>>=1;
}
return res;
}
signed main(){
int n,x;
scanf("%lld%lld",&n,&x);
c[0][0] = 1;
for(int i=1; i<=n; i++){
c[i][0] = 1;
for(int j=1; j<=n; j++){
c[i][j] = (c[i-1][j-1] + c[i-1][j])%MOD;
}
}
for(int i=1; i<=500; i++){
pre[i][0] = 1;
for(int j=1; j<=500; j++){
pre[i][j] = (pre[i][j-1] * i)%MOD;
}
}
for(int i=2; i<=n; i++){
for(int j=1; j<=x; j++){
if(i-1 >= j)
dp[i][j] = ((pre[j][i] - pre[j-1][i])%MOD + MOD) % MOD;
else{
for(int k=1; k<=i; k++){
dp[i][j] = (dp[i][j] + ((c[i][k] * dp[k][j - (i-1)])%MOD * pre[i-1][i-k])%MOD)%MOD;
}
}
}
}
int ans = 0;
for(int i=1; i<=x; i++) ans = (ans + dp[n][i])%MOD;
printf("%lld\n",ans);
return 0;
}
可以预处理出来需要的幂，可以省掉一个 \(O(\log n)\) 的复杂度
标签：p2,p4,记录,int,题解,--,MAXN,2022.8,MOD From： https://www.cnblogs.com/linyihdfj/p/16580351.html总结：
不能看到一道题就肯定他是某种题目，如果一直将这个题当作数学题做，显然做不出来，就像我一样。也要重充分发挥预处理的功能。