# 2023/03/15刷题()-其他

## 2023/03/15刷题()

### 链接

B. Sort the Array

``````#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 100008;
int a[N];
signed main () {
int n;
map<int, int> mp;
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
int flag = 1;
for (int i = 1; i <= n - 1; i++) {
if (a[i] > a[i + 1]) {
flag = 0;
break;

}
}
if (flag == 1) {
cout << "yes" << '\n';
cout << 1 << ' ' << 1 << '\n';
return 0;
}//还是先不进行操作之前进行判断,满足操作打印1  1

int l = -1;
int r = -1;
for (int i = 1; i <= n - 1; i++) {
if (a[i] > a[i + 1]) {
l = i;//找到最左边的点
break;

}
}
for (int i = n; i >= 2; i--) {
if (a[i] < a[i - 1]) {
r = i;//找到最右边的点
break;
}
}

reverse(a + l, a + r + 1);//翻转
flag = 1;
for (int i = 1; i <= n - 1; i++) {
if (a[i] > a[i + 1]) {
flag = 0;
break;

}
}//再次判断
if (flag == 1) {//打印结果

cout << "yes" << '\n';
cout << l << ' ' << r << '\n';
return 0;
} else {

cout << "no" << '\n';

}

//		cout<<a[i]<<' ';
//
//	}

return 0;
}
``````

``````#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 100008;
int a[N], b[N];
signed main () {
int n;
map<int, int> mp;
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &b[i]);
a[i] = b[i];//读入数据并且让a数组和b数组相同
}
sort(b + 1, b + n + 1);//对b数组排序
for (int i = 1; i <= n; i++) {
mp[b[i]] = i;//对b[i]映射到下标
}
for (int i = 1; i <= n; i++) {
a[i] = mp[a[i]];//然后将映射的结果赋值给a,这样a数组就构造好了
}
//	for(int i=1;i<=n;i++){
//		cout<<a[i]<<' ';
//
//	}
int flag = 1;
for (int i = 1; i <= n; i++) {
if (a[i] != i) {
flag = 0;
}
}//先判断一下不用操作是不是可以满足条件
if (flag == 1) {
cout << "yes" << '\n';
cout << 1 << ' ' << 1 << '\n';
return 0;//如果满足打印1  1

}
//否则
int l = -1;
for (int i = 1; i <= n; i++) {
if (a[i] != i) {
l = i;//找到第一个和i不同的数就退出
break;
}
}

int r = -1;
for (int i = n; i >= 1; i--) {
if (a[i] != i) {//倒着寻找最后一个和i不同的数
r = i;
break;
}
}

flag = 1;
reverse(a + l, a + r + 1);//翻转这个区间
for (int i = 1; i <= n; i++) {//判断一下
if (a[i] != i) {
flag = 0;
break;
}
}
if (flag == 1) {//flag=1打印yes和区间信息

cout << "yes" << '\n';
cout << l << ' ' << r << '\n';

} else {
cout << "no" << '\n';

}

return 0;
}

``````

### 链接

B. Worms

``````#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 100008;
int a[N], b[N], s[N];
signed main () {
int n, m;
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
s[i] = s[i - 1] + a[i];//前缀和处理
}
scanf("%lld", &m);//m次查找
while (m--) {
int x;
scanf("%lld", &x);
int l = 0, r = n + 1;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (s[mid] < x) {//分界线为小于x

l = mid;
} else {
r = mid;
}
}
//因为要查找x所在的区间的话
cout << r << '\n';//返回r

}

}
``````

### 链接

C. K-th Not Divisible by n

``````#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 100008;

void solve() {
int n, k;
cin >> n >> k;
int ans;

if (k % (n - 1) == 0) {//如果k%(n-1)为0的话
ans = (k / (n - 1)) + k;//ans
//(k / (n - 1))为需要补的数字,因为如果按照这种情况加上k % (n - 1) == 0,会多加一个之母
cout << ans - 1 << '\n';//打印ans-1
} else {
ans = (k / (n - 1)) + k;//否则直接打印ans就可以

cout << ans << '\n';

}

}
signed main () {
int t;
cin >> t;
while (t) {
solve();
t--;
}

return 0;
}
``````

### 链接

B. Polycarp Training

