「LGOJ」2.6模拟赛

概述

​ LG冬眠营的模拟赛 sorce:90 + 50 + 0 + 0 = 140 Rank 14

​ 还是菜了 同群聚聚210 Orz

A

​ 欧稳欧有若干不同种类的水果,用正整数来编号大小,两个大小为t的水果可以用来合成一个大小为t+1的水果。
现在给出初始的水果,欧稳欧可以任意合成,来让最大的水果尽可能大,你需要计算出这个最大的大小。

​ 我们考虑用一个桶来存入数据 (题目中的 t <= 100 可以存得下来

​ 然后遍历一遍桶,大于2的就下一个桶++,记得%(好像这里无所谓

​ 但是!我90!,因为我输出时是从n…1的,但是又极端情况是全部可以加起来

​ 所以应该从n+1….1 这样子就100了qwq

Code

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
#include <bits/stdc++.h>

#define ll long long
#define RE register

int n,x,f[100100];

inline void fread(int &x) {
x = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9') {
x = (x<<3) + (x<<1) + (ch^48);
ch = getchar();
}
x = x * f;
}

int main() {
//std::freopen("data4.in","r",stdin);
fread(n);
for(RE int i = 1 ; i <= n ; i++) {
fread(x);
f[x]++;
}
for(RE int i = 1 ; i <= n ; i++) {
if(f[i] >= 2){
int p = f[i] / 2;
f[i+1] += p;
f[i] = f[i] % 2;
}
}

for(RE int i = n+1 ; i >= 1 ; i--) {
if(f[i] > 0) {
std::printf("%d\n",i);
break;
}
}
return 0;
}

B

​ 欧稳欧学完了车,去找司玩游戏。

​ 司有n个倒扣的杯子排成一行,一开始11号位置的杯子里面放有一块金牌。司会不断交换两个杯子,最后欧稳欧需要猜出金牌在哪个杯子里

​ 虽然司的动作很快,欧稳欧也很快发现了规律:司会按照一定顺序交换某些位置上的杯子,然后将这一系列动作重复很多遍。具体地,每一轮中,司会执行固定的m个交换,总共循环k

​ 一眼觉得周期问题,但是我是考虑了似过了某几轮是一个周期,然后思路歪到了连边建图上(图遍历K遍

​ 正解:对于1…n个位置我们可以预处理出当奖品在位置i时,经过一轮后所在的位置

​ 然后暴力枚举K次即可

Code

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
#include <bits/stdc++.h>

#define ll long long
#define RE register

#define maxn 100010

struct node{
int a,b;
}f[100010];

int p[10010],ans=0;

inline void fread(int &x) {
x = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9') {
x = (x<<3) + (x<<1) + (ch^48);
ch = getchar();
}
x = x * f;
}

int main() {
int n,m,k;
fread(n);
fread(m);
fread(k);
for(RE int i = 1 ; i <=m; i++) {
fread(f[i].a);
fread(f[i].b);
}
for(RE int i = 1 ; i <= n ;i++) {
p[i] = i;
for(RE int j = 1 ;j <= m;j++) {
if(p[i] == f[j].a) {
p[i] = f[j].b;
}else if(p[i] == f[j].b) {
p[i] = f[j].a;
}
}
}
ans = p[1];
for(RE int i = 2 ; i <= k ;i++) {
ans = p[ans];
}
printf("%d\n",ans);
return 0;
}

C

​ 题目体积太大 戳这里

​ 裸的搜索,主要是多个路由器怎么处理

​ 用bfs,然后把路由器全部进队即可

​ 曼哈顿距离是指两个点之间形成的三角形的两个直角边之和

Code

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
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define RE register

typedef pair<int,int> pii;

int ans=0,d[1005][1005];
int n,m;
char f[1005][1005];

queue<pii> q;

inline void fread(int &x) {
x = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9') {
x = (x<<3) + (x<<1) + (ch^48);
ch = getchar();
}
x = x * f;
}

inline void bfs() {
while(!q.empty()) {
pii w = q.front();
int x = w.first;
int y = w.second;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
q.pop();
for(RE int i = 0 ;i < 4; i++) {
int xx = dx[i] + x;
int yy = dy[i] + y;
if(xx > 0 && yy > 0 && xx <= n && yy <= m&& f[xx][yy] == '.') {
if(d[xx][yy] == -1) {
d[xx][yy] = d[x][y] + 1;
ans = max(ans,d[xx][yy]);
q.push(pii(xx,yy));
}
}
}
}
}

int main() {
fread(n);
fread(m);
memset(d,-1,sizeof(d));
for(int i = 1 ;i <= n; i++) {
for(int j =1 ;j <= m; j++) {
char ch;
cin>>ch;
f[i][j] = ch;
if(ch == 'o') {
q.push(pii(i,j));
d[i][j] = 0;
}
}
}
bfs();
std::printf("%d",ans);
return 0;
}

D

​ 欧稳欧有一个小写字母组成的字符串s,但是他觉得这个字符串不好看,于是决定把它倒过来。

​ 每次操作可以交换两个相邻的字符,求将s变为与s顺序相反的字符串的最小操作次数

​ 这道题有点贪心的意思啦 . 我们对于一个翻转了的字符串s中的一个字符k

​ 考虑这个k是怎么来的

​ 如果要操作数最小,那么是不是越近越好

​ 所以这个k应该来自源字符串第一次出现k的位置

​ 以此类推,第二个k就在源字符串找第二次出现k的位置

​ 我们开一个二位的vector记录一下,就可以得到一个数组a

​ $a_{i}$表示翻转后第i个字母来源于源字符串的第$a_{i}$个

​ 直接求逆序对就行了(逆序对的个数等于在朴素稳定排序情况下,相邻数交换的次数

​ 这里相当于冒泡是稳定的qwq

​ 这里是归并排序,用树状数组会慢一点

Code

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
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define RE register

vector <int> p[28];
int head[28],f[100010],a[100010];

inline void fread(int &x) {
x = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9') {
x = (x<<3) + (x<<1) + (ch^48);
ch = getchar();
}
x = x * f;
}

inline int sovle(int l,int r) {
if(l == r)return 0;
int mid = (l + r) / 2;
int ans = sovle(l,mid) + sovle(mid+1,r);
int i = l;
int j = mid+1;
int k = l;
while(i <= mid && j <= r) {
if(a[i] <= a[j]) {
f[k++] = a[i++];
}else {
ans += mid - i + 1;
f[k++] = a[j++];
}
}
while(i <= mid)f[k++] = a[i++];
while(j <= r)f[k++] = a[j++];
for(RE int i = l; i <= r ; i++)
a[i] = f[i];
return ans;
}

int main() {
string ch;
cin>>ch;
for(RE int i = 0;i < ch.length(); i++)
p[ch[i] - 'a'].push_back(i);
for(RE int i = 0;i < ch.length(); i++) {
int z = ch.length() - i - 1;
a [ p[ch[z] - 'a' ][head [ch[z] - 'a' ] ] ] = i;
head[ch[z] - 'a']++;
}
printf("%d\n",sovle(0,ch.length() - 1));
return 0;
}

0%