USACO 5.3 章节

發表於 2019-05-18 更新於 2024-10-23 分類於 USACO Disqus：文章字數： 3.3k 所需閱讀時間 ≈ 11 分鐘

Heuristic Search,IDDFS,离散化,scc,块状矩阵

相关讲解可在USACO上看原文，也可以搜索nocow找到翻译的！ (nocow上有些微翻译是有问题的，如果想看nocow翻译的建议也对着英文看)

以下记录以下自己之前未掌握的一些要点,以及按自己的括号表述的形式来记录。

USACO Section 5.3 启发式搜索

启发式搜索的主要思想是通过评价一个状态有”多好”来改进对于解的搜索.

0<= 可行的估价函数 <= 实际代价

启发式剪枝: 若搜到最小值，已经搜索到的最优值为C，当前的代价为A(从起始状态到这里的实际代价)，启发的期望剩余代价为B（从当前点到目标的估价），如果A+B>C也就是期望总代价比已经搜索的还大，那么剪枝，注意到上面有提到：估价函数是小于等于实际代价，也就意味实际代价>=A+B>C,所以可以剪枝
Best-First Search最佳优先: 深搜中，在子节点访问顺序部分做估价处理，调整搜索顺序，再结合上面的剪枝
A* 可以和第二条相对，看做广搜中加入了顺序估价。

关于估价函数
如果为0，可以看做毫无优化的默认算法。
如果为实际代价，那么就直接可以最快向目标前进。

Milk Measuring - milk4

题意

从P个数中选取任意个数，使得它们的整数倍数的和=Q

如P: 3,3,5,7

Q:16

16=3*2+5*1

目标，1选的数的个数尽量小，2在个数尽量小的时候，字典序最小

1<=Q<=200000

1<=P<=100

1<=每个数<=10000

输出选择的方案

通过不了的题解

emmmm 我为什么一看就是个sort(从大到小)+dp[当前第几个数][和的值]= {最小选取的个数,最后选择的index,选择的个数,倒数第一次选择的index}

空间O(Q*P),时间O(Q*P) 能得到最小的个和方案,

dp时优先个数(目标要求个数)，其次上一次的index(因为sort过且目标要求字典序)，个数用来反向输出方案

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)

using namespace std;

const string filename = "milk4";

void usefile(){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}

tuple<int,int,int,int>dp[110][20010]; // {usecnt+1,lastuseidx,lastusecnt,preidx};
int val[110];
int Q;
int P;

int main(){
  usefile();
  cin>>Q;
  cin>>P;
  rep(i,0,P){
    scanf("%d",val+i);
  }
  sort(val,val+P,greater<int>());
  rep(p,0,P){
    dp[p][0] = {1,-1,0,-1};
  }
  rep(p,0,P){
    if(p>0){
      rep(q,0,Q+1){
        dp[p][q]=dp[p-1][q];
      }
    }
    rep(q,0,Q){
      auto & item = dp[p][q];
      if(get<0>(item) > 0){
        if(q+val[p] > Q)break;
        auto & pre = dp[p][q+val[p]];
        tuple<int,int,int,int> now = {
          get<0>(item)+ (p !=get<1>(item)),
          p,
          (p!=get<1>(item))?1:get<2>(item)+1,
          (p!=get<1>(item))?get<1>(item):get<3>(item)
        };
        if(get<0>(pre) == 0 || get<0>(pre) >= get<0>(now)){
          pre = now;
        }
      }
    }
  }
  // rep(p,0,P){
  //   cout<<"P:"<<p<<endl;
  //   rep(q,0,Q+1){
  //     printf("[%d %d %d %d]",get<0>(dp[p][q]),get<1>(dp[p][q]),get<2>(dp[p][q]),get<3>(dp[p][q]));
  //   }
  //   cout<<endl;
  // }
  auto ans = dp[P-1][Q];
  printf("%d",get<0>(ans)-1);
  int qq = Q;
  while(1){
    printf(" %d",val[get<1>(ans)]);
    qq-= get<2>(ans) * val[get<1>(ans)];
    if(get<3>(ans) == -1){
      break;
    }
    ans = dp[get<3>(ans)][qq];
  }
  printf("\n");
  return 0;
}

然而不幸的是超空间限制了

