上午
打比赛，基本疯了，myd暴力AT1，wj二分+贪心（错解）AT3，我T2式子推了2h，然后打错±号并同时%少了，成功爆到57.5
wjRank2 235，mydRank10 165
俺枯矣
中午
和myd，wj各下一盘棋，果断输掉（我就应该下国际象棋，正经人谁下中国象棋啊话说军棋，五子棋和围棋好像都没有马，国际象棋最多20只马？？？
输到怀疑人生，然后看了20mins道德经和《庄子》，心态突然协调气不喘了，腿不酸了，一口气能爬8层楼但是道德经里好多生僻字啊，还是《庄子》好，文言文和白话文一样好看
下午
讲的都是毒瘤题，T4的数据八成是出题人用阴寿出的，不然怎么是阴间题？
最大流+黑白染色+语文七级考试=玩毛线
不过有一说一，我这些题改的贼快，已经改完了
晚饭的时候邀请绑架初一党去闲逛刷街，结果……
wj：你不会再迷路吧？
我：所以才叫你们啊
wj：你迟早把我们带迷路……
emmmmm……
不过我没迷路嘿嘿嘿
目前刷街进度：20%->60%
晚上
写题解和游记，预估写完了还能A几道题
T1
这边发现这个范围在开快读等卡常方法下是可以在O(nm)内AC的个人数据自测可A，如若不行，和本人无任何关系
保证在GMOJ可过
所以放暴力啦
其实就是对新增节点暴力跳啊
code:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int n=4,m,a[333000],c[333000],b[333000],wj[333000],fa[333000],ans=3;
inline int read()
{
int ret,c,f=1;
while (((c=getchar())> '9'||c< '0')&&c!='-');
if (c=='-') f=-1,ret=0;
else ret=c-'0';
while ((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
return ret*f;
}
int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
m=read();
a[1]=b[1]=c[1]=1;
fa[2]=fa[3]=fa[4]=1;
wj[2]=1,wj[3]=2,wj[4]=3;
while (m--)
{
int x=read();
fa[n+1]=fa[n+2]=x;
a[x]=b[x]=1;
wj[n+1]=1,wj[n+2]=2;
while (fa[x]!=1)
{
if (wj[x]==1) a[fa[x]]=max(a[fa[x]],max(a[x],b[x])+1);
if (wj[x]==2) b[fa[x]]=max(b[fa[x]],max(a[x],b[x])+1);
x=fa[x];
ans=max(ans,b[x]+a[x]);
}
if (wj[x]==1) a[fa[x]]=max(a[fa[x]],max(a[x],b[x])+1);
if (wj[x]==2) b[fa[x]]=max(b[fa[x]],max(a[x],b[x])+1);
if (wj[x]==3) c[fa[x]]=max(c[fa[x]],max(a[x],b[x])+1);
x=1;
ans=max(max(ans,b[x]+c[x]),max(a[x]+b[x],a[x]+c[x]));
printf("%d\n",ans);
n+=2;
}
return 0;
}
T2
感谢whx老师提前教了这题半个结论
问题可划分成多个子问题，即第i个已知点（高
h
i
h_i
hi，位置为
w
i
w_i
wi）到第i+1个已知点的方案数，最后乘起来即可
抽象子问题得：从(
i
,
h
i
i,h_i
i,hi)点开始，不击穿x轴，到达(
i
+
1
,
h
i
+
1
i+1,h_{i+1}
i+1,hi+1)的方案数
(x,y)可到(x+1,y+1),(x+1,y),(x+1,y-1)
dp+卡常可AC
但这里讲数学方法，时间复杂度最坏是O（n*玄学）……
但非常非常快！！！
单个子问题公式为(设
∣
h
i
−
h
i
+
1
∣
=
m
,
w
i
+
1
−
w
i
=
n
|h_i-h_{i+1}|=m,w_{i+1}-w_i=n
∣hi−hi+1∣=m,wi+1−wi=n)：
∑
k
=
0
n
−
m
(
(
n
−
k
+
m
)
m
o
d
2
+
1
)
m
o
d
2
∗
C
(
n
,
k
)
∗
(
C
(
n
−
k
,
n
−
k
+
m
2
)
−
C
(
n
−
k
,
n
−
k
+
h
i
+
h
i
+
1
+
2
2
)
)
\sum_{k=0}^{n-m}((n-k+m)\bmod2+1)\bmod2*C(n,k)*(C(n-k,{n-k+m\over2})-C(n-k,{n-k+h_i+h_{i+1}+2\over2}))
k=0∑n−m((n−k+m)mod2+1)mod2∗C(n,k)∗(C(n−k,2n−k+m)−C(n−k,2n−k+hi+hi+1+2))是不是又长又臭？？
解释一下，n是总步数，m是需要上升多少，k是在枚举(x+1,y)走的步数，C(n,k)即n步选k步的方案数。
显然若
(
n
−
k
+
m
)
m
o
d
2
=
1
(n-k+m)\bmod2=1
(n−k+m)mod2=1是走不到的，而走得到的要考虑合不合法。
合法总数=全部的-不合法的
我们可以发现，在剩下的n-k步中，一定有(n-k-m)/2步向下走，所以我们在剩下n-k步中选这么多步向下即全部的方案数
接下来我们转化一下条件：
不击穿x轴意味着不触碰y=-1的直线
那么对于每一个不合法的走法，我们把第一次触碰y=-1的直线后的点以后的走法统统翻下来（建议看图理解），容易证明所有不合法的走法翻折后一定汇于一点（留作习题，可感性理解），且其与不合法方案是双射关系，即一一对应的关系，不重复不遗漏。
所以不合法方案数=到这个新点的方案数，即
C
(
n
−
k
,
n
−
k
+
h
i
+
h
i
+
1
+
2
2
)
C(n-k,{n-k+h_i+h_{i+1}+2\over2})
C(n−k,2n−k+hi+hi+1+2)
code:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
long long n,myd=1000000007,fst[40002],e[40002],o[40002],lst=1;
long long ins[40002];
long long ksm(long long x,int y)
{
long long ans=1;
while (y)
{
if (y&1) ans=ans*x%myd;
x=x*x%myd;
y>>=1;
}
return ans;
}
long long inv(long long x)
{
return ksm(x,1000000005);
}
long long Del(long long x,long long y)
{
return x<y?(x-y+myd)%myd:x-y;
}
long long C(long long x,long long y)
{
if (y>x) return 0;
return fst[x]%myd*ins[y]%myd*ins[x-y]%myd;
}
int main()
{
freopen("brick.in","r",stdin);
freopen("brick.out","w",stdout);
scanf("%lld",&n);
lst=1;
fst[0]=1;
ins[0]=inv(1)%myd;
for (long long i=1;i<=2*n;i++)
{
fst[i]=fst[i-1]*i%myd;
ins[i]=inv(fst[i])%myd;
}
for (long long i=1;i<=n;i++)
{
scanf("%lld",&e[i]);
}
if (e[1]>0||e[n]>0)
{
cout<<0;
fclose(stdin);
fclose(stdout);
return 0;
}
e[1]=e[n]=0;
o[1]=1;
for (int i=2;i<=n;i++)
{
if (e[i]<0) continue;
int wj=abs(e[i]-e[lst]);
for (int j=0;j<=i-lst-wj;j++)
{
int kyx=(i-j-lst);
if ((kyx+wj)%2==0)
{
o[i]+=Del(C(kyx,(kyx+wj)>>1),C(kyx,(kyx+e[i]+e[lst]+2)>>1))*C(i-lst,j)%myd;
o[i]%=myd;
}
}
o[i]=o[i]*o[lst]%myd;
lst=i;
}
cout<<o[n];
fclose(stdin);
fclose(stdout);
return 0;
}
//这题还挺短的，同时我出过一个弱化版
T3
二分答案+dp
dp的是前i个人在做j个1号子任务时还可做几个2号任务
方程见代码得了
code:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int x[101][101],n,m,a[101][2];
int max(int x,int y)
{
return x>y?x:y;
}
bool check(int mid)
{
memset(x,-0x3f,sizeof(x));
x[0][0]=0;
for (int k=1;k<=n;k++)
{
for (int j=0;j<=m;j++)
{
for (int i=0;i<=j&&mid>=i*a[k][0];i++)
{
x[k][j]=max(x[k-1][j-i]+(mid-i*a[k][0])/a[k][1],x[k][j]);
}
}
}
return x[n][m]>=m;
}
int main()
{
freopen("company.in","r",stdin);
freopen("company.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d%d",&a[i][0],&a[i][1]);
int l=0,ans,r=100000,mid;
while (l<=r)
{
mid=l+r>>1;
if (check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
T4
首先语文七级考试得可以黑白染色，会得到二分图
接下来就是一个最小割
由著名最小割最大瘤定理，得阴间网络流求最大流
为了保证点数最大，需要这样建边（我们预设二分图左边为
D
1
D_1
D1集合，右边
D
2
D_2
D2集合，INF>inf，inf>所有点权，而且2个都是大很多）：
S连所有
D
1
D_1
D1的点,T连所有
D
2
D_2
D2的点，边权为inf+该点点权
所有原图边设成
D
1
D_1
D1->
D
2
D_2
D2的形式，并连边，边权INF
然后残量网络求方案
code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
long long n,m,s,t,tot=2,tot2=2,head[4101],head2[4101],dep[4101],l,r,u[4101],r2,wj[4101];
long long w,ans,x[90001],y[90001];
bool vis[4101],myd[4101];
long long mn(long long x,long long y)
{
return (x>y?y:x);
}
struct f{
long long to,net;
long long w;
} a[100011],a2[100011];
void add(long long x,long long y,long long w)
{
a[tot].to=y,a[tot].w=w,a[tot].net=head[x],head[x]=tot++;
return;
}
void add2(long long x,long long y)
{
a2[tot2].to=y,a2[tot2].net=head2[x],head2[x]=tot2++;
return;
}
bool bfs()
{
memset(dep,0,sizeof(dep));
l=0,r=0;
u[r++]=s;
dep[s]=1;
while (l<r)
{
r2=r;
for (long long i=l;i<r;i++)
{
for (long long j=head[u[i]];j;j=a[j].net)
{
if (a[j].w!=0&&dep[a[j].to]==0)
{
u[r2++]=a[j].to;
dep[a[j].to]=dep[u[i]]+1;
}
}
}
l=r,r=r2;
}
return dep[t];
}
long long dfs(long long d,long long in)
{
if (d==t)
{
return in;
}
long long out=0;
long long uw=dep[d]+1;
for (long long j=head[d];j&∈j=a[j].net)
{
if (a[j].w==0||dep[a[j].to]!=uw) continue;
long long s=dfs(a[j].to,mn(in,a[j].w));
out+=s,in-=s;
a[j].w-=s,a[j^1].w+=s;
}
if (out==0)
{
dep[d]=0;
}
return out;
}
void dft(int x,int fa,int wjj)
{
if (vis[x]) return;
vis[x]=1;
if (wjj==1)
{
add(s,x,wj[x]+1e9),add(x,s,0);
}
else
{
myd[x]=1;
add(x,t,wj[x]+1e9),add(t,x,0);
}
for (int i=head2[x];i;i=a2[i].net)
{
if (a2[i].to!=fa) dft(a2[i].to,x,wjj^1);
}
return;
}
void gjy(int x)
{
vis[x]=1;
for (int i=head[x];i;i=a[i].net)
{
if (!vis[a[i].to]&&a[i].w>0) gjy(a[i].to);
}
return;
}
int main()
{
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
scanf("%d%d",&n,&m);
t=n+1,s=t+1;
for (int i=1;i<=n;i++) scanf("%d",&wj[i]);
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
add2(x[i],y[i]),add2(y[i],x[i]);
}
for (int i=1;i<=n;i++) dft(i,0,1);
for (int i=1;i<=m;i++)
{
if (myd[x[i]]) swap(x[i],y[i]);
add(x[i],y[i],1e15),add(y[i],x[i],0);
}
memset(vis,0,sizeof(vis));
while (bfs())
{
ans+=dfs(s,1e20);
}
gjy(s);
int we=0,we2=0;
for (int i=1;i<=n;i++) if (myd[i]^vis[i]) we++,we2+=wj[i];
cout<<we<<' '<<we2<<endl;
for (int i=1;i<=n;i++) printf("%d",myd[i]^vis[i]);
fclose(stdin);
fclose(stdout);
return 0;
}