序言

还得是黄神！比赛直接AC四题！挽救了我们队！

2488: Reposts

这题有点像食物链，即第二人转发消息（repost）到第一个人，再以此类推。要求求最大的传播链长度，由于我们不需要考虑该网民不知道消息转发的情况。因此可以采用队列来存储传递信息，用map存储食物链

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 <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>    
#include <utility>    //pair
using namespace std;

typedef pair<string, string> PII;   //二元组

queue<PII> que1;
unordered_map<string, int> unmap;
void bfs() {
  while (!que1.empty()) {
    string str1 = que1.front().first;
    string str2 = que1.front().second;
    auto it = unmap.find(str2);
    // cout << que1.front().first << que1.front().second << endl;

    if (it != unmap.end()) {
      unmap.insert({str1, it->second + 1});
    }
    que1.pop();
  }
}

int main() {
  int n;
  cin >> n;
  int cnt = 0;
  unmap.insert({"POLYCARP", 1});		//始作俑者
  for (int i = 0; i < n; i++) {
    string str1, tmp, str2;
    cin >> str1 >> tmp >> str2;
    transform(str1.begin(), str1.end(), str1.begin(), ::toupper);	//不区分大小写，将
    transform(str2.begin(), str2.end(), str2.begin(), ::toupper);	//id全部转化为大写

    que1.push({str1, str2});
  }
  bfs();
  for (auto x : unmap) {
    // cout << x.first << x.second << endl;
    cnt = max(cnt, x.second);
  }

  cout << cnt << endl;
}

1412: Ice cream coloring

//TODO

3258: Copying Data

由于集训时长限制为2s，因此正常的复制粘贴也是能过的。

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
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];

int main() {
  std::ios::sync_with_stdio(false);

  // 取消cin和cout的绑定
  std::cin.tie(NULL); /*等价于cin.tie(0);*/
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  for (int i = 1; i <= n; i++)
    cin >> b[i];
  while (m--) {
    int op;
    cin >> op;
    if (op == 1) {
      int a1, b1, c1;
      cin >> a1 >> b1 >> c1;
      for (int i = 0; i < c1; i++) {
        b[b1 + i] = a[i + a1];
      }
    }

    if (op == 2) {
      int pos;
      cin >> pos;
      cout << b[pos] << endl;
    }
  }
}

但是这题的正确题解为线段树：线段树能在O(logN)的条件下实现单点和区间操作。

//TODO

3238: Sail

我刚看题目以为是要用bfs做(这里队列数据量太大$2^{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
#include <algorithm>
#include <iostream>
using namespace std;
string s;
int main() {
  int t;
  long long sx, sy, ex, ey;
  cin >> t >> sx >> sy >> ex >> ey;
  if (sx == ex && sy == ey) {
    printf("0");
    return 0;
  }
  cin >> s;
  for (int i = 0; i < t; i++) {
    if (s[i] == 'E' && sx < ex)
      sx += 1;
    else if (s[i] == 'W' && sx > ex)
      sx -= 1;
    else if (s[i] == 'N' && sy < ey)
      sy += 1;
    else if (s[i] == 'S' && sy > ey)
      sy -= 1;
    if (sx == ex && sy == ey) {
      printf("%d", i + 1);
      return 0;
    }
  }
  printf("-1");
  return 0;
}

3157: IQ Test

判断数列是等差还是等比，输出下一项；若不是则输出42。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>
using namespace std;
int a, b, c, d;
int main()
{
	cin >> a >> b >> c >> d;
	if (a - b == b - c && b - c == c - d)		//等差
		cout << d - (a - b);
	else if (a * c == b * b && d * b == c * c)		//等比
		if (d * d % c)
			cout << "42";
		else
			cout << d * d / c;
	else
		cout << "42";
	return 0;
}

1322: Office Keys

这题有二分+贪心和dp+贪心两种做法。

A. Office Keys(贪心+二分枚举)_有n个人和k把钥匙在一条直线上,每个人都想去位于直线p点的办公室找陈老师问题目。-CSDN博客

我们使用二分来确定对应的值，然后用贪心的思路，先将钥匙和人从小到大排序，找到一个最小的 x，使得对于每个 a[i]，可以找到一个 b[j] 使得 |a[i] - b[j]| + |p - b[j]| <= x。从最靠近原点的人和钥匙开始枚举，若每个人都能在x的时间内找到，则答案在l-x区间否则在x-r区间。最后得出最终答案。

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

#include<iostream>
#include <algorithm>
using namespace std;
const int maxn=2e3+10;
typedef long long LL;
LL a[maxn],b[maxn];
LL n,k,p;
bool check(LL x)
{
	LL i=1;
	for(LL j=1;j<=k;j++){
		if(abs(a[i]-b[j])+abs(p-b[j])<=x){
			i++;
		}
		if(i>n) return true; 
	}
	return false;
}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  cin>>n>>k>>p;
  for(LL i=1;i<=n;i++) cin>>a[i];
  for(LL i=1;i<=k;i++) cin>>b[i];
  sort(a+1,a+1+n);sort(b+1,b+1+k);      
  LL l=0;LL r=2e9+100;
  while(l<r)
  {
  	LL mid=(l+r)/2;
  	if(check(mid)) r=mid;
  	else l=mid+1;
  }
  cout<<l<<endl;
return 0;

}

dp题解：CF830A Office Keys - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

2513: Drazil and Factorial

模拟题，将该数拆成更小的阶乘并从大到小输出。

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
#include <stdio.h>
int num[20];
int arr[20];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int a;
		scanf("%1d", &a);
		if (a == 2)
		{
			arr[2]++;
		}
		else if (a == 3)
		{
			arr[3]++;
		}
		else if (a == 4)
		{
			arr[2] += 2;
			arr[3]++;
		}
		else if (a == 5)
		{
			arr[5]++;
		}
		else if (a == 6)
		{
			arr[5]++;
			arr[3]++;
		}
		else if (a == 7)
		{
			arr[7]++;
		}
		else if (a== 8)
		{
			arr[2]+=3;
			arr[7]++;
		}
		else if (a == 9)
		{
			arr[2]++;
			arr[3] += 2;
			arr[7]++;
		}
		
	}
	for (int i = 1; i <= arr[7]; i++) {
		printf("7");
	}
	for (int i = 1; i <= arr[5]; i++) {
		printf("5");
	}
	for (int i = 1; i <= arr[3]; i++) {
		printf("3");
	}
	for (int i = 1; i <= arr[2]; i++) {
		printf("2");
	}
	return 0;
}