网站制作内容,dns是不是做网站用的,htm5移动网站开发,福州seo博客目录 刷题统计
修剪灌木
X进制减法
【前缀和双指针】统计子矩阵
【DP】积木画
【图DFS】扫雷
李白打酒加强版
DFS (通过64%#xff0c;ACwing 3/11#xff09;; DFS(AC)
DP#xff08;AC#xff09;
砍竹子(X) 刷题统计
题目描述
小明决定从下周一开始努力刷题准…目录 刷题统计
修剪灌木
X进制减法
【前缀和双指针】统计子矩阵
【DP】积木画
【图DFS】扫雷
李白打酒加强版
DFS (通过64%ACwing 3/11; DFS(AC)
DPAC
砍竹子(X) 刷题统计
题目描述
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目周六和周日每天做 b 道题目。请你帮小明计算按照计划他将在第几天实现做题数大于等于 n 题
输入格式
输入一行包含三个整数 a, b 和 n.
输出格式
输出一个整数代表天数。
样例输入
10 20 99
样例输出
8
提示
对于 50% 的评测用例1 ≤ a, b, n ≤ 106 . 对于 100% 的评测用例1 ≤ a, b, n ≤ 10^18 .
#includeiostream
using namespace std;
typedef long long LL;
const int N2e510,M1e510;
int main(){int T1;
// cinT;while(T--){LL a,b,n;cinabn;LL ta*5b*2;LL ans0;ansn/t*7;n%t;if(na*5){ans5;n-a*5;ans(nb-1)/b;}else{ans(na-1)/a;}coutansendl;}return 0;
}
修剪灌木
题目描述
爱丽丝要完成一项修剪灌木的工作。有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始每天向右修剪一棵灌木。当修剪了最右侧的灌木后她会调转方向下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。灌木每天从早上到傍晚会长高 1 厘米而其余时间不会长高。在第一天的早晨所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。
输入格式
一个正整数 N 含义如题面所述。
输出格式
输出 N 行每行一个整数第i行表示从左到右第 i 棵树最高能长到多高。
样例输入
3
样例输出
4
2
4
提示
对于 30% 的数据N ≤ 10. 对于 100% 的数据1 N ≤ 10000.
#includeiostream
using namespace std;
typedef long long LL;
const int N2e510,M1e510;
int a[10010];
int main(){int T1;
// cinT;while(T--){int n;cinn;for(int i1,jn;ij;i,j--){a[i]a[j]2*(n-i);}for(int i1;in;i) couta[i]endl;}return 0;
}
X进制减法
题目描述
进制规定了数字在数位上逢几进一。
X 进制是一种很神奇的进制因为其每一数位的进制并不固定例如说某种 X 进制数最低数位为二进制第二数位为十进制第三数位为八进制则 X 进制数 321 转换为十进制数为 65。
现在有两个 X 进制表示的整数 A 和 B但是其具体每一数位的进制还不确定只知道 A 和 B 是同一进制规则且每一数位最高为 N 进制最低为二进制。请你算出 A − B 的结果最小可能是多少。
请注意你需要保证 A 和 B 在 X 进制下都是合法的即每一数位上的数字要小于其进制。
输入格式
第一行一个正整数 N含义如题面所述。
第二行一个正整数 Ma表示 X 进制数 A 的位数。
第三行 Ma 个用空格分开的整数表示 X 进制数 A 按从高位到低位顺序各个数位上的数字在十进制下的表示。
第四行一个正整数 Mb表示 X 进制数 B 的位数。
第五行 Mb 个用空格分开的整数表示 X 进制数 B 按从高位到低位顺序各个数位上的数字在十进制下的表示。
请注意输入中的所有数字都是十进制的。
输出格式
输出一行一个整数表示 X 进制数 A − B 的结果的最小可能值转换为十进制后再模 1000000007 的结果。
样例输入
11
3
10 4 0
3
1 2 0
样例输出
94
提示
当进制为最低位 2 进制第二数位 5 进制第三数位 11 进制时减法得到的差最小。此时 A 在十进制下是 108B 在十进制下是 14差值是 94。
对于 30% 的数据N ≤ 10; Ma, Mb ≤ 8. 对于 100% 的数据2 ≤ N ≤ 1000; 1 ≤ Ma, Mb ≤ 100000; A ≥ B. 123c进制数组1152a1040 A(a1*c1a2)*c3a3
#includeiostream
using namespace std;
typedef long long LL;
const int N1e510;
LL mod1000000007;
LL a[N];
LL b[N];
LL c[N];
int main(){int T1;
// cinT;while(T--){LL N;cinN;int ma;cinma;for(int i1;ima;i) cina[i];int mb;cinmb;for(int i1;imb;i) cinb[i];int kma,jmb;for(kma,jmb;k1j1;k--,j--){c[k]max(a[k],b[j])1;if(c[k]2) c[k]2;}while(k1){c[k]max((LL)2,a[k]1);k--;}LL Aa[1];for(int i2;ima;i){A(A*c[i]%moda[i])%mod;}LL Bb[1];jma-mb2;for(int i2;imb;i,j){B(B*c[j]%modb[i])%mod;}// coutA---B---endl;cout(A-Bmod)%modendl;}return 0;
}
【前缀和双指针】统计子矩阵
给定一个 N × M 的矩阵 A请你统计有多少个子矩阵 (最小 1 × 1最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K?
输入格式
第一行包含三个整数 N, M 和 K.
之后 N 行每行包含 M 个整数代表矩阵 A.
输出格式
一个整数代表答案。
样例输入
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
样例输出
19
提示
满足条件的子矩阵一共有 19包含
大小为 1 × 1 的有 10 个。
大小为 1 × 2 的有 3 个。
大小为 1 × 3 的有 2 个。
大小为 1 × 4 的有 1 个。
大小为 2 × 1 的有 3 个。
对于 30% 的数据N, M ≤ 20. 对于 70% 的数据N, M ≤ 100.
对于 100% 的数据1 ≤ N, M ≤ 500; 0 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.
#includeiostream
#includequeue
#includecstring
using namespace std;
typedef long long LL;
const int N510;
LL w[N][N];
LL s[N][N];
int main(){int n,m,k;cinnmk;for(int i1;in;i){for(int j1;jm;j){cinw[i][j];//每一列的前缀和一维s[i][j]s[i-1][j]w[i][j];}}LL sum0,ans0;//找j-i1行r-l1列的子矩阵for(int i1;in;i){//上边界for(int ji;jn;j){//下边界sum0;for(int l1,r1;rm;r){sums[j][r]-s[i-1][r];while(lrsumk){sum-s[j][l]-s[i-1][l];l;}ansr-l1;}}}coutansendl;//二维
// int n,m,k;
// cinnmk;
// for(int i1;in;i){
// for(int j1;jm;j){
// cinw[i][j];
// s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1]w[i][j];
// }
// }
// LL ans0;
// for(int x11;x1n;x1){
// for(int x2x1;x2n;x2){
// for(int y11,y21;y2m;y2){
// while(y1y2s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]s[x1-1][y1-1]k) y1;
// ansy2-y11;
// }
// }
// }
// coutansendl;return 0;
}
【DP】积木画
题目描述
小明最近迷上了积木画有这么两种类型的积木分别为 I 型大小为 2 个单位面积和 L 型大小为 3 个单位面积 同时小明有一块面积大小为 2 × N 的画布画布由 2 × N 个 1 × 1 区域构成。小明需要用以上两种积木将画布拼满他想知道总共有多少种不同的方式 积木可以任意旋转且画布的方向固定。
输入格式
输入一个整数 N表示画布大小。
输出格式
输出一个整数表示答案。由于答案可能很大所以输出其对 1000000007 取模后的值。
样例输入
3
样例输出
5
提示
五种情况如下图所示颜色只是为了标识不同的积木 对于所有测试用例1 ≤ N ≤ 10000000. f[i][0]表示第 i 列放满得方法数
f[i][1]表示第 i 列放满且第 i1 列多一个得方案数。
#includeiostream
#includequeue
#includecstring
using namespace std;
typedef long long LL;
const int N1e710,mod1000000007;
LL f[N][2];
int main(){int n;cinn;f[1][0]1,f[1][1]2,f[2][0]2,f[2][1]4;for(int i3;in;i){f[i][0](f[i-1][0]f[i-2][0]f[i-2][1])%mod;f[i][1](f[i-1][1]f[i-1][0]*2)%mod;}coutf[n][0]endl;return 0;
}
【图DFS】扫雷
小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下 在一个二维平面上放置着 n 个炸雷第 i 个炸雷 (xi , yi ,ri) 表示在坐标 (xi , yi) 处存在一个炸雷它的爆炸范围是以半径为 ri 的一个圆。
为了顺利通过这片土地需要玩家进行排雷。玩家可以发射 m 个排雷火箭小明已经规划好了每个排雷火箭的发射方向第 j 个排雷火箭 (xj , yj ,rj) 表示这个排雷火箭将会在 (xj , yj) 处爆炸它的爆炸范围是以半径为 rj 的一个圆在其爆炸范围内的炸雷会被引爆。同时当炸雷被引爆时在其爆炸范围内的炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷
你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。
输入格式
输入的第一行包含两个整数 n、m.
接下来的 n 行每行三个整数 xi , yi ,ri表示一个炸雷的信息。
再接下来的 m 行每行三个整数 xj , yj ,rj表示一个排雷火箭的信息。
输出格式
输出一个整数表示答案。
样例输入
2 1
2 2 4
4 4 2
0 0 5
样例输出
2
提示
示例图如下排雷火箭 1 覆盖了炸雷 1所以炸雷 1 被排除炸雷 1 又覆盖了炸雷 2所以炸雷 2 也被排除。 对于 40% 的评测用例0 ≤ x, y ≤ 10^9 , 0 ≤ n, m ≤ 10^3 , 1 ≤ r ≤ 10.
对于 100% 的评测用例0 ≤ x, y ≤ 10^9 , 0 ≤ n, m ≤ 5 × 10^4 , 1 ≤ r ≤ 10.
#includeiostream
#includealgorithm
#includemap
#includevector
#define int long long
//typedef long long LL;
using namespace std;
const int N5e410;
struct str{int x,y,r;int cnt;bool operator(str const m) const{if(xm.x) return ym.y;return xm.x;}
}arr[N];
int n,m;
vectorint e[N];
bool vis[N];
mappairint,int,intmp;
int get(int x1,int y1,int x2,int y2){return (x2-x1)*(x2-x1)(y2-y1)*(y2-y1);
}
void add(int index){for(int iindex-1;i1;i--){if(arr[index].x-arr[index].rarr[i].x) break;if(arr[index].r*arr[index].rget(arr[index].x,arr[index].y,arr[i].x,arr[i].y)){e[index].push_back(i);}}for(int iindex1;in;i){if(arr[index].xarr[index].rarr[i].x) break;if(arr[index].r*arr[index].rget(arr[index].x,arr[index].y,arr[i].x,arr[i].y)){e[index].push_back(i);}}
}
int dfs_2(int index){vis[index]1;int sumarr[index].cnt;for(int i0;ie[index].size();i){int te[index][i];if(!vis[t]) sumdfs_2(t);}return sum;
}
int dfs_1(int x,int y,int r){int cnt0;str str1{x-r,y,r};str str2{xr,y,r};int ll,rr;lllower_bound(arr1,arrn1,str1)-arr;rrlower_bound(arr1,arrn1,str2)-arr;llmin(ll,n),rrmin(rr,n);for(int ill;irr;i){if(i0) continue;if(!vis[i]){if(r*rget(x,y,arr[i].x,arr[i].y)){cntdfs_2(i);}}}return cnt;
}
signed main(){scanf(%lld%lld,n,m);for(int i1;in;i){int x,y,r;scanf(%lld%lld%lld,x,y,r);int tmp[{x,y}];if(t){arr[t].cnt;arr[t].rmax(arr[t].r,r);}else{mp[{x,y}]i;arr[i]{x,y,r,1};}}sort(arr1,arrn1);for(int i1;in;i){add(i);}int ans0;for(int i0;im;i){int x,y,r;scanf(%lld%lld%lld,x,y,r);ansdfs_1(x,y,r);}coutansendl;return 0;
}
李白打酒加强版
题目描述
话说大诗人李白一生好饮。幸好他从不开车。
一天他提着酒壶从家里出来酒壶中有酒 2 斗。他边走边唱
无事街上走提壶去打酒。
逢店加一倍遇花喝一斗。
这一路上他一共遇到店 N 次遇到花 M 次。已知最后一次遇到的是花 他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序有多少种不同的可能
注意壶里没酒 ( 0 斗) 时遇店是合法的加倍后还是没酒但是没酒时遇花是不合法的。
输入格式
第一行包含两个整数 N 和 M.
输出格式
输出一个整数表示答案。由于答案可能很大输出模 1000000007 的结果。
样例输入
5 10
样例输出
14
提示
如果我们用 0 代表遇到花1 代表遇到店14 种顺序如下
010101101000000 010110010010000 011000110010000 100010110010000 011001000110000 100011000110000 100100010110000 010110100000100 011001001000100 100011001000100 100100011000100 011010000010100 100100100010100 101000001010100 对于 40% 的评测用例1 ≤ N, M ≤ 10。 对于 100% 的评测用例1 ≤ N, M ≤ 100。
DFS (通过64%ACwing 3/11;
#includeiostream
using namespace std;
#define int long long
int mod1000000007;
int n,m;
int ans0;
void dfs(int cnt,int x,int y){if(cnt0) return ;if(ym1){if(xn1cnt0){ans;ans%mod;// coutcnt m-y---endl;}return ;}if(cntm-y1||n-xm-y) return ;if(ym1||xn1) return ;dfs(cnt*2,x1,y);dfs(cnt-1,x,y1);
}
signed main(){scanf(%d%d,n,m);dfs(2,1,1);coutans%modendl;return 0;
} DFS(AC)
#includeiostream
#includecstring
using namespace std;
#define int long long
const int N110;
int mod1000000007;
int n,m;
int ans0;
int arr[N][N][N];
int dfs(int n,int m,int cnt){if(m0||n0) return 0;if(arr[n][m][cnt]!-1) return arr[n][m][cnt];if(cnt0) return 0;if(m0){if(n0cnt0) return 1;return 0;}if(cntm||nm) return 0;ansdfs(n-1,m,cnt*2)dfs(n,m-1,cnt-1);ans%mod;arr[n][m][cnt]ans;return ans;
}
signed main(){memset(arr,-1,sizeof arr);scanf(%d%d,n,m);coutdfs(n,m,2)endl;return 0;
}
DPAC
f[i][j][k]走到了第i个位置遇到了j个花还剩k斗酒的合法方案数. #includeiostream
using namespace std;
#define int long long
const int N110;
int f[N*2][N][N*2];
int mod1000000007;
signed main(){int n,m;cinnm;f[0][0][2]1;for(int i1;inm;i){for(int j0;jm;j){for(int k0;km;k){//k为偶数第i个可以是店也可以是花k为奇数只能是花if(k%20){//店转移f[i][j][k](f[i][j][k]f[i-1][j][k1])%mod;}//花转移if(j1) f[i][j][k](f[i][j][k]f[i-1][j-1][k1])%mod;}}}coutf[nm-1][m-1][1]endl;return 0;
}
砍竹子(X)
