题目讲解(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结尾谢幕

嘟嘟嘟嘟嘟

下班啦啦!!!!!!