记录一下刷题心得

string 和 字符数组之间转换

字符数组转成string

1
2
3
char ach2[] = "World";
str2 += ach2;
string str3 = str1 + " " + ach2;

需要注意的是，在使用加法运算符时，运算符两侧的操作数不能都是字符数组。

1
string str4 = ach1 + ach2;//错误

string转换成字符数组

通过string类的c_str()函数，可以将string转化为字符数组。c_str()函数返回值是一个C风格字符串，也就是说，该函数的返回结果是一个指向字符数组的指针。

1
2
3
char ach3[20];
strcpy(ach3, str1);//错误
strcpy(ach3, str1.c_str());//正确

尼姆（nim）游戏

地上有n堆石子，甲乙两人交替取石子，没人每次从任意一堆石子里面取，至少取一枚，不能不取，最后没有石子可以取的就输了
每堆石子的数量是 $a_i$,问是否存在先手必胜的策略

  • 如果初态为必胜态，则先手必胜 $a_1 \oplus a_2 \oplus ··· \oplus a_n\not ={0}$
  • 如果初态为必败态，则先手必败 $a_1 \oplus a_2 \oplus ··· \oplus a_n =0$

结论：

  • 必胜态的后继状态至少存在一个必败态
  • 必败态的后继状态均为必胜态
  • 必胜态与必败态交替出现，终态（0，0，···，0）是必败态

题目地址:洛谷P2197

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;
    while (t--)
    {
        int n,s = 0;
        cin >> n;
        while (n--)
        {
            int a;
            cin >> a;
            s ^= a;
        }
        if(s) cout << "Yes" << endl;
        else cout <<"No" << endl;
        
    }  
    return 0;
}

深入思考

每次要怎么取才是最佳策略呢

我们得到的 s 如果不为 0 的话，说明先手必胜，但是要怎么去取

如何使得我们拿完以后留下的是一个先手必败的选择，那么此时取完以后 s 应该是 0

我们要找到一个可以取的$（a[i]\oplus s) \leq a[i]$ 为什么是这个判断条件呢？

我们要保证我们在某个堆能够取走够数量的石子，这就要求了$(a[i]\oplus s) \leq a[i]$ ，我们要取走 $a[i]-(a[i]\oplus s) \leq a[i]$个石子，剩下$(a[i]\oplus s)$ 个石子

题目地址洛谷P1247

AC代码

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<bits/stdc++.h>
using namespace std;
int main(){
    int k;
    int a[500005];
    cin >> k;
    int s = 0;
    for(int i = 1 ; i <= k ; i++){
        cin >> a[i];
        s ^= a[i];
    }
    if(!s) {cout << "lose";return 0;}
    for(int i = 1 ; i <= k ; i++){
        if((s^a[i]) > a[i]) continue;
        cout << (a[i]-(s^a[i])) << " " << i << endl;
        a[i] ^= s;
        break;
    }
    for(int i = 1 ; i <=k ; i++){
        cout << a[i] <<" ";
    }
    system("pause");
    return 0;
}

substr函数

1
2
3
4
s.substr(pos,len)
string x=s.substr()                 //默认时的长度为从开始位置到尾
string y=s.substr(5)               //获得字符串s中 从第5位开始到尾的字符串
string z=s.substr(5,3);         //获得字符串s中 从第5位开始的长度为3的字符串

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll a, b, p;
	cin >> a >> b >> p;
	ll bb = b ,aa = a;
	ll ans = 1;
	a %= p;
	while (b) {
		if (b & 1) {   
			ans = (ans * a) % p;
		}
		a = (a * a) % p;
		b >>= 1;
	}
	cout << aa <<"^"<<bb << " mod " << p << "=" << ans;
}

矩阵快速幂

斐波那契数列用快速幂实现

本质上原理就是左乘以一个二维矩阵就可以变化为下一对数

求一个 $3^{53}$ 可以转化为

写一个普通的矩阵快速幂

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
typedef long long ll;
const int mod = 1e9 + 7;
struct matrix
{
	ll c[101][101];
	matrix() { memset(c, 0, sizeof c); }
}A,res;
ll n, k;

matrix operator*(matrix &x,matrix &y){
	matrix t;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				t.c[i][j] = (t.c[i][j] + x.c[i][k] * y.c[k][j]) % mod;
			}
		}
	}
	return t;
}

void quickpow(ll k) {
	for (int i = 1; i <= n; i++) res.c[i][i] = 1;
	while (k)
	{
		if (k & 1) res = res * A;
		A = A * A;
		k >> 1;
	}
}

矩阵快速幂

一个 $m \times n$ 的矩阵是一个由 $m$ 行 $n$ 列元素排列成的矩形阵列。即形如

本题中认为矩阵中的元素 $a_{i j}$ 是整数。

两个大小分别为 $m \times n$ 和 $n \times p$ 的矩阵 $A, B$ 相乘的结果为一个大小为 $m \times p$ 的矩阵。将结果矩阵记作 $C$，则

而如果 $A$ 的列数与 $B$ 的行数不相等，则无法进行乘法。

可以验证，矩阵乘法满足结合律，即 $(A B) C = A (B C)$。

一个大小为 $n \times n$ 的矩阵 $A$ 可以与自身进行乘法，得到的仍是大小为 $n \times n$ 的矩阵，记作 $A^2 = A \times A$。进一步地，还可以递归地定义任意高次方 $A^k = A \times A^{k - 1}$，或称 $A^k = \underbrace{A \times A \times \cdots \times A}_{k \text{ 次}}$。

特殊地，定义 $A^0$ 为单位矩阵 $I = \begin{bmatrix} 1 & 0 & \cdots & 0 \ 0 & 1 & \cdots & 0 \ \vdots & \vdots & \ddots & \vdots \ 0 & 0 & \cdots & 1 \end{bmatrix}$。

题目描述

给定 $n\times n$ 的矩阵 $A$，求 $A^k$。

输入格式

第一行两个整数 $n,k$。
接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行的第 $j$ 的数表示 $A_{i,j}$。

输出格式

输出 $A^k$

共 $n$ 行，每行 $n$ 个数，第 $i$ 行第 $j$ 个数表示 $(A^k)_{i,j}$，每个元素对 $10^9+7$ 取模。

样例 #1

样例输入 #1

1
2
3
2 1
1 1
1 1

样例输出 #1

1
2
1 1
1 1

提示

【数据范围】

对于 $100\%$ 的数据，$1\le n \le 100$，$0 \le k \le 10^{12}$，$|A_{i,j}| \le 1000$。

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
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod = 1e9 + 7;
struct matrix
{
	ll c[101][101];
	matrix() { memset(c, 0, sizeof c); }
}A,res;
ll n, k;

matrix operator*(matrix &x,matrix &y){
	matrix t;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				t.c[i][j] = (t.c[i][j] + x.c[i][k] * y.c[k][j]) % mod;
			}
		}
	}
	return t;
}

void quickpow(ll k) {
	for (int i = 1; i <= n; i++) res.c[i][i] = 1;
	while (k)
	{
		if (k & 1) res = res * A;
		A = A * A;
		k >>= 1;
	}

}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> A.c[i][j];
		}
	}
	quickpow(k);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << res.c[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}