CCF-CSP 36

Posted on Edited on In Word count in article: 4.7k Reading time ≈ 17 mins.

...

  • 签到 100
  • TLE 80
  • 不会实现
  • TLE 30
  • TLE 0

周六（12.14）四级，晚点写。。。

  • 参考【题解】第 36 次 CCF-CSP 认证

第 36 次 CCF 计算机软件能力认证

梦境巡查（dream）

题目背景

传说每当月光遍布西西艾弗岛，总有一道身影默默守护着居民们的美梦。

题目描述

梦境中的西西艾弗岛由 个区域组成。梦境巡查员顿顿每天都会从梦之源（ 号区域）出发，顺次巡查 号区域，最后从 号区域返回梦之源。 在梦境中穿梭需要消耗美梦能量：

  • 从梦之源出发时，顿顿会携带若干初始能量；
  • 从第 号区域前往下一区域（）需要消耗 单位能量，因此从第 号区域出发时，顿顿剩余的美梦能量需要大于或等于 单位；
  • 顺利到达第 号区域（）后，顿顿可以从当地居民的美梦中汲取 单位能量作为补给。

假设顿顿初始携带 单位美梦能量，那么首先需要保证 ，这样顿顿便可消耗 能量穿梭到 号区域、进而获得 单位能量补给。巡查 号区域后，顿顿剩余能量为 ，如果该数值大于或等于 ，顿顿便可继续前往 号区域。依此类推，直至最后消耗 单位能量从 号区域返回梦之源，便算是顺利完成整个巡查。西西艾弗岛，又迎来安宁的一夜，可喜可贺！

dream 作为一个成熟的梦境巡查员，顿顿已经知晓初始需要携带多少能量可以保证顺利完成巡查。但在一些意外状况下，比如学生们受期末季的困扰而无法安眠，顿顿可能在某些区域无法采集足够的美梦能量。此时，便需要增加初始携带量以备万全。 具体来说，考虑一个简单的情况：在 到 号区域中，有且仅有一个区域发生意外，顿顿无法从该区域获得能量补给。如果第 号区域（）发生意外（即 变为 ），则此时为顺利完成巡查，顿顿从梦之源出发所携带的最少初始能量记作 。试帮助顿顿计算 的值。

输入格式

从标准输入读入数据。
输入共三行。
输入的第一行包含一个整数 。
输入的第二行包含 个整数 。
输入的第三行包含 个整数 。

输出格式

输出到标准输出。
输出仅一行，包含空格分隔的 个整数 。

样例

样例 1 输入
1
2
3
3
5 5 5 5
0 100 0
样例 1 输出
1
10 20 10

样例 1 解释

和 号区域本身便没有补给，需要携带 单位初始能量抵达 号区域，获得 号区域的大量补给后便可顺利完成巡查；
号区域发生意外，则全程没有补给，初始需携带 单位能量。

样例 2 输入
1
2
3
3
9 4 6 2
9 4 6
样例 2 输出
1
15 10 9

Solution

  • 当时做的时候整复杂了，重复计算了最大(最小)值，没有想到这也是个可重复贡献问题，代码可以在下面看到

为解决这个问题，我们可以计算到每一个区域时剩余的能量值。

当不考虑 变为 时

记刚到 号区域时的剩余能量为，我们先令 ，也就是开始没有能量( 可能小于 )，以及递推式： 那么为了使每一个 ，也就是能到达 号区域，当前不足的能量值的最大值（因为残差小于 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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
ll a[(int)1e5 + 10], b[(int)1e5 + 10];
ll f[(int)1e5 + 10];
ll sufmin[(int)1e5 + 10];
void solve() {
  int n, w = 0;
  cin >> n;
  for (int i = 0; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) cin >> b[i];  // b[0] = 0
  for (int i = 1; i <= n + 1; i++) f[i] = f[i - 1] - a[i - 1] + b[i - 1]; // 递推计算到达第i点时剩余的能量
  sufmin[n + 1] = f[n + 1];
  for (int i = n; i >= 1; i--) sufmin[i] = min(f[i], sufmin[i + 1]);
  w = min(w, sufmin[1]);
  for (int i = 1; i <= n; i++) cout << -min(w, sufmin[i + 1] - b[i]) << " ";
  cout << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}

缓存模拟（cache）

题目背景

西西艾弗岛半导体制造厂近期正在研发一种新型的处理器产品。该处理器的缓存，计划采用组相连的方式。 为了选定合适的组相连参数，我们需要对缓存的工作过程进行模拟，进而推算其性能。

处理器的缓存，存储着内存中的部分数据。当处理器的运行需要访问内存中的数据时，如果所需数据已经存储在缓存中，则可以用更为快捷的缓存访问代替内存访问，来提高处理器性能。