Execution error: Your program (milk4’) exited with signal #11 (segmentation violation [maybe caused by accessing memory out of bounds, array indexing out of bounds, using a bad pointer (failed open(), failed malloc), or going over the maximum specified memory limit]). The program ran for 0.000 CPU seconds before the signal. It used 31552 KB of memory. `

优化可以优化掉p，在实现记录的时候用指针的方式，没有尝试能不能改过

可通过的解

IDDFS 迭代加深搜索，使用场景，在低的层级找到解就是最优/目标解。

和广搜的区别是，广搜过程中会用内存记录，而迭代加深每次都是深搜，但是逐次增加深度。

可行性：每次加深深度，新的状态和上一层的状态是数量级差异，所以其实只和最后成功搜索到的层数的数量级相关。

综上，IDDFS有着接近广搜的性能，有着接近深搜的空间消耗。

实现pass如下

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)

using namespace std;

const string filename = "milk4";

void usefile(){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}

int vis[20010];
int ans[110];
int val[20010];
int Q;
int P;
int dep;

bool check(){
  rep(i,1,Q+1){
    vis[i]=0;
  }
  rep(i,0,dep){
    rep(j,0,Q+1-ans[i]){
      if(vis[j]){
        vis[j+ans[i]]=true;
      }
    }
  }
  if(vis[Q]){
    return true;
  }
  return false;
}

bool dfs(int idx,int cnt){
  ans[cnt] = val[idx];
  if(cnt+1 == dep){
    return check();
  }
  rep(j,idx+1,P+2+cnt-dep){
    if(dfs(j,cnt+1)){
      return true;
    }
  }
  return false;
}

void output(){
  printf("%d",dep);
  rep(i,0,dep){
    printf(" %d",ans[i]);
  }
  printf("\n");
}

int main(){
  usefile();
  cin>>Q;
  cin>>P;
  rep(i,0,P){
    scanf("%d",val+i);
  }
  sort(val,val+P);
  vis[0]=1;
  for(dep=1;dep<=P;dep++){
    rep(i,0,P+1-dep){
      if(dfs(i,0)){
        output();
        return 0;
      }
    }
  }
  return 0;
}

Window Area - window

题意

在电脑上窗口的操作,5种

新建窗口(标识符，x1,y1,x2,y2)
置顶t(标识符)
置底b(标识符)
删除d(标识符)
输出窗体可见百分比s(I) ,询问数<=500

窗体个数上限(2*26+10=62)

坐标范围[1->32767]

题解

那么显然横纵坐标只有((2×62)^2)个，离线+离散+没了？

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
typedef long long ll;

using namespace std;

const string filename = "window";

void usefile(){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}

list<int>Is[240][240]; // 大小猜的

vector<int>x;
vector<int>y;

vector<tuple<int,int> >q;

int itr = 0;
vector<tuple<int,int,int,int> >xys;

tuple<int,int,int,int> xyxy[123];

void rm(int ix,int iy,char I){
  for (list<int>::iterator it=Is[ix][iy].begin(); it!=Is[ix][iy].end(); ++it){
    if(*it == I){
      Is[ix][iy].erase(it);
      return ;
    }
  }
}

void top(int ix,int iy,char I){
  rm(ix,iy,I);
  Is[ix][iy].push_front(I);
}

void bot(int ix,int iy,char I){
  rm(ix,iy,I);
  Is[ix][iy].push_back(I);
}

