统计方形（数据加强版）

题目背景

1997年普及组第一题

题目描述

有一个 \(n \times m\) 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

输入格式

一行，两个正整数 \(n,m\)（\(n \leq 5000,m \leq 5000\)）。

输出格式

一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。

样例 #1

样例输入 #1

1
2 3

样例输出 #1

1
8 10
1
(n-b)*(m-a) 
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
long long n,m,rec,sqr;
int main() {
    cin>>n>>m;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++) {
            if(i==j) sqr+=(n-i)*(m-j);//如果i==j，说明是正方形
            else rec+=(n-i)*(m-j);//如果不等说明是矩形
        }
    cout<<sqr<<" "<<rec<<'\n';
    return 0;
}

烤鸡

题目背景

猪猪 Hanke 得到了一只鸡。

题目描述

猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 \(10\) 种配料（芥末、孜然等），每种配料可以放 \(1\) 到 \(3\) 克，任意烤鸡的美味程度为所有配料质量之和。

现在， Hanke 想要知道，如果给你一个美味程度 \(n\) ，请输出这 \(10\) 种配料的所有搭配方案。

输入格式

一个正整数 \(n\)，表示美味程度。

输出格式

第一行，方案总数。

第二行至结束，\(10\) 个数，表示每种配料所放的质量，按字典序排列。

如果没有符合要求的方法，就只要在第一行输出一个 \(0\)。

样例 #1

样例输入 #1

1
11

样例输出 #1

1
2
3
4
5
6
7
8
9
10
11
10
1 1 1 1 1 1 1 1 1 2 
1 1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 2 1 1 1 
1 1 1 1 1 2 1 1 1 1 
1 1 1 1 2 1 1 1 1 1 
1 1 1 2 1 1 1 1 1 1 
1 1 2 1 1 1 1 1 1 1 
1 2 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1

提示

对于 \(100\%\) 的数据，\(n \leq 5000\)。

暴力枚举，还真是符合呢

恰如其名来形容却是刚刚好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
#define rep(i,a,b) for (int i = a; i <=b; i++)

int main()
{
	int n;
	int ans = 0;
	
	cin >> n;
	rep(a,1,3)rep(b,1,3)rep(c,1,3)rep(d,1,3)rep(e,1,3)
	rep(f,1,3)rep(g,1,3)rep(h,1,3)rep(i,1,3)
	rep(j,1,3)
		if (a+b+c+d+e+f+g+h+i+j==n)
		{
			ans++;
		}
	cout << ans << "\n";
	rep(a, 1, 3)rep(b, 1, 3)rep(c, 1, 3)rep(d, 1, 3)rep(e, 1, 3)
		rep(f, 1, 3)rep(g, 1, 3)rep(h, 1, 3)rep(i, 1, 3)
		rep(j, 1, 3)
		if (a + b + c + d + e + f + g + h + i + j  == n)
		{


			cout << a << " " << b << ' ' << c << ' ' << d << ' ' << e << ' ' << f << ' ' << g << ' ' << h << ' ' << i << ' ' << j  << '\n';
		}

	return 0;
}

三连击（升级版）

题目描述

将 \(1, 2,\ldots, 9\) 共 \(9\) 个数分成三组，分别组成三个三位数，且使这三个三位数的比例是 \(A:B:C\)，试求出所有满足条件的三个三位数，若无解，输出 No!!!。

//感谢黄小U饮品完善题意

输入格式

三个数，\(A,B,C\)。

输出格式

若干行，每行 \(3\) 个数字。按照每行第一个数字升序排列。

样例 #1

样例输入 #1

1
1 2 3

样例输出 #1

1
2
3
4
192 384 576
219 438 657
273 546 819
327 654 981

提示

保证 \(A<B<C\)。

