A - Thickest Burger
水。
#include <bits/stdc++.h>
using namespace std; int t;
int a, b; int main()
{
scanf("%d" ,&t);
while (t--)
{
scanf("%d%d", &a, &b);
if (a > b) swap(a, b);
printf("%d\n", a + b * );
}
return ;
}
B - Relative atomic mass
水。
#include <bits/stdc++.h>
using namespace std; int t;
char s[]; int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%s", s);
int res = ;
for (int i = , len = strlen(s); i < len; ++i)
{
if (s[i] == 'H') res += ;
if (s[i] == 'C') res += ;
if (s[i] == 'O') res += ;
}
printf("%d\n", res);
}
return ;
}
C - Recursive sequence
题意：求$F[n] = F[n - 1] + 2 \cdot F[n - 2] + n^4$
思路：考虑
$n^4 = (n - 1)^4 + 4 \cdot (n - 1) ^ 3 + 6 \cdot (n - 1) ^2 + 4 \cdot (n - 1) ^ 2 + (n - 1) + 1$
然后进行递推即可
#include <bits/stdc++.h>
using namespace std; #define ll long long const ll MOD = ; int t;
ll n, a, b; struct node
{
ll a[][];
node () { memset(a, , sizeof a); }
node operator * (const node &r) const
{
node ans = node();
for (int i = ; i < ; ++i) for (int j = ; j < ; ++j) for (int k = ; k < ; ++k)
ans.a[i][j] = (ans.a[i][j] + a[i][k] * r.a[k][j] % MOD) % MOD;
return ans;
}
}; ll tmp[][] =
{
, , , , , , ,
, , , , , , ,
, , , , , , ,
, , , , , , ,
, , , , , , ,
, , , , , , ,
, , , , , , ,
}; ll tmp2[] =
{
, , , , , , ,
}; node qmod(ll n)
{
node base = node();
for (int i = ; i < ; ++i) for (int j = ; j < ; ++j)
base.a[i][j] = tmp[i][j];
node res = node();
for (int i = ; i < ; ++i) res.a[][i] = tmp2[i];
while (n)
{
if (n & ) res = res * base;
base = base * base;
n >>= ;
}
return res;
} int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%lld%lld%lld", &n, &a, &b);
if (n == ) printf("%lld\n", a);
else if (n == ) printf("%lld\n", b);
else
{
tmp2[] = b; tmp2[] = a;
printf("%lld\n", qmod(n - ).a[][]);
}
}
return ;
}
D - Winning an Auction
留坑。
E - Counting Cliques
题意：给出n个点，m条边，求点集大小为S的完全图个数
思路：以每个点为起点搜有多少完全图
#include<bits/stdc++.h> using namespace std; const int maxn = 1e2 + ; int n, m, s;
int ans;
int arr[maxn], tot;
int mp[maxn][maxn];
vector<int>G[maxn]; void Init(int N)
{
ans = ;
for(int i = ; i <= N; ++i)
{
G[i].clear();
mp[i][i] = ;
for(int j = i + ; j <= N; ++j)
{
mp[i][j] = mp[j][i] = ;
}
}
} void DFS(int u, int cnt)
{
if(cnt == s)
{
++ans;
return ;
}
for(auto it: G[u])
{
bool flag = true;
for(int i = ; i < tot; ++i)
{
if(!mp[arr[i]][it])
{
flag = false;
break;
}
}
if(flag)
{
arr[tot++] = it;
DFS(it, cnt + );
tot--;
}
}
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d %d %d", &n, &m, &s);
Init(n);
for(int i = ; i <= m; ++i)
{
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v);
mp[u][v] = mp[v][u] = ;
}
for(int i = ; i <= n; ++i)
{
tot = ;
arr[tot++] = i;
DFS(i, );
}
printf("%d\n", ans);
}
return ;
}
G - Do not pour out
题意：有一个底部为直径为2的圆，高度为2的桶，现在里面有高度为h的液体，将桶倾斜至最大，求上表面面积
思路：分类，若经过没经过底部则为PI / cos(2.0-d)
否则二分+积分求面积
#include<bits/stdc++.h> using namespace std; const double eps = 1e-;
const double PI = acos(-1.0); int sgn(double x)
{
if(fabs(x) < eps) return ;
else return x > ? : -;
} double d; double calc(double arc)
{
return PI * cos(arc) - arc * cos(arc) + sin(arc) - sin(arc) * sin(arc) * sin(arc) / 3.0;
} int check(double mid)
{
double tmp = (calc(acos(2.0 * tan(mid) - 1.0)) - calc(PI)) / tan(mid);
return sgn(tmp - d * PI);
} double get(double l, double r)
{
if(check(l) == ) return l;
int cnt = ;
while(cnt--)
{
double mid = (l + r) / 2.0;
int tmp = check(mid);
if(tmp == ) return mid;
if(tmp == ) r = mid;
if(tmp == -) l = mid;
}
return l;
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%lf", &d);
if(sgn(d) == )
{
printf("0.00000\n");
}
else if(sgn(d - ) > )
{
double arc = atan(2.0 - d);
double ans = PI / cos(arc);
printf("%.5f\n", ans);
}
else
{
double tmp = get(eps, PI / 4.0);
double t1 = 2.0 * tan(tmp) - 1.0;
double arc = acos(t1);
double ans = PI - arc + cos(arc) * sin(arc);
ans = ans / sin(tmp);
printf("%.5f\n", ans);
}
}
return ;
}
H - Guessing the Dice Roll
留坑。
I - The Elder
题意：给出一棵树，每个点到根节点1的方式可以是连续走，也可以经过一个点消耗时间p，使得重新计算所经过路径，求每个点到根节点最小的最大时间 时间为$L^2$
思路：考虑朴素的转移 $F[i] = min(F[j] + p + (sum[i] - sum[j]) ^ 2) (j 为 i 的祖先们)$
拆分式子
$F[i] = F[j] + p + {sum[i]} ^ 2 - 2 \cdot sum[i] \cdot sum[j] + {sum[j]} ^ 2$
$F[j] = F[i] + 2 \cdot sum[i] \cdot sum[j] - p - {sum[i]} ^ 2 - {sum[j]} ^ 2$
考虑斜率优化
树上的单调队列优化可以通过标记最后一个更改的值，然后还原(XHT)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
struct Edge{
int to, nxt;
ll w;
Edge(){}
Edge(int to, int nxt, ll w): to(to), nxt(nxt), w(w){}
}edge[maxn << ];
ll ans;
ll dis[maxn];
ll dp[maxn];
int n, p;
int que[maxn];
int head[maxn], tot;
void Init(int N)
{
for(int i = ; i <= N; ++i) head[i] = -;
tot = ans = ;
}
void addedge(int u, int v, ll w)
{
edge[tot] = Edge(v, head[u], w);
head[u] = tot++;
}
ll dy(int j, int k)
{
return dp[j] - dp[k] + dis[j] * dis[j] - dis[k] * dis[k];
}
ll dx(int j, int k)
{
return * (dis[j] - dis[k]);
}
void DFS(int u, int fa, int l, int r)
{
int remind = -;
if(u != )
{
while(l < r && dy(que[l + ], que[l]) <= dis[u] * dx(que[l + ], que[l])) l++;
// cout << u << " " << que[l] << " " << dp[que[l]] + p + (dis[u] - dis[que[l]]) * (dis[u] - dis[que[l]]) << endl;
dp[u] = min(dis[u] * dis[u], dp[que[l]] + p + (dis[u] - dis[que[l]]) * (dis[u] - dis[que[l]]));
while(l < r && dy(que[r], que[r - ]) * dx(u, que[r]) >= dy(u, que[r]) * dx(que[r], que[r - ])) r--;
remind = que[++r];
que[r] = u;
}
ans = max(ans, dp[u]);
for(int i = head[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
if(v == fa) continue;
dis[v] = dis[u] + edge[i].w;
DFS(v, u, l, r);
}
if(remind != -) que[r] = remind;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n, &p);
Init(n);
for(int i = ; i < n; ++i)
{
int u, v, w;
scanf("%d %d %d", &u, &v ,&w);
addedge(u, v, w);
addedge(v, u, w);
}
DFS(, -, , );
// for(int i = 1; i <= n; ++i) cout << i << " " << dp[i] << endl;
printf("%lld\n", ans);
}
return ;
}
J - Query on a graph
留坑。
K - New Signal Decomposition
留坑。
L - A Random Turn Connection Game
留坑。
M - Subsequence
留坑。