- Atcoder训练
- Flipping Signs
思维
通过打表观察发现，当负数为偶数时可以全部转化为正，不为偶数时，会留下一个负数，我们取绝对值最小的即可。
- Flipping Signs
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll cd[1000010];
int main(){
ll n;
ll sum=0;
ll mi=2e18;
cin>>n;
vector<ll>v(n+1);
ll fu=0;
for(int i=1;i<=n;i++){
cin>>v[i];
if(v[i]<0)fu++;
sum+=abs(v[i]);
mi=min(mi,abs(v[i]));
}
if(fu%2==0){
cout<<sum;
}else
cout<<sum-2*mi;
}
- Rectangle Cutting
思维
通过该点怎么划分的面积小的最大，只要不是矩形最中间的点，都只有一种可能，其他情况都能分一半。
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
ll prefix[1000010];
ll v[1000010];
set<ll>st;
int main(){
double a,b,c,d;
cin>>a>>b>>c>>d;
if(c*2!=a||d*2!=b){
printf("%.6lf 0",a*b/2);
}else
printf("%.6lf 1",a*b/2);
}
- Maze Master
一个简单的BFS，但是我卡了半小时也没过，原因在于我每次BFS都是拿一个点去搜索，这可能会导致无法找到最远的两个点之间的最大距离。为了找到迷宫中任意两点之间的最大距离，需要对每一个可通行的点都进行BFS，并记录下所有点之间的距离，然后从中找出最大值。
举个例子来说明这个问题：
假设有一个迷宫如下：
5 5
.....
.###.
.....
.###.
.....
在这个迷宫中，如果从左上角的点开始BFS，你可能会找到一个相对较大的距离，但这个距离并不是整个迷宫中最大的距离。
实际上，最大的距离应该是从左上角到右下角，或者从左下角到右上角。
为了找到整个迷宫中任意两点之间的最大距离，需要对每一个可通行的点都进行BFS，并记录下所有点之间的距离，然后从中找出最大值。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dx[] = {0, 0, -1, 1};
ll dy[] = {1, -1, 0, 0};
char mp[25][25];
ll vis[25][25];
ll ans = 0;
ll d[25][25];
struct Node {
int x;
int y;
} v[25 * 25];
int n, m, k = 1;
bool inmp(int x, int y) {
return x > 0 && x <= n && y > 0 && y <= m;
}
void bfs(int tx, int ty) {
memset(vis, 0, sizeof vis);
memset(d, 0, sizeof d);
queue<pair<ll, ll>> q;
d[tx][ty] = 0;
vis[tx][ty] = true;
q.push({tx, ty});
while (q.size()) {
ll x = q.front().first, y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
ll nx = x + dx[i], ny = y + dy[i];
if (inmp(nx, ny) && mp[nx][ny] == '.' && !vis[nx][ny]) {
d[nx][ny] = d[x][y] + 1;
vis[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mp[i][j];
if (mp[i][j] == '.')
v[k].x = i, v[k++].y = j;
}
}
//这里我出问题了，就直接cout<<ans,它只能找到从某个点出发的最大距离，而不能保证这个距离是整个迷宫中任意两点之间的最大距离。
for (int i = 1; i < k; i++) {
bfs(v[i].x, v[i].y);
for (int j = 1; j < k; j++) {
if (i != j) {
ans = max(ans, d[v[j].x][v[j].y]);
}
}
}
cout << ans << endl;
return 0;
}
- Dubious Document 2
差一分，思维不对，我贪心地从后面开始找但是存在前面为优的情况，死活过不去，
看了别人代码，找出所有可以插空的位置，然后全部尝试，比较字典序。
贴上我自己写的代码
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, s2;
cin >> s1 >> s2;
int le = s1.length();
int le2 = s2.length();
string best_s = "";
for (int i = 0; i <= le - le2; ++i) {
bool can_insert = true;
string temp_s = s1;
for (int j = 0; j < le2; ++j) {
if (s1[i + j] != '?' && s1[i + j] != s2[j]) {
can_insert = false;
break;
}
temp_s[i + j] = s2[j];
}
if (can_insert) {
for (int k = 0; k < le; ++k) {
if (temp_s[k] == '?') {
temp_s[k] = 'a';
}
}
if (best_s == "" || temp_s < best_s) {
best_s = temp_s;
}
}
}
if (best_s == "") {
cout << "UNRESTORABLE";
} else {
cout << best_s;
}
return 0;
}
-
动态规划专题
- [NOIP2002]过河卒
入门的动态规划题，转移方程就是f[i][j] = f[i - 1][j]+f[i][j - 1]，加了不可以走的点即马走的点。
把马走过的点f[i][j]设置为0，即为不可以通过。然后两重for循环一行一行计算得出答案，这里需要注意一下越界问题就行。
- [NOIP2002]过河卒
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 21;
ll f[MAXN][MAXN]; // 从0，0出发到i，j的路径条数
bool v[MAXN][MAXN]; // 标记马的控制点
int xx[] = {2, 1, -1, -2, -1, -2, 1, 2};
int yy[] = {1, 2, 2, 1, -2, -1, -2, -1};
int main() {
int n, m, x, y;
cin >> n >> m >> x >> y;
// 初始化f数组
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = 0;
}
}
// 标记马的控制点
v[x][y] = true;
for (int i = 0; i < 8; i++) {
int tx = x + xx[i];
int ty = y + yy[i];
if (tx >= 0 && tx <= n && ty >= 0 && ty <= m) {
v[tx][ty] = true;
}
}
// 动态规划计算路径条数
f[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (v[i][j]) continue; // 如果是马的控制点，跳过
if (i > 0) f[i][j] += f[i - 1][j];
if (j > 0) f[i][j] += f[i][j - 1];
}
}
cout << f[n][m] << endl;
return 0;
}
- [NOIP2008]传球游戏
跟上面的过河卒类似，但是我们需要搞清楚i，j的顺序以及，边界和初始状态
状态转移方程为 f[i][j]=f[i-1][j-1]+f[i-1][j+1]由于是一个圈，当j=n时，j+1=1,当j=1时，j-1=n;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAXN = 300;
ll f[MAXN][MAXN]; // 第i次传球，球在第j个人手里的方案数
int main() {
int n, m;
cin >> n >> m;
//初始化
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = 0;
}
}
// 即前后人手里的方案数
//由于是一个圈，当j==n时，j+1=1,当j==1时，j-1=n;
//初始状态，边界 f[0][1]=1
f[0][1] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (j == n ) {
f[i][j] = f[i-1][j-1]+f[i-1][1];
}
else if (j == 1) {
f[i][j] = f[i-1][n]+f[i-1][j+1];
}
else if(j!=n&&j!=1){
f[i][j] = f[i - 1][j-1]+f[i-1][j+1];
}
}
}
cout << f[m][1] << endl;
return 0;
}
- Codeforces