int main(){
  usefile();
  char op;
  while(~scanf("%c",&op)){
    if(op!='w' && op!='t' && op!='b' && op!='d' && op!='s')continue;
    if(op == 'w'){
      char I;
      int x1,y1;
      int x2,y2;
      scanf("(%c,%d,%d,%d,%d)",&I,&x1,&y1,&x2,&y2);
      if(x1> x2){
        swap(x1,x2);
      }
      if(y1>y2){
        swap(y1,y2);
      }
      x.push_back(x1);
      x.push_back(x2);
      y.push_back(y1);
      y.push_back(y2);
      q.push_back({op,I});
      xys.push_back({x1,y1,x2,y2});
    }else{
      char I;
      scanf("(%c)",&I);
      q.push_back({op,I});
    }
  }
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  for(auto item:q){
    int op = get<0>(item);
    int I = get<1>(item);
    if(op == 'w'){
      xyxy[I] = xys[itr++];
    }
    int x1idx=lower_bound(x.begin(),x.end(),get<0>(xyxy[I]))-x.begin();
    int y1idx=lower_bound(y.begin(),y.end(),get<1>(xyxy[I]))-y.begin();
    int x2idx=lower_bound(x.begin(),x.end(),get<2>(xyxy[I]))-x.begin();
    int y2idx=lower_bound(y.begin(),y.end(),get<3>(xyxy[I]))-y.begin();
    switch(op){
      case 'w':
        {
          rep(ix,x1idx,x2idx){
            rep(iy,y1idx,y2idx){
              Is[ix][iy].push_front(I);
            }
          }
          break;
        }
      case 't':
        {
          rep(ix,x1idx,x2idx){
            rep(iy,y1idx,y2idx){
              top(ix,iy,I);
            }
          }
          break;
        }
      case 'b':
        {
          rep(ix,x1idx,x2idx){
            rep(iy,y1idx,y2idx){
              bot(ix,iy,I);
            }
          }
          break;
        }
      case 'd':
        {
          rep(ix,x1idx,x2idx){
            rep(iy,y1idx,y2idx){
              rm(ix,iy,I);
            }
          }
          break;
        }
      case 's':
        {
          ll sshow = 0;
          rep(ix,x1idx,x2idx){
            rep(iy,y1idx,y2idx){
              sshow+= ((*Is[ix][iy].begin() == I)?(x[ix+1]-x[ix])*ll(y[iy+1]-y[iy]):0);
            }
          }
          ll scnt = (x[x2idx]-x[x1idx])*ll(y[y2idx]-y[y1idx]);
          printf("%.3lf\n",sshow*100/double(scnt));
          break;
        }
    }
  }
  return 0;
}

emmmmmm 在第11个点的时候出现了唯一标识复用的情况，也就是说先创建再删除再创建，所以期望的边数也就不只 (26*2+10)*2，我这里尝试的是开到240*240才能过

所以基本上是离散化 O(长乘宽(分化的区块个数)*62(每次操作代价)*(t+b+r操作个数)+长乘宽(分化区块个数)*1(操作代价)*(w+s操作个数))

以上代码还可以优化的地方:

通过预处理真实值到离散值，让每个这样的计算只发生一次。
再建立一个表来优化top,bot,rm到接近O1每次，额外的指针访问时间，缺点是1增加空间，2本身数据不大的情况，枚举查找的效率是不差的

然后有一些博文有两个矩形之间处理的优化，也就是不分成9块，而是分成最多5块，类似旋图，然后平时只记录相对的层数(z-index)，然后在查询的时候，才自值开始向上查找。

Network of Schools - schlnet

题意

有向图,(N<=100)个节点

求最少选取多少个点，通过这些点能够沿着有向边到达所有的点
求最少加多少边，让真个图变成全连通

题解

emmmm一眼

直接求强连通，然后缩点，然后按照出度排序，从0开始删，直到为最后只剩独立点，进行统计？
把这些缩点后的 max(出度为0的点,入度为0的点)

强连通直接tarjan

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)

using namespace std;

const string filename = "schlnet";

void usefile(){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}

int n;

vector<int>p2[110];

const int N=100;


int id = 0;
bool vis[N+10];
int low[N+10];
int dfn[N+10];
vector<int>stk;
bool instk[N+10];

int incnt[N+10];
int outcnt[N+10];

void scc(int idx){
  // cout<<"scc"<<idx<<endl;
  dfn[idx] = low[idx] = ++id;
  vis[idx] = true;
  stk.push_back(idx);
  instk[idx] = true;
  for(auto item:p2[idx]){
    if(!vis[item]){
      scc(item);
      low[idx]=min(low[idx],low[item]);
    }else if(instk[item]){
      low[idx]=min(low[idx],dfn[item]); // dfn->low
    }
  }
  if(low[idx] == dfn[idx]){
    // cout<<"zip:"<<idx<<endl;
    // for(auto item:stk){
    //   printf("\t\tstk[%d]\n",item);
    // }
    int u;
    do{
      u = *(stk.end()-1);
      // cout<<"\tu:"<<u<<endl;
      dfn[u] = idx;
      instk[u] = false;
      stk.pop_back();
    }while(u != idx);
  }
}

