A
直接输出两个数的差即可。再判一下无解的情况。
B
其实思路还挺顺的，首先拿的牌肯定是一段增一段减一段增一段减……的序列，并且
>
n
>n
>n 的开头和
≤
n
\leq n
≤n 的开头两种序列是对称的，我们随便考虑一种最后答案乘以二即可。
下面称
1
1
1 ~
n
n
n 的数为一堆，
n
+
1
n+1
n+1 ~
2
n
2n
2n 为一堆。
为了避免计重，考虑在每个序列最后一张被取走的牌的那个位置统计答案，设
f
i
,
j
f_{i,j}
fi,j 表示前
i
i
i 位合法的放置方案数，并且
i
i
i 不在的那一堆里还有
j
j
j 个没用过的数。
j
j
j 这一维存在的意义很明确，就是要用来转移的，先考虑对答案的贡献，分为两种：
-
j
j
j 个全部按顺序用完，并且剩下没有数了（即
i
+
j
=
2
n
i+j=2n
i+j=2n），则对答案产生贡献
2
n
×
f
i
,
j
2n\times f_{i,j}
2n×fi,j
- 如果不是所有数都放完了，而且还要取走了最后一张牌（即后面不能取了），那么一定是出现了不合法的取法，即同一堆数不是按递减或递增顺序取的。假设最后这堆取了
k
k
k 张牌，那么一定是
k
−
1
k-1
k−1 张按顺序的以及 最后一张不按顺序的，贡献为
(
i
+
k
)
×
f
i
,
j
×
C
j
k
×
(
k
−
1
)
(i+k)\times f_{i,j}\times C_j^k\times (k-1)
(i+k)×fi,j×Cjk×(k−1)，其中
k
−
1
k-1
k−1 表示选出来的
k
k
k 张牌中还要选一个放在最后（且不能是最小/最大的那张）。
f
f
f 的转移类似，具体可以看代码。
说起来多其实写起来很短，而且还没啥细节：
#include <bits/stdc++.h>
using namespace std;
#define maxn 610
int n,mod,C[maxn][maxn],fac[maxn];
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
int add(int x){return x>=mod?x-mod:x;}
int f[maxn][maxn];
int main()
{
int Te;cin>>Te;while(Te--){
cin>>n>>mod;
for(int i=0;i<=2*n;i++){
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=add(C[i-1][j]+C[i-1][j-1]);
}
fac[0]=1;
for(int i=1;i<=2*n;i++)
fac[i]=1ll*fac[i-1]*i%mod;
for(int i=0;i<=2*n;i++)
for(int j=0;j<=n;j++)
f[i][j]=0;
f[0][n]=1;
int ans=0;
for(int i=0;i<2*n;i++){
for(int j=1;i+j<=2*n&&j<=n;j++){
if(i+j==2*n)add(ans,1ll*f[i][j]*2*n%mod);
for(int k=2;k<=j;k++)
add(ans,1ll*(i+k)*f[i][j]%mod*C[j][k]%mod*(k-1)%mod*fac[2*n-i-k]%mod);
}
for(int j=1;i+j<=2*n&&j<=n;j++)
for(int k=1;k<=j;k++)
if(2*n-i-j<=n)
add(f[i+k][2*n-i-j],1ll*f[i][j]*C[j][k]%mod);
}
ans=2ll*ans%mod;
cout<<ans<<'\n';
}
}
D
手玩一下发现其实只有全
0
0
0 或全
1
1
1 的矩阵才是满足要求的。
考虑一个比较粗略的证明：
首先
0
≤
r
i
,
c
j
≤
2
n
−
1
0\leq r_i,c_j\leq 2^n-1
0≤ri,cj≤2n−1
假如第一列全是
1
1
1，那么
max
(
c
j
)
=
2
n
−
1
\max(c_j) =2^n-1
max(cj)=2n−1，则
min
(
r
i
)
=
2
n
−
1
\min(r_i)=2^n-1
min(ri)=2n−1，即所有行都是全
1
1
1。
假如第一列存在一个
0
0
0 且不在第一行，那么
max
(
c
j
)
≥
2
n
−
1
,
min
(
r
i
)
<
2
n
−
1
\max(c_j)\geq 2^{n-1},\min(r_i)<2^{n-1}
max(cj)≥2n−1,min(ri)<2n−1，与条件不符，所以不可能出现。
所以第一列要是有
0
0
0，第一行必然有一个，此时
min
(
r
i
)
<
2
n
−
1
\min(r_i)<2^{n-1}
min(ri)<2n−1，要使
max
(
c
j
)
<
2
n
−
1
\max(c_j)<2^{n-1}
max(cj)<2n−1，则第一行不能有
1
1
1。
由此可知，第一行全是
0
0
0，所以
min
(
r
i
)
=
0
\min(r_i)=0
min(ri)=0，故
max
(
c
j
)
=
0
\max(c_j)=0
max(cj)=0，即每一列都全是
0
0
0。
证毕。
说着有点儿绕，总结起来就是：
- 第一列全是
1
→
1\red\to
1→ 所有行全是
1
1
1
- 第一列有
0
→
0\red\to
0→ 第一行肯定有
0
→
0\red\to
0→第一行全是
0
→
0\red\to
0→ 所有列全是
0
0
0
所以考虑能不能将整个矩阵变成全
0
/
1
0/1
0/1 的矩阵。两种思路是一样的，就将变全
0
0
0 的吧。
首先每一行每一列至多翻转一次，重复翻转没意义。于是可以枚举第一行是否翻转，操作后假如第一行还有
1
1
1，那么只能翻转他所在的这一列来消除掉这个
1
1
1。接下来为了不改变第一行已经合法的状态，所以不能再翻转列了，看下面每一行需不需要翻转即可，假如有一行既有
1
1
1 也有
1
1
1 则无解。
其实是个很贪心很暴力的简单思路，代码如下：
#include <bits/stdc++.h>
using namespace std;
#define maxn 2010
#define inf 999999999
int n;
char s[maxn][maxn];
bool line[maxn],col[maxn];
int get(int x,int y){
int re=s[x][y]-'0';
return (re^line[x]^col[y]);
}
int solve(){
int re=inf;
for(int line1=0;line1<=1;line1++){
memset(line,false,sizeof(line));
memset(col,false,sizeof(col));
line[1]=line1;
int tot=line1;
for(int i=1;i<=n;i++)
if(get(1,i))col[i]=true,tot++;
for(int i=2;i<=n;i++)
if(get(i,1))line[i]=true,tot++;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(get(i,j))tot=inf;
re=min(re,tot);
}
return re;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
int ans=inf;
ans=min(ans,solve());
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(s[i][j]=='1')s[i][j]='0';
else s[i][j]='1';
ans=min(ans,solve());
if(ans>=2*n)puts("-1");
else printf("%d",ans);
}
E
其实就是问 是否 dfs顺序如何变化整张图每个点的深度都不变。
先跑一次bfs跑出每个点的深度，将图分层，考虑不在bfs树上的几种边
(
u
,
v
)
(u,v)
(u,v)：
- 假如
d
e
p
u
+
1
=
d
e
p
v
dep_u+1=dep_v
depu+1=depv，那么这种边不影响答案
- 假如
d
e
p
u
+
1
≠
d
e
p
v
dep_u+1\neq dep_v
depu+1=depv，首先基于分层图的性质不可能是
d
e
p
u
+
1
<
d
e
p
v
dep_u+1<dep_v
depu+1<depv，那么只可能是
d
e
p
u
+
1
>
d
e
p
v
dep_u+1>dep_v
depu+1>depv，假如
v
v
v 不支配
u
u
u，那么一定存在一条路径会使得
v
v
v 能得到更大的深度。此时答案为 No。否则，这条边一定没用，因为遍历到
u
u
u 时一定已经遍历过
v
v
v 了，
u
u
u 无法再更新
v
v
v。
所以其实这题难点是会不会支配树……然而我还不会，但是上网膜了个板子魔改一下之后居然过了。
代码参考性也许不是很大：
#include<bits/stdc++.h>
using namespace std;
#define maxn 500010
#define cn getchar
template<class TY>void read(TY &x){
x=0;int f1=1;char ch=cn();
while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}
while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
}
template<class TY>void write2(TY x){
if(x>9)write2(x/10);
putchar(x%10+'0');
}
template<class TY>void write(TY x){
if(x<0)putchar('-'),x=-x;
write2(x);
}
int n,m,dfn[maxn],id[maxn],tot,dep[maxn];
int ffa[maxn],fa[maxn],semi[maxn],val[maxn],du[maxn],ff[25][maxn];
queue<int>q,q1;
vector<int>cg[maxn];
struct node{
vector<int>edge[maxn];
void add(int u,int v){
edge[u].push_back(v);
}
void clear(int n){
for(int i=1;i<=n;i++)
edge[i].clear();
}
}a,b,c,d;
void dfs(int x,int f){
dfn[x]=++tot,id[tot]=x,ffa[x]=f,c.add(f,x);
for(int i=0;i<a.edge[x].size();++i)
if(!dfn[a.edge[x][i]])dfs(a.edge[x][i],x);
}
int find(int x){
if(x==fa[x]) return x;
int tmp=fa[x];fa[x]=find(fa[x]);
if(dfn[semi[val[tmp]]]<dfn[semi[val[x]]]) val[x]=val[tmp];
return fa[x];
}
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
int d=dep[x]-dep[y];
for(int i=20;i>=0;i--)
if(d&(1<<i)) x=ff[i][x];
for(int i=20;i>=0;i--)
if(ff[i][x]^ff[i][y])
x=ff[i][x],y=ff[i][y];
return x==y?x:ff[0][x];
}
inline void tarjan(){
for(int i=n;i>=2;--i){
if(!id[i]) continue;
int x=id[i],res=n;
for(int j=0;j<b.edge[x].size();++j){
int v=b.edge[x][j];
if(!dfn[v]) continue;
if(dfn[v]<dfn[x]) res=min(res,dfn[v]);
else find(v),res=min(res,dfn[semi[val[v]]]);
}
semi[x]=id[res],fa[x]=ffa[x],c.add(semi[x],x);
}
for(int x=1;x<=n;x++)
for(int i=0;i<c.edge[x].size();++i)
du[c.edge[x][i]]++,cg[c.edge[x][i]].push_back(x);
for(int x=1;x<=n;x++)
if(!du[x]) q.push(x);
while(!q.empty()){
int x=q.front();q.pop();q1.push(x);
for(int i=0;i<c.edge[x].size();++i)
if(!--du[c.edge[x][i]]) q.push(c.edge[x][i]);
}
while(!q1.empty()){
int x=q1.front(),f=0,len=cg[x].size();q1.pop();
if(len) f=cg[x][0];
for(int j=1;j<len;j++)
f=LCA(f,cg[x][j]);
ff[0][x]=f,dep[x]=dep[f]+1,d.add(f,x);
for(int p=1;p<=20;p++)
ff[p][x]=ff[p-1][ff[p-1][x]];
}
}
int u[maxn],v[maxn];
int fid[maxn],ID,con[maxn];
void dfs2(int x){
fid[x]=++ID;
for(int y:d.edge[x])
dfs2(y);
con[x]=ID;
}
int mydep[maxn],myq[maxn],st,ed;
void mybfs(){
myq[st=ed=1]=n;mydep[n]=1;
while(st<=ed){
int x=myq[st++];
for(int y:a.edge[x])
if(!mydep[y]){
mydep[y]=mydep[x]+1;
myq[++ed]=y;
}
}
}
int main()
{
int T;read(T);while(T--){
read(n);read(m);
for(int i=1;i<=n;i++){
fa[i]=val[i]=semi[i]=i;
dfn[i]=id[i]=dep[i]=ffa[i]=du[i]=mydep[i]=0;
cg[i].clear();
}tot=0;
for(int i=1;i<=m;i++){
read(u[i]);read(v[i]);
u[i]=n-u[i]+1;v[i]=n-v[i]+1;
a.add(u[i],v[i]),b.add(v[i],u[i]);
}
// root: n
dfs(n,0);tarjan();
ID=0;dfs2(n);mybfs();
bool ans=true;
for(int i=1;i<=m;i++)
if(mydep[u[i]]+1!=mydep[v[i]]){
if(fid[u[i]]>=fid[v[i]]&&fid[u[i]]<=con[v[i]]);
else {ans=false;break;}
}
puts(ans?"Yes":"No");
a.clear(n);b.clear(n);c.clear(n);d.clear(n);
}
}
G
当时一眼就想到了马拉车，但是没细想，开玩笑说了个是不是什么二维马拉车的神奇科技……
其实仔细考虑马拉车的话思路是很简单的，考虑每一行，枚举上下匹配对少列，然后直接跑马拉车，每次比较就是比较两段列，这个用哈希整一下就行。
代码晚点儿补……
H
n
=
1
n=1
n=1 的时候特判一下，
n
=
2
n=2
n=2 的时候根据哥德巴赫猜想来整就行，
n
=
3
n=3
n=3 其实一样，先判断总和是否大于等于
2
n
2n
2n，是的话就一定可以，假设除了
1
,
2
1,2
1,2 位置全放
2
2
2，剩下的总和是偶数那么就成功了，如果不是偶数，那么就把三号位变成
3
3
3，总和就变成偶数了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
bool prime(long long x){
for(long long i=2;i*i<=x;i++)
if(x%i==0)return false;
return true;
}
int main()
{
int n;long long sum=0;
cin>>n;
for(int i=1;i<=n;i++){
int x;cin>>x;
sum+=x;
}
if(sum<2*n)puts("No");
else if(n==1){
if(prime(sum))puts("Yes");
else puts("No");
}else if(n==2){
if(sum&1){
if(prime(sum-2))puts("Yes");
else puts("No");
}else puts("Yes");
}else{
puts("Yes");
}
}
I
沿着路径走的过程肯定是贪心的，能不换颜色就不换颜色，但是每次要换什么颜色呢？只需要将这个点的颜色和后面的点取交集，尽可能往后走，直到交集为空。
于是问题变成了如何快速进行一条路径的贪心，其实这个贪心并不好拆成两段贪并且合并，所以考虑在lca处枚举一个颜色，然后看看这个颜色最多能往
x
,
y
x,y
x,y 处延伸到哪儿，比如
x
x
,
y
y
xx,yy
xx,yy，那么现在就拆成了
x
→
x
x
x \to xx
x→xx 和
y
→
y
y
y\to yy
y→yy 的两段贪心。
一段子孙到祖先的贪心时很好求的，每个点向上二分一下找到最远能延伸到的点，然后倍增跳一下就求出步数了。
另外有个小优化，就是不用每次枚举之后都重新倍增跳，只需要一开始跳一次，跳到再跳一次就会跨过lca的位置就可以了，利用这个位置的深度和枚举即可求解。
时间复杂度
O
(
60
n
log
n
)
O(60n \log n)
O(60nlogn)，加上上面的优化时间复杂度其实也不变，但是由于常数可能有点儿大实在是过不去……
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define maxn 500010
#define inf 1000000
#define ll long long
#define cn getchar
template<class TY>void read(TY &x){
x=0;int f1=1;char ch=cn();
while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}
while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
}
template<class TY>void write2(TY x){
if(x>9)write2(x/10);
putchar(x%10+'0');
}
template<class TY>void write(TY x){
if(x<0)putchar('-'),x=-x;
write2(x);
}
int n,m;
ll c[maxn];
vector<int> to[maxn];
int sum[maxn][60];
int f[maxn][19],dep[maxn];
void dfs(int x){
for(int i=0;i<60;i++)
if(c[x]>>i&1)sum[x][i]++;
for(int y:to[x]){
if(y==f[x][0])continue;
f[y][0]=x;
for(int i=0;i<60;i++)
sum[y][i]=sum[x][i];
dep[y]=dep[x]+1;
dfs(y);
}
}
int fa[maxn][19];
void getfa(){
for(int i=1;i<=n;i++){
int x=i;
for(int j=18;j>=0;j--){
bool tf=false;
for(int k=0;k<60;k++)
if((c[f[x][j]]>>k&1) && sum[i][k]-sum[f[x][j]][k]==dep[i]-dep[f[x][j]])tf=true;
if(tf)x=f[x][j];
}
fa[i][0]=x;
}
for(int j=1;j<19;j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
}
int getlca(int x,int y){
if(dep[x]>dep[y])swap(x,y);
for(int i=18;i>=0;i--)
if(dep[f[y][i]]>=dep[x])y=f[y][i];
if(x==y)return x;
for(int i=18;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
int dis(int x,int y){
if(dep[x]>dep[y])swap(x,y);
int re=0;
for(int i=18;i>=0;i--)
if(dep[f[y][i]]>=dep[x])
y=f[y][i],re+=(1<<i);
if(x==y)return re;
for(int i=18;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i],re+=(1<<i+1);
return re+2;
}
struct par{
int x,step;
};
par calc(int x,int y){
if(x==y)return (par){y,0};
int re=0;
for(int i=18;i>=0;i--)
if(dep[fa[y][i]]>dep[x])
y=fa[y][i],re+=(1<<i);
if(dep[fa[y][0]]<=dep[x])return (par){y,re+1};
else return (par){y,inf};
}
int calc_ans(int x,int y){
int lca=getlca(x,y);
if(lca==x)return calc(x,y).step-1;
if(lca==y)return calc(y,x).step-1;
int re=inf;
par xx=calc(lca,x),yy=calc(lca,y);
if(xx.step==inf||yy.step==inf)return inf;
for(int i=0;i<60;i++)
if(c[lca]>>i&1){
int tot=xx.step+yy.step;
if(sum[xx.x][i]-sum[lca][i]==dep[xx.x]-dep[lca])tot--;
if(sum[yy.x][i]-sum[lca][i]==dep[yy.x]-dep[lca])tot--;
re=min(re,tot);
}
//优化前写法
/*for(int i=0;i<60;i++)if(c[lca]>>i&1){
int xx=x,yy=y;
for(int j=18;j>=0;j--){
if(dep[f[xx][j]]>=dep[lca] && sum[f[xx][j]][i]-sum[lca][i]<dep[f[xx][j]]-dep[lca])
xx=f[xx][j];
if(dep[f[yy][j]]>=dep[lca] && sum[f[yy][j]][i]-sum[lca][i]<dep[f[yy][j]]-dep[lca])
yy=f[yy][j];
}
if(sum[xx][i]-sum[lca][i]<dep[xx]-dep[lca])xx=f[xx][0];
if(sum[yy][i]-sum[lca][i]<dep[yy]-dep[lca])yy=f[yy][0];
re=min(re,calc(xx,x)+calc(yy,y));
}*/
return re;
}
int main()
{
read(n);read(m);
for(int i=1;i<=n;i++)read(c[i]);
for(int i=1,x,y;i<n;i++){
read(x);read(y);
to[x].push_back(y);
to[y].push_back(x);
}
dep[1]=1;dfs(1);
for(int j=1;j<19;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
getfa();
for(int i=1;i<=m;i++){
int x,y;read(x);read(y);
int ans=calc_ans(x,y)+dis(x,y);
if(ans>=inf)puts("-1");
else write(ans),puts("");
}
}
J
题意一开始还没看懂……就是要找几个
1
1
1 ~
n
n
n 的排列，使得给出的每个偏序关系都在某个排列中存在。
其实最多只需要两个，如果整一个
1
1
1 ~
n
n
n 再整个
n
n
n ~
1
1
1 那么所有偏序关系都有了。
那么就是要判断一下能不能一个排列整完，将偏序关系连边跑一个拓扑就行，有环就是需要两个排列，否则拓扑序就是答案。
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000010
struct edge{int y,next;}e[maxn];
int first[maxn],et=0;
void buildroad(int x,int y){
e[++et]=(edge){y,first[x]};
first[x]=et;
}
int main()
{
int n,m;cin>>n>>m;
vector<int> du(n+1);
for(int i=1;i<=m;i++){
int x,y;cin>>x>>y;
buildroad(x,y);
du[y]++;
}
vector<int> sta,ans;
for(int i=1;i<=n;i++)
if(!du[i])sta.push_back(i);
while(sta.size()){
int x=sta.back();sta.pop_back();
ans.push_back(x);
for(int i=first[x];i;i=e[i].next){
int y=e[i].y;du[y]--;
if(!du[y])sta.push_back(y);
}
}
if(ans.size()==n){
cout<<"1\n";
for(auto i:ans)
cout<<i<<' ';
}else{
cout<<"2\n";
for(int i=1;i<=n;i++)
cout<<i<<' ';
cout<<"\n";
for(int i=n;i>=1;i--)
cout<<i<<' ';
}
}
