DuLiu
题目描述
LF 是毒瘤出题人中 AK IOI2019，不屑于参加 NOI 的唯一的人。他对人说话，总是满口垃圾题目者也，教人半懂不懂的。因为他姓李，别人便从 QQ 群上的“毒瘤李 Fee”这半懂不懂的话里，替他取下一个绰号，叫做李 Fee。
李 Fee 一到机房，所有做题的人便都看着他笑，有的叫道，“李 Fee，你又来出毒瘤题了！”他不回答，对验题人说，“我又出了两道题，给我验验。”便排出一排毒瘤题。大家又故意的高声嚷道，“你又暴露奸商本性拿毒瘤题骗钱剥削验题人了！”李 Fee 睁大眼睛说，“你怎么这样凭空污人清白……”“什么清白？我前天亲眼见你出了道毒瘤骗钱题，被 PTY 把 std 吊着打。” 李 Fee 便涨红了脸，额上的青筋条条绽出，争辩道，“出题人的题不能算骗……毒瘤！……出题人的题，能算毒瘤骗钱题么？”接连便是难懂的话，什么“多叉 splay 随机点分治”，什么“树链剖分套分治 FFT”之类，引得众人都哄笑起来：机房内外充满了快活的空气。
虽然他的题十分毒瘤，但他的题还总是有买家。李 Fee 现在有 N 道毒瘤题，想将这些题出成一组题来骗大钱。然而显而易见的是，一组题的毒瘤程度不仅和每道题的毒瘤程度有关，也跟它们的排列顺序有关，李 Fee 需要将它们排列成最毒瘤但又最能骗钱的那个顺序。
具体来说，这 N 道题每题都有一个毒瘤值，它们构成了一个序列。李 Fee 心目中有一个理想的毒瘤值序列，这个序列并不一定每一题的毒瘤值都是原本 N 道题中出现的，所以李 Fee 准备进行一些改动。这些改动体现在毒瘤值上就是将某道题的毒瘤值改为所有题的毒瘤值的二进制异或值。但是，改动题目是很麻烦的，他想算出最少需要多少次改动才能将原本的毒瘤值序列改成理想的毒瘤值序列，李 Fee 忙于出毒瘤题，他想请发明 O(1/n)算法用暴力搜过所有毒瘤题的你帮他算出答案。但是他是个奸商，所以他并不打算给你报酬。
思路
我们发现异或和放进去再异或一下相当于还原了被替换的那个数。也就是我们要对 $n+1$ 个数排序，每次操作允许交换两个数，使得它和另外的一个给定数列相等。我们可以用并查集来维护数列里环的关系，每次交换是将一对数加入环中，合并时统计答案。最后注意是每个环都要消耗 1 的代价，另行计算即可。
代码
#include
#define maxn 100010
using namespace std;
int n,a[maxn],b[maxn],spt,ans;
int cnt[maxn],fa[maxn],tot;
mapid;
int find(int x){return fa[x]!=x?fa[x]=find(fa[x]):x;}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if (fx!=fy) fa[fy]=fx;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",a+i),spt=spt^a[i];
a[n+1]=spt;spt=0;
for (int i=1;i<=n;i++)
scanf("%d",b+i),spt=spt^b[i];
b[n+1]=spt;n++;
for (int i=1;i<=n;i++)
if (a[i]!=b[i]||i==n){
if (!id.count(a[i])) id[a[i]]=++tot;
cnt[id[a[i]]]++;
}
for (int i=1;i<=n;i++)
if (a[i]!=b[i]||i==n)
cnt[id[b[i]]]--;
for (int i=1;i<=tot;i++)
if (cnt[i]){puts("-1");return 0;}
for (int i=1;i<=n;i++) a[i]=id[a[i]];
for (int i=1;i<=n;i++) b[i]=id[b[i]];
for (int i=1;i<=tot;i++) fa[i]=i;
for (int i=1;i<=n;i++)
if (a[i]!=b[i]){
if (i Travel
题目描述
EZ 同学家里非常富有，但又极其的谦虚，说话又好听，是个不可多得的人才。
EZ 常常在假期环游世界，他准备去N（N<=100000）个国家之多，一些国家有航线连接，由于 EZ 同学有一定的强迫症，任意两个国家之间都能通过航路直接或间接到达，并且这样的路径仅有一种。（简单来说，这些国家构成了一棵树）
由于 EZ 是 C 国人，因此将 C 国（1号国家）作为整棵树的根。
每个国家有一个旅游热度 A[i] 和影响力 D[i]。由于目的地有点多，为了避免选择困难症，他给每个国家设置了一个向往值 F[i]，它等于所有的 A[j]之和，满足 i 国在 j 国向 C 国走 D[j] 步的路径上（经过一条航路算一步，i=j 也会被统计，如果 D[j] 步超过了 C 国，则超出部分不用管）。
LYD 同学家里有矿，富有程度与 EZ 不相上下，但他却在宅与现充间摇摆不定。某次机缘巧合，EZ 外出旅游刺激了 LYD，他决定也要开始旅游。为了避免又被判高重复率导致被取消资格，他将 EZ 的旅游地图略微做了一点调整，每条航路将有一定的概率出现。
现在他有 Q 个询问，每次询问某个国家所在的联通块（由于每条边是一定概率出现，因此它所在的联通块可以是很多种）中所有国家的 F[i] 值的和的平方的期望（对 998244353 取模），以此来决定他旅游的目的地。但他极其厌恶繁琐的计算，于是他找到了能算出圆周率并将它倒背下来的你，答应给你丰厚的报酬。家里没矿，老爸也不是 X 达集团老总的你决定接受他的任务。
思路
求两个块以一条出现概率为 $p$ 的边合并时的答案。不妨令原本的块为 $a$，并入的块为 $b$，根据期望的线性可加性，那么答案是$p(a + b)^2 + (1 − p)a^2 =a^2 + p(2ab + b^2)$。
这样对于每个点 i，维护以它为根的子树中期望和的平方 h[i][1]，以及期望和 h[i][0]。
坦率地讲，这道题我不会做。
代码
坦率地讲，这份代码只有 50分，我也不知道我写的是什么意思。
#include
#define mod 998244353
#define maxn 200010
#define ll long long
using namespace std;
struct Edge{
int to,next,val;
Edge(int a=0,int b=0,int c=0){
to=a,next=b,val=c;
}
}l[maxn<<1];
int head[maxn],dep[maxn];
int A[maxn],D[maxn],F[maxn];
int sta[maxn],top,n,q,cnt;
int h[maxn][3],g[maxn][6],ans[maxn];
int del(int x,int y){return x=mod?x+y-mod:x+y;};
int ksm(int x,int y){
int res=1;
while(y){
if (y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;y>>=1;
}
return res;
}
void Add(int a,int b,int c){
l[++cnt]=Edge(b,head[a],c);
head[a]=cnt;
}
void Dfs(int u,int f){
sta[++top]=u;
F[u]+=A[u];
F[sta[max(top-D[u]-1,0)]]-=A[u];
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==f) continue;
Dfs(v,u);
}
top--;
}
void Sum(int u,int f){
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==f) continue;
Sum(v,u);
(F[u]+=F[v])%=mod;
}
}
void Merge(int x,int y,int p){
h[x][1]=inc((ll)del(1,p)*h[x][1]%mod,(ll)p*inc(2ll*h[x][0]%mod*h[y][0]%mod,inc((ll)h[x][1]*h[y][2]%mod,(ll)h[x][2]*h[y][1]%mod))%mod);
h[x][0]=inc((ll)del(1,p)*h[x][0]%mod,(ll)p*inc((ll)h[x][0]*h[y][2]%mod,(ll)h[x][2]*h[y][0]%mod)%mod);
h[x][2]=inc((ll)del(1,p)*h[x][2]%mod,(ll)p*h[x][2]%mod*h[y][2]);
}
void Dp(int u,int f){
h[u][0]=F[u],h[u][2]=1,h[u][1]=(ll)F[u]*F[u]%mod;
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==f) continue;
Dp(v,u);Merge(u,v,l[i].val);
}
}
void Solve(int u,int f){
ans[u]=h[u][1];
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==f) continue;
for (int j=0;j<3;j++)
g[u][j]=h[u][j],g[u][j+3]=h[v][j];
int inv=ksm(inc(del(1,l[i].val),(ll)l[i].val*h[v][2]%mod),mod-2);
h[u][2]=(ll)h[u][2]*inv%mod,h[u][0]=(ll)del(h[u][0],(ll)l[i].val*h[u][2]%mod*h[v][0]%mod)*inv%mod;
h[u][1]=(ll)del(h[u][1],(ll)l[i].val*inc(2ll*h[u][0]*h[v][0]%mod,(ll)h[u][2]*h[v][1]%mod)%mod)*inv%mod;
Merge(v,u,l[i].val);
Solve(v,u);
for (int j=0;j<3;j++) h[u][j]=g[u][j],h[v][j]=g[v][j+3];
}
}
int main(){
freopen("travel.in","r",stdin);
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",A+i,D+i);
for (int i=1;i VanUSee
题目描述
众所周知，cqf 童鞋对哲学有着深入的理解和认识，并常常将哲学思想应用在实际生活中，例如锻炼摔角技术或者研究化(fa)学。
由于 cqf 童鞋哲学造诣太过高深，以至于影响到了 pty，他们常常给在一块 VanUSee。Van 的都是一些像“装备回收交易自由”、“开局一条鲲进化全靠吞”、“今晚八点是兄弟就来肝”这样高端大气上档次的著名 USee。
有一天他们决定 Van 一个亲民的 USee 来和大家分享他们的哲学心路历程。
规则是这样的：
- 给定两个串 S 和 T，|S| >= |T|。
- cqf 和 pty 轮流操作串S，cqf 先手。
- 对于每次操作，cqf 或 pty 会选择删掉 S 的第一位或最后一位。
- 当操作以后的串的长度等于 |T| 时，游戏停止。
- 如果停止时的串 =T，则 pty 获胜，否则 cqf 获胜。
cqf 和 pty 的哲学思维都很强，他们都能采取最优的策略来行动。
作为高级玩家的苏巴先生在一旁观战，他早已看穿了这个 USee 的本质，当两个串给出的那一瞬间胜负已分，然而不是所有围观者的水平都像苏巴先生那么高，其中也没有五年级的积分小哥，他们又想知道结果，于是围观者们找到了能预见一局围棋接下来 40 手的你。
思路
设左边已经删掉了 L 个字符，右边已经删掉了 R 个字符，那么用 R-L 来表示当前状态，用 KMP 求出有哪些目标状态。
一开始 R-L 为 0，每一次操作可以让它+1 或者-1，双方轮流操作，总共|S|-|T|次操作，双方都用最优策略看最后是否能到达目标状态。
显然所有的目标状态奇偶性相同，当|S|-|T|为奇数时，最后一次操作是先手做，它肯定往不是目标状态走，那么一个位置在最后一次操作前是目标状态当且仅当它 +1 以及它 -1 都是目标状态。
现在就全部转化成|S|-|T|为偶数的情况：
- 假如 0 是目标状态，那么显然后手会赢，因为无论先手往哪里走后手都可以把他拉回来
- 如果 0 不是，并且-2 和 2 不全是，那么先手一定会朝不是的那一边走，后手无论如何都没有办法将它拉回到是的那一边了
因此后手会赢当且仅当 0 是目标状态或者-2 和 2 都是目标状态，否则都是先手赢。
代码
#include
#define maxn 100101
using namespace std;
char s1[maxn],s2[maxn];
int next[maxn],pos[maxn],tot;
int f[maxn];
bool solve(){
memset(next,0,sizeof(next));
memset(f,0,sizeof(f));
tot=0;
scanf("%s%s",s1+1,s2+1);
int len1=strlen(s1+1),len2=strlen(s2+1);
for (int i=2,j=0;i<=len2;i++){
while(j&&s2[j+1]!=s2[i]) j=next[j];
if (s2[j+1]==s2[i]) j++;next[i]=j;
}
for (int i=1,j=0;i<=len1;i++){
while(j&&s1[i]!=s2[j+1]) j=next[j];
if (s1[i]==s2[j+1]) j++;
if (j==len2) f[len1-i]=1,j=next[j];
}
int turn=len1-len2;
if (turn&1){
for (int i=0;i<=len1;i++)
f[i]=f[i]&f[i+1];turn--;
}
if (!turn) return f[0]!=1;
turn=turn/2-1;
for (int i=0;i<=len1;i++) f[i]|=f[i+1];
for (int i=0;i<=len1;i++) f[i]&=f[i+1];
return f[turn]!=1;
}
int main(){
int T;scanf("%d",&T);
while(T--) puts(solve()?"cqf":"pty");
return 0;
}