void tarjan(){
  rep(i,1,n+1){
    if(!vis[i]){
      scc(i);
    }
  }
  // rep(i,1,n+1){
  //   cout<<"dfn:"<<i<<" = "<<dfn[i]<<endl;
  // }
}

int main(){
  usefile();
  cin>>n;
  rep(i,1,n+1){
    while(1){
      int v;
      scanf("%d",&v);
      if(v == 0)break;
      p2[i].push_back(v);
    }
  }
  tarjan();
  rep(i,1,n+1){
    if(dfn[i]!=i){
      for(auto item:p2[i]){
        p2[dfn[i]].push_back(dfn[item]);
      }
    }else{
      for(auto &item:p2[i]){
        item = dfn[item];
      }
    }
  }
  rep(i,1,n+1){
    if(dfn[i] == i){
      sort(p2[i].begin(),p2[i].end());
      p2[i].erase(unique(p2[i].begin(),p2[i].end()),p2[i].end());
      for(auto item:p2[i]){
        if(item == i)continue;
        // printf("%d -> %d\n",i,item);
        incnt[item]++;
        outcnt[i]++;
      }
    }
  }
  int in0cnt=0,out0cnt=0;
  rep(i,1,n+1){
    if(dfn[i] == i){
      in0cnt+=incnt[i] == 0;
      out0cnt+=outcnt[i] == 0;
    }
  }
  printf("%d\n",in0cnt);
  // single check
  int pcnt = 0;
  rep(i,1,n+1){
    pcnt+=dfn[i]==i;
  }
  if(pcnt == 1){
    printf("0\n");
  }else{
    printf("%d\n",max(in0cnt,out0cnt));
  }
  return 0;
}

Big Barn - bigbrn

题意

NxN(N<=1000)矩阵A点上值有0或1

1的个数<=10000

求最大的全0正方形(不能斜着)

输出边长即可

题解

这感觉二分答案？因为二分的话如果大的可行，那么小的必定可行

又必定正方形的左侧和上侧都有点（边界看做全是点）

假设存在一个最优解左侧没有相邻点，则可以向左平移直到有点，对上侧同理。

emm 这样想下去，暂时没想到一个时间复杂度内能完成的解法，再看又像是二维线段树,跟着2维线段树的思路联想到前缀和的类似的矩阵处理

假设当前测试的长度为len

那么用B[i][j]表示 A[i->i+len-1][j]为1的个数

C[i][j]表示A[i->i+len-1][j->j+len-1]为1的个数,即是C[i][j->j+len-1]

根据前缀和类似的算法，A->B可以在O(N^2)完成B->C也同理,综上O(N^2*log(N))

然而很不幸的是 usaco给的空间是真的有限，就算换成 new 也会在第11个点挂掉,所以bit压位,然而事后发现，可以不用存储C，直接判断C的值就好了，从空间O(3N^2)变为O(2N^2)就能过

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)

using namespace std;

const string filename = "bigbrn";

void usefile(){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}

int n,t;

// bitset<8> A[1010][130];// [1010][1010]; // N*N
// bitset<8> B[1010][130];// [1010][1010]; // (N+1-len)*N
// //bitset<8> C[1010][130];// [1010][1010]; // (N+1-len)*(N+1-len)

// 如果注释掉下面两行用 上面bitset的A和B也能过
int A[1010][1010];
int B[1010][1010];

void setv(bitset<8> *arr,int idx,int v){
  arr[idx/8].set(idx%8,bool(v));
}

int getv(bitset<8> *arr,int idx){
  return arr[idx/8][idx%8];
}

void setv(int *arr,int idx,int v){
  arr[idx]=v;
}

int getv(int *arr,int idx){
  return arr[idx];
}

bool ok(int len){
  if(len == 0)return true;
  // A->B
  rep(j,0,n){
    int cnt = 0;
    rep(i,0,len){
      cnt+=getv(A[i],j);
    }
    setv(B[0],j,cnt);
    rep(i,1,n+1-len){
      cnt+=getv(A[i+len-1],j)-getv(A[i-1],j);
      setv(B[i],j,cnt);
    }
  }
  // B->C
  rep(i,0,n+1-len){
    int cnt= 0;
    rep(j,0,len)
      cnt+=getv(B[i],j);
    if(cnt == 0)return true;
    rep(j,1,n+1-len){
      cnt+=getv(B[i],j+len-1)-getv(B[i],j-1);
      if(cnt == 0)return true;
    }
  }
  return false;
}

