B. Boundary
题意：
给 n 个点，问最多有多少个点可以和原点共圆， n 个点各不相同，且不与原点重合
思路：
（官方正解）O(n ^ 3) 肯定T飞，利用同弧所对的圆周角相等这一性质来做，首先枚举一个点 P，再枚举第二个点 A，求出所有的 ∠OAP，max( 其众数的个数 + 1 ) 就是答案（这里的1是第一个枚举的点P）。
需要注意的是，如果用 map 记录每个角的大小来求众数会被精度卡掉，可以存到double数组里再排个序，扫一遍即可，这里判相等的时候 eps 需要设到 1e-11 以下，否则会被卡。
还有一个问题，我还是截个题解的图8：
科普一下叉积的小知识：两个向量 P、Q，
P × Q > 0 说明 P 在 Q 的顺时针方向
P × Q < 0 说明 P 在 Q 的逆时针方向
P × Q = 0 说明 P 与 Q 共线，可能同向也可能反向
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-11; //1e-10 WA了 qaq
const int N = 2e3 + 5;
struct point
{
double x, y;
point() {};
point(double xx, double yy):x(xx), y(yy) {}
double operator *(const point &b)const //点乘
{
return x * b.x + y * b.y;
}
double operator ^(const point &b)const //叉乘
{
return x * b.y - y * b.x;
}
} s[N];
double len(point a) //向量的模
{
return 1.0 * sqrt(a.x * a.x + a.y * a.y);
}
double cos(point P, point A) //求 cos∠OAP
{
point a = point(0.0 - A.x, 0.0 - A.y);
point b = point(P.x - A.x, P.y - A.y);
return a * b / (len(a) * len(b));
}
int main()
{
int n;
while(~scanf("%d", &n))
{
for(int i = 1; i <= n; ++i)
{
scanf("%lf%lf", &s[i].x, &s[i].y);
}
if(n < 3)
{
cout<<n<<'\n';
continue;
}
int ans = 0;
for(int i = 1; i <= n; ++i)
{
vector<double>vec;
for(int j = 1; j <= n; ++j)
{
if(j == i)
continue;
if((s[i] ^ s[j]) < 0)
vec.push_back(cos(s[i], s[j]));
}
sort(vec.begin(), vec.end());
int siz = vec.size();
if(siz)
{
int cnt = 1;
for(int j = 1; j < siz; ++j)
{
if(fabs(vec[j] - vec[j - 1]) < eps)
cnt++;
else
{
ans = max(ans, cnt);
cnt = 1;
}
}
ans = max(ans, cnt);
}
vec.clear();
}
cout<<ans + 1<<'\n';
}
return 0;
}C. Cover the Tree
题意：
给一棵 n 个点的树，问最少要用多少条树链，覆盖整棵树，只输出树链的起点和终点
思路：
话说这题不应该是最小链覆盖？
先求一个dfs序，然后把叶子节点两两配对，怎么配对呢？看题解：
缩一下句就是一共 s 个叶子节点，把第 i 个叶子节点和第 i + (s + 1) / 2 个叶子节点成对输出就好了
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
vector<int>g[N];
vector<int>q;
int n;
void dfs(int s, int pre)
{
if(g[s].size() == 1)
q.push_back(s);
int siz = g[s].size();
for(int i = 0; i < siz; ++i)
{
if(g[s][i] != pre)
{
dfs(g[s][i], s);
}
}
}
int main()
{
int u, v;
while(~scanf("%d", &n))
{
q.clear();
for(int i = 1; i <= n; ++i)
g[i].clear();
for(int i = 1; i < n; ++i)
{
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
if(n == 1)
{
cout<<0<<'\n';
continue;
}
if(n == 2)
{
cout<<1<<'\n'<<"1 2"<<'\n';
continue;
}
dfs(1, 0);
int siz = q.size();
int cnt = (siz + 1) / 2;
cout<<cnt<<'\n';
for(int i = 0; i < cnt; ++i)
{
cout<<q[i]<<' '<<q[(i + siz / 2) % siz]<<'\n';
}
}
return 0;
}D. Duration
u1s1写完这道题我们就挂机了
#include<bits/stdc++.h>
using namespace std;
string s[3];
int main()
{
cin >> s[0];
cin >> s[1];
sort(s, s + 2);
int h = (s[1][0] - s[0][0]) * 10 + (s[1][1] - s[0][1]);
int m = (s[1][3] - s[0][3]) * 10 + (s[1][4] - s[0][4]);
int sec = (s[1][6] - s[0][6]) * 10 + (s[1][7] - s[0][7]);
cout << h * 3600 + m * 60 + sec << endl;
}F. Fake Maxpooling
题意：
n * m 的矩阵中 lcm[i][j] = lcm(i, j)，求所有 k * k 的子矩阵中最大值的和
思路：
（滑动窗口）
横向纵向分别用一次单调队列：先用两层循环求出以 lcm[i][j] 为起点、长度为 k 的横向区间的最大值，存到res[i][j]中；再两层循环求出以res[i][j]为起点、长度为 k 的纵向区间的最大值（也就是以 lcm[i][j] 为左上角、大小为 k * k 的子矩阵中的最大值），累加起来即为答案。
如何用单调队列：
队首存最大值的下标，向后遍历到一位时，将队列中小于该值的元素从队首弹出，把该值放入队尾（由于对队首一直存的最大值，现在队里就这一个值了），然后把当前长度为 k 的区间之前的元素都弹出（当然是在队首了），操作完后队首的元素就是该区间内的最大值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e3 + 5;
int lcm[N][N], res[N][N], cnt;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
lcm[i][j] = i / gcd(i, j) * j;
deque<int>q;
for(int i = 1; i <= n; ++i)
{
cnt = 0;
q.clear();
for(int j = 1; j <= k; ++j)
{
while(q.size() && lcm[i][q.back()] <= lcm[i][j])
q.pop_back();
q.push_back(j);
}
res[i][++cnt] = lcm[i][q.front()];
for(int j = k + 1; j <= m; ++j)
{
while(q.size() && lcm[i][q.back()] <= lcm[i][j])
q.pop_back();
q.push_back(j);
if(q.size() && q.front() < j - k + 1)
q.pop_front();
res[i][++cnt] = lcm[i][q.front()];
}
}
ll ans = 0;
for(int j = 1; j <= cnt; ++j)
{
q.clear();
for(int i = 1; i <= k; ++i)
{
while(q.size() && res[q.back()][j] <= res[i][j])
q.pop_back();
q.push_back(i);
}
ans += 1ll * res[q.front()][j];
for(int i = k + 1; i <= n; ++i)
{
while(q.size() && res[q.back()][j] <= res[i][j])
q.pop_back();
q.push_back(i);
if(q.size() && q.front() < i - k + 1)
q.pop_front();
ans += 1ll * res[q.front()][j];
}
}
cout<<ans<<'\n';
return 0;
}J. Just Shuffle
题意：
求一个置换P，使 A(1，2，3.....，n) 经过 K 次置换后变为排列 B
思路：
这里求的 P 也就是 A 置换一次得到的结果。
对 A 的每一个循环节单独处理，设某位置 A 的循环节长度为 r ，假如 B 置换 Z 次后会回到 A，也就是 A 置换 K * Z 次后会再回到 A，这里 Z 满足 K * Z % r == 0 。那么要求 P 的话，也就是求一个 Z1，使 K * Z1 % r == 1。
参考：https://blog.csdn.net/qq_43552826/article/details/107353622?%3E
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-11;
const int N = 1e5 + 5;
ll a[N], b[N], n, k;
bool vis[N];
vector<ll>vec;
void solve()
{
ll r = vec.size(), inv;
for(ll j = r - 1; j >= 0; --j)
{
if((k * j) % r == 1)
{
inv = j;
break;
}
}
for(ll j = 0; j < r; ++j)
b[vec[j]] = vec[(j + inv) % r];
}
int main()
{
while(~scanf("%lld%lld", &n, &k))
{
for(ll i = 1; i <= n; ++i)
{
scanf("%lld", &a[i]);
}
for(ll i = 1; i <= n; ++i)
{
if(vis[i]) continue;
vec.clear();
ll x = a[i];
while(!vis[x])
{
vec.push_back(x);
vis[x] = 1;
x = a[x];
}
solve();
}
for(ll i = 1; i <= n; ++i)
{
cout<<b[i];
if(i < n)
cout<<' ';
}
cout<<'\n';
}
return 0;
}
第二场先到这儿吧，去补第一场了
京公网安备 11010502036488号