处理器的缓存包含若干缓存行，每个缓存行存储特定大小的数据。为了便于叙述，我们认为处理器对内存的访问，也是以缓存行为单位进行的。 以缓存行的大小为单位，将全部内存空间划分为若干块（编号从 开始），这样每个内存块的数据便可以恰好存储在一个缓存行中。

-路组相联是这样的一种缓存结构：每 个缓存行划分为一组。假设共有 个这样的组（编号从 到 ），那么编号为 的内存块仅可以被存储在编号为 的组这 个缓存行的任意一个中。其中， 表示忽略余数的整除运算， 表示整除取余数运算。一般而言， 和 是 的幂次。例如，当 、 时，编号为 的内存块可以被存储在组 的任意缓存行中；编号为 的内存块可以被存储在组 的任意缓存行中。

cache

题目描述

具体而言，给定要读取或写入的内存块编号，即可确定该内存块可能位于的缓存行 组的编号。此时，可能存在的情况有两种：

  • 该缓存行组的某个缓存行已经存储了该内存块的数据，即命中；
  • 该缓存行组的所有缓存行都没有存储该内存块的数据，即未命中。

当发生命中时，处理器可以直接使用或修改该缓存行中的数据，而不需要实际读写内存。当发生未命中时，处理器需要从内存中读取数据，并将其存储到该缓存行组中的一个缓存行中，然后再使用或修改该缓存行中的数据。这个将内存中的数据读入到缓存的过程称为载入。

当执行载入操作时，如果该缓存行组中有尚未存储数据的缓存行，那么将数据存储到其中一个尚未存储数据的缓存行中，并在缓存行中记录所存储的数据块的编号；否则，按照一定方法，选择该组中的一个缓存行，并将数据存储到其中，这一过程称为替换。

当发生替换时，需要考虑被替换的缓存行是否发生过修改，即执行过写操作。如果发生过修改，则需要先将缓存行中的数据写入内存中的对应位置；然后忽略该缓存行中的数据、将新读入的数据存入其中，并记录所存储数据块的编号。

在一个缓存行组中选择被替换的缓存行的方法有很多种，该种处理器采用的是最近最少使用（LRU）方法。该方法将一个缓存行组中存有数据的缓存行排成一队，每次读或写一个缓存行时，都将该缓存行动到队列的最前端。当需要替换缓存行时，选择队列的最后一个缓存行（最久没被读写）进行替换。

本题目中，将给出一系列的处理器运行时遇到的对内存的读写指令，并假定初始时处理器的缓存为空。你需要根据上文描述的缓存工作过程，给出处理器对内存的实际读写操作序列。

输入格式

从标准输入读入数据。
输入的第一行包含空格分隔的三个整数 , 分别表示组相联的路数 和组数 ，以及要处理的读写指令的数量 。 接下来 行，每行包含空格分隔的两个整数 和 。其中， 表示读写指令的类型， 表示要读写的内存块的编号。 为 或 ，分别表示读和写操作。

输出格式

输出到标准输出。
输出若干行，每行包含空格分隔的两个整数 和 ，表示实际处理器对内存的读写操作。为 或 ，分别表示读和写操作； 表示要读写的内存块的编号。

样例

样例输入
1
2
3
4
5
6
7
8
9
4 8 8
0 0
0 1
1 2
0 1
1 0
0 32
1 33
0 34
样例输出
1
2
3
4
5
6
7
0 0
0 1
0 2
0 32
1 2
0 33
0 34

样例解释

该处理器的缓存为 路组相联，共有 组。初始时，处理器的缓存为空。共需要处理 条指令：

第 条指令为读取内存块 ，未命中，要实际读取内存块 ，并存储到组 的一个缓存行；
第 条指令为读取内存块 ，未命中，要实际读取内存块 ，并存储到组 的另一个缓存行；
第 条指令为写入内存块 ，未命中，要实际读取内存块 ，并存储到组 的第三个缓存行，然后根据指令在缓存中对其进行修改；
第 条指令为读取内存块 ，命中，直接从缓存中调取数据；
第 条指令为写入内存块 ，命中，直接修改缓存中的数据；
第 条指令为读取内存块 ，未命中，要实际读取内存块 ，并存储到组 的第四个缓存行；
第 条指令为写入内存块 ，未命中，此时组 中的 个缓存行都保存了数据：最近使用的是保存有内存块 的缓存行，其次是保存有内存块 的缓存行，然后是 ，最后是 ，因此选择替换保存有内存块 的缓存行。注意到该缓存行在执行第 条指令时被修改过，因此需要先将其写入内存，然后再读取内存块 的数据存储到该缓存行中；
第 条指令为读取内存块 ，未命中，此时组 中的 个缓存行都保存了数据，按照同样的办法，选择保存有内存块 的缓存行替换。注意到该缓存行未被修改过，因此可以直接读取内存块 的数据存储到该缓存行中。

