源代码:ACM/OpenjudgeNow/Codeforces at master · abmcar/ACM (github.com)
A. Reverse
题目大意:
思路:
已知数组为一个排列,那么最优情况应该是1,2,3,4,5,6这种
如果i != nums[i] 不难发现把nums[i]换为i应该是最优的变换
如果有比他更优的选择,则在这个之前存在i != nums[i] 同理,再此之后的变化一定不最优
代码:
void work()
{
cin >> n;
vector<int> nums(n + 1);
for (int i = 1; i <= n; i++)
cin >> nums[i];
vector<int> ans;
bool fir = true;
for (int i = 1; i <= n; i++)
{
if (fir)
if (i != nums[i])
{
fir = false;
stack<int> s;
for (int j = i; j <= n; j++)
{
s.push(nums[j]);
if (nums[j] == i)
{
for (int k = i; k <= j; k++)
{
nums[k] = s.top();
s.pop();
}
break;
}
}
}
cout << nums[i] << " ";
}
cout << endl;
}
B. Odd Swap Sort
题目大意:
思路:
已知元素只能和相邻的交换
同时,奇数+奇数 = 偶数, 偶数 + 偶数 = 偶数 我们发现
奇数只能和偶数交换,偶数只能和奇数交换
因此我们按奇偶性分为两个数组,如果他们是非递减的,则可以构成非递减
否则因为同奇偶间无法交换,则不可能构成非递减
代码:
void work()
{
cin >> n;
vector<int> nums(n + 1);
for (int i = 1; i <= n; i++)
cin >> nums[i];
vector<int> n1, n2;
for (int i = 1; i <= n; i++)
{
if (nums[i] % 2)
n1.push_back(nums[i]);
else
n2.push_back(nums[i]);
}
// cout << n1.size() << " " << n2.size() << Endl;
for (int i = 0; i < int(n1.size() - 1); i++)
{
if (n1[i] > n1[i + 1])
{
cout << "No" << endl;
return;
}
}
for (int i = 0; i < int(n2.size() - 1); i++)
if (n2[i] > n2[i + 1])
{
cout << "No" << endl;
return;
}
cout << "Yes" << endl;
}
C. Inversion Graph
题目大意:
思路:
单调栈维护起点,当nums[i] > s.top() 时,说明之前所有点无法建边, 压入栈
当 nums[i] < s.top()时, pop掉所有大于nums[i]的点,因为他们可以和其建边
代码:
void work()
{
cin >> n;
vector<int> nums(n+1);
for (int i = 1; i <= n; i++)
cin >> nums[i];
stack<int> s;
for (int i = 1; i <= n; i++)
{
if (s.empty() || s.top() < nums[i])
s.push(nums[i]);
else
{
int nowTop = s.top();
while (!s.empty() && s.top() > nums[i])
s.pop();
s.push(nowTop);
}
}
cout << s.size() << Endl;
}
D. Big Brush
题目大意:
思路:
一个思路简单但实现十分复杂的题
考虑倒着操作,我们可以找到最后一次操作的位置,判断周围
如果周围是前一次操作,则那4个格子除了被最后一次涂了之外,应该只有1中颜色
按照此思路bfs扩展,每找到一个位置就用栈记录下了
最后判断是否所有格子都被涂过了即可
代码:
bool check(int x, int y)
{
if (x + 1 > n || y + 1 > m)
return false;
if (x < 1 || y < 1)
return false;
int cnt = 0;
unordered_map<int, bool> M;
if (bd[x][y] != -1)
M[bd[x][y]] = true, cnt++;
if (bd[x + 1][y] != -1)
M[bd[x + 1][y]] = true, cnt++;
if (bd[x][y + 1] != -1)
M[bd[x][y + 1]] = true, cnt++;
if (bd[x + 1][y + 1] != -1)
M[bd[x + 1][y + 1]] = true, cnt++;
return M.size() == 1;
}
void clear(int x, int y)
{
bd[x][y] = -1;
bd[x + 1][y] = -1;
bd[x][y + 1] = -1;
bd[x + 1][y + 1] = -1;
}
int getColor(int x, int y)
{
if (bd[x][y] != -1)
return bd[x][y];
if (bd[x + 1][y] != -1)
return bd[x + 1][y];
if (bd[x][y + 1] != -1)
return bd[x][y + 1];
if (bd[x + 1][y + 1] != -1)
return bd[x + 1][y + 1];
}
signed main()
{
cin >> n >> m;
bd = new vector<int>[n + 10];
for (int i = 0; i < n + 5; i++)
bd[i].resize(m + 10);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> bd[i][j];
queue<pair<int, int>> Q;
stack<vector<int>> ansS;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (bd[i][j] == bd[i][j + 1] && bd[i][j + 1] == bd[i + 1][j] && bd[i][j] == bd[i + 1][j + 1])
{
Q.push({i, j});
ansS.push({i, j, bd[i][j]});
clear(i, j);
// break;
}
}
while (!Q.empty())
{
int nowX = Q.front().first;
int nowY = Q.front().second;
Q.pop();
for (int i = 0; i < neX.size(); i++)
{
int nextX = nowX + neX[i];
int nextY = nowY + neY[i];
if (!check(nextX, nextY))
continue;
Q.push({nextX, nextY});
ansS.push({nextX, nextY, getColor(nextX, nextY)});
clear(nextX, nextY);
}
}
bool ok = true;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (bd[i][j] != -1)
ok = false;
if (!ok)
{
cout << -1 << endl;
return 0;
}
cout << ansS.size() << endl;
while (!ansS.empty())
{
vector<int> tmp = ansS.top();
ansS.pop();
for (int i = 0; i < 3; i++)
cout << tmp[i] << " \n"[i == 2];
}
return 0;
}