题目练习（生死时速版）

第一题（最大正方形）

题目描述

在一个 n×m 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形，输出边长。

输入格式

输入文件第一行为两个整数 n,m(1≤n,m≤100)，接下来 n 行，每行 m 个数字，用空格隔开，0 或 1。

输出格式

一个整数，最大正方形的边长。

输入输出样例

输入 #1

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

输出 #1

2

思路： 题目主要考察动态规划，枚举，前缀和。 

dp[i][j]数组的含义是：构成正方形的最大边长，其中节点i，j为最右下角的坐标。

直接看代码吧： 

#include<bits/stdc++.h>//C++万能头文件
using namespace std;//标配不能少
int g[1000][1000];//储存0，1
int dp[1000][1000];
//构成正方形的最大边长，其中节点i，j为最右下角的坐标
int maxx;//找最大边长用的
int main()
{
	int n, m;//地图大小输入
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &g[i][j]);
		}
	}
    //寻找最大边长
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {//要比较三个
            //要找到附近的最大边长再加上1，表示这次的
			if (g[i][j] == 1)dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
			maxx = max(maxx, dp[i][j]);
		}
	}
	printf("%d", maxx);
	return 0;
}

第二题（封印）：

题目背景

很久以前，魔界大旱，水井全部干涸，温度也越来越高。为了拯救居民，夜叉族国王龙溟希望能打破神魔之井，进入人界“窃取”水灵珠，以修复大地水脉。可是六界之间皆有封印，神魔之井的封印由蜀山控制，并施有封印。龙溟作为魔界王族，习有穿行之术，可任意穿行至任何留有空隙的位置。然而封印不留有任何空隙！ 龙溟无奈之下只能强行破除封印。破除封印必然消耗一定的元气。为了寻找水灵珠，龙溟必须减少体力消耗。他可以在破除封印的同时使用越行术。

题目描述

神魔之井的封印共有 n 层，每层封印都有一个坚固值。身为魔族的龙溟单独打破一层封印时需要消耗的元气为该层封印的坚固值和封印总层数 n 的平方的乘积； 但他也可以打破第 i 层到第 j 层之间的所有封印( i<j)，总元气消耗为第 i,j 层封印的坚固值之和与第 i,j 层之间所有封印层（包括第 i,j 层）的坚固值之和的乘积，但为了不惊动蜀山，第 i,j 层封印的坚固值之和不能大于 t （单独打破可以不遵守）。

输入格式

第一行包含两个正整数 n 和 t。
第二行有 n 个正整数，第 i 个数为 ai​，表示第 i 层封印的坚固值。

输出格式

仅一行，包含一个正整数，表示最小消耗元气。

输入输出样例

输入 #1

6 10
8 5 7 9 3 5

输出 #1

578

说明/提示

样例解释

先单独打破第一层，再用越行术从第二层直接打破到最后一层。 这样消耗元气 8×36+(5+5)×(5+7+9+3+5)=578。

数据范围

对于 10% 的数据， n≤10；
对于 50% 的数据， n≤100；
对于 70% 的数据， n≤500；
对于 100% 的数据， n≤1000， ai(1≤i≤n),t≤20000。

思路： 题目主要考察动态规划，前缀和。 

看代码吧，上面有解析

#include <iostream>//可以改成万能头文件
#include <cstdio>
using namespace std;
//数值有点大，开大点用长整型
long long int dp[1000000];
long long int a[10000],q[10000];
int main()
{
	long long int n, t;//输入
	scanf("%lld%lld", &n, &t);
	long long int m = n * n;
	for (long long int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		q[i] = q[i - 1] + a[i];//求总和，后面求前缀和要用到
		dp[i] = 100000000009;
	}
	for (long long int i = 1; i <= n; i++) {
		dp[i] = min(a[i] * m+dp[i-1], dp[i]);
		for (long long int j = 1; j < i; j++) {
			if (a[i]+a[j] <= t)//找最小值，前缀和在这里用到了
dp[i] = min((q[i] - q[j - 1]) *(a[i]+a[j])+dp[j-1], dp[i]);
		}
	}
	printf("%lld", dp[n]);
	return 0;
}
	