\(\text{upd 2022.8.3}\)：新增加二组 Hack 数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
using namespace std;
int a[10], b1, b2, b3, l, k1, k2, k3, ans;
int main()
{
    cin >> k1 >> k2 >> k3;
    for (int b = 1; b <= 1000 / k3; b++)
    {
        b1 = b * k1;
        b2 = b * k2;
        b3 = b * k3;
        //枚举三个数字
        if (b1>999||b2 > 999 || b3 > 999)break;
        //特判
        for (int c = 1; c <= 3; ++c)
        {
            a[b1 % 10]++;
            b1 /= 10;
        }
        for (int c = 1; c <= 3; ++c)
        {
            a[b2 % 10]++;
            b2 /= 10;
        }
        for (int c = 1; c <= 3; ++c)
        {
            a[b3 % 10]++;
            b3 /= 10;
        }
        //分解3个数字
        for (int c = 1; c <= 9; ++c)if (a[c] != 1) { l = 1; break; }
//进行哈希
        for (int c = 1; c <= 9; ++c)a[c] = 0;
//进行重置
        if (l==0) { cout << b * k1 << " " << b * k2 << " " << b * k3 << "\n"; ans++; }
        else l = 0;
        //注意l重置
    }
    if (!ans)cout << "No!!!";
    //没答案时候输出
}

[NOIP2002 普及组] 选数

题目描述

已知 \(n\) 个整数 \(x_1,x_2,\cdots,x_n\)，以及 \(1\) 个整数 \(k\)（\(k<n\)）。从 \(n\) 个整数中任选 \(k\) 个整数相加，可分别得到一系列的和。例如当 \(n=4\)，\(k=3\)，\(4\) 个整数分别为 \(3,7,12,19\) 时，可得全部的组合与它们的和为：

\(3+7+12=22\)

\(3+7+19=29\)

\(7+12+19=38\)

\(3+12+19=34\)

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：\(3+7+19=29\)。

输入格式

第一行两个空格隔开的整数 \(n,k\)（\(1 \le n \le 20\)，\(k<n\)）。

第二行 \(n\) 个整数，分别为 \(x_1,x_2,\cdots,x_n\)（\(1 \le x_i \le 5\times 10^6\)）。

输出格式

输出一个整数，表示种类数。

样例 #1

样例输入 #1

1
2
4 3
3 7 12 19

样例输出 #1

1
1

提示

【题目来源】

NOIP 2002 普及组第二题

深搜也是暴力的一种（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;
int n,  k;
int a[100000];
long long ans = 0;
bool isprime(int a) {
	if (a == 1)
	{
		return 0;
	}
	for (int i = 2; i * i <= a; i++)
	{
		if (a % i == 0)
			return false;
	}
	return true;
}
//判断
void dfs(int m,int sum,int starx)
{
	if (m==k)
	{
		if (isprime(sum))
		{
			ans++;
		}
		return;
	}
	for (int i = starx; i < n; i++)
	{
		dfs(m + 1, sum + a[i], i + 1);
	}
}
int main()
{

	cin >> n;
	cin >> k;
	for (int i = 0; i <n ; i++)
	{
		cin >> a[i];
	}
	dfs(0, 0, 0);
	cout << ans;
	return 0;
}

组合的输出

题目描述

排列与组合是常用的数学方法，其中组合就是从 \(n\) 个元素中抽出 \(r\) 个元素（不分顺序且 \(r \le n\)），我们可以简单地将 \(n\) 个元素理解为自然数 \(1,2,\dots,n\)，从中任取 \(r\) 个数。

现要求你输出所有组合。

例如 \(n=5,r=3\)，所有组合为：

\(123,124,125,134,135,145,234,235,245,345\)。

输入格式

一行两个自然数 \(n,r(1<n<21,0 \le r \le n)\)。

输出格式

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

注意哦！输出时，每个数字需要 \(3\) 个场宽。以 C++ 为例，你可以使用下列代码：

1
cout << setw(3) << x;

输出占 \(3\) 个场宽的数 \(x\)。注意你需要头文件 iomanip。

样例 #1

