kalipolis
洛谷部分代码展示

洛谷部分代码展示

2023年09月13日 4.3k 字 大概 21 分钟
  • 集合了我洛谷不看题解通过部分题目的代码我的实力也就这样了😩，贴心写了较为详细的中文注释，供各位学习思路
  • 我的洛谷账号（现在基本不用了）：点此跳转
  • 由于我在hexo没有找到可用的插件对latex公式的支持，下方的变量显示会有问题，如果对公式有疑问，建议点击题目链接跳转阅读
  • P1450 [HAOI2008] 硬币购物

[HAOI2008] 硬币购物

题目描述

共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$。

某人去商店买东西，去了 $n$ 次，对于每次购买，他带了 $d_i$ 枚 $i$ 种硬币，想购买 $s$ 的价值的东西。请问每次有多少种付款方法。

输入格式

输入的第一行是五个整数，分别代表 $c_1,c_2,c_3,c_4, n$。

接下来 $n$ 行，每行有五个整数，描述一次购买，分别代表 $d_1, d_2, d_3, d_4,s$。

输出格式

对于每次购买，输出一行一个整数代表答案。

样例 #1

样例输入 #1

1
2
3
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

样例输出 #1

1
2
4
27

提示

数据规模与约定

  • 对于 $100%$ 的数据，保证 $1 \leq c_i, d_i, s \leq 10^5$，$1 \leq n \leq 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
#include<bits/stdc++.h>
using namespace std;

int c[5]; // 硬币面值
int d[5]; // 每种硬币数量
long long ans[100000+10]; // 动态规划数组

long long ff(int a){
	if(a<0)
		return 0;
	else
		return ans[a];
}

int main() {
	int n;
	cin>>c[1]>>c[2]>>c[3]>>c[4]>>n; // 输入硬币面值和购买次数

	for(int i=1;i<=n;i++){
		int goal;
		cin>>d[1]>>d[2]>>d[3]>>d[4]>>goal; // 输入每次购买的硬币数量和目标价值

		memset(ans,0,sizeof(ans)); // 初始化动态规划数组
		ans[0]=1; // 初始值

		// 动态规划计算付款方法
		for(int j=1;j<=4;j++){
			for(int s=0;s<=goal-c[j];s++){
				ans[s+c[j]]+=ans[s];
			}
		}

		// 计算不同付款方式的数量
		long long g[5];
		for(int j=1;j<=4;j++){
			g[j]=(long long)(d[j]+1)*c[j];
		}
		long long da[6];
		da[1]=ff(goal);
		da[2]=ff(goal-g[1])+ff(goal-g[2])+ff(goal-g[3])+ff(goal-g[4]);
		da[3]=ff(goal-g[1]-g[2])+ff(goal-g[1]-g[3])+ff(goal-g[1]-g[4])+ff(goal-g[2]-g[3])+ff(goal-g[2]-g[4])+ff(goal-g[3]-g[4]);
		da[4]=ff(goal-g[1]-g[2]-g[3])+ff(goal-g[1]-g[4]-g[3])+ff(goal-g[1]-g[2]-g[4])+ff(goal-g[4]-g[2]-g[3]);
		da[5]=ff(goal-g[1]-g[2]-g[3]-g[4]);

		cout<<da[1]-da[2]+da[3]-da[4]+da[5]<<endl; // 输出答案
	}
}

[NOI2001] 食物链

题目描述

动物王国中有三类动物 $A,B,C$，这三类动物的食物链构成了有趣的环形。$A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$。

现有 $N$ 个动物，以 $1 \sim N$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述：

  • 第一种说法是 1 X Y，表示 $X$ 和 $Y$ 是同类。
  • 第二种说法是 2 X Y，表示 $X$ 吃 $Y$。

此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

  • 当前的话与前面的某些真的话冲突，就是假话；
  • 当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；
  • 当前的话表示 $X$ 吃 $X$，就是假话。

你的任务是根据给定的 $N$ 和 $K$ 句话，输出假话的总数。

输入格式

第一行两个整数，$N,K$，表示有 $N$ 个动物，$K$ 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

样例输出 #1

1
3

提示

对于全部数据，$1\le N\le 5 \times 10^4$，$1\le K \le 10^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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 50000

int bing[150000+1]; // 用于记录食物链关系

// 查找操作，返回节点的根节点
int find(int a){
	if(bing[a]==a)
		return a;
	else
		return find(bing[a]);
}

// 合并操作，将两个节点所在的集合合并
void hebing(int a,int b){
	int x=find(a),y=find(b);
	bing[x]=y;
}