bool all1(){
  rep(i,0,n){
    rep(j,0,n){
      if(A[i][j] == 0){
        return false;
      }
    }
  }
  return true;
}

int main(){
  usefile();
  cin>>n>>t;
  rep(i,0,t){
    int x,y;
    scanf("%d %d",&x,&y);
    setv(A[x-1],y-1,1);
  }

  int lenl=0,lenr=n+1;
  while(lenl+1<lenr){
    int mid=(lenl+lenr)/2;
    if(ok(mid)){
      lenl=mid;
    }else{
      lenr=mid;
    }
  }
  cout<<lenl<<endl;

  return 0;
}

总结

emmmmm所以这些题目和标题的启发式搜索的关系是?

Codeforces Round 554

發表於 2019-04-30 更新於 2024-10-23 分類於 Codeforces ， Div2 Disqus：文章字數： 710 所需閱讀時間 ≈ 2 分鐘

D (最值可达入门)

D原题

才2000分我自闭了

n(1<=n<=1000)个左括号和n个右括号组成合法括号序列

把所有合法序列来建立一个trie树

求问，给树的边上色或不上色，要求任意两个上色边不能共点，求最大上色边数

结果MOD 1e9+7

题解

首先我想到树上dp，f[当前配对数量][剩余左括号数量][是否染色边]

有关系

f[i][j][0] = max(
     f[i][j+1][1]+f[i+1][j-1][0],
     f[i][j+1][0]+f[i+1][j-1][1],
     );
f[i][j][1] =
     f[i][j+1][0]+f[i+1][j-1][0]+1;

ll f(ll p,ll l,int pick){
  if(p==n)return pick;
  if(ret[p][l][pick] != 0)return ret[p][l][pick];
  if(l==0){ // 没有剩余左括号了，所以在树上的向下分之一定是左括号
    return ret[p][l][pick]=f(p,l+1,1-pick)+pick; // 偏序关系?
  }
  if(p+l==n){ // 左括号已经达到上限只能用右括号
    return ret[p][l][pick]=f(p+1,l-1,1-pick)+pick;// 偏序关系?
  }
  if(pick == 1){ // 当前选下面则不选
    return ret[p][l][pick]=f(p,l+1,0)+f(p+1,l-1,0)+1;// 偏序关系?
  }else{
    return ret[p][l][pick]=
      max(f(p,l+1,1)+f(p+1,l-1,0),
          f(p,l+1,0)+f(p+1,l-1,1));
  }
}

那么只要访问f(0,1,1),就可以得到答案,然后就遇到了一个问题:最大值和取模运算是冲突的

那么有什么办法可以不用比较直接直到偏序关系?

我没想出来,那么现在一个办法是偏序关系，一个办法是做高精度，还有一个办法是换方法。

来自群友梦月大佬的一句话方法:奇数层节点个数

注:按题目原型来说最初空白节点为0层

注意每次染色一条边，如果去看树上，实际就是奇数层次的点和偶数层次的点被各染色一个，因为不同染色边不能有交点，所以边=奇数层数染色的点=偶数层数染色的点。

下面又有因为是合法对，所以从根节点到叶子节点的点数永远是偶数也就意味着每一个奇数层数的点下方一定有至少一个节点(在偶数层数)

所以边<= min(奇数层数总节点数，偶数层数总结点数) =奇数层数总结点数

下面看可达性，同上述，每个奇数节点选一个下方的偶数节点染色边，即可，保证了不会共点，又达到了奇数层数的总节点数。

综上我们找到了一个方案达到上限，那么这个上限也就是答案了。

