上半最后一次正式模拟赛，感觉还彳亍
Rank
A. 小孩召开法1
签到题。
博弈论+状压+记搜秒了，感觉不用太细说。
不过是暑假以来第一次首 A 啊，开始还胡乱想 SG 定理的做法，后来发现不用那么复杂。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=1e5+5;
const int mod=998244353;
int n,sg[1<<17][17];
string s[17];
namespace Wisadel
{
int Wdfs(int now,int las)
{
if(sg[now][las]!=-1) return sg[now][las];
fo(i,1,n)
if(!(now&(1<<(i-1))))
{
bool can=0;
if(!las) can=1;
else
{
int len=s[las].size();
if(s[las][len-1]==s[i][0]) can=1;
}
if(!can) continue;
if(!Wdfs((now|(1<<(i-1))),i)) return sg[now][las]=1;
}
return sg[now][las]=0;
}
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
memset(sg,-1,sizeof sg);
n=qr;
fo(i,1,n) cin>>s[i];
if(Wdfs(0,0)) printf("First\n");
else printf("Second\n");
return Ratio;
}
}
int main(){return Wisadel::main();}
B. 小孩召开法2
原LibreOJ 6669.Nauuo and Binary Tree‘
又挂在交互题上了。
果然是对树不敏感导致的，询问次数超了。
正解是逐层遍历，通过找最近公共祖先来优化询问的次数。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx int
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=3e3+5;
const int mod=998244353;
int n;
int fx[N],dep[N],in[N],dpt;
vector<int>v[N];
unordered_map<int,int>mp;
namespace Wisadel
{
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
n=qr;
fo(i,2,n)
{
printf("? 1 %d\n",i);fflush(stdout);
dep[i]=qr;v[dep[i]].emplace_back(i);
if(dep[i]==1) fx[i]=1;
dpt=max(dpt,dep[i]);
}
fo(i,2,dpt)
for(int x:v[i])
{
int lca=1;mp.clear();
fo(j,0,v[i-1].size()-1)
{
int y=v[i-1][j];
if(j==v[i-1].size()-1)
{
fx[x]=y;in[y]++;
break;
}
if(in[y]==2) continue;
int zc=y;
while(zc&&zc!=lca&&!mp[zc]) zc=fx[zc];
if(zc!=lca) continue;
printf("? %d %d\n",x,y);fflush(stdout);
int dis=qr;
if(dis==1)
{
fx[x]=y;in[y]++;
break;
}
int lcdp=(dep[x]+dep[y]-dis)/2;
zc=y;
while(dep[zc]!=lcdp) mp[zc]=1,zc=fx[zc];
lca=zc;
}
}
printf("! ");
fo(i,2,n) printf("%d ",fx[i]);
fflush(stdout);
return Ratio;
}
}
int main(){return Wisadel::main();}
C. 小孩召开法3
赛时由于又又被 T2 硬控了，这道题也是只打了个最低级的暴力，每次询问做一次 dp。
正解是猫树分治，挺新奇的玩意，（下午光颓了还没细学。
D. 小孩召开法4
更抽象的题，不评价了。
末
这回排的高主要是因为把 T1 做出来了，感觉 T2 T3 都还有提高的空间。
嗯嗯好的所以明天有人愿意跟我组队吗（呜呜
嗯嗯好的所以明天有人愿意跟我组队吗（呜呜
嗯嗯好的所以明天有人愿意跟我组队吗（呜呜
嗯嗯好的所以明天有人愿意跟我组队吗（呜呜
嗯嗯好的所以明天有人愿意跟我组队吗（呜呜
可能想看的
完结撒花~
标签：13,ch,fx,int,zc,dep,lx,CSP,模拟 From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18337435