中小型网站建设价格,网站 刷流量,江苏省工程建设协会网站,北京建站免费模板这里写目录标题一、刷题统计#xff08;ceil函数返回的是等值于某最小整数的浮点值#xff0c;不强制转换回int就wa#xff0c;没错就连和int整数相加都wa二、修剪灌木#xff08;主要应看清楚会调转方向三、统计子矩阵#xff08;前缀和滑动窗口⭐#xff09;四、[积木画…
这里写目录标题一、刷题统计ceil函数返回的是等值于某最小整数的浮点值不强制转换回int就wa没错就连和int整数相加都wa二、修剪灌木主要应看清楚会调转方向三、统计子矩阵前缀和滑动窗口⭐四、[积木画](https://www.lanqiao.cn/problems/2110/learning/)顺子日期X进制减法一、刷题统计ceil函数返回的是等值于某最小整数的浮点值不强制转换回int就wa没错就连和int整数相加都wa ceil函数我给你跪了总之ceilx) 返回的是 等值于 大于或等于x(一般为浮点数可能是整数的最小整数 的浮点数
#include bits/stdc.h
using namespace std;
#define int long long int
signed main()
{
int res0,sum0;
int a,b,n;
cinabn;int x5*a2*b;
res(n/x*7);
sumn/x*x;
int yn-sum;
//x0;
//while(y0){
// x;
// if(x5)y-a;
// else y-b;//}
//resx;
if(y5*a){resres5(int)ceil((y-5*a)*1.0/b);
}
else res(int)ceil(1.0*y/a);
//if(y5*a){
// res5;
// int z((y-5*a)%b0)?(y-5*a)/b:(y-5*a)/b1;
// resz;
//}
//else{
// int z((y%a)0)?y/a:y/a1;
// resz;
//}
coutres;return 0;
}二、修剪灌木主要应看清楚会调转方向 #include bits/stdc.h
using namespace std;
#define int long long int
int n;
const int N10000;
int a[N];
int b[N];
signed main(){
//在第一天的 早晨, 所有灌木的高度都是 0 厘米 每天从早上到傍晩会长高 1 厘米
//当修剪了最右侧的灌木后, 她会调转方向
cinn;for(int i1;in;i){a[i]2*max(n-i,i-1);couta[i]endl;} //3 4 5// 1 1 1 0 1 1
// 1 2 2 1 0 2
// 2 1 3 2 1 0
// 3 2 1 3 0 1
// 4 1 2 0 1 2
// 1 2 3 1 0 3
// 2 1 4 2 1 0// 首先容易发现
// 1、最高的时候永远出现在晚上未修剪之前(马上要修剪了)轮流变成0
// 2、灌木的最高长度应该是对称的(调转方向)
// 3、因为有最高高度这应该是个循环的固定模式即每个灌木都是从0-max 重复
// 固定模式的哪个时刻出现最高高度呢
// 刚把a[x]砍到0后向左或向右走到底a[n]再往回走到a[x]的时候return 0;
}三、统计子矩阵前缀和滑动窗口⭐
结错婚是惨过输钱看错题惨过。。。 是不超过k不是等于k啊大佬
#include bits/stdc.h
using namespace std;
#define int long long int
int n,m,k;
const int N1005;
int a[N][N];
int b[N][N];//b[i][j],第i列 前j行的前缀和
int res0;
void fun(int x,int y){int s[N];int sum[N];memset(s,sizeof(s),0);memset(sum,sizeof(sum),0);for(int i1;in;i){s[i]b[i][y]-b[i][x-1];sum[i]sum[i-1]s[i];}//这里是暴力枚举区间在双重循环下暴力导致超时//用滑动窗口(maybe)
// for(int l1;ln;l){
// for(int rl;rn;r){
// if((sum[r]-sum[l-1])k)res;
// }
// }int l1,r1;for(int rl;rn;r){while(sum[r]-sum[l-1]k){l;}resr-l1;
//此时sum[r]-sum[l-1]k,由于枚举的是右端点以r为右端点有r-l1个空间满足条件}
// l l1 l2 l3 (l,l3) (l1,l3) (l2,l3) (l3,l3)
}
void fun1(int i,int ii){
// 这里a[i][j]是第j列前i行的前缀和
//我的题解b[i][j]是第i列前j行的前缀和int l 1, r 1;//滑动窗口的左右端点int sum 0;//区间前缀和[l,r]区间的累计和for(r 1; r n; r)//遍历右端点根据区间和调整左端点{sum a[ii][r] - a[i-1][r];//加上右端点处的和while(sum k)//区间和了左端点右移区间变小{sum - a[ii][l] - a[i-1][l];//减去移出去的左端点处的和l;}res r - l 1;//方法数就是找到的区间大小累加}
}
signed main(){cinmnk;for(int i1;im;i){for(int j1;jn;j){cina[i][j];b[j][i]b[j][i-1]a[i][j];}}
// 子矩阵的和
// for(int i1;in;i){
// for(int j1;jm;j){
// coutb[i][j] ;
// }
// coutendl;
// } for(int i1;im;i){for(int ji;jm;j){fun(i,j);}}coutres;return 0;
}三个样例运行超时了
#include bits/stdc.h
using namespace std;
#define int long long int
int n,m,k;
const int N1005;
int a[N][N];
int b[N][N];//b[i][j],第i列 前j行的前缀和
int res0;
void fun(int x,int y){int s[N];int sum[N];memset(s,sizeof(s),0);memset(sum,sizeof(sum),0);for(int i1;in;i){s[i]b[i][y]-b[i][x-1];sum[i]sum[i-1]s[i];}for(int i1;in;i){for(int ji;jn;j){if((sum[j]-sum[i-1])k)res;}}}
signed main(){cinmnk;for(int i1;im;i){for(int j1;jn;j){cina[i][j];b[j][i]b[j][i-1]a[i][j];}}
// 子矩阵的和
// for(int i1;in;i){
// for(int j1;jm;j){
// coutb[i][j] ;
// }
// coutendl;
// } for(int i1;im;i){for(int ji;jm;j){fun(i,j);}}coutres;return 0;
}四、积木画 我一直以为我是对的来着0%通过率excuse me呜呜呜 fine我看完n3的情况下意识地以为 组合情况 要么 长方形单独拼L形单独拼或者是 长方形和L形混拼而且下意识觉得两种混拼的形式只有n3情况中枚举的这么几种但显然简单化了稍微动脑想想n5一个L形两个长方形这种组合情况就超出了n3枚举的那些情况
#include bits/stdc.h
using namespace std;
#define int long long int
int n,m,k;
const int mod1000000007;
const int N10000005;
int dp[N];signed main(){cinn;dp[1]1;dp[2]2;dp[3]5;for(int i4;in;i){dp[i](dp[i-1]*1%moddp[i-2]*2%moddp[i-3]*5%mod)%mod;}coutdp[n];return 0;
}递归还是讲究一个状态转移那么对于第 iii 列可能会有哪几种情况呢 (阴影部分表示第 i−1i-1i−1 列已经拼好的状态由于长方形和L形都只占两列只需要观察第 i−1i-1i−1 列和第 iii 列) 最后所求的方案数 等值于 dp[n][4]dp[n][4]dp[n][4] 不用担心除了第n列之外的列上下没有被覆盖满因为看我们的状态转移图转移方式无一不会使得第 i−1i-1i−1 列存在未被覆盖的情况由此拼图方式递推推到第 iii 列时不管第 iii 列状态咋样第 i−1i-1i−1 列一定被覆盖满了 正当我以为我要AC的时候没有一声不好意思竟让我崩溃至此
当需要开很大的数组这里高达 1e71e71e7 ),尽量不要开longlong实在不行将中途结果用强制转化成longlong的方法防止爆int,其次就是空间本来就已经不够了数组下标还是不要作妖从1开始从0开始节省一点 这里给256M
一、数组太大超内存
#define int long long int
const int N10000005;
int dp[N][5];vectorvectorint dp(n 1, vectorint(5));数开八位的真敢啊你清一色的runerror以后超过六位数就用vector(等等 不对vector似乎更占空间看这题最后的一块题解同样不开long longvector反而不行了这里能过30%不过是因为是根据n的大小针对性开的有部分测试样例n比较小
二、初始化 没错的都是内存的错 dp[1][4]1;dp[1][0]1;但为什么这个能过35% 即便避开了上面两个任意让人过%0的点也只有勉强的30%
#include bits/stdc.h
using namespace std;
#define int long long int
int n,m,k;
const int mod1000000007;
// const int N10000005;
// int dp[N][5];signed main(){cinn;vectorvectorint dp(n 1, vectorint(5));// dp[1][4]1;// dp[1][0]1;dp[0][4] 1;for(int i1;in;i){dp[i][1](dp[i-1][4])%mod;dp[i][2](dp[i-1][1]dp[i-1][3])%mod;dp[i][3](dp[i-1][1]dp[i-1][2])%mod;dp[i][4](dp[i-1][4]dp[i-1][3]dp[i-1][2]dp[i-1][1])%mod;}coutdp[n][4];return 0;
}AC代码 人已疯仍然不知道在数组越界的情况下是怎么AC的都要怀疑自己二维数组的表示一直以来是错的了
#include bits/stdc.h
using namespace std;
#define LL long long int
int n,m,k;
const int mod1000000007;
const int N10000005;
LL dp[N][3];//改成4 变 35%。全是超过内存限制signed main(){cinn;// vectorvectorLL dp(n 1, vectorLL(4));这种数组声明 30% 运行错误or超内存
//忘记LL直接0%,二维长度改成3 全军覆没0%运行错误数组越界
//难道两种数组声明二维长度的含义不同dp[0][3] 1;for (int i 1; i n; i) {dp[i][0] dp[i - 1][3];dp[i][1] (dp[i - 1][0] dp[i - 1][2]) % mod;dp[i][2] (dp[i - 1][0] dp[i - 1][1]) % mod;dp[i][3] (dp[i - 1][0] dp[i - 1][1] dp[i - 1][2] dp[i - 1][3]) % mod;}cout dp[n][3];return 0;
}如果要是开long long 的dp则会因为空间太大错误。要是开int的dp数组又会因为数据类型不够大在多个int数据相加时会超出int的范围导致答案错误… 真正的解决办法
当需要开很大的数组这里高达 1e81e81e8 ),尽量不要开longlong实在不行将中途结果用强制转化成longlong的方法防止爆int,其次就是空间本来就已经不够了数组下标还是不要作妖从1开始从0开始节省一点
两种初始化方法都行 dp[1][0] 1;dp[1][1] 0;dp[1][2] 0;dp[1][3] 1;for(int i2;in;i){dp[0][3] 1;for(int i1;in;i){#include bits/stdc.h
using namespace std;
#define ll long long int
int n,m,k;
const int mod1000000007;const int N10000005;int dp[N][4];signed main(){cinn;
// vectorvectorint dp(n 1, vectorint(4));
// dp[1][3]1;
// dp[1][0]1;dp[0][3] 1;for(int i1;in;i){dp[i][0]((ll)dp[i-1][3])%mod;dp[i][1]((ll)dp[i-1][0](ll)dp[i-1][2])%mod;dp[i][2]((ll)dp[i-1][0](ll)dp[i-1][1])%mod;dp[i][3]((ll)dp[i-1][3](ll)dp[i-1][2](ll)dp[i-1][1](ll)dp[i-1][0])%mod;}coutdp[n][3];return 0;
}问题又来了即使不开 longlong数组这里用vector声明二维数组的时候又只能过35%我不理解
力扣原题-动态规划解释 找规律解释类似这种的动态规划找方法数都有规律
顺子日期
#include iostream
using namespace std;
int a[10];
int mon[15]{0,31,28,31,30,31,30,31,31,30,31,30,31};
bool ok(int x){int yx/10000;int m(x%10000)/100;int dx%100;if(m1||m12)return false;if(d1)return false;if(dmon[m])return false;return true;
}
int main()
{int res0;for(int i20220101;i20221231;i){if(!ok(i))continue;int cnt0;int xi;while(x){a[cnt]x%10;x/10;}//翻转了判断是否 321for(int j0;j6;j){if(a[j1]a[j]-1a[j2]a[j]-2){res;break;}}
}
coutres;return 0;
}X进制减法 样例输入
11
3
10 4 0
3
1 2 0样例输出
94首先是找规律第 iii 位的权重是累乘 111 ~ i−1i-1i−1 的所有进制 最小的差值我下意识以为要暴力搜索所有权值的组合情况因为毕竟虽然 ABABAB ,难免可能统一位上 A[i]B[i]A[i]B[i]A[i]B[i] 但也许是贪心思想每一位都取最低的权值就能得到最小的差值 暴力搜索版过了30%剩下的超时了
#include bits/stdc.h
using namespace std;
#define ll long long int
const int mod1000000007;
const int N100005;
int n,x,y;
int a[N],b[N],c[N];
ll res0x3f3f3f3f;
int X[N];
void dfs(int u){if(ux1){ll tmpa[1];ll base1;for(int i2;ix;i){basebase*X[i-1]%mod;tmp(tmpa[i]*base)%mod;}resmin(tmp,res);return ;}for(int i2;in;i){if(ic[u]){X[u]i; dfs(u1);}}
}
signed main(){scanf(%d,n);scanf(%d,x);
for(int ix;i1;i--)scanf(%d,a[i]);scanf(%d,y);for(int iy;i1;i--)scanf(%d,b[i]);
// 最小的差
// 既然AB ,那么x一定大于等于y
// 每一数位上的数 字要小于其进制for(int i1;ix;i){c[i]max(a[i],b[i])1;//进制大于等于c[i]a[i]a[i]-b[i];if(c[i]2)c[i]2;}dfs(1);coutres;return 0;
}贪心AC版 解释一 因为每一位进制都会 乘到 A 和 B里面当 base 越大的时候 A 和 B都会越大但是因为 A B 的所以 A 的增长速率是始终大于 B 的 所以 base越大A - B 的差值就越大所以我们只要每次取 base 最小就能满足 A - B 的差值最小了又因为每一位的值都是由前面每一位的进制乘起来的
解释二 借位思想极限思维 一旦碰到A[i]B[i]A[i]B[i]A[i]B[i]就向高位借位由于 ABABAB最后一定可以使得 每个位置都有A[i]B[i]A[i]B[i]A[i]B[i] 解释三 秦九韶算法
#include bits/stdc.h
using namespace std;
#define ll long long int
const int mod1000000007;
const int N100005;
int n,x,y;
int a[N],b[N],c[N];
ll res0;
signed main(){scanf(%d,n);scanf(%d,x);for(int ix;i1;i--)scanf(%d,a[i]);scanf(%d,y);for(int iy;i1;i--)scanf(%d,b[i]);
// 最小的差
// 既然AB ,那么x一定大于等于y
// 每一数位上的数 字要小于其进制ll base1;for(int i1;ix;i){c[i]max(a[i],b[i])1;//进制大于等于c[i]a[i]a[i]-b[i];//不要改变了a[i]的含义又去用原a[i]的值 不要交换两句顺序if(c[i]2)c[i]2;res(resa[i]*base)%mod;basebase*c[i]%mod;}coutres;return 0;
}