样例输入 #1

1
5 3

样例输出 #1

1
2
3
4
5
6
7
8
9
10
1  2  3
  1  2  4
  1  2  5
  1  3  4
  1  3  5
  1  4  5
  2  3  4
  2  3  5
  2  4  5
  3  4  5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
using namespace std;
int n, k;
int a[10000];
void dfs(int step,int flag)
{
	if (step==k)
	{
		for (int i = 0; i < k; i++)
		{
			cout << setw(3) << a[i];
		}
		cout << "\n";
		return;
	}
    //输出过程，不要忘记return 
	if (n-flag<k-step)
	{
		return;
	}
    //如果剩下的数字不够了，那其实没有必要选择了
	for (int i = flag+1; i <=n ; i++)
	{
		a[step] = i;
		dfs(step + 1, i);
	}
}
int main()
{
	cin >> n >> k;
	dfs(0, 0);
}

全排列问题

题目描述

按照字典序输出自然数 \(1\) 到 \(n\) 所有不重复的排列，即 \(n\) 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 \(n\)。

输出格式

由 \(1 \sim n\) 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 \(5\) 个场宽。

样例 #1

样例输入 #1

1
3

样例输出 #1

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

提示

\(1 \leq n \leq 9\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
using namespace std;
int n, a[1000], book[1000];
void dfs(int step)
{
	if (step==n)
	{
		for (int i = 0; i < n; i++)
		{
			cout << setw(5) << a[i];
		}
		cout << "\n";
		return;
	}
	for (int i = 1; i <=n ; i++)
	{
		if (!book[i])
		{
			a[step] = i;//记录答案
			book[i] = 1;//标记为已经用过
			dfs(step+1);//下一层
			book[i] = 0;//恢复现场
		}
	}
}
int main()
{

	cin >> n;
	dfs(0);
	return 0;
}

[NOIP2004 普及组] 火星人

题目描述

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为 \(1,2,3,\cdots\)。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为 \(1,2,3,4\) 和 \(5\)，当它们按正常顺序排列时，形成了 \(5\) 位数 \(12345\)，当你交换无名指和小指的位置时，会形成 \(5\) 位数 \(12354\)，当你把五个手指的顺序完全颠倒时，会形成 \(54321\)，在所有能够形成的 \(120\) 个 \(5\) 位数中，\(12345\) 最小，它表示 \(1\)；\(12354\) 第二小，它表示 \(2\)；\(54321\) 最大，它表示 \(120\)。下表展示了只有 \(3\) 根手指时能够形成的 \(6\) 个 \(3\) 位数和它们代表的数字：

三进制数 代表的数字
\(123\) \(1\)
\(132\) \(2\)
\(213\) \(3\)
\(231\) \(4\)
\(312\) \(5\)
\(321\) \(6\)

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

输入格式

共三行。
第一行一个正整数 \(N\)，表示火星人手指的数目（\(1 \le N \le 10000\)）。
第二行是一个正整数 \(M\)，表示要加上去的小整数（\(1 \le M \le 100\)）。
下一行是 \(1\) 到 \(N\) 这 \(N\) 个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

输出格式

\(N\) 个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。

样例 #1

样例输入 #1

1
2
3
5
3
1 2 3 4 5

样例输出 #1

1
1 2 4 5 3

提示

对于 \(30\%\) 的数据，\(N \le 15\)。

对于 \(60\%\) 的数据，\(N \le 50\)。

对于 \(100\%\) 的数据，\(N \le 10000\)。

noip2004 普及组第 4 题 > 题意就是输出下一个全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int n, m, a[1000000];
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i <m ; i++)
	{
		next_permutation(a + 0, a + n);//无赖做法
	}
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	return 0;


}