[至于怎么算奇数节点上总个数就无脑dp了,我想没有必要赘述了吧.

Forethought Future Cup - Elimination Round

發表於 2019-04-20 更新於 2024-10-23 分類於 Codeforces ， Div1+2 Disqus：文章字數： 483 所需閱讀時間 ≈ 2 分鐘

D (gcd入门)

D原题

这题分才2100 XD,没想到[a+b]是一个可行上限

大意:

青蛙在长度为i的区间内跳跃，要么向右a,要么向左b. f(i)=能跳到的不同点的个数

输入m(<=1e9),(1<=a<=1e5),(1<=b<=1e5)

求sum{i=0->m,f(i)}

题解

首先，假设在长度为x的时候，足够长，能够通过反复横跳,跳到gcd(a,b)的位置，那么也就意味着[0,x]可以到达gcd(a,b)

从而[gcd(a,b),gcd(a,b)+x] 能跳到2gcd(a,b)

注意到存在 a*n-b*m=gcd(a,b) 其中n和m非负

意味着如果令x=a+b,也就是区间给[0,a+b],

那么保证了任何一个点p，

p+a(向右跳)<=a+b(没有超过右边界)

和

p-b(向左跳)>=0(没有超过左边界)

至少有一个成立

即是说，如果不能向右跳时一定能向左再跳一次，如果不能向左跳一定能向右再跳一次

也意味着，每向右跳一次a的系数增加，且可以在[0,a+b]中系数增加任意次数，从而达到期望的n

对应的在达到n时，任然在区间内，向左跳的次数也就可以取到m，从而在[0,a+b]中一定能跳到gcd(a,b);

同理 a+b明显是gcd(a,b)的倍数，假设k倍

那么 a*(n*k)-b*(m*k)也是可达的，因为保证了b的次数，也就是向左跳的次数可以从0逐个增大到无穷，所以达到m*k时，对应可以让a填充达到a+b。

再同理,如果给定[0,a+b]，那这区间里所有gcd的倍数都可以达到。

因此大于[a+b]的简单计算gcd个数，我们只用关心0到a+b的情况.

显然f(0-a+b)的这部分用dijkstra

Codeforces Round 551

發表於 2019-04-16 更新於 2024-10-23 分類於 Codeforces ， Div2 Disqus：文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘

D树上DP,E 简单二分

D

题目

这题分才1800 XD,卡C卡太久了

给你一个树，树节点个数n<=3e5

有k个叶子k<n

非叶子节点有操作符f,f=0表示取子节点最小值，f=1表示取子节点最大值

你需要把值1到k的放到叶子上，使得根节点得到的结果最大，求这个最大值

题解

dp[节点] = 节点以下的叶子数量-节点以下能达到的最大值，所以dp越小越好

这样答案=k-dp[root]

举例

一个max节点i，如果它的子节点全是叶子，那么dp[i]=0

一个min节点i，如果它的子节点全是叶子，且它有m个子节点，那么dp[i]=m-1

那么更一般的

一个max节点i,dp[i] = min(dp[child])

一个min节点i,`dp[i] = i以下叶子节点总数-max(childi以下叶子节点总数-dp[childi]) 吗 ?

并不,考虑min下两个节点，分别长度，和dp为

leni,dpi 和 lenj,dpj,比如你想 (4,2),(16,8)

那么如果我们选取i为min的取值，那么这两个节点贡献的dp最小为dpi+(dpj+1)

那么如果我们选取j为min的取值，那么这两个节点贡献的dp最小为dpj+(dpi+1)

一个min节点i,`dp[i] = dp[?] + sum 剩余dp + 直接子节点个数-1;

初始化dp[叶子]=0

CODE

code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);

int op[300010];
vector<int>child[300010];
int leafcnt[300010];
int n;
int dfs(int idx){
  if(child[idx].size() == 0){
    leafcnt[idx] = 1;
    return 0;
  }
  if(op[idx] == 1){
    int ret = 300001;
    for(auto item:child[idx]){
      ret=min(ret,dfs(item));
      leafcnt[idx]+=leafcnt[item];
    }
    return ret;
  }else{
    int ret = 0;
    for(auto item:child[idx]){
      ret += dfs(item)+1;
      leafcnt[idx]+=leafcnt[item];
    }
    return ret -1;
  }
}

int main(){
  cin>>n;
  rep(i,0,n){
    scanf("%d",op+i);
  }
  rep(i,1,n){
    int fa;
    scanf("%d",&fa);
    child[fa-1].pb(i);
  }
  int ret = dfs(0);
  printf("%d",leafcnt[0]-ret);
  return 0;
}

E

2100分

交互题

n*n格子 (n<=1000)

里面有一条弯曲的蛇，如果碰到蛇的头和尾则会挂掉