Solution

其实简单，但是场上没写出来，一个是没心思去读题干，另一个是样例没看明白。这里其实应该提一下如果没有读写内存操作就不输出，我当时没有去对输入输出的条数，看样例解析和输出对不上人傻了。

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define pb push_back
#define PII pair<int, int>
#define fst first
#define snd second
using namespace std;
void solve() {
  int n, N, q;
  int o, a;
  int now = 0;
  int gid;
  cin >> n >> N >> q;
  map<int, pair<int, bool>> state;  // a : {index, isUpdated}
  vector<vector<PII>> cache(N);
  while (q--) {
    cin >> o >> a;  // o: 0: read / 1: write, a: memory block id
    gid = (a / n) % N;
    if (state.count(a)) {
      if (o == 1) {
        state[a].second = true;  // updated
      }
      cache[gid][state[a].first].fst = now;  // last modified time
    } else {
      if ((int)cache[gid].size() < n) {
        state[a].fst = cache[gid].size();  // exist
        cache[gid].pb({now, a});
      } else {
        sort(cache[gid].begin(), cache[gid].end());
        if (state[cache[gid][0].snd].snd == true) {
          cout << 1 << " " << cache[gid][0].snd << endl;
        }
        state.erase(cache[gid][0].snd);  // remove from cache
        cache[gid][0].fst = now;         // last modified time
        cache[gid][0].snd = a;
        state[a].fst = 0;  // exist
      }
      state[a].snd = false;  // not updated
      if (o == 1) {
        state[a].snd = true;  // updated
      }
      cout << 0 << " " << a << endl;
    }
    now++;
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}

我的伞兵代码

1.cpp
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
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pb push_back
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll LLMAX = 9223372036854775807;
const double PI = acos(-1);
using namespace std;
inline void rd(ll &x){
	x=0;
	short f=1;
	char c = getchar();
	while((c < '0' || c > '9') && c != '-') c = getchar();
	if(c == '-') f = -1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	x*=f;
}
inline void pt(ll x){
	if(x<0) putchar('-'), x=-x;
	if(x>9) pt(x/10);
	putchar(x % 10 + '0');
}
void solve(){
	int n,k;
	cin >> n >> k;
	int x,y;
	string s;
	while(k--){
		cin >> x >> y >> s;
		for(char c: s){
			if(c=='f'){
				if (y+1 <= n) y++;
			}else if(c == 'b'){
				if (y-1 >= 1) y--;
			}else if(c == 'l'){
				if (x-1 >= 1)x--;
			}else if(c=='r'){
				if (x+1 <= n)x++;
			}
		}
		cout << x << " " << y << endl;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--) solve();
	return 0;
}
2.cpp
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
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pb push_back
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll LLMAX = 9223372036854775807;
const double PI = acos(-1);
using namespace std;
inline void rd(ll &x){
	x=0;
	short f=1;
	char c = getchar();
	while((c < '0' || c > '9') && c != '-') c = getchar();
	if(c == '-') f = -1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	x*=f;
}
inline void pt(ll x){
	if(x<0) putchar('-'), x=-x;
	if(x>9) pt(x/10);
	putchar(x % 10 + '0');
}
ll a[1010],b[1010],w[1010];
ll suma[1010],sumb[1010];
void solve(){
	int n;
	cin >> n;
	for(int i = 0; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= n; i++){
		cin >> b[i];
	}
	for(int i = 0; i<= n; i++){
		if (i == 0) suma[i] = a[0];
		else suma[i]=suma[i-1]+a[i];
	}
	for(int i = 1; i<= n; i++){
		if (i == 1) sumb[i] = b[1];
		else sumb[i]=sumb[i-1]+b[i];
	}
	int m;
	for(int i = 1; i <= n; i++){
		w[i]=a[0];
		for(int j = 1; j <= n; j++){
//			cout << suma[j]-sumb[j] + (j >= i ? b[i] : 0) << endl;
			w[i] = max(suma[j]-sumb[j] + (j >= i ? b[i] : 0),w[i]);
		}
		cout<<w[i]<<" ";
	}
	cout << endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--) solve();
	return 0;
}
4.cpp
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
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pb push_back
#define ps push
#define pp pop
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll LLMAX = 9223372036854775807;
const double PI = acos(-1);
using namespace std;
inline void rd(ll &x){
	x=0;
	short f=1;
	char c = getchar();
	while((c < '0' || c > '9') && c != '-') c = getchar();
	if(c == '-') f = -1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	x*=f;
}
inline void pt(ll x){
	if(x<0) putchar('-'), x=-x;
	if(x>9) pt(x/10);
	putchar(x % 10 + '0');
}
ll a[(int)1e5+10],k[(int)1e5+10],vis[(int)1e5+10];
void solve(){
	int n;
	rd(n);
	for(int i = 1; i <= n; i++) rd(a[i]);
	for(int i = 1; i <= n; i++) rd(k[i]);
	queue<PLL>q;
	PLL cur;
	int s;
	q.ps({1,0});
	while(q.size()){
		cur = q.front();
//		cout << cur.fst << endl;
		q.pp();
		if(cur.fst == n){
			printf("%d\n",cur.snd);
			return;
		}
		if(vis[cur.fst]) continue;
		vis[cur.fst]=1;
		s = min(n,cur.fst+k[cur.fst]);
		for(int i = cur.fst+1;i<=s;i++){
			if(!vis[i-a[i]]) q.ps({i - a[i],cur.snd+1});
		}
	}
	printf("-1");
}
signed main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--) solve();
	return 0;
}

