目录
写在前面
比赛地址：https://codeforces.com/gym/103055。
以下按个人难度向排序。
唐唐唐唐唐，又是死在数学手上的一次。
妈的为什么上个大学这么累好相似
A
签到。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
LL s1 = 0, s2 = 0;
for (int i = 1; i <= 5; ++ i) {
int a; std::cin >> a;
s1 += a;
}
for (int i = 1; i <= 5; ++ i) {
int a; std::cin >> a;
s2 += a;
}
std::cout << (s1 >= s2 ? "Blue" : "Red");
return 0;
}
M
签到，期望。
发现 Grammy 坑骗每个学生的过程是独立的，有答案可知 \(n=1\) 时答案为 0，由期望的性质可知 \(n\) 为任意值时答案即为 \(n\times 0 = 0\)。
Coded by hjxddl：
//Coded by hjxddl
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
const int N=2e5+5;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
cout<<fixed<<setprecision(4)<<0.0000;
}
L
签到。
发现只要字符串 \(T\) 中满足 \(\exists 2\le i\le |T|, T_i = T_1\) 时，即可构造：
\[T_1T_2\cdots T_{i - 1}T_1T_2\cdots T_n \]把代码卡掉。
赛时先写了个 KMP 太唐乐。
//
/*
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
char s[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int lth2 = read(), flag = 0;
scanf("%s", s + 1);
for (int i = 2; i <= lth2; ++ i) {
if (s[1] == s[i]) flag = 1;
}
if (!flag) std::cout << "Correct\n";
else std::cout << "Wrong Answer\n";
return 0;
}
C
模拟。
两两枚举八个点求距离，检查其中最短边长是否有 12 条；再随便枚举一个点，检查以它为顶点的三个角是否均为直角即可。
//Coded by hjxddl
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#define ll long long
#define db double
using namespace std;
const db eps=1e-7;
double x[9],y[9],z[9];
int ans[5],tot;
db ans1[5],ans2[5],ans3[5];
double cul_dis(int i,int j){
return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
bool vis=0;
map<pair<pair<db,db>,db>,int>mp;
for(int i=1;i<=8;i++){
cin>>x[i]>>y[i]>>z[i];
if(mp.count({{x[i],y[i]},z[i]}))vis=1;
mp[{{x[i],y[i]},z[i]}]=1;
}
if(vis){
cout<<"NO"<<"\n";
continue;
}
db dis=1e7+7;
for(int i=1;i<=8;i++){
for(int j=i+1;j<=8;j++){
dis=min(cul_dis(i,j),dis);
}
}
int cnt=0,tot=0;
for(int i=1;i<=8;i++){
for(int j=i+1;j<=8;j++){
// cout<<i<<" "<<j<<" "<<cul_dis(i,j)<<"\n";
if(fabs(cul_dis(i,j)-dis)<=eps){
if(i==1)ans[++tot]=j;
cnt++;
}
}
}
if(cnt!=12){
cout<<"NO"<<"\n";
continue;
}
for(int i=1;i<=tot;i++)
ans1[i]=x[1]-x[ans[i]],ans2[i]=y[1]-y[ans[i]],ans3[i]=z[1]-z[ans[i]];
for(int i=1;i<=tot;i++){
for(int j=1;j<=tot;j++){
if(i==j)continue;
if(fabs(ans1[i]*ans1[j]+ans2[i]*ans2[j]+ans3[i]*ans3[j])>eps)
vis=1;
}
}
if(!vis)cout<<"YES"<<"\n";
else cout<<"NO"<<'\n';
}
}
I
手玩。
现场拿打草纸撕出三条来手搓。这不是我们圣三一综合学园的标志吗，下次记得标明出处！
判断两个环是否链接在一起仅需检查两个环的交点是否不同在一侧即可。于是大力讨论：
- 若有两个环链接，一个环独立，则答案为 6。
- 若有两个环链接在同一个环上，则答案为 5。
- 若三个环两两链接，答案为 4。
若没有环链接，考虑求得三个环叠起来的顺序：
- 若三个环有序地叠在一起（如 3 在 2 上，2 在 1 上，3 在 1 上），则答案为 8。
- 若三个环之间环形地叠在一起（如 3 在 2 上，2 在 1 上，1 在 3 上），发现此时也是可以形成无法解开的稳定结构的，则答案为 7。
判断上述两种没有环链接的情况，可以考虑求得每个环下面有多少环。若每个环下面均有 1 个环则为第二种情况，否则为第一种情况。
场上没想到最后一种情况一直挂，拿三根纸条穿来穿去突然就把最后一种情况造出来了我真是 hack 数据的天才。然而扔给 dztle 实现写了个集贸呃呃战犯、、、
Code by dztle：
#include<bits/stdc++.h>
using namespace std;
#define int long long
char c[10][10];
bool ok[10];
int cnt=0;
int rk[4];
signed main(){
for(int i=1;i<=6;++i){
scanf("%s",c[i]);
if(c[i][0]=='t') ok[i]=1;
else ok[i]=0;
}
if(ok[1]^ok[4]) ++cnt; //1 2
else if(ok[1]) rk[2]++;
else rk[1]++;
if(ok[2]^ok[5]) ++cnt; //1 3
else if(ok[2]) rk[3]++;
else rk[1]++;
if(ok[3]^ok[6]) ++cnt; //2 3
else if(ok[3]) rk[3]++;
else rk[2]++;
if(cnt==0){
bool fl=0;
for(int i=1;i<=3;++i){
if(rk[i]==2){
fl=1;
}
}
if(fl) cout<<8;
else cout<<7;
}
if(cnt==1) cout<<6;
if(cnt==2) cout<<5;
if(cnt==3) cout<<4;
return 0;
}
J
BFS。
队友写的看都没看。
Code by dzlte：
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1; char s;
while((s=getchar())<'0'||s>'9'){
if(s=='-') f=-1;
}
while(s>='0'&&s<='9'){
x=x*10+(s^'0');
s=getchar();
}
return x*f;
}
const int N=3005;
int n,m,T,a[N],head[N],tot;
struct node{
int to,nxt;
}e[N<<1];
inline void add(int u,int v){
e[++tot].nxt=head[u],head[u]=tot,e[tot].to=v;
}
int w[N],f[N],q[N],top,bo;
void bfs(){
bo=1;
q[++top]=1;
memset(w,0x3f,sizeof(w));
w[1]=0;
while(top>=bo){
int u=q[bo];
++bo;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(w[v]>w[u]+1){
w[v]=w[u]+1;
q[++top]=v;
}
}
}
}
signed main(){
n=read(),m=read(),T=read();
for(int i=2;i<=n;++i){
a[i]=read();
}
for(int i=1,u,v;i<=m;++i){
u=read(),v=read();
add(u,v);
add(v,u);
}
bfs();
f[0]=0;
for(int i=2;i<=n;++i){
for(int j=w[i]*2;j<=T;++j){
f[j]=max(f[j],f[j-w[i]*2]+a[i]);
}
}
for(int i=1;i<=T;++i){
cout<<f[i]<<' ';
}
return 0;
}
F
数学，整除分块。
妈的都忘了这东西了我是数论麻瓜。
记最后剩余 \(n'\) 个人，则此时最少应将每个人手中的物品调整为 \(\left\lceil \frac{m}{n'} \right\rceil\) 个。则最少操作次数为：
\[\begin{aligned} &(n - n') + \left\lceil \frac{m}{n'} \right\rceil \times n' - m\\ =&\left( \left\lceil \frac{m}{n'} \right\rceil - 1 \right)\times n' + (n - m) \end{aligned}\]有 \(1\le n'\le n\)，由整除分块可知，\(\left\lceil \frac{m}{n'} \right\rceil\) 仅有 \(\sqrt{n}\) 种取值，对于每一种取值为了最小化上式应取满足该取值的最小的 \(n'\)。于是考虑整除分块枚举 \(\left\lceil \frac{m}{n'} \right\rceil\) 对应的每一种取值的 \(n'\) 的区间检查上式求最小值即可。
总时间复杂度 \(O(T\sqrt{n})\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int n, m; std::cin >> n >> m;
LL ans = 1e9;
//(n - nn) + ceil(m / nn) * nn - m
//(ceil(m / nn) - 1) * nn + n - m
for (LL j = n, i; j; j = i - 1) {
i = ceil(1.0 * m / ceil(1.0 * m / j));
LL k = ceil(1.0 * m / j) - 1;
ans = std::min(ans, k * i + n - m);
}
std::cout << ans << "\n";
}
return 0;
}
G
并查集。
一个显然的想法是先使用 map 建立位置与编号的映射，然后使用并查集维护所有连通块的边界数量。
考虑加入一个位置对所在连通块的影响。发现仅需考虑六个相邻位置，且每有一个已存在的相邻位置均会令所在连通块的边界数量减 2，并查集合并时直接维护即可。
总时间复杂度 \(O(q\log q\alpha(q))\)
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pii std::pair<int,int>
#define mp std::make_pair
const int kN = 2e6 + 10;
const int ex[6] = {1, 0, -1, -1, 0, 1};
const int ey[6] = {0, 1, 1, 0, -1, -1};
//=============================================================
int nodenum, fa[kN], sz[kN];
std::map <pii, int> id;
//=============================================================
int getid(int x_, int y_) {
if (!id.count(mp(x_, y_))) return -1;
return id[mp(x_, y_)];
}
int find(int x_) {
return fa[x_] == x_ ? x_ : fa[x_] = find(fa[x_]);
}
void merge(int x_, int y_) {
int fax = find(x_), fay = find(y_);
if (fax == fay) return ;
fa[fax] = fay;
sz[fay] += sz[fax];
}
void newnode(int x_, int y_) {
id[mp(x_, y_)] = ++ nodenum;
fa[nodenum] = nodenum;
sz[nodenum] = 6;
int p = nodenum, cnt = 0;
for (int i = 0; i < 6; ++ i) {
int q = getid(x_ + ex[i], y_ + ey[i]);
if (q == -1) continue;
merge(p, q);
cnt += 2;
}
sz[find(p)] -= cnt;
return ;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int q; std::cin >> q;
while (q --) {
int opt, x, y; std::cin >> opt >> x >> y;
if (opt == 1) {
newnode(x, y);
} else {
std::cout << sz[find(getid(x, y))] << "\n";
}
}
return 0;
}
/*
8
1 0 0
2 0 0
1 0 2
1 1 2
1 0 3
2 0 3
1 0 1
2 0 0
*/
D
二叉树，最短路。
本场好玩题。
写在最后
学到了什么：
- F：整除分块求最小值。
- I：偏序关系 or 成环。