第三题（奇怪的函数）

题目描述

使得  达到或超过 n 位数字的最小正整数 x 是多少？

输入格式

一个正整数 n。

输出格式

使得 达到 n 位数字的最小正整数 x。

输入输出样例

输入 #1

11

输出 #1

10

说明/提示

对于全部数据，1≤n≤2×1000000000。

思路：二分

看代码：

#include<stdio.h>
#include<math.h>
int n, l = 1, r = 3e8;//要开大一点
int main()
{
	scanf("%d", &n);
	n -= 1;
	int m;
	while (l < r) {//二分查找
		m = (l + r) / 2;
		if (m * log10(m) < n)
		{
			l = m + 1;
		}
		else r = m;
	}
	printf("%d", l);
	return 0;
}

第四题（【模板】并查集）

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。

接下来 M 行，每行包含三个整数 Zi​,Xi​,Yi​ 。

当 Zi​=1 时，将 Xi​ 与 Yi​ 所在的集合合并。

当 Zi​=2 时，输出 Xi​ 与 Yi​ 是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个 Zi​=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入输出样例

输入 #1

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出 #1

N
Y
N
Y

说明/提示

对于 30%30% 的数据，N≤10，M≤20。

对于 70%70% 的数据，N≤100，M≤1000。

对于 100%100% 的数据，1≤N≤10000，1≤M≤2×100000，1≤Xi​,Yi​≤N，Zi​∈{1,2}。

知识点可以去B站上看里面的老师讲的很好。

代码：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAXSIZE 10100
int father[10100], size[10100];
void make(int size) {
	for (int i = 1; i <= size; i++)
		father[i] = i;//以自己为代表
}
int find(int i) {//经典模板
	if (i != father[i])father[i] = find(father[i]);
	return father[i];
}
bool Set(int x, int y)//判断是否是同一集合
{
	return find(x) == find(y);
}
void un(int x, int y) {//合并
	father[find(x)] = find(y);
}
int main()
{
	int n, m, z, x, y;
	scanf("%d%d", &n, &m);
	make(n);
	while (m--) {
		scanf("%d%d%d", &z, &x, &y);
		if (z == 1) {
			if (!Set(x, y)) //如果不是同一集合就合并
				un(x, y);
		}
		else {
			if (Set(x, y))printf("Y\n");
			else printf("N\n");
		}
	}
	return 0;
}

第五题（修复公路）

题目背景

A 地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

题目描述

给出 A 地区的村庄数 N，和公路数 M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）。

输入格式

第 11 行两个正整数 N,M。

下面 M 行，每行 33 个正整数 x,y,t，告诉你这条公路连着 x,y 两个村庄，在时间t时能修复完成这条公路。

输出格式

如果全部公路修复完毕仍然存在两个村庄无法通车，则输出 −1，否则输出最早什么时候任意两个村庄能够通车。

输入输出样例

输入 #1

4 4
1 2 6
1 3 4
1 4 5
4 2 3

输出 #1

5

说明/提示

1≤x,y≤N≤1000，1≤M,t≤100000。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, m, father[10005], cnt = 0, ans = 0;
struct gl {
	int x, y, t;
}g[101000];
//与上一个题目相比，一些函数放入主函数更加便捷
bool cmp(gl a, gl b) {//排序（修路是同时一起修）
	return a.t < b.t;
}
int find(int x) {
	if (father[x] != x)father[x] = find(father[x]);
	return father[x];
}
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)father[i] = i;
	for (int i = 1; i <= m; i++)
		scanf("%d %d %d", &g[i].x, &g[i].y, &g[i].t);
	sort(g + 1, g + 1 + m, cmp);
	for (int i = 1; i <= m; i++) {
		int f1 = find(g[i].x); int f2 = find(g[i].y);
		if (f1 == f2)continue;
		father[f1] = f2;
		cnt++;//判断是否村村通
		ans = max(ans, g[i].t);
	}
	if (cnt != n - 1)printf("-1");
	else printf("%d", ans);
}

判断村村通还有一种方法：就是通过寻找这一个集合的代表数量来判断是否达到村村通。如果寻找到的代表数量是一个的话，那就是达到了，如果有多个就是没有达到。