分就不多说了，这里给个满分代码。
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int gen(string &s)
{
int res = 0;
for (int i = 0; i < s.size(); i++)
res = res * 10 + s[i] - '0';
return res;
}
bool p(int x)
{
if (x < 2)
return false;
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
sort(s.begin(), s.end());
do
{
if (p(gen(s)))
{
cout << s << "\n";
return 0;
}
} while (next_permutation(s.begin(), s.end()));
cout << "-1\n";
return 0;
}
显然不停减 可以通过 来加速。有一些经典的错误是没注意到小于等于 得数不能处理。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k;
pair<int, int> a[100000 + 5]; // ai,i
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i].first;
for (int i = 1; i <= n; i++)
{
a[i].second = i;
if (a[i].first <= 0)
continue;
a[i].first %= k;
if (a[i].first)
a[i].first -= k;
}
sort(a + 1, a + n + 1);
int cnt = 1;
for (int i = 2; i <= n; i++)
if (a[i].first != a[i - 1].first)
cnt++;
cout << a[n].second << " " << cnt;
return 0;
}
原题是：https://codeforces.com/problemset/problem/939/D
首先要想清楚，当两个数不一样时，把所有 变成 和把所有的 变成 是没区别的。然后就一个个看过去不一样就变就好。因为并查集是提高组考点，所以这题给的是染色做法的标程。
#include <bits/stdc++.h>
using namespace std;
int n, ans;
long long a[5005];
long long b[5005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
ans = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] == b[i])
continue;
ans++;
long long x = a[i];
long long y = b[i];
for (int j = 1; j <= n; j++)
{
if (a[j] == x)
a[j] = y;
if (b[j] == x)
b[j] = y;
}
}
cout << ans;
return 0;
}
原题：https://atcoder.jp/contests/abc170/tasks/abc170_f
经典广搜
// subtask 2
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int x, y, xx, yy;
char g[1005][1005];
int dis[1005][1005];
queue<pair<int, int>> q;
int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};
int main()
{
freopen("hun.in", "r", stdin);
freopen("hun.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
cin >> x >> y >> xx >> yy;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> g[i][j];
assert(g[x][y] != '@' && g[xx][yy] != '@');
q.push(make_pair(x, y));
dis[x][y] = 1;
while (!q.empty() && !dis[xx][yy])
{
pair<int, int> now = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
for (int j = 1; j <= k; j++)
{
int nx = now.first + dx[i] * j;
int ny = now.second + dy[i] * j;
if (nx < 1 || nx > n || ny < 1 || ny > m ||
g[nx][ny] == '@')
break;
if (dis[nx][ny])
continue;
dis[nx][ny] = dis[now.first][now.second] + 1;
q.push(make_pair(nx, ny));
}
}
}
if (dis[xx][yy])
cout << dis[xx][yy] - 1 << "\n";
else
cout << -1 << "\n";
return 0;
}
显然开不下 的数组。可以用动态数组或者字符串的形式，用多少开多少。
// 暴力
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1'000'000;
int n, m, k;
int x, y, xx, yy;
char temp;
vector<char> g[MAXN + 5];
vector<int> dis[MAXN + 5];
queue<pair<int, int>> q;
int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};
int main()
{
freopen("hun.in", "r", stdin);
freopen("hun.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
cin >> x >> y >> xx >> yy;
for (int i = 1; i <= n; i++)
{
g[i].push_back('@');
dis[i].push_back(0);
for (int j = 1; j <= m; j++)
{
cin >> temp;
g[i].push_back(temp);
dis[i].push_back(0);
}
}
assert(g[x][y] != '@' && g[xx][yy] != '@');
q.push(make_pair(x, y));
dis[x][y] = 1;
while (!q.empty() && !dis[xx][yy])
{
pair<int, int> now = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
for (int j = 1; j <= k; j++)
{
int nx = now.first + dx[i] * j;
int ny = now.second + dy[i] * j;
if (nx < 1 || nx > n || ny < 1 || ny > m ||
g[nx][ny] == '@')
break;
if (dis[nx][ny])
continue;
dis[nx][ny] = dis[now.first][now.second] + 1;
q.push(make_pair(nx, ny));
}
}
}
if (dis[xx][yy])
cout << dis[xx][yy] - 1 << "\n";
else
cout << -1 << "\n";
return 0;
}
满分只需要注意本来要走 步，但是如果路途中间遇到了一样近或更近的点就可以停了，后面没走的那些位置显然可以通过这个点走过去而不会更劣。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1'000'000;
int n, m, k;
int x, y, xx, yy;
char temp;
vector<char> g[MAXN + 5];
vector<int> dis[MAXN + 5];
queue<pair<int, int>> q;
int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};
int main()
{
freopen("hun.in", "r", stdin);
freopen("hun.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
cin >> x >> y >> xx >> yy;
for (int i = 1; i <= n; i++)
{
g[i].push_back('@');
dis[i].push_back(0);
for (int j = 1; j <= m; j++)
{
cin >> temp;
g[i].push_back(temp);
dis[i].push_back(0);
}
}
assert(g[x][y] != '@' && g[xx][yy] != '@');
q.push(make_pair(x, y));
dis[x][y] = 1;
while (!q.empty() && !dis[xx][yy])
{
pair<int, int> now = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
for (int j = 1; j <= k; j++)
{
int nx = now.first + dx[i] * j;
int ny = now.second + dy[i] * j;
if (nx < 1 || nx > n || ny < 1 || ny > m ||
g[nx][ny] == '@')
break;
// 40 分来自这一句 if
if (dis[nx][ny] && dis[nx][ny] <= dis[now.first][now.second])
break;
if (dis[nx][ny])
continue;
dis[nx][ny] = dis[now.first][now.second] + 1;
q.push(make_pair(nx, ny));
}
}
}
if (dis[xx][yy])
cout << dis[xx][yy] - 1 << "\n";
else
cout << -1 << "\n";
return 0;
}