日常爆炸，考得一次比一次差XD
可能还是被身体拖慢了学习的进度吧，虽然按理来说没有影响。大家听的我也听过，大家学的我也没有缺勤多少次。
那么果然还是能力问题吗……？
虽然不愿意承认，但显然就是这样。对于多次考试来说，身体原因状态原因都是一时的理由，而肉眼可见的下滑不能用这些去掩饰。
今天还有考试，让我看看我是不是到此为止。
T1建设城市：
一眼组合数学插板法+容斥，抓起笔写了写式子，插板法没有难度，容斥就emmmm。
没写过容斥的题…也没有自己推过式子…
再看一眼数据范围看看能拿多少部分分，想到一个DP。其实会想到很正常，因为之前考过一次类似的题目，那道题的解法就有DP和容斥两种。但是数据范围不一样，这边只适合容斥。
考场上我没想起来那道题，但是很容易推出来DP，写了个搜索当对拍，码完就滚蛋了。
考完试就在摸鱼【老毛病】，然后最后十分钟盯着DP突然垂死病中惊坐起想到前缀和可以把一部分内容优化掉，然后试图码出来。当时那道题其实也有前缀和这个过程。然后再次暴露了我码力不足的问题，前缀和打炸了，40分封顶。
正解是很简单的容斥【但我没推出来】。首先是把所有情况算出来，插板法可得C(m-1,n-1)。然后减去一个城市拿多了，先把整个m减去k，之后再给这个城市强行加上，就是C(m-k-1,n-1)，然后可以任选每个城市取多，所以再乘上一个C(n,1)。但是这样会减多，保证一个城市拿多，其他城市可能在分的时候也会多，例如两个城市拿多的情况可能就被重复算了好几次。于是再加上两个城市拿多的情况，C(m-2&k-1,n-1)*C(n,2)。然后一直容斥下去…边界是m-i*k-1>n-1。
预处理一下阶乘和逆元。对于n>m的情况，一定无法满足每个城市至少拿一个，判断一下输出0就好了。我忘了这个…差点以为阶乘逆元要处理到109…
#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,k;
const long long mod=;
long long rec[],inv[],ans;
long long ks(long long x,long long k){
long long num=;
while(k){
if(k&){
num=num*x%mod;
}
x=x*x%mod;
k>>=;
}
return num;
}
long long C(int n,int m){
return rec[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&k);
if(n>m){
printf("0\n");
return ;
}
rec[]=inv[]=rec[]=;
for(int i=;i<=m;i++){
rec[i]=rec[i-]*i%mod;
}
inv[m]=ks(rec[m],mod-);
for(int i=m-;i>=;i--){
inv[i]=inv[i+]*(i+)%mod;
}
ans=C(m-,n-);
for(int i=;m-i*k>=n&&i<=n;i++){
if(i&)ans=(ans-(C(m-i*k-,n-)*C(n,i)%mod)+mod)%mod;
else ans=(ans+(C(m-i*k-,n-)*C(n,i)%mod)%mod)%mod;
}
printf("%lld\n",ans);
return ;
}
不要摸鱼，不要摸鱼，不要摸鱼！提醒今天的我也提醒未来的我以及所有能看到的人。不要太早对自己丧失信心…不要放弃思考。
要对自己有信心啊墨雨笙！！！【啊这话说出来自己都觉得无力】
T2轰炸行动：
这是一道语文神题，至少一半的人都看错了题。限制是连通性而不是相邻边。
而我就更睿智了，我是错误看题的错解，我二分图染色…
实际上就按错的理解，也不可能是二分图染色。只要完全图就必爆炸。完全没想到呢我大约五行缺脑？
正解是tarjan板子。首先对于一条链上的点，一定要一个一个炸，所以最优解一定大于等于最长链的长度。然后对于其它短链，都可以和最长链平行操作。所以答案就是最长链长度。
scc缩点记一个tarjan，然后拓扑记最大可能链长，输出就好了。比较的时候是f[y]与f[x]+siz[y]比较，因为f[y]可能已经被别的入边传来的答案更新过了，而siz[y]才是一开始的初值。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,ans,f[];
int ver[],Next[],head[],tot,tim,vis[];
int dfn[],low[],cnt,c[],siz[],stack[],st;
int du[],ver1[],Next1[],head1[],tot1;
queue<int>q;
void add(int x,int y){
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
void add1(int x,int y){
ver1[++tot1]=y;
Next1[tot1]=head1[x];
head1[x]=tot1;
}
void tarjan(int x){
low[x]=dfn[x]=++tim;
stack[++st]=x;
vis[x]=;
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(vis[y])low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
int p;
cnt++;
do{
p=stack[st--];
vis[p]=;
c[p]=cnt;
siz[cnt]++;
}while(p!=x);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=;i<=n;i++){
for(int j=head[i];j;j=Next[j]){
int y=ver[j];
if(c[i]!=c[y]){
add1(c[i],c[y]);
du[c[y]]++;
}
}
}
for(int i=;i<=cnt;i++){
if(!du[i]){
q.push(i);
ans=max(ans,siz[i]);
}
f[i]=siz[i];
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head1[u];i;i=Next1[i]){
int y=ver1[i];
f[y]=max(f[y],f[u]+siz[y]);
ans=max(ans,f[y]);
du[y]--;
if(!du[y])q.push(y);
}
}
printf("%d",ans);
return ;
}
仔细审题至少三遍！第三题的坑点都看出来了，第二题死得这么惨烈……
T3石头剪刀布：
这个之后好好写一下，现在没时间了，先丢代码。
考完模拟测试16回来填坑，但是已经忘得差不多了…其实也没太理解
神仙DP题。
思路大概是，先算出一个不用考虑当前对手是谁的每种情况下的概率，然后转移总的方案概率，最后按期望来算答案。
设g[i][j][k][l]表示第i个人，之前已经出了j个石头，k个剪刀，l个布的概率。这个很好转移，枚举每一个人，用每个人的概率转移每一种情况的概率，最后出来的会是每种情况下总体的概率，不用考虑针对的是哪一个人。
然后设f[i][j][k][u]表示已经出了i个石头，j个剪刀，k个布，下一轮要出u的概率。f的转移有两个途径，一个是假设有一个人插入了队列当中成为之前计算的对手，这个时候f可以由下一轮出的u相同的，ijk任意一个少1的f转移过来。而另一个途径是他排在队列后面，那么由g转移过来就好了。
std利用f和g的转移有相似之处，把f的u维中123当成石剪布，0当成g…f和g同时处理灵魂压行，学不来也不好理解，于是我跟着gls把g拆开来处理，先处理g再处理f。
神仙DP…现在也不是很理解，之后再回来瞅瞅吧orz
#include<iostream>
#include<cstdio>
using namespace std;
int n;
double a[],b[],c[],tol[][],f[][][][],g[][][][],ans;
double C[][];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%lf%lf%lf",&a[i],&c[i],&b[i]);
tol[i][]=a[i]/300.0;
tol[i][]=b[i]/300.0;
tol[i][]=c[i]/300.0;
}
for(int i=;i<=;i++){
C[i][]=;
for(int j=;j<=i;j++){
C[i][j]=C[i-][j-]+C[i-][j];
}
}
g[][][][]=;
for(int i=;i<=n;i++){
for(int j=i;j>=;j--){
for(int k=i-j;k>=;k--){
for(int l=i-j-k;l>=;l--){
g[i][j][k][l]=g[i-][j][k][l];
if(j)g[i][j][k][l]+=g[i-][j-][k][l]*tol[i][];
if(k)g[i][j][k][l]+=g[i-][j][k-][l]*tol[i][];
if(l)g[i][j][k][l]+=g[i-][j][k][l-]*tol[i][];
}
}
}
}
for(int i=;i<=n;i++){
for(int j=i;j>=;j--){
for(int k=i-j;k>=;k--){
for(int l=i-j-k;l>=;l--){
if(j){
f[j][k][l][]+=f[j-][k][l][]*tol[i][];
f[j][k][l][]+=f[j-][k][l][]*tol[i][];
f[j][k][l][]+=f[j-][k][l][]*tol[i][];
}
if(k){
f[j][k][l][]+=f[j][k-][l][]*tol[i][];
f[j][k][l][]+=f[j][k-][l][]*tol[i][];
f[j][k][l][]+=f[j][k-][l][]*tol[i][];
}
if(l){
f[j][k][l][]+=f[j][k][l-][]*tol[i][];
f[j][k][l][]+=f[j][k][l-][]*tol[i][];
f[j][k][l][]+=f[j][k][l-][]*tol[i][];
}
f[j][k][l][]+=g[i-][j][k][l]*tol[i][];
f[j][k][l][]+=g[i-][j][k][l]*tol[i][];
f[j][k][l][]+=g[i-][j][k][l]*tol[i][];
}
}
}
}
for(int j=;j<n;j++){
for(int k=;k+j<n;k++){
for(int l=;l+k+j<n;l++){
ans+=max(f[j][k][l][]+f[j][k][l][]*,max(f[j][k][l][]+f[j][k][l][]*,f[j][k][l][]+f[j][k][l][]*))/(C[n][j+k+l]*(n-j-k-l));
}
}
}
printf("%.12lf",ans);
return ;
}
所以又是日常爆炸的一次考试，暴露问题很多，但是有种这就是我的极限的感觉。
很差，我很糟糕，没什么好说的。
今天的考试…祝诸位和自己RP++，并且希望自己不要放弃…
更完T3回来给自己加油打气
你还没有到此为止。
![[考试反思]0801NOIP模拟测试11](https://www.kunjuke.com/file/css/thumb/2.jpg/280-180.jpg)
