Codeforces Round #792 (Div. 1 + Div. 2)
Problem A
题目保证了没有0，那么一直除以10，取模10的数最小。但是要特判一位数和两位数的情况。
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
int n, T = 1;
void ready()
{
int cnt = 0;
cin >> n;
int t = n;
int minn = 10;
while (n) {
cnt++;
minn = min(n % 10, minn);
n /= 10;
}
if (cnt == 2) {
minn = t % 10;
}
cout << minn << '\n';
}
void work()
{
}
signed main()
{
IOS;
cin>>T;
while (T--) {
ready();
work();
}
return 0;
}
Problem B
三种情况，使x=a或y=b或z=c，三种情况分别推出x，y，z的公式，都去判断是否满足条件即可。
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
int n, T = 1;
int a, b, c;
int x, y, z;
void ready()
{
cin >> a >> b >> c;
}
bool check_() {
if (x % y == a && y % z == b && z % x == c)
return true;
return false;
}
void work()
{
x = a; y = a + b + c; z = a + c;
if (check_()) {
cout << x << ' ' << y << ' ' << z << '\n';
return;
}
x = a + b; y = b; z = a + b + c;
if (check_()) {
cout << x << ' ' << y << ' ' << z << '\n';
return;
}
x = a + b + c; y = b + c; z = c;
if (check_()) {
cout << x << ' ' << y << ' ' << z << '\n';
return;
}
}
signed main()
{
IOS;
cin>>T;
while (T--) {
ready();
work();
}
return 0;
}
Problem C
只能调换两列，如果一行非递增，调换了两列之后成为了递增，那么其他行业必须调转这两列也是递增的状态。所以每一行每一行操作，排序后判断是否有错位的列，如果错位的列数超过2，则直接输出-1。如果所有行都判断后错位的列数为0，则说明已经处于递增情形，交换1行和1列。如果出现了错位列数刚好为2 的，跳出循环，调换这两列，看之后的总体是否也是递增的即可。
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
const int N = 2e5 + 5;
vector<int> ve[N];
vector<int> bad;
vector<int> alls;
unordered_set<int> se;
int n, T = 1, m;
int a[N];
int f[N];
void ready()
{
cin >> n >> m;
ffor(i, 1, n) {
ve[i].clear();
ffor(j, 1, m) {
int temp;
cin >> temp;
ve[i].push_back(temp);
}
}
ffor(i, 1, m) f[i] = false;
}
int find(int x) {
int l = 0, r = alls.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}
void out() {
cout << "f=";
ffor(i, 1, m) cout << f[i] << ' ';
cout << '\n';
}
void work()
{
bad.clear();
bool win = true;
ffor(i, 1, n) {
alls.clear();
for (auto item : ve[i]) {
alls.push_back(item);
}
sort(alls.begin(), alls.end());
for (int j = 0; j < m; j++) {
if (alls[j] != ve[i][j]) {
bad.push_back(j);
win = false;
}
}
if (!win) {
break;
}
}
if (win) {
cout << "1 1\n";
return;
}
if (bad.size() != 2) {
//cout << "size=" << bad.size() << '\n';
cout << "-1\n";
return;
}
int l = bad[0], r = bad[1];
//cout << l << ' ' << r << '\n';
ffor(i, 1, n) swap(ve[i][l], ve[i][r]);
win = true;
ffor(i, 1, n) {
ffor(j, 1, m - 1) {
if (ve[i][j] < ve[i][j - 1]) {
win = false;
break;
}
}
}
if (win) cout << l + 1 << ' ' << r + 1 << '\n';
else cout << -1 << '\n';
}
signed main()
{
IOS;
cin>>T;
while (T--) {
ready();
work();
}
return 0;
}
Problem D
贪心，跳过a[i]+i最大的点。
感谢Lnn哥的解答，为何能选择这个贪心策略。
主要还是j的和是固定的，这个比较难想到。
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n, T = 1, k;
PII a[N];
bool f[N];
int b[N];
void ready()
{
cin >> n >> k;
ffor(i, 1, n) {
f[i] = false;
cin >> a[i].first;
a[i].second = i;
b[i] = a[i].first;
a[i].first += i;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n;i++) {
PII item = a[i];
//cout << item.first << ' ' << item.second << '\n';
}
}
void work()
{
rrep(i, n, n - k + 1) f[a[i].second] = true;
int ans = 0, t = 0;
ffor(i, 1, n) {
if (!f[i]) {
ans += b[i] + t;
}
else {
t++;
//cout << "i=" << i << "\n";
}
}
cout << ans << '\n';
}
signed main()
{
IOS;
cin>>T;
while (T--) {
ready();
work();
}
return 0;
}
