2019 CSP-J 江西
P5681 面积（语法）
题意
求出边长为 \(a\) 的正方形与长宽分别为 \(b,c\) 的矩形哪一个面积更大。
题解
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
void Solve(void)
{
lnt a, b, c;
cin >> a >> b >> c;
if (a * a > b * c)
{
cout << "Alice" << endl;
}
else
{
cout << "Bob" << endl;
}
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
freopen("IN.txt", "r+", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T = 1; //cin >> T;
while (T--)Solve();
return 0;
}
P5682 次大值（数学，STL）
题意
\(n\) 个正整数，求出所有的 \(a_i \bmod a_j (1 \le i,j \le n \wedge i \neq j)\) 中严格次大值是多少。
数据规模与约定
对于 \(100\%\) 的数据，\(3 \le n \le 2\times 10^5\)，\(1\le a_i \le 10^9\)。
题解
对于 \(70\%\) 的数据显然我们可以暴力。
考虑对于 \(100\%\) 的数据怎么办。首先我们假设 \(a \bmod b = c\)：
-
当 \(a < b\) 时，\(c=a<b\)。
-
当 \(a=b\) 时，\(c=0\)。
-
当 \(a>b\) 时，\(c<b<a\)。
综上，\(c \le min(a,b),c \ne max(a,b)\)。所以序列中的最大值一定无法取到。
现在我们不妨假设 \(a\) 为最大值，\(b\) 为次大值。我们有以下结论：\(a \bmod b<b,b \bmod a=b\)。
所以当使用次大值 \(b\) 对最大值 \(a\) 取模时，我们能获得 \(c\) 的最大值。证明可以使用反证法：若存在比 \(c=b\) 更大的值 \(b'\)，即存在 \(b'\)，使得 \(b' \bmod a=b'>b\)。与 \(b\) 为次大值矛盾。
那么同理若 \(b\) 为次次大值时，获得的 \(c\) 为次大值。
所以我们发现，只有最大的三个不同的数是有效的。
因为要分类讨论有效的数为 \(1,2,3\) 时的情况，所以我们不如直接对有效的数进行 \(70\%\) 部分的暴力做法。
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
int n;
set<int>lib;
/*====================*/
void Solve(void)
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
int temp; cin >> temp; lib.insert(temp);
}
vector<int>usefulnum;
for (auto it = lib.rbegin(); it != lib.rend() && usefulnum.size() < 3; ++it)
{
usefulnum.push_back(*it);
}
vector<int>ans;
for (int i = 0; i < usefulnum.size(); ++i)
{
for (int j = 0; j < usefulnum.size(); ++j)
{
if (i != j)
{
ans.push_back(usefulnum[i] % usefulnum[j]);
}
}
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
reverse(ans.begin(), ans.end());
if (ans.size() <= 2)
{
cout << "-1" << endl;
}
else
{
cout << ans[1] << endl;
}
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
freopen("IN.txt", "r+", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T = 1; //cin >> T;
while (T--)Solve();
return 0;
}
P5683 道路拆除（最短路）
题意
给定一张 \(n\) 点 \(m\) 边的无向图，边权为 \(1\)。求最多可以删多少条边，使得从 \(1\) 号点出发，能到达 \(s_1\) 号点与 \(s_2\) 号点，且经过的边的数量分别不超过 \(t_1\) 与 \(t_2\)。若无论如何都不能，则输出 \(-1\)。
数据规模与约定
对于 \(100\%\) 的数据，\(2 \le n,m \le 3000\)，\(1\le x,y \le n\)，\(2 \le s_1,s_2 \le n\)，\(0 \le t_1,t_2 \le n\)。
题解
我们发现题目的要求只和三个点有关：\(1,s_1,s_2\)。
考虑从 \(1\) 号点分别到 \(s1,s2\) 的路径形态：
- \(1 \rightarrow ...\rightarrow s_1\rightarrow ...\rightarrow s_2\)。
- \(1 \rightarrow ...\rightarrow s_2\rightarrow ...\rightarrow s_1\)。
- \(1\rightarrow \begin{cases} ...\rightarrow s_1\\...\rightarrow s_2 \end{cases}\)
- \(1\rightarrow ... \rightarrow x \rightarrow \begin{cases} ...\rightarrow s_1\\...\rightarrow s_2 \end{cases}\)
我们发现，所有形态都可以归结到第四种形态，只不过第一种形态 \(x=s_1\)，第二种形态 \(x=s_2\)，第三种形态 \(x=1\)。
于是我们分别求出 \(1,s_1,s_2\) 到所有点的最短路径，然后枚举 \(x\) 即可。
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 3e3 + 10;
const int M = 3e3 + 10;
/*====================*/
const int INF = 0X3F3F3F3F;
/*====================*/
int n, m;
int s1, t1;
int s2, t2;
/*====================*/
namespace _Graph
{
struct Edge
{
int u, v;
Edge(int _u = 0, int _v = 0)
{
u = _u, v = _v;
}
int node(int x)const
{
return x == u ? v : u;
}
};
/*====================*/
int cntedge;
Edge edge[M];
vector<int>G[N];
/*====================*/
void AddEdge(int u, int v)
{
edge[++cntedge] = Edge(u, v);
G[u].push_back(cntedge);
G[v].push_back(cntedge);
}
}
/*====================*/
int dis_s0[N], dis_s1[N], dis_s2[N];
/*====================*/
namespace _Dijkstra
{
using namespace _Graph;
/*====================*/
struct Unit
{
int v, w;
Unit(int _v = 0, int _w = 0)
{
v = _v, w = _w;
}
friend bool operator<(const Unit& a, const Unit& b)
{
return a.w > b.w;
}
};
/*====================*/
bool vis[N];
/*====================*/
void Init(int s, int dis[])
{
memset(vis, false, sizeof(vis));
priority_queue<Unit>q;
q.push(Unit(s, dis[s] = 0));
while (!q.empty())
{
int cur = q.top().v; q.pop();
if (vis[cur])continue; vis[cur] = true;
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = edge[G[cur][i]].node(cur);
if (dis[nxt] > dis[cur] + 1)
{
dis[nxt] = dis[cur] + 1;
q.push(Unit(nxt, dis[nxt]));
}
}
}
}
}
/*====================*/
void Solve(void)
{
cin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int u, v; cin >> u >> v;
_Graph::AddEdge(u, v);
}
cin >> s1 >> t1 >> s2 >> t2;
memset(dis_s0, INF, sizeof(dis_s0)); _Dijkstra::Init(01, dis_s0);
memset(dis_s1, INF, sizeof(dis_s1)); _Dijkstra::Init(s1, dis_s1);
memset(dis_s2, INF, sizeof(dis_s2)); _Dijkstra::Init(s2, dis_s2);
int ans = -1;
for (int i = 1; i <= n; ++i)
{
if (dis_s1[i] + dis_s0[i] <= t1 && dis_s2[i] + dis_s0[i] <= t2)
{
ans = max(ans, m - (dis_s0[i] + dis_s1[i] + dis_s2[i]));
}
}
cout << ans << endl;
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
freopen("IN.txt", "r+", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T = 1; //cin >> T;
while (T--)Solve();
return 0;
}
P5684 非回文串（组合计数）
题意
给定 \(n\) 个小写英文字符，从 \(1 \sim n\) 编号，分别为 \(c_1,c_2, \dots , c_n\)。
将这些字符重新排列，组成一个字符串 \(S\)。求一共有多少种不同的排列字符的方案，能使得 \(S\) 是个非回文串。
数据规模与约定
对于 \(100\%\) 的数据，\(3 \le n \le 2000\)。
题解
正难则反，用总排列方案数减去回文串排列方案数即为非回文串排列方案数。
如何求总排列方案数？\(n\) 个字符，一共有 \(A^n_n=n!\) 种排列方案。
如何求回文串排列方案数？分两步：
- 求出本质不同的回文串的个数。
- 对于每一个本质不同的回文串，乘上每一种字符的排列方案数。
值得注意的是，出现次数为奇数次的字符，最多有一种。否则不能组成回文串。
第一步对应下面代码的69-74行，第二步对应下面代码的75-79行。
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 2e3 + 10;
/*====================*/
const lnt MOD = 1e9 + 7;
/*====================*/
int n;
string str;
int cnt[26];
/*====================*/
lnt factorial[N];
/*====================*/
class INV
{
public:
lnt operator[](lnt x)
{
return Pow(x % MOD, MOD - 2);
}
private:
lnt Pow(lnt a, lnt b)
{
lnt res = 1;
while (b)
{
if (b & 1)
{
res = (res * a) % MOD;
}
b >>= 1, a = (a * a) % MOD;
}
return res;
}
}inv;
/*====================*/
void Solve(void)
{
cin >> n >> str;
/*====================*/
for (auto c : str)
{
cnt[c - 'a']++;
}
/*====================*/
factorial[0] = 1;
for (int i = 1; i <= n; ++i)
{
factorial[i] = (factorial[i - 1] * lnt(i)) % MOD;
}
lnt tot = factorial[n];
/*====================*/
int odd = 0;
for (int i = 0; i < 26; ++i)
{
if (cnt[i] & 1)
{
odd++;
}
}
/*====================*/
lnt palindrome = 0;
if (odd <= 1)
{
//计算本质不同的回文串方案数
palindrome = factorial[n / 2];
for (int i = 0; i < 26; ++i)
{
palindrome = (palindrome * inv[factorial[cnt[i] / 2]]) % MOD;
}
//乘以每种字符排列的方案数
for (int i = 0; i < 26; ++i)
{
palindrome = (palindrome * factorial[cnt[i]]) % MOD;
}
}
/*====================*/
cout << (tot - palindrome + MOD) % MOD << endl;
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
freopen("IN.txt", "r+", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T = 1; //cin >> T;
while (T--)Solve();
return 0;
}