/** 10
0 1 1 1 1 3 1 0 3 0
2 4 5 4 1 4 1 3 5 3**/

/**
5
0 1 2 3 0
3 4 4 10 15**/
5.cpp
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pb push_back
#define ps push
#define pp pop
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll LLMAX = 9223372036854775807;
const double PI = acos(-1);
using namespace std;
inline void rd(ll &x){
	x=0;
	short f=1;
	char c = getchar();
	while((c < '0' || c > '9') && c != '-') c = getchar();
	if(c == '-') f = -1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	x*=f;
}
inline void pt(ll x){
	if(x<0) putchar('-'), x=-x;
	if(x>9) pt(x/10);
	putchar(x % 10 + '0');
}
ll a[(int)1e5+10],b[(int)1e5+10];map<int,PII>changed;
int dfs(int atk,int l,int r,int mi,int n){
	int la,ra,lb,rb,now=atk;
	int ml,mr;
	if(l>=1 || r<=n){
	//	cout << l << " " << r << " " << atk << " " << mi << endl;
		if(l >= 1 && r <= n){
			la = changed.count(l) ? changed[l].fst : a[l];
			lb = changed.count(l) ? changed[l].snd : b[l];
			ra = changed.count(r) ? changed[r].fst : a[r];
			rb = changed.count(r) ? changed[r].snd : b[r];
			if(now >= la && now >= ra){
				return min(dfs(now+lb,l-1,r,mi,n),dfs(now+rb,l,r+1,mi,n));
			}else if(now >= la){
				return dfs(now+lb,l-1,r,mi,n);
			}else if(now >= ra){
				return dfs(now+rb,l,r+1,mi,n);
			}else{
				return min(dfs(la+lb,l-1,r,la-now+mi,n),dfs(ra+rb,l,r+1,ra-now+mi,n));
			}
		}else if(l>=1){
			la = changed.count(l) ? changed[l].fst : a[l];
			lb = changed.count(l) ? changed[l].snd : b[l];
			if(now >= la){
				return dfs(now+lb,l-1,r,mi,n);
			}else{
				return dfs(la+lb,l-1,r,la-now+mi,n);
			}
		}else if(r<=n){
			ra = changed.count(r) ? changed[r].fst : a[r];
			rb = changed.count(r) ? changed[r].snd : b[r];
			if(now >= ra){
				return dfs(now+rb,l,r+1,mi,n);
			}else{
				return dfs(ra+rb,l,r+1,ra-now+mi,n);
			}
		}
	}
	return mi;
}
void solve(){
	int n,q,k,i,ai,bi,res;
	rd(n);
	for(i = 1; i<=n; i++) rd(a[i]);
	for(i = 1; i<=n; i++) rd(b[i]);
	rd(q);
	int l,r,mi;
	while(q--){
		rd(k);
		changed.clear();
		while(k--){
			rd(i),rd(ai),rd(bi);
			changed[i] = {ai,bi};
		}
		for(int i = 1; i < n; i++){
			mi = dfs(0,i,i+1,0,n);
//			mi = 0;
			//cout << "p" << i << ": " <<  mi << endl;
			if(i==1) res=mi;
			else res^= mi;
		}
		cout << res << endl;
	}
}
signed main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--) solve();
	return 0;
}
/**
6
4 9 3 1 7 7
4 2 1 3 1 4
2
2
3 8 1
5 4 3
0
**/