int main() {
	for(int i=1;i<=150001;i++){
		bing[i]=i;
	}

	int n,k;
	cin>>n>>k; // 输入动物数量和句子数量

	int a,b,c;
	int ans=0;

	for(int i=1;i<=k;i++){
		cin>>a>>b>>c; // 输入每句话的描述

		if(b>n||c>n){
			ans++;
			continue;
		}

		if(a==1){ // 第一种说法：X和Y是同类
			if(find(b+N)==find(c)||find(b+2*N)==find(c)){
				ans++; // 与前面的真话冲突，为假话
				continue;
			}
			else {
				hebing(b,c); // 合并同类关系
				hebing(b+N,c+N);
				hebing(b+2*N,c+2*N);
			}
		}
		if(a==2){ // 第二种说法：X吃Y
			if(b==c){
				ans++; // X吃X，为假话
				continue;
			}
			if(find(b)==find(c)||find(b)==find(c+2*N)){
				ans++; // 与前面的真话冲突，为假话
				continue;
			}
			else{
				hebing(b,c+N); // 建立吃食关系
				hebing(b+N,c+2*N);
				hebing(b+2*N,c);
			}
		}
	}

	cout<<ans; // 输出假话数量
}

[SDOI2009] E&D

题目描述

小 E 与小 W 进行一项名为 E&D 游戏。

游戏的规则如下：桌子上有 $2n$ 堆石子，编号为 $1 \sim 2n$。其中，为了方便起见，我们将第 $2k-1$ 堆与第 $2k$ 堆（$1 \le k \le n$）视为同一组。第 $i$ 堆的石子个数用一个正整数 $S_i$ 表示。

一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子数必须保证大于 $0$。显然，被分割的一堆的石子数至少要为 $2$。两个人轮流进行分割操作。如果轮到某人进行操作时，所有堆的石子数均为 $1$，则此时没有石子可以操作，判此人输掉比赛。

小 E 进行第一次分割。他想知道，是否存在某种策略使得他一定能战胜小 W。因此，他求助于小 F，也就是你，请你告诉他是否存在必胜策略。例如，假设初始时桌子上有 $4$ 堆石子，数量分别为 $1,2,3,1$。小 E 可以选择移走第 $1$ 堆，然后将第 $2$ 堆分割（只能分出 $1$ 个石子）。接下来，小 W 只能选择移走第 $4$ 堆，然后将第 $3$ 堆分割为 $1$ 和 $2$。最后轮到小 E，他只能移走后两堆中数量为 $1$ 的一堆，将另一堆分割为 $1$ 和 $1$。这样，轮到小 W 时，所有堆的数量均为 $1$，则他输掉了比赛。故小 E 存在必胜策略。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行一个整数 $N$，表示桌子上共有 $N$ 堆石子，这里的 $N$ 即为题目描述中的 $2n$。

第二行 $N$ 个整数 $S_{1 \dots N}$。

输出格式

对于每组数据，如果小 E 必胜，则一行一个字符串 YES，否则一行一个字符串 NO。

样例 #1

样例输入 #1

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

样例输出 #1

1
2
YES
NO

提示

对于 $20%$ 的数据，$N=2$。

对于另外 $20%$ 的数据，$N \le 4$，$S_i \le 50$。

对于 $100%$ 的数据，$1 \le T \le 20$，$1 \le N \le 2 \times 10^4$ 且 $N$ 为偶数，$1 \le S_i \le 2 \times 10^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
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;

// 递归函数，计算必胜策略的情况
long long gui(long long a, long long b) {
	if (a % 2 == 1 && b % 2 == 1)
		return 0; // 如果两堆石子数都是奇数，返回0，表示无法必胜
	if (a % 2 == 0 && b % 2 == 0) {
		return gui(a / 2, b / 2) + 1; // 如果两堆石子数都是偶数，递归调用gui函数，并加1
	}
	else {
		if (a % 2 == 1) {
			return gui(a + 1, b); // 如果第一堆石子数是奇数，将其加1，继续递归调用gui函数
		}
		else {
			return gui(a, b + 1); // 如果第二堆石子数是奇数，将其加1，继续递归调用gui函数
		}
	}
}

int main() {
	int t;
	cin >> t; // 输入游戏的轮数

	for (int i = 1; i <= t; i++) {
		long long n, g, h, ans = 0;
		cin >> n; // 输入石子堆的数量

		// 遍历每一组石子堆
		for (int j = 1; j <= n / 2; j++) {
			cin >> g >> h; // 输入每组石子堆的石子数量
			ans = (ans ^ gui(g, h)); // 异或运算，计算所有组的结果
		}

		if (ans == 0)
			cout << "NO" << endl; // 如果结果为0，表示无法必胜
		else
			cout << "YES" << endl; // 如果结果不为0，表示存在必胜策略
	}
	return 0;
}

