• 差分
  • bfs
  • 01背包dp
  • Dijkstra
  • 递归，大数

A. 阿卡的萝卜

单点时限: 1.0 sec

内存限制: 512 MB

1

输入：

1

输出：

1

1

 

差分+前缀和+dp求最大子段和

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
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn = 5e5 + 5;
ll n, m;
ll a[maxn];
ll cha[maxn];
ll dp[maxn];
int main() {
	cin.sync_with_stdio(false);
	cin >> n ;
	for (ll i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> m;
	for (ll i = 0; i < m; i++) {
		char act;
		ll st, ed;
		cin >> act >> st >> ed;
		if (act == 'J') {
			cha[st]++;
			cha[ed + 1]--;
		}
		else {
			cha[st]--;
			cha[ed+1]++;
		}
	}
	for (ll i = 1; i <= n; i++) {
		cha[i] = cha[i - 1] + cha[i];
		a[i] = a[i] + cha[i];
	}
	ll sum1 = 0;
	ll ans = 0;
	for (ll i = 1; i <= n; i++) {
		if (sum1 + a[i] > a[i])
			sum1 += a[i];
		else sum1 = a[i];
		if (sum1 > ans)
			ans = sum1;
	}
	cout << ans;
	return 0;
}

 

B. 烤乐滋逃亡

单点时限: 1.0 sec

内存限制: 512 MB

2

输入：

2

输出：

2

2

 

以树为起点bfs

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
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m;
char mz[1005][1005];
bool vis[1005][1005];
int ans[1005][1005];
int hah[2]{ -1,1 };
struct nd
{
	int x, y, dis;
};
struct cmp {
	bool operator()(nd a, nd b) {
		return a.dis > b.dis;
	}
};
priority_queue<nd, vector<nd>, cmp>que;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mz[i][j];
			if (mz[i][j] == '*') {
				que.push(nd{ i,j,0 });
			}
		}
	}
	while (!que.empty()) {
		nd tp = que.top();
		que.pop();
		int x = tp.x, y = tp.y, dis = tp.dis;
		for (int i = 0; i <= 1; i++) {
			if (x + hah[i] >= 1 && x + hah[i] <= n&&!vis[x + hah[i]][y]) {
				if (mz[x + hah[i]][y] == '.') {
					ans[x + hah[i]][y] = dis + 1;
					que.push(nd{ x + hah[i],y,dis + 1 });
					vis[x + hah[i]][y] = 1;
				}
			}
			if (y + hah[i] >= 1 && y + hah[i] <= m&&!vis[x][y + hah[i]]) {
				if (mz[x][y + hah[i]] == '.') {
					ans[x][y + hah[i]] = dis + 1;
					que.push(nd{ x,y + hah[i],dis + 1 });
					vis[x][y + hah[i]] = 1;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (mz[i][j] == '*')cout << 0 << ' ';
			else if (mz[i][j] == '#')cout << "ovo" << ' ';
			else {
				if (ans[i][j] == 0)cout << "GoDie" << ' ';
				else cout << ans[i][j] << ' ';
			}
		}
		cout << endl;
	}
	return 0;
}

 

C. 阿瓦的礼物

单点时限: 1.0 sec

内存限制: 512 MB

3

输入：

3

输出：

3

3

 

把问题转化为01背包问题，dp

dp[i] [j]表示到第i个人，有j个炸弹。

由于本题只有j≥Pj\geq P，而对j无上限限制，故要自行添加3000的上限，大于3000的都整合到3000里。

状态转移：

二维dp：

a[i]/K>0:

  • 可能有炸弹 dp[i+1] [j+a[i]/K]+=dp[i] [j]
  • 可能没有炸弹 dp[i+1] [j]+=dp[i] [j]

a[i]/K==0:

  • 肯定没有炸弹 dp[i+1] [j]+=dp[i] [j]

一维dp类似，但是注意01背包从后往前更新：

a[i]/K>0:

  • 可能有炸弹 dp[j+a[i]/K]+=dp[j]
  • 可能没有炸弹 ，此时就不用更新了，因为一维数组dp[j]可视为本身就已经加上了dp[j]；而二维数组dp[i+1] [j]初始为0。

a[i]/K==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
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int mod = 998244353;
int n, K, P;
int a[3005];
int dp[3005][3005];
int main() {
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> K >> P;
	for (int i = 1; i <= n; i++) {
		a[i] /= K;
	}
	dp[1][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= 3000; j++) {
			if (a[i])
				dp[i + 1][min(3000, j + a[i])] = (dp[i][j] + dp[i + 1][min(3000, j + a[i])]) % mod;
			dp[i + 1][j] = (dp[i][j] + dp[i + 1][j]) % mod;
		}
	}
	int ans = 0;
	for (int i = P; i <= 3000; i++) {
		ans = (ans + dp[n + 1][i]) % mod;
	}
	cout << ans;
	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
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int mod = 998244353;
int n, K, P;
int a[3005];
int dp[3005];
int main() {
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> K >> P;
	for (int i = 1; i <= n; i++) {
		a[i] /= K;
	}
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 3000; j >= 0; j--) {
			if (a[i])
				dp[min(3000, j + a[i])] = (dp[min(3000, j + a[i])] + dp[j]) % mod;
		}
	}
	int ans = 0;
	for (int i = P; i <= 3000; i++) {
		ans = (ans + dp[i]) % mod;
	}
	cout << ans;
	return 0;
}

 

