赛时 rank 28,T1 44,T2 0,T3 30,T4 5
啊哈哈哈哈哈，我要挂没啦，啊哈哈哈哈哈哈哈哈哈
最后10min的心路历程
- 感觉应该又要挂分了 (11:20)
- 感觉一分没有 (11:23)
- 要被薄纱了 (11:25)
- 感觉人均AK，就我不会(11:25)
- 啊哈哈哈哈哈，我太菜了，我要AF0了(11:27)
啊哈哈哈，看了一眼自己代码，我咋只会打暴力啊，啊哈哈哈(11:28)- 啊哈哈哈，要死了，啊啊(11:29)
这几天做的梦是越来越逆天了。没准哪天就写一个记梦之作？
T1 小孩召开法 1
记搜状压
赛时胡了一个错的结论
签到失败
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 17;
int n;string s[N];
bool vis[N][1<<N],ans[N][1<<N];
bool dfs(int last,int state){
if(vis[last][state]) return ans[last][state];
for(int i = 1;i <= n; ++i){
if((state&(1<<(i-1)))) continue;
if(last == 0 || s[last].back() == s[i].front()){
if(!dfs(i,state|(1<<(i-1)))){
vis[last][state] = true;
return ans[last][state] = true;
}
}
}
vis[last][state] = true;
return ans[last][state] = false;
}
inline void solve(){
cin>>n;
for(int i = 1;i <= n; ++i) cin>>s[i];
if(dfs(0,0)) cout<<"First";
else cout<<"Second";
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T2 小孩召开法 2
神仙交互题。
\(O(n^2)\)的非常简单，考虑如何优化这个东西。
先求出以1为根的所有点的深度。
从小到大枚举深度，当枚举到第i层时，那么说明\(1\sim i-1\)层已经处理好了。
那么将这个已经处理好的树剖开，枚举第i层中的点\(x\)，求与点\(y\)(初始时钦定为1)的lca。
跳到lca所在重链的底部，求出\(x\)与\(y\)的距离。
如果距离不为0，那么就从这里跳到距离级父亲。
如果正好为第i-1层，那么这个就是x的父亲，反之，那么说明重链肯定没有x的父亲，走到轻链。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
const int N = 3010;
int ans[N],n;
vector<int> a[N];
int ch[N][2],siz[N],son[N],dist[N],fa[N];
void dfs(int x){
if(!x) return;
dfs(ch[x][0]);dfs(ch[x][1]);
siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]];
if(siz[ch[x][0]] > siz[ch[x][1]]) son[x] = son[ch[x][0]];
else son[x] = son[ch[x][1]];
if(siz[x] == 1) son[x] = x;
}
inline void solve(){
cin>>n;int mx = 0;
auto Query = [](int x,int y) -> int{
cout<<"? 1 "<<x<<' '<<y<<endl;
int dis;cin>>dis;
return dis;
};
for(int i = 2,dis;i <= n; ++i){
dis = Query(1,i);
dist[i] = dis;
mx = max(dis,mx);
a[dis].push_back(i);
}
for(int i = 1;i <= mx; ++i){
dfs(1);
for(int x : a[i]){
int y = 1;
while(dist[y] != i-1){
int z = son[y],dis = dist[z] - (dist[z] + dist[x] - Query(z,x))/2;
while(dis--) z = fa[z];
if(dist[z] == i - 1){ y = z;break;}
if(siz[ch[z][0]] > siz[ch[z][1]]) y = ch[z][1];
else y = ch[z][0];
}
fa[x] = y;
if(!ch[y][0]) ch[y][0] = x;
else ch[y][1] = x;
}
}
cout<<"! ";
for(int i = 2;i <= n; ++i) cout<<fa[i]<<' ';
cout<<endl;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T3 小孩召开法 3
猫树分治的trick
先去学猫树了
T4 小孩召开法 4
放AK题，离谱中的离谱
标签：11,13,ch,int,siz,集训,using,son,csp From： https://www.cnblogs.com/hzoi-Cu/p/18337353