P2241 统计方形（数据加强版）(矩形中的正方,长方形统计)

统计方形（数据加强版）

题目背景

1997年普及组第一题

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

1
2 3

样例输出 #1

1
8 10

这里直接给结论了

n*m的矩形中长方形(不包括正方形)的数量,等于子矩形的数量减去子正方形的数量

又子矩形的数量等于 \((m+1)\times m/2\times(n+1)\times n/2\),

这里把除以二拆成两个地方还可以防止爆int,或者爆long long

而子正方形的数量等于矩行中最大正方形的子正方形数量等于 \(\sum_{i=1}^{n}i\times (m-n+i)\)

换成代码就是:

1
for(int i=m,j=n;i>=1&&j>=1;i--,j--)zheng+=i*j;

得到子正方形的个数之后,就可以直接使用总的子矩形的数量,减去子正方形的数量得到子长方形的数量得到答案了.

1
2
3
4
5
6
7
8
int main() {
	long long n, m,c=0,z=0;
	cin >> n >> m;
	for (int i = n, j = m; i >= 1 && j >= 1; i--, j--)z += i * j;
	c = ((m + 1) * m/2) * ((n + 1) * n /2) - z;
	cout << z << " " << c << endl;
	return 0;
}

P1177 【模板】快速排序

这次没有题目水字数了，记录一个很棒的快速排序模板！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Qsort(int beg, int end) {
	int mid = str[(beg + end) / 2];
	int i = beg, j = end;
	do {
		while (str[i] < mid)i++;
		while (str[j] > mid)j--;
		if (i <= j) {
			swap(str[i], str[j]);
			i++;
			j--;
		}
	} while (i <= j);
	if(beg<j)Qsort(beg,j);
	if(i<end)Qsort(i, end);
}

P1045 [NOIP2003 普及组] 麦森数——快速幂

[NOIP2003 普及组] 麦森数

题目描述

形如 \(2^{P}-1\) 的素数称为麦森数，这时 \(P\) 一定也是个素数。但反过来不一定，即如果 \(P\) 是个素数，\(2^{P}-1\) 不一定也是素数。到 1998 年底，人们已找到了 37 个麦森数。最大的一个是 \(P=3021377\)，它有 909526 位。麦森数有许多重要应用，它与完全数密切相关。

任务：输入 \(P(1000<P<3100000)\)，计算 \(2^{P}-1\) 的位数和最后 \(500\) 位数字（用十进制高精度数表示）

输入格式

文件中只包含一个整数 \(P(1000<P<3100000)\)

输出格式

第一行：十进制高精度数 \(2^{P}-1\) 的位数。

第 \(2\sim 11\) 行：十进制高精度数 \(2^{P}-1\) 的最后 \(500\) 位数字。（每行输出 \(50\) 位，共输出 \(10\) 行，不足 \(500\) 位时高位补 \(0\)）

不必验证 \(2^{P}-1\) 与 \(P\) 是否为素数。

样例 #1

样例输入 #1

1
1279

样例输出 #1

1
2
3
4
5
6
7
8
9
10
11
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

提示

【题目来源】

NOIP 2003 普及组第四题

快速幂

这题算是我自己第一次使用快速幂吧，感觉对快速幂还是有一种恐惧感，所以来总结一下所学。
首先是一个已经很熟悉的快速幂模板

1
2
3
4
5
while(n){
  if(n%2==1)multi1();
  n/=2;
  multi2();
}

其中的multi1和multi2分别对应乘底数和自乘。
至于高精度的一个乘法就可以使用数组快速实现，再次编写代码以提升自己的熟练程度

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
using namespace std;
#include <cstring>
#include <iostream>
#include <cmath>
#include <cstdlib>
int ans[510], res[510], sav[510];//分别对应答案，底数和缓存数组
void multi1();
void multi2();
int main() {
    int n;
    cin >> n;
    ans[1] = 1, res[1] = 2;
    cout << (int)(n * log10(2) + 1);
    while (n) {
        if (n % 2 == 1)multi1();
        n /= 2;
        multi2();
    }
    ans[1]--;
    for (int i = 500; i >= 1; i--) {
        if (!(i % 50))cout << endl;
        cout << ans[i];
    }
}
void multi1() {
    memset(sav, 0, sizeof(sav));
    for (int i = 1; i <= 500; i++)
        for (int j = 1; j <= 500; j++)
            if (i + j - 1 <= 500)sav[i + j - 1] += ans[i] * res[j];//答案乘以底数
            else break;
    for (int i = 1; i <= 500; i++) {
        sav[i + 1] += sav[i] / 10;
        sav[i] %= 10; //进位
    }
    memcpy(ans, sav, sizeof(sav));//把sav中大小为sizeof(sav)的值复制给ans。
}
void multi2() {
    memset(sav, 0, sizeof(sav));
    for (int i = 1; i <= 500; i++)
        for (int j = 1; j <= 500; j++)
            if (i + j - 1 <= 500)sav[i + j - 1] += res[i] * res[j];//底数自乘
            else break;
    for (int i = 1; i <= 500; i++) {
        sav[i + 1] += sav[i] / 10;
        sav[i] %= 10;
    }
    memcpy(res, sav, sizeof(sav));
}

好了，这篇就写到这吧。

P5461 赦免战俘

赦免战俘

题目背景

借助反作弊系统，一些在月赛有抄袭作弊行为的选手被抓出来了！

题目描述

现有 \(2^n\times 2^n (n\le10)\) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。

给出 \(n\)，请输出每名作弊者的命运，其中 0 代表被赦免，1 代表不被赦免。

输入格式

一个整数 \(n\)。

输出格式

\(2^n \times 2^n\) 的 01 矩阵，代表每个人是否被赦免。数字之间有一个空格。

样例 #1

样例输入 #1

1
3

样例输出 #1

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

自己写的时候一直在思考该如何模拟，建起1<<n大小的数组吗？想了大半夜，早上爬起来看题解。被Ritanlisa的一篇博客吸引住了。位运算，因为高度对称，i,j=j,i所以思考位运算，其实互换之后不变的还有加法和乘法，但是很明显是不成立的。找到一个未被赦免的人，比如(7,0)=(111,000)1111|000就是111，再试几个位置，发现成立，就有了：

f(i , j)=(i | j)==((1<<n)-!)?1:0

那么就可以很轻松的实现代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
int main(){
  int n,i=0,j=0;
  scanf("%d",&n);
  for(;i<(1<<n);i++){
    for(j=0;j<(1<<n);j++){
      printf("%d ",(i|j)==((1<<n)-1)?1:0);
    }
  printf("\n");
  }
return 0;
}

我学到了什么？

1.对称时思考i和j的关系，而不是一味模拟

2.使用位运算实现2^n(1<<n)

非常感谢Ritanlisa大佬的题解

|