D. Bits

单点时限: 1.0 sec

内存限制: 256 MB

4

输入：

4

输出：

4

 

E. 最短路

单点时限: 1.0 sec

内存限制: 512 MB

Mark 驾驶特斯拉电动车从 Boston 去 New York。他希望找一条最短驾驶路线，但是他的电动车充满一次电只能开 k 英里。令 Mark 欣慰的是从 Boston 到 New York 的路上有很多强力充电站，能够瞬间给电动车充满电。

Boston 到 New York 的路上有编号从 1 到 n 共 n 个驿站（包括 Boston 和 New York，其中 Boston 的编号是 1，New York 的编号是 n），其中一些驿站设有强力充电站。一共有 m 条道路，第 i 条道路长度为 wi 并连接两个驿站 ui,vi (1≤ui,vi≤n,ui≠vi)。

现在 Mark 已经得到了地图，他想知道从 Boston 到 New York 的最短路径的长度是多少。

输入格式

第一行三个整数 n,m,k (2≤n≤1000,1≤m≤2000,1≤k≤1018)。

第二行 n 个整数，第 i 个整数 bi (0≤bi≤1)，bi=1 代表编号为 i 的驿站设有强力充电站，bi=0 代表没有，保证 b1=1 。

接下来 m 行，每行三个整数 ui,vi,wi (1≤ui,vi≤n,1≤wi≤109)。

输入保证存在解，没有重边和自环，且 Boston 设有强力充电站。

输出格式

一行一个整数，代表最短路径长度。

数据约定

子任务 n 分值
1 k=1018 50
2 n≤100,m≤200 20
3 n≤1000,m≤2000 30

样例的图示为

5

 

Dijkstra最短路

存在两种点，一种是普通节点，另一种是加油站，由于在普通节点会受到上一节点的影响，即若已经走了100m到达普通节点，而k=300m，则从该普通节点到下一点最多只能走200m，并且该距离随着普通节点与上一个节点的距离变化而改变，也就是说，普通节点与另一固定点的距离是会不断变化的，这会影响我们建图，而两个加油站之间只要距离小于k，都是可以达到的。

所以我们把所有普通节点都去掉。

先以每个加油站点为起点跑最短路，找到与加油站直接相连的加油站点，并以他们之间的最短路为新图的两点距离。（不需要跑全图，我们只要与一加油站直接相连的加油站点）

建立新图之后，图上就只有加油站点（默认1，n为加油站点），这时再以1为起点跑最短路，d[n]就是结果。

注意：

  • 距离要用long long存

刚开始为了方便把if放在for里面写了

像这样：