提供一个设备，传入一个矩形，可以返回蛇身体穿过矩形边界的次数

他只能进行2019次询问，需要得到蛇头和尾的坐标。

蛇可以1x1，也就是身体长度为0,头尾在一个格子里

蛇在询问过程中不会动。

题解

显然如果头和尾有且只有一个在矩形,那么返回值为0或奇数

然后就先定行或列，首先如果长度不为0，那么必定不在同一个格子里，所以x和y必定有一个不同，

所以按照1xn的列和行依次尝试一定有2个为奇数返回，再二分对应的行或列

依次尝试O(2*n),二分O(2*log n),注意到只有2019次机会，所以我们需要加一些细节判断(否则会wa23)

我们注意到，如果一共n列，那么前n-1列有一个奇数出现，那么最有一列一定是奇数，如果前面全是偶数，那么最后一列也一定是偶数。行同理，所以可以少掉两个依次尝试

长度为0的，我们无法检测到，无脑输出! 1 1 1 1即可

CODE

CODE LINK

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);

int q(int x1,int y1,int x2,int y2){
  printf("? %d %d %d %d\n",x1,y1,x2,y2);
  fflush(stdout);
  int ret;
  scanf("%d",&ret);
  return ret;
}

void ok(int x1,int y1,int x2,int y2){
  printf("! %d %d %d %d\n",x1,y1,x2,y2);
  fflush(stdout);
}

int main(){
  int n;
  cin>>n;
  int ii0=-1;
  int ii1=-1;
  rep(i,1,n+1){
    if(i == n){
      if(ii0!=-1 && ii1 ==-1){
        ii1=n;
      }
      break;
    }
    int r = q(i,1,i,n);
    if(r%2==1){
      if(ii0 == -1){
        ii0 = i;
      }else if(ii1 == -1){
        ii1 = i;
        break;
      }
    }
  }
  int jj0=-1;
  int jj1=-1;
  if(ii0 == -1){ // samex;
    rep(i,1,n+1){
      if(i == n && jj0!=-1 && jj1 !=-1){
        jj1=n;
        break;
      }
      int r = q(1,i,n,i);
      if(r%2==1){
        if(jj0 == -1){
          jj0 = i;
        }else if(jj1 == -1){
          jj1 = i;
          break;
        }
      }
    }
    // er fen
    int l =1,r=n;
    while(l != r){
      int m=(l+r)/2;
      int ret = q(l,jj0,m,jj0);
      if(ret%2==1){
        r=m;
      }else{
        l=m+1;
      }
    }
    ii0=l;
    l = 1;
    r = n;
    while(l != r){
      int m=(l+r)/2;
      int ret = q(l,jj1,m,jj1);
      if(ret%2==1){
        r=m;
      }else{
        l=m+1;
      }
    }
    ii1=l;
  }else{ // specific i0 & i1
    int l =1,r=n;
    while(l != r){
      int m=(l+r)/2;
      int ret = q(ii0,l,ii0,m);
      if(ret%2==1){
        r=m;
      }else{
        l=m+1;
      }
    }
    jj0 = l;
    l =1;
    r=n;
    while(l != r){
      int m=(l+r)/2;
      int ret = q(ii1,l,ii1,m);
      if(ret%2==1){
        r=m;
      }else{
        l=m+1;
      }
    }
    jj1 = l;
  }
  if(ii0 == -1){
    ok(1,1,1,1);
    return 0;
  }
  ok(ii0,jj0,ii1,jj1);
  return 0;
}

F

这篇文章鸽了这么久买就是因为这道题，我现在还是没有完全理解到，所以可以忽略下面所写TODO,因为下面只写了我能理解到的部分

CF 评分2800

长度l线段

随机取n个子线段,线段端点随机,可以非整数

求被这n条线段覆盖次数>=k的线段期望长度

l<=1e9

n,k<=2000

除法使用乘法逆元,结果模998244353

题解

官方

首先放缩原理,期望与l正相关，所以l就是个倍数，所以只用考虑长度为1的情况.

~~根据实分析~~

贡献累计

考虑这n个线段的2n个端点，分割出的2n+1条线段，

计算每条线段被覆盖至少k次区间的期望数量 *期望长度

首先这2n个点是相互独立的

期望数量 = (>=k)概率