[USACO19DEC] Greedy Pie Eaters P

题目背景

Farmer John has $M$ cows, conveniently labeled $1 \ldots M$, who enjoy the occasional change of pace
from eating grass. As a treat for the cows, Farmer John has baked $N$ pies ($1 \leq N \leq 300$), labeled
$1 \ldots N$. Cow $i$ enjoys pies with labels in the range $[l_i, r_i]$ (from $l_i$ to $r_i$ inclusive),
and no two cows enjoy the exact same range of pies. Cow $i$ also has a weight, $w_i$, which
is an integer in the range $1 \ldots 10^6$.

Farmer John may choose a sequence of cows $c_1,c_2,\ldots, c_K,$ after which the
selected cows will take turns eating in that order. Unfortunately, the cows
don’t know how to share! When it is cow $c_i$’s turn to eat, she will consume
all of the pies that she enjoys — that is, all remaining pies in the interval
$[l_{c_i},r_{c_i}]$. Farmer John would like to avoid the awkward situation
occurring when it is a cows turn to eat but all of the pies she enjoys have already been
consumed. Therefore, he wants you to compute the largest possible total weight
($w_{c_1}+w_{c_2}+\ldots+w_{c_K}$) of a sequence $c_1,c_2,\ldots, c_K$ for which each cow in the
sequence eats at least one pie.

题目描述

Farmer John 有 $M$ 头奶牛，为了方便，编号为 $1,\dots,M$。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。Farmer John 一天烤了 $N$ 个派请奶牛吃，这 $N$ 个派编号为 $1,\dots,N$。第 $i$ 头奶牛喜欢吃编号在 $\left[ l_i,r_i \right]$ 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 $i$ 头奶牛有一个体重 $w_i$，这是一个在 $\left[ 1,10^6 \right]$ 中的正整数。

Farmer John 可以选择一个奶牛序列 $c_1,c_2,\dots,c_K$，并让这些奶牛按这个顺序轮流吃派。不幸的是，这些奶牛不知道分享！当奶牛 吃派时，她会把她喜欢吃的派都吃掉——也就是说，她会吃掉编号在 $[l_{c_i},r_{c_i}]$ 中所有剩余的派。Farmer John 想要避免当轮到一头奶牛吃派时，她所有喜欢的派在之前都被吃掉了这样尴尬的情况。因此，他想让你计算，要使奶牛按 $c_1,c_2,\dots,c_K$ 的顺序吃派，轮到这头奶牛时她喜欢的派至少剩余一个的情况下，这些奶牛的最大可能体重（$w_{c_1}+w_{c_2}+\ldots+w_{c_K}$）是多少。

输入格式

第一行包含两个正整数 $N,M$；

接下来 $M$ 行，每行三个正整数 $w_i,l_i,r_i$。

输出格式

输出对于一个合法的序列，最大可能的体重值。

样例 #1

样例输入 #1

1
2
3
2 2
100 1 2
100 1 1

样例输出 #1

1
200

提示

样例解释

在这个样例中，如果奶牛 $1$ 先吃，那么奶牛 $2$ 就吃不到派了。然而，先让奶牛 $2$ 吃，然后奶牛 $1$ 只吃编号为 $2$ 的派，仍可以满足条件。

对于全部数据，$1 \le N \le 300,1 \le M \le \dfrac{N(N-1)}{2},1 \le l_i,r_i \le N,1 \le w_i \le 10^6$。

数据范围

对于测试点 $2-5$，满足 $N \le 50,M \le 20$；

对于测试点 $6-9$，满足 $N \le 50$。

USACO 2019 December 铂金组T1

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
#include <bits/stdc++.h>
using namespace std;
int dp[310][310];
int he[310][310][310]; // a, b, c: 对于区间bc，位置a处最大能吃的牛的重量
int main() {
	int n, m;
	cin >> n >> m; // 输入n和m的值

	int w, l, r;
	for (int i = 1; i <= m; i++) {
		cin >> w >> l >> r;
		for (int i = l; i <= r; i++) {
			he[i][l][r] = w; // 记录每个位置和区间的最大能吃的牛的重量
		}
	}

	// 动态规划预处理最大能吃的牛的重量
	for (int len = 0; len < n; len++) {
		for (int i = 1, j; i + len <= n; i++) {
			j = i + len;
			for (int k = i; k <= j; k++) {
				he[k][i - 1][j] = max(he[k][i - 1][j], he[k][i][j]);
				he[k][i][j + 1] = max(he[k][i][j + 1], he[k][i][j]);
			}
		}
	}

	// 动态规划求解最优解
	for (int len = 0; len < n; len++) {
		for (int i = 1, j; i + len <= n; i++) {
			j = i + len;
			for (int k = i; k < j; k++) {
				dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
			}
			for (int k = i; k <= j; k++) {
				dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + he[k][i][j]);
			}
		}
	}

	cout << dp[1][n];
	return 0;
}

