文章目录
第一次算法作业
Problem A. 思维之花-方程
时间限制 1000 ms
内存限制 128 MB
题目描述
有形如：ax^3+bx^2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值> =1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1< x2，f(x1)*(x2)< 0，则在(x1，x2)之间一定有一个根。
输入数据
输入该方程中各项的系数 (a,b,c,d (a,b,c,d 均为实数)，
输出数据
由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 22 位。
样例输入
1 -5 -4 20
样例输出
-2.00 2.00 5.00
#include <iostream>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
double a, b, c, d;
#define f(x) (a*(x)*(x)*(x)+b*(x)*(x)+c*(x)+d)
void ef(double s, double e)
{
if (f(s) * f(e) <= 0)
{
double mid = (s + e) / 2.0;
if (fabs(f(mid)) <= 1e-8)
{
cout<<setiosflags(ios::fixed) << setprecision(2) << mid << " ";
return;
}
if (f(mid) * f(s) < 0)
ef(s, mid);
else
ef(mid, e);
}
}
int main()
{
cin >> a >> b >> c >> d;
for (double s = -101; s <= 101; s += 1)
{
ef(s, s + 1);
}
return 0;
}
Problem C. 课堂作业-7-1
时间限制 1000 ms
内存限制 64 MB
题目描述
有n根小木棒，任选三根木棒组成一个三角形，问三角形周长最大是多少。（保证至少存在一种选法能组成三角形）
输入数据
第一行为一个正整数n，3=<n<=100 第二行为n个正整数，代表小木棒长度，不超过100.
输出数据
三角形周长的最大值
样例输入
5
1 2 3 4 5
样例输出
12
解法1：
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX_N = 105;
int cmp(const void* a, const void* b)
{
return *(int*)a - *(int*)b;
}
void solve(int n, int* a)
{
qsort(a, n, sizeof(a[0]), cmp);
int sum = 0;
for (int i = n - 1; i > 1; --i)
{
if (a[i] + a[i - 1] > a[i - 2])
if (a[i] + a[i - 2] > a[i - 1])
if (a[i - 1] + a[i - 2] > a[i])
{
sum = a[i] + a[i - 1] + a[i - 2]; break;
}
}
cout << sum;
}
int main()
{
int n, a[MAX_N];
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
solve(n, a);
return 0;
}
第二次算法作业
Problem A. 课堂作业-6-1
时间限制 1000 ms
内存限制 64 MB
题目描述
如果一个质数能被表示为三个不同的质数的和的形式，那么我们称它为立方质数。现在给你一个数n，判断它是不是立方质数。
输入数据
正整数n，n<=1000
输出数据
Yes或者No
样例输入
19
样例输出
Yes
解法1
#include <iostream>
#include <cmath>
using namespace std;
//判断是否为质数
bool isPrime(int num) {
if (num <= 3) {
return num > 1;
}
// 不在6的倍数两侧的一定不是质数
if (num % 6 != 1 && num % 6 != 5) {
return false;
}
for (int i = 5; i <= sqrt(num); i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
bool flag = false;
if (!isPrime(n)) {
cout << "No" << endl;
}
else {
for (int i = 1; i <= n; i++) {
if (isPrime(i)) {
for (int j = i + 1; j <= n; j++) {
if (isPrime(j) && isPrime(n - i - j) && (n - i - j) != i && (n - i - j) != j) {
flag = true;
}
}
}
}
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
Problem B. 课堂作业-5-1
时间限制 1000 ms
内存限制 64 MB
题目描述
有n盏灯，编号都是1-n，初始灯都是关着的。有n个人，第1个人会打开所有的灯，第2个人会按下所有编号为2的倍数的灯的开关（这些灯将被关掉），第3个人会按下所有编号为3的倍数的开关，以此类推，第n个人会按下所有编号为n的倍数的开关。问最后有几盏灯是亮着的。
输入数据
一个正整数n，n<100000
输出数据
亮着的灯的数量
样例输入
5
样例输出
2
解法1：
#include <iostream>
using namespace std;
int check(int x) {
int cnt = 0;
int i;
for (i = 1; i * i < x; ++i) {
if (!(x % i)) {
cnt += 2;
}
}
if (i * i == x) {
++cnt;
}
return cnt;
}
int main() {
int n;
cin >> n;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (check(i) % 2) {
++cnt;
}
}
cout << cnt << endl;
return 0;
}
解法2：
# include "iostream"
# include "vector"
# include "numeric"
using namespace std;
#define MAX_SIZE 100000
int main(){
int n;
cin >>n;
vector<int> p(n+1, 1);
for(int i = 2; i <= n; i++){
for(int j = 1; j*i <= n; j++){
if(p[j*i] == 1)
p[j*i] = 0;
else
p[j*i] = 1;
}
}
p[0] = 0;
cout << accumulate(p.begin(), p.end(), 0) << endl; // 累加范围，和累加初值
return 0;
}
解法3：
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
int i = 1;
for(; i * i <= n; i++){}
cout << i - 1 << endl;
return 0;
}
Problem C. 课堂作业-4-4
时间限制 1000 ms
内存限制 64 MB
题目描述
小明刚买了一个机械键盘，但他在用机械键盘打字的时候发现键盘的Home键和End键坏掉了，于是他在打字的时候光标有时会突然跑到行首，有时又会突然跑到行尾，现在给你键盘的输入，求最后屏幕上的字符串。
输入数据
输入数据为一行字符串，字符串只包含小写英文字母,’[‘符号以及’]‘符号，’['代表按下了Home键，‘]’代表按下了End键，字符串长度不超过100000。
输出数据
输出最后屏幕上的字符串。
样例输入
xiechengxuz[henhao]wan
样例输出
henhaoxiechengxuzwan
样例说明
可能出现多个’[‘和’]’，也可能没有’[‘和’]’
解法1：
# include <iostream>
# include <string>
# include <queue>
using namespace std;
deque<string> q;
string buf;
void fun(int flag, string& buf) {
if (flag)
q.push_back(buf);
else
q.push_front(buf);
buf.clear();
}
int main() {
string s;
cin >> s;
int flag = 0;// flag=0,放在前面； flag =1, 放在后面
for (int i = 0; i < s.length(); i++)
{
if (s[i] != '[' && s[i] != ']') {
buf += s[i];
}else if (s[i] == '[') {
fun(flag, buf);
flag = 0;
}
else {
fun(flag, buf);
flag = 1;
}
}
fun(flag, buf);
for (auto i : q)
cout << i;
}
Problem D. Superprime
时间限制 1000 ms
内存限制 128 MB
题目描述
农民约翰的母牛总是生产出最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。
农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说:
7 3 3 1
全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。
7331 被叫做长度 4 的特殊质数。
写一个程序对给定的肋骨的数目 N (1< =N< =8),求出所有的特殊质数。数字1不被看作一个质数。
输入数据
单独的一行包含 N 。
输出数据
按顺序输出长度为 N 的特殊质数,每行一个。
并按大小顺序排列(从小到大).
样例输入
4
样例输出
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
解法1：
#include<iostream>
#include<cmath>
#include <queue>
using namespace std;
bool isPrime(int num) { //判断是否为质数
if (num <= 3) {
return num > 1;
}
if (num % 6 != 1 && num % 6 != 5) { // 不在6的倍数两侧的一定不是质数
return false;
}
for (int i = 5; i <= sqrt(num); i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
int main() {
queue <int> q;
int n, m = 4;
int a[] = { 2,3,5,7 }; // 单独一个数是质数
int b[] = { 1,3,7,9 }; //一这些数字为结尾的，可能是质数
cin >> n;
for (int i = 0; i < 4; i++) q.push(a[i]);
for (int i = 2; i <= n; i++) {
int l = m;
m = 0;
for (int j = 0; j < l; j++) {
for (int k = 0; k < 4; k++) //选择枚举b[k]
if (isPrime(q.front() * 10 + b[k]))
q.push(q.front() * 10 + b[k]), m++;
q.pop();
}
}
while (!q.empty()) {
cout << q.front() << endl;
q.pop();
}
return 0;
}
解法2
#include <iostream>
#include <vector>
using namespace std;
int mn = 1, mx = 1;
vector<int> bones;
bool isprime(int x) {
if (x == 2) {
return true;
}
if (x == 1 || !(x % 2)) {
return false;
}
for (int i = 3; i * i <= x; i += 2) {
if (!(x % i)) {
return false;
}
}
return true;
}
void dfs(int x) {
if (x >= mn && x < mx) {
bones.push_back(x);
return;
}
x *= 10;
for(int i = 1; i < 10; ++i) {
if (isprime(x + i)) {
dfs(x + i);
}
}
}
int main() {
int n;
cin >> n;
while (--n) {
mn *= 10;
mx = mn;
}
mx *= 10;
dfs(0);
for (int i : bones) {
cout << i << endl;
}
return 0;
}
Problem E. 整数变换
时间限制 1000 ms
内存限制 128 MB
题目描述
给出一个小于2^32的正整数。这个数可以用一个32位的二进制数表示（不足32位用0补足）。我们称这个二进制数的前16位为“高位”，后16位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。
例如，数1314520用二进制表示为0000 0000 0001 0100 0000 1110 1101 1000（添加了11个前导0补足为32位），其中前16位为高位，即0000 0000 0001 0100；后16位为低位，即0000 1110 1101 1000。将它的高低位进行交换，我们得到了一个新的二进制数0000 1110 1101 1000 0000 0000 0001 0100。它即是十进制的249036820。
输入数据
一个小于 232232 的正整数
输出数据
将新的数输出
样例输入
1314520
样例输出
249036820
解法1：
#include<iostream>
using namespace std;
int main()
{
unsigned long long x;
cin >> x;
cout << ((x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16) << endl;
}
第三次算法作业
Problem A. 课堂作业-6-2
时间限制 1000 ms
内存限制 64 MB
题目描述
我们有n根的木棍。现在从这些木棍中切割出来m条长度相同的木棍，问这m根木棍最长有多长？
输入数据
第一行输入两个数字，n(1<=n<=1000)为木棍数目，m(1<=m<=1000)为需要切割出的相同长度的木棍数目 随后n个正整数，表示原始木棍的长度(<=10000)
输出数据
每组输出一行结果，表示切割后绳子的最长长度(保留两位小数)
样例输入
4 5
5 6 7 8
样例输出
4.00
解法1
#include <iostream>
using namespace std;
#include <vector>
#include <iomanip>
#include <cmath>
int main()
{
int n,m;
cin >>n>> m;
vector<int> v;
double max=0;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
v.push_back(t);
if (t > max)
max = t;
}
double s = 0, e = max;
double mid;
while (s + 0.01 < e) {
int cnt = 0;
mid = round(((s + e) / 2.00) * 100) / 100.00; //四舍五入
for (int i = 0; i < n; i++)
cnt += (double)(v[i] / mid);
if (cnt >= m) s = mid;
else e = mid;
}
cout << setiosflags(ios::fixed) << setprecision(2) << s ;
}
Problem B. 课堂作业-7-2
时间限制 1000 ms
内存限制 64 MB
题目描述
有一条河，河中间有一些石头，已知石头的数量和相邻两块石头之间的距离。现在可以移除一些石头，问最多移除m块石头后（首尾两块石头不可以移除），相邻两块石头之间的距离的最小值最大是多少。
输入数据
第一行输入两个数字，n（2<=n<=1000）为石头的个数，m（0<=m<=n-2）为可移除的石头数目 随后n-1个数字，表示顺序和相邻两块石头的距离d（d<=1000）
输出数据
输出最小距离的最大值
样例输入
4 1
1 2 3
样例输出
3
解法1：
#include <stdio.h>
int n, m,ans;
int d[1005];
int l[1005] = { 0 };
int main() {
scanf("%d%d", &n, &m);
for (int i = 2; i <= n; i++) {
scanf("%d", &d[i]);
l[i] = d[i] + l[i - 1];
}
int left=0,right=l[n];
while(left<=right)
{
int now=0,mid=(left+right)>>1,s=0;
for(int i=2;i<=n;++i)
{
if(l[i]-l[now]<mid) ++s;
else now=i;
}
if(s>m) right=mid-1;
else
{
ans=mid;
left=mid+1;
}
}
printf("%d",ans);
return 0;
}
Problem C. 课堂作业-9-1
时间限制 1000 ms
内存限制 64 MB
题目描述
楼梯有n阶，可以一步上一阶、两阶或三阶，问有多少种不同的走法
由于答案很大，mod(1e9+7)输出
输入数据
一个正整数n，代表楼梯的阶数，n<=1000000
输出数据
方案数
样例输入
3
样例输出
4
解法1
# include <iostream>
# include <cmath>
# include <vector>
using namespace std;
int main() {
long n;
cin >> n;
long long f[3];
f[0] = 1;
f[1] = 2;
f[2] = 4;
int mod = (1e9 + 7);
long long ans;
if (n < 3) {
ans = f[n - 1];
}
else {
for (long i = 3; i < n; i++)
{
long long t;
t = f[0];
f[0] = f[1];
f[1] = f[2];
f[2] = (t + f[0] + f[1]) % mod;
}
ans = f[2];
}
cout << ans;
}
Problem D. 包裹快递
时间限制 1000 ms
内存限制 128 MB
题目描述
一个快递公司要将n个包裹分别送到n个地方，并分配给邮递员小K一个事先设定好的路线，小K需要开车按照路线给的地点顺序相继送达，且不能遗漏一个地点。小K得到每个地方可以签收的时间段，并且也知道路线中一个地方到下一个地方的距离。若到达某一个地方的时间早于可以签收的时间段，则必须在这个地方停留至可以签收，但不能晚于签收的时间段，可以认为签收的过程是瞬间完成的。
为了节省燃料，小K希望在全部送达的情况下，车的最大速度越小越好，就找到了你给他设计一种方案，并求出车的最大速度最小是多少。
输入数据
第 11 行为一个正整数 n (n<2×104)，n (n<2×104)， 表示需要运送包裹的地点数。
下面 nn 行，第 i+1i+1 行有 33 个正整数 xi,yi,si，xi,yi,si， 表示按路线顺序给出第 ii 个地点签收包裹的时间段为 [xi,yi]，[xi,yi]， 即最早为距出发时刻 xi，xi， 最晚为距出发时刻 yi，yi， 从前一个地点到达第 ii 个地点距离为 si，si， 且保证路线中 xixi 递增。
可以认为 s1s1 为出发的地方到第 11 个地点的距离，且出发时刻为 00 。
输出数据
仅包括一个整数，为车的最大速度最小值，结果保留两位小数。
样例输入
3
1 2 2
6 6 2
7 8 4
样例输出
2.00
样例说明
第一段用1的速度在时间2到达第1个地点，第二段用0.5的速度在时间6到达第2个地点，第三段用2的速度在时间8到达第3个地点。
解法1：
#include <stdio.h>
#define maxn 200005
long double st=0,en=1e9,mid;
int i,n;
int v[maxn][3];
bool check(long double x) {
long double minT, totalT=0;
for (int i = 0; i < n; i++) {
minT = v[i][2] / x;
totalT = minT + totalT;
if (totalT < v[i][0])
totalT = v[i][0];
else if (totalT > v[i][1])
return false;
}
return true;
}
int main(){
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d%d%d",&v[i][0], &v[i][1], &v[i][2]);
while(en-st>1e-9){
mid=(en+st)/2.00;
if(check(mid)) en=mid;
else st=mid;
}
printf("%.2f",double(st));
return 0;
}
Problem E. 课堂作业-8-2
时间限制 1000 ms
内存限制 64 MB
题目描述
有ABC三根杆和一些圆盘，开始的时候圆盘从小到大摞在A杆上，小盘在上大盘在下，规定如果圆盘p摞在圆盘q上面，那么rp<=rq，rp和rq为p和q的半径。
现在有若干个圆盘，半径从1到n，半径为i的圆盘有i个，每次操作可以移动一个圆盘，问把所有圆盘从A杆移动到C杆上最少需要几次操作。 由于最终答案可能很大，所以答案对1e9+7取模输出。
输入数据
一个正整数n，n<=1e5
输出数据
最少操作次数
样例输入
2
样例输出
4
样例说明
第一步把半径为1的圆盘从A放到B 第二步和第三步把两个半径为2的圆盘从A放到C 第四步把半径为1的圆盘从B放到C
解法1：
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long cnt=0;
long long mod = 1e9 + 7;
for (long long i = 1; i <= n; i++)
{
cnt =(cnt*2+i)%mod;
}
cout << cnt<<endl;
}
第四次算法作业
Problem A. 采药
时间限制 1000 ms
内存限制 128 MB
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入数据
输入的第一行有两个整数 T (1≤T≤1000) 和 M (1≤M≤100) 用一个空格隔开，T 代表总共能够用来采药的时间 ，M 代表山洞里的草药的数目。接下来的 M 行每行包括两个在 1 到100之间（包括 1 和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出数据
输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2
样例输出
3
解法1
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e4;
int f[maxn]; //f：草药的总价值
int w[maxn], val[maxn]; //w: 时间花费 val:草药价值
void solve(int m, int t) {
memset(f, 0, sizeof f);
for (int i = 1; i <= m; i++) {
for (int v = t; v > 0; v--) {
if (v >= w[i])
f[v] = max(f[v], f[v - w[i]] + val[i]);
}
}
cout << f[t];
}
int main() {
int m, t; //t 采药的时间，m草药的数目
cin >> t >> m;
for (int i = 1; i <= m; i++) {
cin>>w[i] >> val[i] ;
}
solve(m,t);
return 0;
}
Problem B. 装箱问题
时间限制 1000 ms
内存限制 128 MB
题目描述
有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
输入数据
第一行，一个整数，表示箱子容量；
第二行，一个整数，表示有 n 个物品；
接下来 n 行，分别表示这 n 个物品的各自体积。
输出数据
一个整数，表示箱子剩余空间。
样例输入
24
6
8
3
12
7
9
7
样例输出
0
解法1
# include <iostream>
# include <algorithm>
# include <cmath>
using namespace std;
int v;
int n;
int a[35];
int dp[20005];
int main() {
cin >> v >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i=1;i<=n;i++)
for(int j=v;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
int minV = v - dp[v];
cout << minV;
return 0;
}
Problem C. 合唱队形
时间限制 1000 ms
内存限制 128 MB
题目描述
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1< …< Ti> Ti+1> …> TK(1< =i< =K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入数据
输入的第一行是一个整数 N (2≤N≤100)， 表示同学的总数。第一行有 n 个整数，用空格分隔，第 i 个整数 Ti (130≤Ti≤230) 是第 i 位同学的身高(厘米)。
输出数据
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
样例输入
8
186 186 150 200 160 130 197 220
样例输出
4
解法一
# include <iostream>
using namespace std;
int l[105],r[105],h[105],dp[105];
int main() {
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i];
l[i]=r[i]=1;
}
for(int i=n-1;i>=1;i--){
for (int j=i+1;j<=n;j++)
{
if(h[i]>h[j]&&r[i]<=r[j]+1)
r[i]=r[j]+1;
}
}
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
if(h[i]>h[j]&&l[i]<=l[j]+1)
l[i]=l[j]+1;
}
}
int max=0;
for(int i=1;i<=n;i++){
dp[i]=l[i]+r[i]-1;
if(dp[i]>max)
max=dp[i];
}
cout<<n-max;
}
Problem D. 马拦过河卒
时间限制 1000 ms
内存限制 128 MB
题目描述
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入数据
一行四个数据，分别表示 B 点坐标和马的坐标。
输出数据
一个数据，表示所有的路径条数。
样例输入
6 6 3 3
样例输出
6
解法1
#include<iostream>
#define ll long long
using namespace std;
bool a[30][30];
ll dp[30][30];
//B(n,m) ma(x,y)
int main() {
int n, m, x, y;
cin >> n >> m >> x >> y;
dp[1][1] = 1;
n++; m++; x++; y++;
a[x][y] = 1;
a[x - 1][y + 2] = 1;
a[x - 1][y - 2] = 1;
a[x + 1][y + 2] = 1;
a[x + 1][y - 2] = 1;
a[x - 2][y - 1] = 1;
a[x - 2][y + 1] = 1;
a[x + 2][y - 1] = 1;
a[x + 2][y + 1] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++) {
if ((i != 1 || j != 1) && !a[i][j])
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
cout << dp[n][m];
}
Problem E. 传球游戏
时间限制 1000 ms
内存限制 128 MB
题目描述
上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。
游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。
聪明的小蛮提出了一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有三个同学1号、2号、3号，并假设小蛮为1号，球传了三次回到小蛮手里的方式有1-> 2-> 3-> 1和1-> 3-> 2-> 1，共2种。
输入数据
输入共一行，有两个用空格隔开的整数 n,m (3≤n≤30,1≤m≤30)。
输出数据
输出共一行，有一个整数，标示符合题意的方法数。
样例输入
3 3
样例输出
2
样例说明
40%的数据满足：3< =n< =30 1< =m< =20
100%的数据满足：3< =n< =30 1< =m< =30
解法1：
dp[i][j]： 传了i次球，传到编号为j的同学的方法数。
#include<iostream>
using namespace std;
int dp[40][40];
int main() {
int n, m, x, y;
cin >> n >> m;
dp[0][1] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
x = j - 1;
y = j + 1;
if (x == 0) x = n;
if (y == n + 1) y = 1;
dp[i][j] = dp[i - 1][x] + dp[i - 1][y];
}
}
cout << dp[m][1];
}
第五次算法作业
Problem A. 单行最大子矩阵和问题
时间限制 1000 ms
内存限制 64 MB
题目描述
给定1×N的单行矩阵，矩阵每个元素都是-127到+127之间的整数。请找到一个连续子矩阵，使得其元素之和最大。例如行矩阵0 -2 -7 0 -2 11 -4 13 -5 -2，最大子矩阵和为11+(-4)+13=20.
输入数据
多组测试数据，每组数据的第一行为一个整数 N (N<=100)，第二行包含N个整数，为行矩阵的N个元素，每个元素介于-127到127之间。
输出数据
最大子矩阵之和，每组对应一行。
样例输入
10
0 -2 -7 0 -2 11 -4 13 -5 -2
样例输出
20
解法1
#include <stdio.h>
int N;
int a[105];
int main(){
while(scanf("%d",&N)!=EOF){
for(int i=0;i<N;i++ ){
scanf("%d",&a[i]);
}
int sum=0;
int max=a[0];
for(int i=0;i<N;i++){
sum+=a[i];
if(sum<0)
sum=0;
if(sum>max)
max=sum;
}
printf("%d\n",max);
}
}
Problem B. 多行最大子矩阵和问题
时间限制 1000 ms
内存限制 64 MB
题目描述
给定N×N矩阵，矩阵元素都是-127到+127之间的整数。请找到一个子矩阵，使得其元素之和最大。例如给定4*4矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 最大子矩阵为 9 2 -4 1 -1 8 最大子矩阵和为9+2+（-4）+1+（-1）+8 = 15.
输入数据
多组测试数据，每组测试数据的第一行整数 N (N<=100)。接下来N行元素，每行N个元素，每个元素介于-127到127之间。
输出数据
最大子矩阵元素之和，每组测试数据对应一行。
样例输入
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
样例输出
15
解法1
#include <stdio.h>
#include <string.h>
int n;
int a[105][105];
int temp[105];
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++ ){
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}
int max=-32767;
for(int i=0;i<n;i++){
memset(temp,0,sizeof(temp));
for(int j=i;j<n;j++){
int sum=0; int tempmax=-32767;
for(int k=0;k<n;k++){
temp[k]+=a[j][k];
sum+=temp[k];
if(sum<0) sum=0;
if(sum>tempmax) tempmax=sum;
}
if(tempmax>max) max=tempmax;
}
}
printf("%d\n",max);
}
}
Problem C. 小明的打工计划
时间限制 2000 ms
内存限制 64 MB
题目描述
作为一个有很多游戏想买但囊中羞涩的大学生，小明决定在这个暑假开始打工赚钱。经过一段时间的寻找，他一共找到了n个打工的招聘广告，其中第i个打工的日期从li开始，到ri为止，一共付给他ci元钱。因为这些打工的时间都相互冲突，所以同一天小明最多参加一个打工，并且一个打工一旦开始，就必须一直工作到结束，不能中途退出。现在小明想要知道，这个暑假他打工最多能得到多少钱？
输入数据
第一行一个整数n(1≤n≤10000001≤n≤1000000)，表示招聘广告的数量。 接下来一共n行，每行3个整数li,ri,ci(1≤li≤ri≤1000000,1≤ci≤10000000001≤li≤ri≤1000000,1≤ci≤1000000000)，表示打工的开始时间，结束时间和报酬。
输出数据
一行一个整数k，表示小明最多能够得到的钱数。
样例输入
3
1 2 3
3 4 3
2 3 5
样例输出
6
解法1
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
struct job{
int l,r,w;
}a[1100000];
long long f[1100000];
int n,id;
bool cmp(job x,job y){
return (x.r<y.r )||(x.r==y.r && x.l<y.l);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r>>a[i].w;
}
sort(a+1,a+n+1,cmp);
id=1;
for(int i=1;i<=a[n].r;i++){
f[i]=f[i-1];
while(i==a[id].r&&id<=n){ // 可能有多个项目的结束时间一致
f[i]=max(f[i],f[a[id].l-1]+a[id].w);
id++;
}
}
cout<<f[a[n].r];
}
Problem D. 邮票面值设计
时间限制 1000 ms
内存限制 128 MB
题目描述
给定一个信封，最多只允许粘贴N张邮票，计算在给定M（N+M< =10）种邮票的情况下（假定所有的邮票数量都足够）,如何设计邮票的面值，能得到最大max ，使得1～max之间的每一个邮资值都能得到。
例如，N=3，M＝2，如果面值分别为1分、4分，则在l分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，M＝2时，7分就是可以得到连续的邮资最大值，所以MAX=7，面值分别为l分、3分。
样例输入：共一行，两个整数，分表为N与M的值。
输入数据
一行，分别为 N,M。
输出数据
两行。
第一行为 mm 种邮票的面值，按升序排列，各数之间用一个空格隔开。
第二行为最大值。
样例输入
3 2
样例输出
1 3
max=7
题解1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
int m,n,ans,a[1005],b[1005],s[1005];
int stamp(int t)
{
int i,res;
for (i=1; i<=1000; i++) b[i]=1e6;
for (i=1; i<=t; i++) b[a[i]]=1;
res=0;
do
{
res++;
for (i=1; i<=t; i++)
if (res>a[i] && b[res-a[i]]+1<b[res])
b[res]=b[res-a[i]]+1;
}while (b[res]<=m);
return res;
}
void find(int i)
{
int k,z;
z=stamp(i-1);
if (i>n)
{
int ii;
if (z-1>ans)
{
ans=z-1;
for (ii=2; ii<=n; ii++) s[ii]=a[ii];
}
return;
}
for (k=z; k>=a[i-1]+1; k--)
{
a[i]=k;
find(i+1);
}
}
int main()
{
int i;
cin>>m>>n;
a[1]=1;
find(2);
s[1]=1;
for (i=1; i<n; i++)
cout<<s[i]<<" ";
cout<<s[i];
cout<<endl;
cout << "MAX=" << ans<< endl;
return 0;
}
Problem E. 导弹拦截
时间限制 1000 ms
内存限制 128 MB
题目描述
某国为了防御敌国的导弹袭击，研发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试验阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入数据
输入数据只有一行，该行包含若干个数据，之间用半角逗号隔开，表示导弹依次飞来的高度（导弹最多有 20枚，其高度为不大于 3×103 的正整数）。
输出数据
输出数据只有一行，该行包含两个数据，之间用半角逗号隔开。第一个数据表示这套系统最多能拦截的导弹数；第二个数据表示若要拦截所有导弹至少要再添加多少套这样的系统。
样例输入
389,207,155,300,299,170,158,65
样例输出
6,1
解法1
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], d1[N], d2[N], n;
int main() {
char ch;
int n=0;
while (1){
cin >> a[++n];
ch= getchar();
if(ch=='\n') break;
};
int len1 = 1, len2 = 1; //初始长度为1
d1[1] = a[1]; //用于求不上升序列长度
d2[1] = a[1]; //用于求上升序列长度
for (int i=2; i<=n; i++) { //从a[2]开始枚举每个数(a[1]已经加进去了)
if (d1[len1] >= a[i]) d1[++len1] = a[i]; //如果满足要求(不上升)就加入d1
else { //否则用a[i]替换d1中的一个数
int p1 = upper_bound(d1 + 1, d1 + 1 + len1, a[i], greater<int>()) - d1;
d1[p1] = a[i];
}
if (d2[len2] < a[i]) d2[++len2] = a[i]; //同上
else {
int p2 = lower_bound(d2 + 1, d2 + 1 + len2, a[i]) - d2;
d2[p2] = a[i];
}
}
cout << len1 <<"," << len2-1; //输出
return 0; //结束
}
第六次算法作业
Problem A. 合并果子
时间限制 1000 ms
内存限制 128 MB
题目描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
输入数据
输入包括两行，第一行是一个整数 n (1<＝n<103)，n (1<＝n<103)， 表示果子的种类数。第二行包含 n 个整数，用空格分隔，第 i个整数 ai (1<＝ai<2×103) 是第 ii 种果子的数目。
输出数据
输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 231。
样例输入
3
1 2 9
样例输出
15
解法1
#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
int n;
int a[maxn];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
priority_queue<int, vector<int>, greater<int>> que;
for(int i = 0; i<n; i++){
cin>>a[i];
que.push(a[i]);
}
if(n==1){
cout<<0;
return 0;
}
int ans = 0;
while(!que.empty()){
int t1 = que.top(); que.pop();
int t2 = que.top(); que.pop();
ans+=t1+t2;
if(que.empty())break;
que.push(t1+t2);
}
cout<<ans;
return 0;
}
Problem B. 最小差距
时间限制 1000 ms
内存限制 128 MB
题目描述
给定一些不同的一位数字，你可以从这些数字中选择若干个，并将它们按一定顺序排列，组成一个整数，把剩下的数字按一定顺序排列，组成另一个整数。组成的整数不能以0开头（除非这个整数只有1位）。
例如，给定6个数字，0,1,2,4,6,7，你可以用它们组成一对数10和2467，当然，还可以组成其他的很多对数，比如210和764，204和176。这些对数中两个数差的绝对值最小的是204和176，为28。
给定N个不同的0~9之间的数字，请你求出用这些数字组成的每对数中，差的绝对值最小的一对（或多对）数的绝对值是多少？
输入数据
第一行包括一个数 T (T≤1000), 为测试数据的组数。
每组数据包括两行，第一行为一个数 N (2≤N≤10)， 表示数字的个数。下面一行为 N 个不同的一位数字。
输出数据
T 行，每行一个数，表示第 i 个数据的答案。即最小的差的绝对值。
样例输入
2
6
0 1 2 4 6 7
4
1 6 3 4
样例输出
28
5
解法1
#include<bits/stdc++.h>
using namespace std;
int n;
int a[12];
int vis[12];
void solve(){
cin>>n;
for(int i = 1; i<=n; i++) cin>>a[i];
sort(a+1, a+n+1);
if(n==2){
cout<<a[2]-a[1]<<'\n';
return;
}
if(n&1){
if(a[1]==0) swap(a[1], a[2]);
int x = 0;
for(int i = 1; i<=n/2+1; i++) x = 10*x+a[i];
int y = 0;
for(int i = n; i>=n/2+2; i--) y = 10*y+a[i];
cout<<abs(x-y)<<'\n';
return;
}
int ret = 1e9;
for(int i = 2; i<=n; i++) {
if(a[i-1]==0) continue;
memset(vis, 0, sizeof(vis));
int x = a[i], y = a[i-1];
int l = 1, r = n;
vis[i] = vis[i-1] = 1;
for(int j = 1; j<=n/2-1; j++){
while(vis[l]) l++;
while(vis[r]) r--;
x = 10*x+a[l];
y = 10*y+a[r];
vis[l] = vis[r] = 1;
l++, r--;
}
ret = min(ret, abs(x-y));
}
cout<<ret<<'\n';
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int tt; cin>>tt;
while(tt--){
solve();
}
return 0;
}
Problem C. 上帝的爱好
时间限制 1000 ms
内存限制 128 MB
题目描述
我们知道，词都是按照词牌来填的，上帝为了考验小杉，只给了他四种词牌，但只要压韵就算符合词牌。
小杉已经想好了N个意境优美的句子，每个句子都有一个韵脚。
符合要求的词的句式应当有如下四种" XXYY" ，" XYXY" ，" XYYX" ，" XXXX" ，其中X或Y表示韵脚。
现在小杉想知道，从他想的N个句子之中，最多能按顺序挑选出几首符合条件的词。
并且词的句子间不能交错，比如你选了1 4 6 8做为一首诗，那么7你就不能再选了。
输入数据
每组测试数据的
第一行有一个数 N (N≤4000)。
第二行有N个不超10^{3}的正整数，第i个整数表示第i个句子的韵脚，整数相同表示韵脚相同。
3030 的数据 N≤100N≤100
输出数据
对每组测试数据输出一行，仅有一个数字，表示小杉最多能挑出几首词来。
样例输入
12
1 2 4 2 3 1 2 2 1 1 2 2
样例输出
2
样例说明
样例最多可以挑出两首词，一种方案如下：
1 2 4 6/9 10 11 12
解法1
#include <iostream>
using namespace std;
int a[10000];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int s=0;
int cnt=0;
int j;
int ans=0;
for(int i=0;i<n;i++){
for(j=s;j<i;j++){
if(a[i]==a[j]){
cnt++;
a[i]=a[j]=0; //标记已用
break;
}
}
if(cnt==2){ //两对相同的数
cnt =0;
s=i;
ans++;
}
}
cout<<ans;
return 0;
}
Problem D. 任务调度问题
时间限制 1000 ms
内存限制 128 MB
题目描述
一个单位时间任务是恰好需要一个单位时间完成的任务。给定一个单位时间任务的有限集S。关于S 的一个时间表用于描述S 中单位时间任务的执行次序。时间表中第1 个任务从时间0 开始执行直至时间1 结束，第2 个任务从时间1 开始执行至时间2 结束，…，第n个任务从时间n-1 开始执行直至时间n结束。具有截止时间和误时惩罚的单位时间任务时间表问题可描述如下：
(1) n 个单位时间任务的集合S={1,2,…,n}（n≤500）
(2) 任务i的截止时间d[i], 1≤i≤n, 1≤d[i]≤n，即要求任务i在时间d[i]之前结束；
(3) 任务i 的误时惩罚1≤w[i]< 1000,1≤i≤n,即任务i 未在时间d[i]之前结束将招致w[i]的惩罚；若按时完成则无惩罚。
任务时间表问题要求确定S 的一个时间表（最优时间表）使得总误时惩罚达到最小。
输入数据
第一行是正整数 n， 表示任务数。接下来的 2 行中，每行有 n个正整数，分别表示各任务的截止时间和误时惩罚。
输出数据
将计算出的最小总误时惩罚输出
样例输入
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
样例输出
50
解法1
#include <iostream>
#include <algorithm>
using namespace std;
struct task{
int d,w;
}a[505];
bool cmp(task t1,task t2)
{
return t1.w>t2.w;
}
int main(){
int d[505];
int w[505];
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i].d;
int total=0;
for(int i=0;i<n;i++)
{
cin>>a[i].w;
total+=a[i].w;
}
sort(a,a+n,cmp);
int flag[505]={0};
int ans=0;
for(int i=0;i<n;i++){
for(int j=a[i].d-1;j>=0;j--){
if(flag[j]==0){
ans+=a[i].w;
flag[j]=1;
break;
}
}
}
cout<<total-ans;
return 0;
}
Problem E. sqy 的锡纸烫
时间限制 1000 ms
内存限制 64 MB
题目描述
前不久 sqy 老师花了大价钱，去做了一个帅气的锡纸烫。有着商业眼光的 sqy 一下子发现了大商机，于是他自己开了一家美容美发店。
sqy 找了刚刚做完纹理烫的大预言家 cbj 预测了未来，发现每个顾客都只在白天来美发店，并且第一次来店里的时候都会充一次价值 xi 的卡，然后从第二天开始，每天白天都会来这里打理头发，而 sqy 仅收取成本价 1 元钱来吸引顾客，直到把卡掏空为止，这个顾客就再也不会回来。
黑心商人 sqy 找大预言家要来了每个顾客的充卡时间和充值金额，他准备在某一天晚上跑路，他想知道自己最多能卷走多少钱。
输入数据
第一行包括一个整数 n(1≤n≤105)表示有 n 个顾客。 接下来共 n 行，每i+1行包括两个整数 xi,yi 表示第 xi 天一个顾客来充值了 yi 元 (1≤xi≤106,0≤yi≤231−1)。
输出数据
输出一行包括一个整数 ans, 表示 sqy 最多能卷走多少钱。
样例输入
5
1 5
2 5
3 5
4 5
5 5
样例输出
15
样例说明
在第五天的时候，第一个人消费4元还剩1元，第二个人消费3元还剩2元，第三个人消费2元还剩3元，第四个人消费1元还剩4元，第五个人还没有开始消费就被卷钱跑路了。
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAX 1000010
using namespace std;
long long my_min(long long a,long long b){
if(a<b) return a;
else return b;
}
long long my_max(long long a,long long b){
if(a<b) return b;
else return a;
}
long long in[MAX];//收益
long long out[MAX]; //花费
long long ans =0;
int main(){
for (int i=0;i<1000010;i++)
in[i] = out[i] = 0;
long long n;
scanf("%lld",&n);
long long day,income;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&day,&income);
in[day]+=income;
out[day+1]--;
long long leave=my_min(day+income+1,MAX);
out[leave] ++;
}
long long cur_out=0;//当天理发人数
long long cur_in=0;//当天收益
for(int i=1;i<=MAX-10;i++){
cur_out+=out[i];
cur_in=cur_in+in[i]+cur_out;
ans=my_max(ans,cur_in);
}
printf("%lld",ans);
return 0;
}
第七次算法作业
Problem A. 海战
时间限制 1000 ms
内存限制 128 MB
题目描述
在这个著名的游戏中，在一个方形的盘上放置了固定数量和形状的船只，每只船却不能碰到其它的船。在这个题中，我们仅考虑船是方形的，所有的船只都是由图形组成的方形。编写程序求出该棋盘上放置的船只的总数。
输入数据
输入文件头一行由用空格隔开的两个整数 R 和 C 组成 ，1≤R,C≤1000，，1≤R,C≤1000， 这两个数分别表示游戏棋盘的行数和列数。接下来的 R 行每行包含 C 个字符，每个字符可以为“#”，也可为“.”，“#”表示船只的一部分，“.”表示水。
输出数据
为每一个段落输出一行解。如果船的位置放得正确（即棋盘上只存在相互之间不能接触的方形，如果两个“#”号上下相邻或左右相邻却分属两艘不同的船只，则称这两艘船相互接触了）。就输出一段话“There are S ships.”,S表示船只的数量。否则输出“Bad placement.”。
样例输入
6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#
样例输出
There are 5 ships.
方法1
- 从左到右，从上到下进行遍历，如果是”#“（说明可能出现方形），则以该点作为基准点S(i,j)进行，进入下一步的判断
- 以基准点向右，向下扫描单行和单列，找到连续出现”#“最大长度y和宽度x。
- 判断以(i,j)为左上角的顶点，长宽分别为x,y的区域是否为方形，以及是否与其他的区域相邻，即是否满足如下的两个条件
- 遍历i+1~i+x-1行，每一行连续的宽度==x 以及该行j-1列的值！=’#‘
- 遍历j~j+x-1列，每一列连续的长度==y以及该列j-1列的值！=’#‘
- 如果不满足，则输出Bad Placement, 否则ans++
#include<iostream>
using namespace std;
char a[1000][1000];
int r, c;
int ans = 0;
int check(int i, int j) {
int m,n;
int x=0, y=0;//行，数
for (m = i; m < r && a[m][j] == '#'; m++) {
if (j > 0 && a[m][j - 1] == '#')
break;
x++;
}
for (n = j; n < c && a[i][n] == '#'; n++) {
if (i > 0 && a[i - 1][n] == '#')
break;
y++;
}
for (m = i; m < i + x; m++) {
int tx = 0;
for (n = j; n < c && a[m][n]=='#'; n++) {
tx++;
}
if (tx != y)
return 0;
}
for (n = j; n < j + y; n++) {
int ty = 0;
for (m = i; m < r&&a[m][n]=='#'; m++) {
ty++;
}
if (ty != x)
return 0;
}
for (m = i; m < i + x; m++)
for (n = j; n < j + y; n++)
a[m][n] = '.';
ans++;
return 1;
}
int main() {
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (a[i][j] == '#') {
int flag = check(i, j);
if (flag == 0) {
cout << "Bad placement." << endl;
return 0;
}
}
}
}
cout << "There are " << ans << " ships." << endl;
return 0;
}
方法2
方法1的check 函数复杂度高，每一行和每一列都要进行遍历。方法2则通过寻找子结构来简化判断。可以发现在任意一个2*2的区域内如果出现了3个#, 则一定是有船相邻。方法2对check 进行优化。
#include<iostream>
using namespace std;
char a[1000][1000];
int r, c;
int ans = 0;
int check(int i, int j) {
int cnt=0;
if(g[x][y]=='#') cnt++;
if(g[x+1][y]=='#') cnt++;
if(g[x][y+1]=='#') cnt++;
if(g[x+1][y+1]=='#') cnt++;
return cnt==3;
}
int main() {
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (a[i][j] == '#') {
int flag = check(i, j);
if (flag == 0) {
cout << "Bad placement." << endl;
return 0;
}
}
}
}
cout << "There are " << ans << " ships." << endl;
return 0;
}
方法3
方法3则是通过dfs算法，即每一次深搜的时候把与#连通的所有点改成*因为它们是同一艘船
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int r,c;
char map[1010][1010];
int fx[4]={0,-1,1,0};
int fy[4]={-1,0,0,1};
int dfs(int x,int y){
map[x][y]='*';
for(int i=0;i<4;i++){
if(x+fx[i]>0 && x+fx[i]<=r && y+fy[i]>0 && y+fy[i]<=c && map[x+fx[i]][y+fy[i]]=='#') dfs(x+fx[i],y+fy[i]);
}
} //把与#连通的所有点改成*因为它们是同一艘船
int check(int i, int j) {
int cnt=0;
if(g[x][y]=='#') cnt++;
if(g[x+1][y]=='#') cnt++;
if(g[x][y+1]=='#') cnt++;
if(g[x+1][y+1]=='#') cnt++;
return cnt==3;
}
int main(){
scanf("%d%d",&r,&c);
int i,j;
for(i=1;i<=r;i++){
for(j=1;j<=c;j++){
cin>>map[i][j];
}
}
int s=0;
for(i=1;i<=r;i++){
for(j=1;j<=c;j++){
if(i<r&&j<c&&check(i,j)==0){
printf("Bad placement.");
return 0; //不合法后面就没必要继续了
}
}
}
for(i=1;i<=r;i++){
for(j=1;j<=c;j++){
if(map[i][j]=='#'){
s++;
dfs(i,j);
}//因为前面已经确保了是合法的，现在只需统计船的数量
}
}
printf("There are %d ships.",s);
return 0;
}
Problem B. 课堂作业-9-2
时间限制 1000 ms
内存限制 64 MB
题目描述
在一个被分成n*n个格子的平原上，有一些格子有铁矿，两格铁矿如果相邻那么就认为他们属于同一个矿床，每个矿床都包含一个或更多个铁矿，问一共有几个矿床。
两个格子只要有公共边或公共点就算相邻。
输入数据
第一行为一个正整数n，n<=1000 接下来有n行，每行有n个字符，表示平原的对应位置有没有铁矿，*代表没有，#代表有
输出数据
矿床个数
样例输入
6
*#*###
###*#*
*##***
*#****
***###
******
样例输出
2
样例说明
最下面三块铁矿属于一个矿床，其他铁矿属于一个矿床，所以一共有两个矿床
方法1
典型的dfs, 每次搜索周围的8个点
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
int n;
string a[maxn];
int di[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dj[] = {1, -1, 0, 0, 1, -1, 1, -1};
bool inB(int i, int j){
return 1<=i&&i<=n&&1<=j&&j<=n;
}
void dfs(int i, int j){
a[i][j] = '*';
for(int k = 0; k<8; k++){
int ii = i+di[k], jj = j+dj[k];
if(!inB(ii, jj)||a[ii][jj]=='*') continue;
dfs(ii, jj);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i = 1; i<=n; i++){
cin>>a[i];
a[i] = " "+a[i];
}
int cnt = 0;
for(int i = 1; i<=n; i++){
for(int j = 1; j<=n; j++){
if(a[i][j]=='*') continue;
cnt++;
dfs(i, j);
}
}
cout<<cnt;
return 0;
}
Problem C. 课堂作业-9-4
时间限制 1000 ms
内存限制 64 MB
题目描述
众所周知，八皇后问题是一个非常经典的算法问题，现在将题目改为在n*m的棋盘上，放min(n,m)个互不攻击的皇后，问有多少种放法。
输入数据
两个正整数n,m，n和m均不超过12
输出数据
方案数
样例输入
2 3
样例输出
2
方法1
思路：一行一行得进行摆放，用for循环来确定每一行中摆放的列数。用check判断第j行的摆放位置与1~j-1行不冲突。
#include <iostream>
using namespace std;
int n, m;
int a[15];
int res = 0;
int check(int i, int j) {
int j1 = j, i1 = i, ok1 = 1;
while ((j1 > 1) && ok1) {
j1--;
if (a[j1] == i)
ok1 = 0;
}
j1 = j; i1 = i;
while ((j1 > 1) && (i1 > 1) && ok1) {
j1--; i1--;
if (a[j1] == i1)
ok1 = 0;
}
j1 = j; i1 = i;
while ((j1>1) && (i1 < n) && ok1) {
j1--; i1++;
if (a[j1] == i1)
ok1 = 0;
}
return ok1;
}
void queue(int j) {
if (j > m)
{
res++;
}
else {
for (int i = 1; i <= n; i++) {
if (check(i, j)) {
a[j] = i;
queue(j + 1);
}
}
}
}
int main() {
cin >> n >> m;
int temp;
if (n < m) {
temp = n;
n = m;
m = temp;
}
queue(1);
cout << res;
}
方法2
思路：dfs
一行一行得进行摆放，用for循环来确定每一列,由于是一行一行得摆放所以不可能同行，我们只需要标记同列，同对角线，就行，会发现主对角线一条对角线上的行列和等于同一个常数，副对角线一条对角线行列差等于一个常数，只不过会是负数，防止下标是负数我们可以进行+n。
#include<bits/stdc++.h>
using namespace std;
#define maxn 50
int n, m;
int a[maxn][maxn];
const int bias = 25;
int visc[maxn], vis1[maxn], vis2[maxn];//表示这一列，主对角线，负对角线有没有皇后
int cnt;
void dfs(int i){
if(i>n){
cnt++;
return;
}
for(int j = 1; j<=m; j++){
if(visc[j]||vis1[i+j]||vis2[i-j+bias]) continue;
visc[j] = vis1[i+j] = vis2[i-j+bias] = 1;
dfs(i+1);
visc[j] = vis1[i+j] = vis2[i-j+bias] = 0;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
if(n>m) swap(n, m);
dfs(1);
cout<<cnt;
return 0;
}
Problem D. 课堂作业-8-4
时间限制 1000 ms
内存限制 64 MB
题目描述
给一个n个点，m条边的无向图，和一个起点s，一个终点t，问能不能从s经过一些边走到t，能走到则输出Yes，否则输出No
点的编号从1到n
输入数据
第一行为两个正整数n，m，n<=1e5，m<=1e5 接下来m行每行两个正整数t1，t2，代表t1到t2有一条无向边 最后一行为两个正整数s和t
输出数据
Yes或No
样例输入
3 2
1 2
2 3
1 3
样例输出
Yes
方法1
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int n, m;
vector<int> G[maxn];
int vis[maxn];
void dfs(int u){
if(vis[u]) return;
vis[u] = 1;
for(auto v:G[u]){
dfs(v);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
for(int i = 1; i<=m ;i++){
int u, v; cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
int s, t; cin>>s>>t;
dfs(s);
cout<<(vis[t]?"Yes\n":"No\n");
return 0;
}
Problem E. 24点游戏
时间限制 1000 ms
内存限制 128 MB
题目描述
几十年前全世界就流行一种数字扑克游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1-13（在扑克牌里用A代替1，J代替11，Q代替12，K代替13）之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算（可以使用+、-、*、/、括号），判断运算结果是否等于24。能输出1，不能输出0。
输入数据
四个牌面值。牌面值与牌面值之间用一个空格隔开。
输出数据
输出 0 或 1 。
样例输入
3 8 10 Q
样例输出
1
样例说明
Q×(10/(8-3))=24
方法1
#include <iostream>
#include <vector>
using namespace std;
double nums[4];
int vist[4] = {0};
bool dfs(double res) {
double num;
bool last = true;
for (int i = 0; i < 4; ++i) {
if (!vist[i]) {
vist[i] = true;
num = nums[i];
if (res) {
if (dfs(res + num) || dfs(res - num) || dfs(num - res) ||
dfs(res * num) || dfs(res / num) || dfs(num / res)) {
return true;
}
}
else {
if (dfs(num)) {
return true;
}
}
vist[i] = false;
last = false;
}
}
return last && res == 24;
}
int main() {
string tmp;
for (int i = 0; i < 4; ++i) {
cin >> tmp;
if (tmp == "A") {
nums[i] = 1;
} else if (tmp == "J") {
nums[i] = 11;
} else if (tmp == "Q") {
nums[i] = 12;
} else if (tmp == "K") {
nums[i] = 13;
} else {
nums[i] = atoi(tmp.c_str());
}
}
if (dfs(0)) {
cout << 1 << endl;
} else {
cout << 0 << endl;
}
return 0;
}