``````#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 200008;
int a[N];
signed main () {
int n;
scanf("%lld", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
sort(a, a + n);//排序
int ans = 1;//初始化ans为1
for (int i = 0; i < n; i++) {
if (a[i] >= ans) {
ans++;//满足条件ans++
}

}
cout << ans - 1 << '\n';//打印结果

return 0;
}
``````
————————

### 链接

B. Sort the Array

``````#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 100008;
int a[N];
signed main () {
int n;
map<int, int> mp;
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
int flag = 1;
for (int i = 1; i <= n - 1; i++) {
if (a[i] > a[i + 1]) {
flag = 0;
break;

}
}
if (flag == 1) {
cout << "yes" << '\n';
cout << 1 << ' ' << 1 << '\n';
return 0;
}//还是先不进行操作之前进行判断,满足操作打印1  1

int l = -1;
int r = -1;
for (int i = 1; i <= n - 1; i++) {
if (a[i] > a[i + 1]) {
l = i;//找到最左边的点
break;

}
}
for (int i = n; i >= 2; i--) {
if (a[i] < a[i - 1]) {
r = i;//找到最右边的点
break;
}
}

reverse(a + l, a + r + 1);//翻转
flag = 1;
for (int i = 1; i <= n - 1; i++) {
if (a[i] > a[i + 1]) {
flag = 0;
break;

}
}//再次判断
if (flag == 1) {//打印结果

cout << "yes" << '\n';
cout << l << ' ' << r << '\n';
return 0;
} else {

cout << "no" << '\n';

}

//		cout<<a[i]<<' ';
//
//	}

return 0;
}
``````

``````#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 100008;
int a[N], b[N];
signed main () {
int n;
map<int, int> mp;
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &b[i]);
a[i] = b[i];//读入数据并且让a数组和b数组相同
}
sort(b + 1, b + n + 1);//对b数组排序
for (int i = 1; i <= n; i++) {
mp[b[i]] = i;//对b[i]映射到下标
}
for (int i = 1; i <= n; i++) {
a[i] = mp[a[i]];//然后将映射的结果赋值给a,这样a数组就构造好了
}
//	for(int i=1;i<=n;i++){
//		cout<<a[i]<<' ';
//
//	}
int flag = 1;
for (int i = 1; i <= n; i++) {
if (a[i] != i) {
flag = 0;
}
}//先判断一下不用操作是不是可以满足条件
if (flag == 1) {
cout << "yes" << '\n';
cout << 1 << ' ' << 1 << '\n';
return 0;//如果满足打印1  1

}
//否则
int l = -1;
for (int i = 1; i <= n; i++) {
if (a[i] != i) {
l = i;//找到第一个和i不同的数就退出
break;
}
}

int r = -1;
for (int i = n; i >= 1; i--) {
if (a[i] != i) {//倒着寻找最后一个和i不同的数
r = i;
break;
}
}

flag = 1;
reverse(a + l, a + r + 1);//翻转这个区间
for (int i = 1; i <= n; i++) {//判断一下
if (a[i] != i) {
flag = 0;
break;
}
}
if (flag == 1) {//flag=1打印yes和区间信息

cout << "yes" << '\n';
cout << l << ' ' << r << '\n';

} else {
cout << "no" << '\n';

}

return 0;
}

``````

### 链接

B. Worms

``````#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 100008;
int a[N], b[N], s[N];
signed main () {
int n, m;
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
s[i] = s[i - 1] + a[i];//前缀和处理
}
scanf("%lld", &m);//m次查找
while (m--) {
int x;
scanf("%lld", &x);
int l = 0, r = n + 1;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (s[mid] < x) {//分界线为小于x

l = mid;
} else {
r = mid;
}
}
//因为要查找x所在的区间的话
cout << r << '\n';//返回r

}

}
``````

### 链接

C. K-th Not Divisible by n

``````#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 100008;

void solve() {
int n, k;
cin >> n >> k;
int ans;

if (k % (n - 1) == 0) {//如果k%(n-1)为0的话
ans = (k / (n - 1)) + k;//ans
//(k / (n - 1))为需要补的数字,因为如果按照这种情况加上k % (n - 1) == 0,会多加一个之母
cout << ans - 1 << '\n';//打印ans-1
} else {
ans = (k / (n - 1)) + k;//否则直接打印ans就可以

cout << ans << '\n';

}

}
signed main () {
int t;
cin >> t;
while (t) {
solve();
t--;
}

return 0;
}
``````

### 链接

B. Polycarp Training

``````#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 200008;
int a[N];
signed main () {
int n;
scanf("%lld", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
sort(a, a + n);//排序
int ans = 1;//初始化ans为1
for (int i = 0; i < n; i++) {
if (a[i] >= ans) {
ans++;//满足条件ans++
}

}
cout << ans - 1 << '\n';//打印结果

return 0;
}
``````