B Boundary
题意
在平面上给若干个点，求一个过原点的圆，使得尽量多的点在圆上。
保证点数不超过 ，坐标绝对值不超过
。
枚举两个点，与原点三点确定一个圆。
求得每个点的圆心位置，用数据结构或排序维护每个圆心的出现次数。
AC代码：
const int N = 2010;
ld x[N], y[N];
map<pair<ld, ld>, int> mp;
int main()
{
int n;
sd(n);
rep(i, 1, n)
cin >>
x[i] >> y[i];
ll ans = 0, now;
rep(i, 1, n)
{
mp.clear(); //每次枚举完点后清空
for (int j = i + 1; j <= n; j++)
{
if (x[i] * y[j] - x[j] * y[i] == 0)
continue; //三点共线无圆
ld xx = ((y[j] - y[i]) * y[i] * y[j] - x[i] * x[i] * y[j] + x[j] * x[j] * y[i]) / (x[j] * y[i] - x[i] * y[j]);
ld yy = ((x[j] - x[i]) * x[i] * x[j] - y[i] * y[i] * x[j] + y[j] * y[j] * x[i]) / (y[j] * x[i] - y[i] * x[j]);
++mp[pair<ld, ld>(xx, yy)];
ans = max(ans, (ll)mp[pair<ld, ld>(xx, yy)]);
}
}
pld(ans + 1);
}
C Cover the Tree
题意;
选取最小的链数，把树的边缘都覆盖。答案就是，即每次连两个叶子，dfs一遍把叶子节点按dfs序排序，然后按照
AC代码：
const int N = 5e5 + 50;
int n, k, m;
int head[N], deg[N], tot;
int ans[N];
struct node
{
int to;
int nex;
} e[N << 1];
void add(int u, int v)
{
e[++tot].to = v, e[tot].nex = head[u];
head[u] = tot;
}
void dfs(int u, int fa)
{
for (int i = head[u], v = e[i].to; i; i = e[i].nex, v = e[i].to)
{
if (v != fa)
dfs(v, u);
}
if (deg[u] == 1)
ans[++ans[0]] = u;
}
int main()
{
sd(n);
rep(i, 0, n)
head[i] = deg[i] = 0;
tot = 0;
rep(i, 1, n - 1)
{
int u, v;
sdd(u, v);
add(u, v);
add(v, u);
deg[u]++, deg[v]++;
}
if (n == 1)
{
puts("1");
puts("1 1");
return 0;
}
else if (n == 2)
{
puts("1");
puts("1 2");
return 0;
}
int root = 0;
rep(i, 1, n)
{
if (deg[i] > 1)
{
root = i;
break;
}
}
ans[0] = 0;
dfs(root, 0);
pd((ans[0] + 1) / 2);
rep(i, 1, (ans[0] + 1) / 2)
pdd(ans[i], ans[i + ans[0] / 2]);
return 0;
}
D Duration
题意：
水题
AC代码：
int main(void)
{
ll h1,m1,s1;
ll h2,m2,s2;
scanf("%lld:%lld:%lld",&h1,&m1,&s1);
scanf("%lld:%lld:%lld",&h2,&m2,&s2);
ll k1=h1*3600+m1*60+s1;
ll k2=h2*3600+m2*60+s2;
printf("%lld",abs(k1-k2));
return 0;
}
F Fake Maxpooling
题意：
的矩阵中每一位为
，求所有
单调队列，将每个位置往下k个中最大值记录下来。然后再 遍历时以前面求出的答案为基础往右
AC代码：
const int N = 2e6 + 50;
const int mod = 998244353;
int n, m, k, x;
deque<PII> q;
int maxn[5005][5005];
int main()
{
sddd(n, m, k);
ll ans = 0;
rep(i, 1, n)
{
while (!q.empty())
q.pop_back();
rep(j, 1, m)
{
int l = lcm(i, j);
if (!q.empty() && q.front().fi <= j - k)
q.pop_front();
while (!q.empty() && q.back().se <= l)
q.pop_back();
q.emplace_back(j, l);
if (j >= k)
maxn[i][j - k + 1] = q.front().se;
}
}
rep(j, 1, m - k + 1)
{
while (!q.empty())
q.pop_back();
rep(i, 1, n)
{
if (!q.empty() && q.front().fi <= i - k)
q.pop_front();
while (!q.empty() && q.back().se <= maxn[i][j])
q.pop_back();
q.emplace_back(i, maxn[i][j]);
if (i >= k)
ans += 1ll * q.front().se;
}
}
pld(ans);
return 0;
}
J Just Shuffle
题意：
给你正整数 ，和一个长度为
的排列
，求一个置换排列
，使得原排列
在进行
次
置换之后变成排列
。输出所求的排列
，如果不存在就输出
。
因为 为质数，所以在置换时循环大小不会变化，所以给定排列的循环大小就是置换的循环大小，对于每一个循环单独考虑，将
当做一次置换，那么只要找到 $x∗k mod len=1 $时的
，做
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn=100010;
int a[mxn],n,k;
bool vis[mxn];
int sz,qd,s[mxn];
ll GCD;
ll gcd(ll a,ll b){
if(!b) return a;
return gcd(b,a%b);
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1;y=0;return a;
}
GCD=exgcd(b,a%b,y,x);
y-=a/b*x;
return GCD;
}
ll niyuan(ll a,ll mod){
ll x,y;
GCD=exgcd(a,mod,x,y); //让b=mod 然后用拓展欧几里得公式求解
return GCD==1? (x%mod+mod)%mod:0;
}
void dfs(int x){
s[++sz]=x;
vis[x]=1;
if(x==qd) return;
dfs(a[x]);
}
int ans[mxn];
bool sol(){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) if(!vis[i]){
sz=0;
qd=i;
dfs(a[i]);
if(sz==1){
ans[i]=i;
continue;
}
int g=k%sz;
if(gcd(sz,g)>1) return 0;
int ny=niyuan(g,sz);
int na=i,nb=i;
for(int i=1;i<=ny;i++) nb=a[nb];
for(int i=1;i<=sz;i++){
ans[na]=nb;
na=a[na];
nb=a[nb];
}
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
printf("\n");
return 1;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
if(!sol()) printf("-1\n");
/*
int g[100],h[mxn];
for(int i=1;i<=n;i++) g[i]=i;
for(int i=0;i<5;i++){
for(int i=1;i<=n;i++) h[i]=g[a[i]];
for(int i=1;i<=n;i++) g[i]=h[i];
for(int i=1;i<=n;i++) printf("%d ",g[i]);
printf("\n");
}
*/
return 0;
}