7.10 多校适应训练1

比赛过程

今天比赛自己十分混乱，开场和队友商量看C，遇上小学期第一天下午老师讲课，边听课边思考，一度裂开。后面想到了方法但是还是wa了(枯了)。

题解

I：思维模拟

题意
两个人A和B分别持有两个数组，每一轮都要扔出去一个数，直到最后都只剩下最后一个数字。A想要使得两个数的差最多，B则相反。现在给你数组，要你求出两人的最佳决策后最后的答案。

思路
不管A剩下哪一个数字，B都有办法剩下那个与之相差最小的数。那么答案就是A的所有数与B的所有数字中最小差里面最大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n, a[N], b[N];

int main() {
   scanf("%d", &n);
   for1(i, n) scanf("%d", a+i);
   for1(i, n) scanf("%d", b+i);
   int ans = 0, minn;
   for1(i, n) {
      minn = INF;
      for1(j, n) {
         minn = min(minn, abs(a[i] - b[j]));
      }
      ans = max(ans, minn);
   }
   cout<<ans<<endl;
}
D：找出规律构造

题意
给出一个长度为2n的循环字符串，问是否能重新排列使得没有相同的长度为n的子串。

思路
分四种情况：

  1. 只有一种字符，不可能成功；
    有两种字符，其中一种占一半以上，另一半一定<=n.

  2. 少的一种小于3时，不可能成功；

  3. 少的一种至少为3个，成功；

  4. 如果种类多于2种，成功；

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
vector<char> v;
map<char, ll> mp;
int main() {
	string s;
	cin >> s;
	ll n = (int)s.length() / 2;
	for (auto it : s) {
		if (mp[it] == 0)
			v.push_back(it);
		mp[it]++;
	}
	if (v.size() == 1) {
		puts("NO");
		return 0;
	}
	int flag = 0;
	if (v.size() == 2) {
		if ((mp[v[0]] > n && mp[v[1]] < 3) || (mp[v[1]] > n && mp[v[0]] < 3)) {
			puts("NO");
			return 0;
		}
		if (mp[v[0]] > n && mp[v[1]] >= 3) {
			mp[v[1]]--;
			flag = 1;
		}
		else if (mp[v[1]] > n && mp[v[0]] >= 3) {
			char tem = v[0];
			v[0] = v[1];
			v[1] = tem;
			mp[v[1]]--;
			flag = 1;
		}
	}
	puts("YES");
	queue<char> q;
	char la = '0';
	for (auto it : v)
	{
		q.push(it);
		if (la != '0') q.push(la);
		if (mp[it] > n) la = it;
	}
	while (!q.empty()) {
		char t = q.front();
		q.pop();
		int len = min(mp[t], n);
		mp[t] -= len;
		for1(i, len) cout<<t;
	}
	if (flag == 1)
		cout << v[1];
	puts("");
}
B：DP

题意
有n个问题和两种状态。每个问题的两种状态下获得的经验和所需时间都不同。初始状态为状态一，且获得足够经验后才可以到状态二，同理获得足够经验才可以通过状态二。求通关的最短时间。

思路
建立三维dp数组dp[i][j][k]，代表解决任务i是获得状态一的j点经验，状态二的k点经验。

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
struct ac{
  ll x, t, y, r;
} a[501];
bool cmp(ac a,ac b){
  return a.x < b.x;
}
ll dp[2][501][501];
int main() {
    ll n, s1, s2, f = 0;
    cin >> n >> s1 >> s2;
    for(int j = 0; j <= s1; ++j) for(int k = 0; k <= s2; ++k) {
        dp[0][j][k] = INF;
    }
    dp[0][0][0] = 0;
    for1(i, n) {
      cin >> a[i].x >> a[i].t >> a[i].y >> a[i].r;
    }
    sort(a + 1, a + 1 + n, cmp);
    for1(i, n) {
      for(int j = 0; j <= s1; ++j) for(int k = 0; k <= s2; ++k) {
          dp[f ^ 1][j][k] = dp[f][j][k];
      }
      for(int j = 0; j <= s1; ++j) {
        for(int k = 0; k <= s2; ++k){
          if(dp[f][j][k] < INF){
            if(j<s1){
              if(j+a[i].x<s1){
                dp[f ^ 1][j + a[i].x][k] = min(dp[f ^ 1][j + a[i].x][k], dp[f][j][k] + a[i].t);
              }
              else{
                dp[f ^ 1][s1][min(k + j + a[i].x - s1, s2)] = min(dp[f ^ 1][s1][min(k + j + a[i].x - s1, s2)], dp[f][j][k] + a[i].t);
              }
            }
            if(k + a[i].y<s2){
              dp[f ^ 1][j][k + a[i].y] = min(dp[f ^ 1][j][k + a[i].y], dp[f][j][k] + a[i].r);
            }
            else{
              dp[f ^ 1][j][s2] = min(dp[f ^ 1][j][s2], dp[f][j][k] + a[i].r);
            }
          }
        }
      }
      f ^= 1;
    }
    if(dp[f][s1][s2]>0&&dp[f][s1][s2]<INF) cout << dp[f][s1][s2] << endl;
    else cout << -1 << endl;
    return 0;
}
一只GIS专业的ACMer