自然是有正经做法的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
const int maxn = 10000 + 10;
int n, m, a[maxn], flag, flagx;
bool s[maxn];
void dfs(int step)
{
    if (flagx == 1)
        return;
    if (step > n)
    {
        flag++;
        if (flag == m + 1)//现在到了我们要加上的那个数的全排列的时候，我们就直接地输出，然后标记flagx，一直return，结束程序
        {
            for (int j = 1; j <= n; j++)
                cout<<a[j]<<' ';
    cout<<'\n';
            flagx = 1;
        }
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (flag == 0)i = a[step];//当还在外星人给出的排列这个阶段的时候，我们就直指外星人给出的序列中的数    
        //就是说我一来就来到了外星人这个排列
        if (s[i] == 0)
        {
            s[i] = 1;
            a[step] = i;
            dfs(step + 1);
            s[i] = 0;
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dfs(1);
    return 0;
}

涂国旗

题目描述

某国法律规定，只要一个由 \(N \times M\) 个小方块组成的旗帜符合如下规则，就是合法的国旗。（毛熊：阿嚏——）

  • 从最上方若干行（至少一行）的格子全部是白色的；
  • 接下来若干行（至少一行）的格子全部是蓝色的；
  • 剩下的行（至少一行）全部是红色的；

现有一个棋盘状的布，分成了 \(N\) 行 \(M\) 列的格子，每个格子是白色蓝色红色之一，小 a 希望把这个布改成该国国旗，方法是在一些格子上涂颜料，盖住之前的颜色。

小a很懒，希望涂最少的格子，使这块布成为一个合法的国旗。

输入格式

第一行是两个整数 \(N,M\)。

接下来 \(N\) 行是一个矩阵，矩阵的每一个小方块是W（白），B（蓝），R（红）中的一个。

输出格式

一个整数，表示至少需要涂多少块。

样例 #1

样例输入 #1

1
2
3
4
5
4 5
WRWRW
BWRWB
WRWRW
RWBWR

样例输出 #1

1
11

提示

样例解释

目标状态是：

1
2
3
4
WWWWW
BBBBB
RRRRR
RRRRR

一共需要改 \(11\) 个格子。

数据范围

对于 \(100\%\) 的数据，\(N,M \leq 50\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int a1[55];
int a2[55];
int a3[55];
int main()
{
	int n, m;
	int sum;
	int ans = 99999;
	cin >> n >> m;
	char tmp;
	for (int i = 1; i <=n ; i++)
	{
		for (int j = 1; j <=m ; j++)
		{
			cin >> tmp;
			if (tmp=='W')
			{
				a1[i]++;
			}
			if (tmp == 'B')
			{
				a2[i]++;
			}
			if (tmp == 'R')
			{
				a3[i]++;
			}
		}
	}
    //计数每一行颜色个数
	for (int w = 1; w <=n-2 ; w++)
	{
		for (int b = 1; b <=n-w-1 ; b++)
		{
			sum = 0;
			for (int i = 1; i <=w ; i++)
			{
				sum += m - a1[i];
			}
			for (int i = w+1; i <=w+b ; i++)
			{
				sum += m - a2[i];
			}
			for (int i = w+b+1; i <=n ; i++)
			{
				sum += m - a3[i];
			}
			if (sum<ans)
			{
				ans = sum;
			}
		}
	}
    //枚举两种颜色。从而计算第三种颜色
	cout << ans;
}

First Step (ファーストステップ)

题目背景

知らないことばかりなにもかもが（どうしたらいいの？）
一切的一切 尽是充满了未知数（该如何是好）
それでも期待で足が軽いよ（ジャンプだ！）
但我仍因满怀期待而步伐轻盈（起跳吧！）
温度差なんていつか消しちゃえってね
冷若冰霜的态度 有朝一日将会消失得无影无踪
元気だよ元気をだしていくよ
拿出活力 打起精神向前迈进吧

我们 Aqours，要第一次举办演唱会啦！

虽然学生会长看上去不怎么支持我们的样子，可是有了理事长的支持，我们还是被允许在校内的篮球场里歌唱！

歌曲也好好地准备过了，名字叫“最喜欢的话就没问题！ (ダイスキだったらダイジョウブ！)“，大家一定会喜欢的吧！

演唱会一定会顺利进行的！

希望不要发生停电什么的事故哦……！

题目描述

可是……这个篮球场，好像很久没有使用过的样子啊……

里面堆满了学校的各种杂物呢……

我们 Aqours 的成员要怎么在里面列队站下呢？

我们浦之星女子学院的篮球场是一个 \(R\) 行 \(C\) 列的矩阵，其中堆满了各种学校的杂物 (用 # 表示)，空地 (用 . 表示) 好像并不多的样子呢……

我们 Aqours 现在已经一共有 \(K\) 个队员了，要歌唱舞蹈起来的话，我们得排成一条 \(1\times K\) 的直线，一个接一个地站在篮球场的空地上呢 (横竖均可)。

我们想知道一共有多少种可行的站位方式呢。

Aqours 的真正的粉丝的你，能帮我们算算吗？

输入格式

第一行三个整数 \(R, C, K\)。

接下来的 \(R\) 行 \(C\) 列，表示浦之星女子学院篮球场。

输出格式

总共的站位方式数量。

样例 #1

样例输入 #1

1
2
3
4
5
6
5 5 2
.###.
##.#.
..#..
#..#.
#.###

样例输出 #1

1
8

提示

\(R\) \(C\) \(K\) 备注
\(1\sim2\) \(\leq 10\) \(\leq 10\) \(\leq \min(R,C)\) 无
\(3\sim4\) \(\leq 100\) \(\leq 100\) \(\leq 1\) 无
\(5\sim6\) \(\leq 100\) \(\leq 100\) \(\leq \min(R,C)\) 没有障碍
\(7\sim10\) \(\leq 100\) \(\leq 100\) \(\leq \min(R,C)\) 无

对于所有数据，\(1 \leq R,C \leq 100\)，\(1 \leq k \leq \min(R,C)\)。

以下是彩蛋

在 LoveLive!Sunshine!! 动画第一季第三集中，Aqours 队长高海千歌演唱“最喜欢的话就没问题！”到副歌前时，学校因为雷击停电。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include<iostream>
using namespace std;
int r, c, k, a[500][550], ans,sum;
bool   search1(int x,int y)
{
	if (y+k-1>c)
	{
		return 0;
	}
    //超出
	for (int i = y; i < y+k; i++)
	{
		if (a[x][i]==0)
		{
			return 0;
		}	
	}
	return 1;
    //符合
    //按行找  
}
bool search2(int x, int y)
{
	if (x+k-1>r)
	{
		return 0;
	}
    //超出
	for (int i = x; i <x+k ; i++)
	{
		if (a[i][y]==0)
		{
			return 0;
		}
	}
	return 1;
    //符合
    //按列找
}
int main()
{
	char temp;
	cin >> r >> c >> k;
	for (int i = 1; i <=r ; i++)
	{
		for (int j = 1; j<=c ; j++)
		{
			cin >> temp;
			if (temp=='.')
			{
				a[i][j] = 1;
				sum++;
			}
		}
	}
	//数据预处理
	if (k==1)
	{
		cout << sum;
		return 0;
	}
 //数据特殊处理
	for (int i = 1; i <=r ; i++)
	{
		for (int j = 1; j <=c ; j++)
		{
			if (a[i][j]==1)
			{
				if (search1(i,j))
				{
					ans++;
				}
				if (search2(i,j))
				{
					ans++;
				}
			}
		}
	}
	cout << ans;
	return 0;
}

[USACO1.5] 回文质数 Prime Palindromes

题目描述

因为 \(151\) 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 \(151\) 是回文质数。

写一个程序来找出范围 \([a,b] (5 \le a < b \le 100,000,000)\)（一亿）间的所有回文质数。

输入格式

第一行输入两个正整数 \(a\) 和 \(b\)。

输出格式

输出一个回文质数的列表，一行一个。

样例 #1

样例输入 #1

1
5 500

样例输出 #1

1
2
3
4
5
6
7
8
9
10
11
12
5
7
11
101
131
151
181
191
313
353
373
383

提示

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数（素数）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

题目翻译来自NOCOW。

USACO Training Section 1.5

产生长度为 \(5\) 的回文数：

1
2
3
4
5
6
7
8
for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
     for (d2 = 0; d2 <= 9; d2++) {
         for (d3 = 0; d3 <= 9; d3++) {
           palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
         }
     }
 }

不解释了（）这题出镜率也太高了（）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
		int d1, d2, i, y, q;
	int a1, a2;
	cin >> a1 >> a2;
	for (i = a1; i <= a2; i++)
	{
	    if(i%2==0)
	    {
	        continue;
	    }
	       if(i%3==0)
	    {
	        continue;
	    }
	        if(i%5==0)
	    {
	        continue;
	    }
		d2 = 0;
		d1 = 0;
		for (int x = 2; x * x <= i; x++)
		{
		  
			if (i % x == 0)
			{
				d1 = 1; break;
			}
		}
		y = i;
		int a3 = 0;
		while (y != 0)
		{
			q = y % 10;
			a3 = a3 * 10 + q;
			y = y / 10;
		}

		if (a3 != i) { d2 = 1; }

		if (d1 + d2 == 0)
		{
			cout << i << "\n";
		}
	}
}

[NOIP2008 提高组] 火柴棒等式

题目描述

给你 \(n\) 根火柴棍，你可以拼出多少个形如 \(A+B=C\) 的等式？等式中的 \(A\)、\(B\)、\(C\) 是用火柴棍拼出的整数（若该数非零，则最高位不能是 \(0\)）。用火柴棍拼数字 \(0\sim9\) 的拼法如图所示：

img

注意：

  1. 加号与等号各自需要两根火柴棍；
  2. 如果 \(A\neq B\)，则 \(A+B=C\) 与 \(B+A=C\) 视为不同的等式（\(A,B,C\geq0\)）；
  3. \(n\) 根火柴棍必须全部用上。

输入格式

一个整数 \(n(1 \leq n\leq 24)\)。

输出格式

一个整数，能拼成的不同等式的数目。

样例 #1

样例输入 #1

1
14

样例输出 #1

1
2

样例 #2

样例输入 #2

1
18

样例输出 #2

1
9

提示

【输入输出样例 1 解释】

\(2\) 个等式为 \(0+1=1\) 和 \(1+0=1\)。

【输入输出样例 2 解释】

\(9\) 个等式为

\(0+4=4\)、\(0+11=11\)、\(1+10=11\)、\(2+2=4\)、\(2+7=9\)、\(4+0=4\)、\(7+2=9\)、\(10+1=11\)、\(11+0=11\)。

noip2008 提高第二题

暴力枚举！！！！

就是枚举+拆分数字每一位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int counts[10] = {6,2,5,5,4,5,6,3,7,6};
int f(int n)
{
	if (n==0)
	{
		return 6;
	}
	int ans = 0;
	while (n!=0)
	{
		ans += counts[n % 10];
			n /= 10;
	}
	return ans;
}
int main()
{
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 0; i < 720; i++)
	{
		for (int j = 0; j < 720 ;j++)
		{
			if (f(i) + f(j) + f(i+j) + 4 == n)
			{
				ans++;
			}

		}

	}
	cout <<  ans;
	return 0;
}

妖梦拼木棒

题目背景

上道题中，妖梦斩了一地的木棒，现在她想要将木棒拼起来。

题目描述

有 \(n\) 根木棒，现在从中选 \(4\) 根，想要组成一个正三角形，问有几种选法？

答案对 \(10^9+7\) 取模。

输入格式

第一行一个整数 \(n\)。

第二行往下 \(n\) 行，每行 \(1\) 个整数，第 \(i\) 个整数 \(a_i\) 代表第 \(i\) 根木棒的长度。

输出格式

一行一个整数代表答案。

样例 #1

样例输入 #1

1
2
3
4
5
4 
1
1
2
2

样例输出 #1

1
1

提示

数据规模与约定

  • 对于 \(30\%\) 的数据，保证 \(n \le 5 \times 10^3\)。
  • 对于 \(100\%\) 的数据，保证 \(1 \leq n \le 10^5\)，\(1 \le a_i \le 5 \times 10^3\)。

4根木棒组成一个正三角形，则必有 2根长度相等。

另外2根长度之和，等于 前2根相等的木棒 的长度

挺有意思的一题，需要考虑情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int kMaxn = 1e6 + 10;
const ll kMod = 1e9 + 7;
ll n, ans, maxa, a[kMaxn], num[kMaxn];
ll C(ll x, ll k) { 
  //求得从n个数中取出k个数的组合
  //k = 1 时，C(x, 1) = x;
  //k = 2 时，C(x, 2) = x * (x - 1) / 2;
  return (k == 1ll ? x : x * (x - 1ll) / 2ll) % kMod;
}
int main() {
cin>>n;
  for (int i = 1; i <= n; ++ i) { 
 	cin>>a[i];
    maxa = max(a[i], maxa);
    num[a[i]] ++;
  }

  for (int i = 2; i <= maxa; ++ i) { 
    if (num[i] >= 2ll) {
      ll times = C(num[i], 2ll) % kMod; 
      for (int j = 1; j <= i / 2; ++ j) { 
        if (j != i - j && num[j] >= 1 && num[i - j] >= 1)  
          ans += times * C(num[j], 1) * C(num[i - j], 1) % kMod;
        if (j == i - j && num[j] >= 2) 
          ans += times * C(num[j], 2) % kMod;
        ans %= kMod;
      }
    }
  }
cout<<ans;
  return 0;
}

[COCI2008-2009 #2] PERKET

题目描述

Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 \(n\) 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 \(s\) 和苦度 \(b\)。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。

众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。

另外，我们必须添加至少一种配料，因为没有任何食物以水为配料的。

输入格式

第一行一个整数 \(n\)，表示可供选用的食材种类数。

接下来 \(n\) 行，每行 \(2\) 个整数 \(s_i\) 和 \(b_i\)，表示第 \(i\) 种食材的酸度和苦度。

输出格式

一行一个整数，表示可能的总酸度和总苦度的最小绝对差。

样例 #1

样例输入 #1

1
2
1
3 10

样例输出 #1

1
7

样例 #2

样例输入 #2

1
2
3
2
3 8
5 8

样例输出 #2

1
1

样例 #3

样例输入 #3

1
2
3
4
5
4
1 7
2 6
3 8
4 9

样例输出 #3

1
1

提示

数据规模与约定

对于 \(100\%\) 的数据，有 \(1 \leq n \leq 10\)，且将所有可用食材全部使用产生的总酸度和总苦度小于 \(1 \times 10^9\)，酸度和苦度不同时为 \(1\) 和 \(0\)。 #### 说明 - 本题满分 \(70\) 分。 - 题目译自 COCI2008-2009 CONTEST #2 PERKET，译者 @mnesia。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//加的部分初始化为0，乘的部分为1，枚举到最后一位即可收
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int n, a[25], b[25];
int ans = 1e9;
void f(int sd, int kd, int step)
{
	if (step==n)
	{
		int tmp = abs(sd - kd);
		if (tmp<ans&&kd!=0)
		{
			ans = tmp;
		}
		return;
	}
	step++;
	f(sd * a[step], kd + b[step], step);
	f(sd, kd, step);
}
int main()
{
	cin >> n;
	for (int i = 1; i <=n ; i++)
	{
		cin >> a[i] >> b[i];
	}
	f(1, 0, 0);
	cout << ans;
}