[蓝桥杯 2021 省 AB2] 国际象棋

题目描述

众所周知， “八皇后” 问题是求解在国际象棋棋盘上摆放 $8$ 个皇后，使得两两之间互不攻击的方案数。已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹末尽。作为一个国际象棋迷，他想研究在 $N \times M$ 的棋盘上，摆放 $K$ 个马，使得两两之间互不攻击有多少种摆放方案。由于方案数可能很大，只需计算答案除以 $1000000007$ (即 $\left.10^{9}+7\right)$ 的余数。

如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字, 位于 $(x, y)$ 格的马（第 $x$ 行第 $y$ 列）可以攻击 $(x+1, y+2),(x+1, y-2),(x-1, y+2),(x-1, y-2),(x+2, y+1),(x+2, y-1),(x-2, y+1),(x-2, y-1)$ 共 $8$ 个 格子。

输入格式

输入一行包含三个正整数 $N, M, K$, 分别表示棋盘的行数、列数和马的个数。

输出格式

输出一个整数，表示摆放的方案数除以 $1000000007\left(\right.$ 即 $\left.10^{9}+7\right)$ 的余数。

样例 #1

样例输入 #1

1
1 2 1

样例输出 #1

1
2

样例 #2

样例输入 #2

1
4 4 3

样例输出 #2

1
276

样例 #3

样例输入 #3

1
3 20 12

样例输出 #3

1
914051446

提示

对于 $5 %$ 的评测用例, $K=1$;

对于另外 $10 %$ 的评测用例, $K=2$;

对于另外 $10 %$ 的评测用例, $N=1$;

对于另外 $20 %$ 的评测用例, $N, M \leq 6, K \leq 5$;

对于另外 $25 %$ 的评测用例, $N \leq 3, M \leq 20 ， K \leq 12$;

对于所有评测用例, $1 \leq N \leq 6,1 \leq M \leq 100,1 \leq K \leq 20$。

蓝桥杯 2021 第二轮省赛 A 组 I 题（B 组 J 题）。

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
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int P=1e9+7;
const int yasuo=64;

// 计算 a 的逆元（在模 P 下）
ll inv(ll a){
	ll m=P-2;
	ll ans=a;
	ll now=P;
	while(m!=0){
		if(m&1){
			ans=(ans*now)%P;
		}
		now=(now*now)%P;
		m=m>>1;
	}
	return ans;
}

// 判断两个位置是否互不攻击
bool gehang(int a,int c){
	int m=a;
	int n=c;
	m>>=1;
    if(m&n) return false; 
	m=a;
	n=c;
	n>>=1;
    if(m&n) return false;
	return true;
}

// 判断两个位置是否互不攻击（斜线方向）
bool xiangling(int a,int b){
	int m=a;
	int n=b;
	m>>=2;
    if(m&n) return false;
	m=a;
	n=b;
	n>>=2;
    if(m&n) return false;
	return true;
}

int counts[64];
int dp[2][yasuo][yasuo][30]; // 前两行的信息，走的马数 

int main(){
    int n,m,k;
    cin>>n>>m>>k;

    // 统计每个二进制位上 1 的个数
    for(int i=0;i<64;i++){
    	int c=i,now=0;
		while(c!=0){
			if(c&1)now++;
			c=c>>1;
		}
		counts[i]=now; 
	}

	int ff=1<<n;  // 需要保存的状态压缩位数 

    for(int i=1;i<=m;i++){
	    memset(dp[i%2],0,sizeof(dp[i%2]));
    	if(i==1)dp[0][0][0][0]=1;

    	for(int l=0;l<ff;l++){
			for(int h=0;h<ff;h++){
	    		for(int num=0;num<=k;num++){
	    			if(!dp[(i-1)%2][h][l][num]) continue;
					for(int j=0;j<ff;j++){
			    		if(xiangling(l,j)&&gehang(h,j)){
			    			dp[i%2][l][j][num+counts[j]]=(dp[(i-1)%2][h][l][num]+dp[i%2][l][j][num+counts[j]])%P;
					}
					}
				}
			}
		}
	}

	ll ans=0;
    for(int i=0;i<ff;i++)
    for(int j=0;j<ff;j++){
    	ans=(ans+dp[m%2][i][j][k])%P;
	}

	cout<<ans; 
    return 0;
}
本文作者：kalipolis
本文链接：https://kalipolis.gitee.io/2023/09/13/洛谷部分代码合计/
版权声明：本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
技术