现在假设我们的到了一个已经生成好的点列，我们并不知道它们的连接情况。

f(i,j,0/1 )表示以上点列前i个点中剩余j个点未匹配(线段左端)，满足(>=k覆盖)的段的数量,P点是否出现(0,1)

P在i点的时候,f(i,j,1) = f(i-1,j,0) // j>=k

新的线段i+j+x < 2n, f(i-1,j-1,x)->f(i,j,x)

匹配开始idea线段:f(i-1,j+1,x)*(j+1)->f(i,j,x)

所有的arrangements一共有(2n+1)!条

CF 愚人节赛题目鉴赏

發表於 2019-04-01 更新於 2024-10-23 分類於 Codeforces Disqus：文章字數： 878 所需閱讀時間 ≈ 3 分鐘

题目

A Thanos Sort

没啥讲的，阅读理解，模拟实现

B Kanban Numbers

我的解题过程：搜索kanban->signboard->led number,尝试和led显示相关，未果

你群群友，有暴力枚举过B题的orz

实际解法是标题+英语, kanban number = 'k' 'a' 'n' ban number,也就是英文不含字母k a n的

C Mystery Circuit

量子计算相关(实际没有到量子)

有工具Quirk

4位2进制表示
前后倒序
按工具上面的按钮
前后倒序
再转换为10进制数

3->0011->1100->1011->1101->13

https://en.wikipedia.org/wiki/Quantum_logic_gate

首先十字+圆圈 表示的是一个非门

然后竖着看，黑色的点是控制点，也就是竖着一条线上黑点传入的数据全是1时，非门才工作

这就是工具的运作原理，因为数也只有15个，你可以枚举打表，也可以实现这个控制逻辑

D Pigeon d’Or

我也发现是错误单词了，https://www.grammarcheck.net/editor/ 可以检查拼写错误,但是ai的范围是误导XD..我还在想 1 2 3 4 5的样例数据是怎么解释。

正确的解法是，把错的字母连接起来，变成一个句话,这句话就是一个英文描述的公式,66666

E Fourier Doodles

这是近年的机器学习识数梗

我已经发现的有:前20张图size很大[指文件大小，不是图片尺寸]

正确解法就是标题+压缩包，如题名的傅里叶，把前20个图做傅里叶，然后拼出表达式，即可

请把下面程序放到和图片同目录下，然后运行(自行用pip install安装依赖包)

#!/usr/bin/python2
from PIL import Image
import numpy as np
from scipy import fftpack
import matplotlib.pyplot as plt

if __name__ == '__main__':
    plt.figure(figsize=(5, 5)) # 画布大小
    for i in range(1, 21): # 20张图片
        img = Image.open(str(i) + '.png').convert('L')  # 灰度 多色应该也可以，但是还要加更多处理
        imgout = fftpack.fftshift(fftpack.fft2(img)) # 2维傅里叶
        psd2D = np.log(np.abs(imgout))  # (256,256) 取log
        plt.subplot(4, 5, i) # 把它们依次显示在画布上
        plt.axis('off')
        plt.imshow(psd2D, cmap='Greys_r')
    plt.show()

官方题解给的在线工具 http://www.ejectamenta.com/Imaging-Experiments/fourierimagefiltering.html

F Neat Numbers

嗯。。我去google查了单词，但。。。。 google的翻译并不能成功的帮助我

正确解法是标题+英文单词理解+样例，neat words要的是所有大写字母都是直线段组成的即可AEFHIKLMNTVWXYZ，相对来说其它字母是带有弯的

G AI Takeover

和机器人石头剪刀布，它有6个测试，6种策略，对你是未知的，你需要自行猜测

如果你们出一样的，算机器人赢

机器人不会peeking你的选择（就是理论上同时）

R石头P布S剪刀

你需要的是20场内赢至少10场

题解:关键在于成功的猜到机器人的6种方法

题透: 机器人的方案

全R
全P
全S，
循环R-P-S
从R开始，然后总是扮演人类玩家的最后一步，
从R开始，然后总是发挥击败人类玩家最后一步的动作。

赛内建议的探测方法，用memory allocation ，或者sleep time，也就是可以读到的cf输出，来编码你直接看不到的结果，从而探测，机器人的方案

综上

真好玩+只会签到,题目都有实际的背景，出题不是乱出….总结逐渐开花