题目讲解(1到5)
1
编写一个能够输出?Hello,World!?的程序。
提示：
- 使用英文标点符号；
Hello,World!?逗号后面没有空格。H?和?W?为大写字母。
输入格式
无
输出格式
无
输入输出样例
输入 #1复制
无
输出 #1复制
Hello,World!
这个不会写没啥讲的自裁吧,程序员的开始,一切罪恶的起点!!!!!
毁灭吧
2台阶问题
有?N?级台阶，你一开始在底部，每次可以向上迈?1～K?级台阶，问到达第?N?级台阶有多少种不同方式。
输入格式
两个正整数?N,K。
输出格式
一个正整数?ans(mod100003)，为到达第?N?级台阶的不同方式数。
输入输出样例
输入 #1复制
5 2
输出 #1复制
8
说明/提示
- 对于?20%20%?的数据，1≤N≤10，1≤K≤3；
- 对于?40%40%?的数据， 1≤N≤1000；
- 对于?100%100%?的数据，1≤N≤100000，1≤K≤100。
题目大意肯定是非常容易理解的
1...反向推导->首先我们想要求得到第n阶,
我们可以枚举他的最后一步往前看
可以得到ans[n]=? ans[n-1]+ans[n-2]........?(从1到k) 但是k不能超过第n阶
不断的传下去最后一定会归于 ans[1]一个台阶需要几步
2...正向推导->首先我们想到一个台阶需要几步
一步(显然)
两个台阶嘞
有两种情况 1一步一步走两步 2一次走两步(前提是可以一次两步)
三个台阶嘞 只考虑最后一步 可以一步那就是加上ans[2],两步加上ans[1],三步加上ans[0]
有此完全可以看出我们只要枚举最后一步即可(其实与上面一样)
不断的往后退推到最后的未知数只有ans[0]和ans[1]很显然这两个我们知道
都为一
写法有两种可以递归(dfs)记忆化
也可以迭代(动态规划)
思路其实都一样
1递归(dfs)记忆化
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int kk[100000] = {0};
int ans(int i,int n) {
if (i == 0 || i == 1) {
return 1;}
else if (kk[i] > 0) {
return kk[i];}
else {
int sum = 0;//当前有多少种
for (int kl = 1;kl<=n&&kl<i;kl++){
kk[i-kl] =ans(i-kl,n)%100003;
sum=(sum+kk[i-kl])%100003;
}
if(n >= i)
sum++;
kk[i] = sum;
return sum;
}
}
int main()
{
int x,y;
cin >>x>>y;
cout << ans(x,y);
return 0;
}2.迭代(dp)
#include <iostream>
using namespace std;
int arr[100000] = {0};
int main() {
int n, k;
cin >> n >> k;
arr[0] = 1;
arr[1] = 1;
for (int zi = 2;zi <= n;zi++) {
for (int si = 1;si <= k && si <= zi;si++)
arr[zi]=(arr[zi]+arr[zi - si])%100003;
}
cout << arr[n];
return 0;
}显然下面的方法代码更少推荐写下面的写法,可以迭代就不搞递归(建议)?
难度真的不大qwq
B3738 [信息与未来 2018] 素数方阵
题目描述
把前?n2?个素数从左上角开始按右、下、左、上、右、下、左、上……的顺序填入n×n?的方阵就得到了蛇形素数方阵。以下是?n=4?和?n=5?的蛇形素数方阵：
给出?n，你的任务是求出?n×n?的蛇形素数方阵，并输出其中某个方格中的数值。
素数，又称质数，是指除?11?和其自身之外，没有其他约数的大于?11?的正整数。
输入格式
输入一行三个正整数?n,x,y。
输出格式
输出一行一个整数，表示?n×n?蛇形素数方阵第?x?行第?y?列中的数字。
输入输出样例
输入 #1复制
5 1 4
输出 #1复制
7
输入 #2复制
5 4 3
输出 #2复制
79
说明/提示
样例解释
参考上图?n=5。
数据规模
所有数据满足?1≤x,y≤n≤20。
本题原始满分为?15pts15pts。
我相信你看到这个题目就会写,但是不知道如何写出来,这个故事相当的悲伤
写了半天发现还是没有把这个正方形搞出来
哎, 我是真的想哭呜呜呜
来教你们一招简单易懂的,就像是贪吃蛇一样,我们
需要一个地图起点表示arr[1][1]
k=1向右
k=2向下.....
每次走过的地方打下标签碰到了就回退平且改变方向
上代码看看
#include <iostream>
using namespace std;
int arr[500] = { 0 };//存放质数
int zi[100001] = { 0 };//质数筛选
int brr[21][21];//地图
int n, lu;
int pan(int size) {
if (size == 1)
return 0;
for (int j = 2;j < size;j++)
if (size % j == 0) {
return 0;
}
return 1;
}
void start2() {
lu = 1;
for (int ll = 1;ll < 100001 && lu < 401;ll++) {
if (pan(ll) == 1)
{
arr[lu] = ll;
lu++;
}
}
}
void start1() {
for (int lp = 1;lp <= 20;lp++)
for (int li = 1;li <= 20;li++)
brr[lp][li] = 0;
}//初始化
//上面都是初始化,求素数,暴力求也是可以通过的
int main() {
start2();
start1();
int x, y;
cin >> n >> x >> y;
int xl = 1, yl = 1;
int k = 1;
int ans = 1;//初始位置
brr[1][1]=1;//打上标记
if (xl == x && yl == y)
cout << arr[ans] << endl;
else
while(true){
if (k == 1) {
yl++;
if (yl>n||yl<1||brr[xl][yl] == 1) {
yl--;
k++;
}//碰到墙壁了
else {
ans++;
brr[xl][yl] = 1;
}
}
else if (k==2) {
xl++;
if (xl > n || xl < 1 || brr[xl][yl] == 1) {
xl--;
k++;
}//碰到墙壁了
else {
ans++;
brr[xl][yl] = 1;
}
}
else if (k==3) {
yl--;
if (yl > n || yl < 1 || brr[xl][yl] == 1) {
yl++;
k++;
}//碰到墙壁了
else {
ans++;
brr[xl][yl] = 1;
}
}
else {
xl--;
if (xl > n || xl < 1 || brr[xl][yl] == 1) {
xl++;
k=1;
}//碰到墙壁了
else {
ans++;
brr[xl][yl] = 1;
}
}
if (x == xl && yl == y)
break;
}
cout << arr[ans] << endl;
return 0;
}看着很长其实就这样,求素数很简单随便咋写都可以,我们最后只要得到他到底是第多少个素数既可
输出就结束了.
注意越界也是墙壁的?
碰到墙壁了 要返回以及转换方向
ok 很简单吧qwq (不简单噶了你)
P1147 连续自然数和
题目描述
对一个给定的正整数?M，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为?M。
例子：1998+1999+2000+2001+2002=100001998+1999+2000+2001+2002=10000，所以从?19981998?到?20022002?的一个自然数段为?M=10000?的一个解。
输入格式
包含一个整数的单独一行给出?M?的值（10≤M≤2,000,000）。
输出格式
每行两个正整数，给出一个满足条件的连续正整数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。
输入输出样例
输入 #1复制
10000
输出 #1复制
18 142 297 328 388 412 1998 2002
我一看好家伙题目直白明了
数据给到了2,000,000
对半砍也就是1000000
普通的暴力可以拿到70分也可以没有想到优化那也行等于写完了
好吧其实靠前缀和就可以简单的拉满分数了
把求和提前算好时间复杂度降低了不少呀
而且前缀和肯定是学了的
没学那就是刷的少了(有这个题组的)
欧克话不多讲
上代码
#include <iostream>
using namespace std;
int arr[1000050] = { 0 };
void start(int n) {
arr[0] = 0;
arr[1] = 1;
for (int j = 2;j <= n / 2+1;j++)
arr[j] = j + arr[j - 1];
}//前缀和
int main() {
int m;
cin >> m;
start(m);
for (int kl = 0;kl <= m / 2-1;kl++) {
for (int kk = kl + 2;kk <= m / 2+1;kk++) {
if (arr[kk]- arr[kl] == m) {
cout << kl + 1 << " " << kk << endl;
break;
}
else if(arr[kk] - arr[kl] >m){
break;//后面只会越来越大不可能有结果的
}
}
}
return 0;
}循环到m/2-1是因为后面不会有可能有答案了
由于数据是递增的还可以二分优化,但是前缀和已经可以全部拿下了那就算了
简单啊真的简单qwq你为啥没写出来
啊啊啊啊啊
P1007 独木桥
题目背景
战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳?11?个人通过。假如有?22?个人相向而行在桥上相遇，那么他们?22?个人将无法绕过对方，只能有?11?个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。
题目描述
突然，你收到从指挥部发来的信息，敌军的轰炸机正朝着你所在的独木桥飞来！为了安全，你的部队必须撤下独木桥。独木桥的长度为?L，士兵们只能呆在坐标为整数的地方。所有士兵的速度都为?11，但一个士兵某一时刻来到了坐标为?0?或?L+1?的位置，他就离开了独木桥。
每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何的时间。
由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。
输入格式
第一行共一个整数?L，表示独木桥的长度。桥上的坐标为?1,2,??,1,2,?,L。
第二行共一个整数?N，表示初始时留在桥上的士兵数目。
第三行共有?N?个整数，分别表示每个士兵的初始坐标。
输出格式
共一行，输出?22?个整数，分别表示部队撤离独木桥的最小时间和最大时间。22?个整数由一个空格符分开。
输入输出样例
输入 #1复制
4 2 1 3
输出 #1复制
2 4
说明/提示
对于?100%?的数据，满足初始时，没有两个士兵同在一个坐标，1≤L≤5 0≤N≤5×103，且数据保证?N≤L。
由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。
如果你能想到方向其实都是迷惑
两个人碰撞了那么最最终有任何的影响吗
一点都没有,相当于两个人穿过了对方
如何理解了这点那这题目也是嘎嘎乱杀
那就演变为了比较大小了
最大比一比
最小比一比
没了
#include<stdio.h>
int max(int x,int y){
if(x>=y){
return x;
}
return y;
}
int min(int j,int k){
if(j<=k){
return j;
}
return k;
}
int main(){
int l,m;
int a[99999];
scanf("%d%d",&l,&m);
for(int h=1;h<=m;h++){
scanf("%d",&a[h]);
}
int maxe=0;
int mine=0;
for(int j=1;j<=m;j++){
int kl=max(a[j],l+1-a[j]);
int mi=min(a[j],l+1-a[j]);
if(kl>maxe){
maxe=kl;
}
if(mi>mine){
mine=mi;
}
}
printf("%d %d",mine,maxe);
return 0;
}是不是觉得自己都能写出来,确实是没有啥难的
最后这道考了点思维,不多呀
宝儿们,路很长你要慢慢的走
前进,远方!
ok结尾谢幕
嘟嘟嘟嘟嘟
下班啦啦!!!!!!
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！