1
2
for (int i = 1; i <= n && is_big[i]; i++) {
  		for (int j = 1; j <= n && is_big[j]; j++) {

导致调了好久，像上面这样写是错的！！

直接在for里面判断会在i不满足条件的时候直接停止，不会跳过！！！

正确的应该是下面这样：

1
2
3
for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if ((!is_big[i]) || (!is_big[j]))continue;

代码：

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<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define ll long long
typedef pair<ll, int> pii;
const ll INF = 1LL << 62;
int n, m;
ll k;
bool is_big[1005];
struct Edge
{
	int to;
	ll cost;
	Edge(int t,ll c):to(t),cost(c){}
};
vector<Edge>G[1005], gg[1005];
ll d[1005];
ll g[1005][1005];
void add_edge(int u, int v, int w) {
	G[u].push_back(Edge{ v,w });
	G[v].push_back(Edge{ u,w });
}
void Dij1(int s) {
	priority_queue<pii, vector<pii>, greater<pii> >que;
	g[s][s] = 0;
	que.push(pii(0ll, s));
	while (!que.empty()) {
		pii tp = que.top();
		que.pop();
		int id = tp.second;
		for (int i = 0; i < G[id].size(); i++) {
			Edge e = G[id][i];
			if (g[s][e.to] > g[s][id] + e.cost) {
				g[e.to][s]=g[s][e.to] = g[s][id] + e.cost;
				if(!is_big[e.to])
					que.push(pii(g[s][e.to], e.to));
			}
		}
	}
}
void rebuild() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if ((!is_big[i]) || (!is_big[j]))continue;
			if (i != j && g[i][j] <= k)
				gg[i].push_back(Edge{ j,g[i][j] });
		}
	}
}
void solve() {
	memset(d, 0x3f, sizeof(d));
	priority_queue<pii, vector<pii>, greater<pii> >que;
	que.push(pii(0ll, 1));
	d[1] = 0;
	while (!que.empty()) {
		pii tp = que.top();
		que.pop();
		int id = tp.second;
		for (int i = 0; i < gg[id].size(); i++) {
			Edge e = gg[id][i];
			if (d[e.to] > d[id] + e.cost) {
				d[e.to] = d[id] + e.cost;
				que.push(pii(d[e.to], e.to));
			}
		}
	}
	cout << d[n];
}
int main() {
	cin.sync_with_stdio(false);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> is_big[i];
	}
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add_edge(u, v, w);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			g[i][j] = INF;
	}
	for (int i = 1; i <= n ; i++) {
		if(is_big[i])
			Dij1(i);
	}
	rebuild();
	solve();
	return 0;
}

 

F. 格雷码

单点时限: 1.0 sec

内存限制: 256 MB

格雷码是一种整数编码方式，它使得相邻的两个整数只有一个位置上的位元不同。格雷码有多种编码形式。二进制反射格雷码(Reflected binary Gray code)是使用最广泛的格雷码。

下表为 1 位， 2 位， 3 位和 4 位的二进制反射格雷码。

N=1 N=2 N=3 N=4
0 00 000 0000
1 01 001 0001
11 011 0011
10 010 0010
110 0110
111 0111
101 0101
100 0100
1100
1101
1111
1110
1010
1011
1001
1000

可以采用下面方法来构建上述表中的 (N+1) 位二进制反射格雷码：

顺序书写 N 位二进制反射格雷码，然后在前面加上 0 ；

逆序书写 N 位二进制反射格雷码，然后在前面加上 1 。

根据上述方法构建的二进制反射格雷码是一种循环格雷码，即最后一项只改动 1 个位元即可得到第一项。

现给定 N(1≤N≤200) ，输出按照上述方法构建出的 N 位二进制反射格雷码中的第 K(1≤K≤2N2^N) 项。

输入格式

输入数据仅包含一行，两个整数 N 和 K （ 1≤N≤200,1≤k≤2N2^N ） 。

输出格式

输出仅包含一行，表示答案，即 N 位二进制反射格雷码中的第 K 的十进制表示。

 

递归+大数

python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n,k=input().split()
n=int(n)
k=int(k)
def solve(n,k):
    if n==1:
        if k==1:
            return 0
        else:
            return 1
    if k>2**(n-1):
        return 2**(n-1)+solve(n-1,2**n-k+1)
    else:
        return solve(n-1,k)

print(solve(n,k))