Postal Vans

题目大意

4*n的网格，要经过所有点的有向有环，不重复经过点的路径总数

n<=1000

题解

显然插头dp

以4为切面

问题是，会发现超精度

解决呢要么实现高精度，要么换python XD

c++实现未+高精度，会爆掉

#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 = "vans";

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

int n;

const int S1001 = 0;
const int S1122 = 1;
const int S1100 = 2;
const int S0110 = 3;
const int S0011 = 4;
const int S1221 = 5;
const int S0000 = 6;

long long dp[1010][10];
int s2[10][10];

void init(){
  s2[S1001][S0000] = 1;
  s2[S1001][S1100] = 1;
  s2[S1001][S0110] = 1;
  s2[S1001][S0011] = 1;
  s2[S1001][S1221] = 1;

  s2[S1122][S1001] = 1;
  s2[S1122][S1122] = 1;
  // s2[S1122][S1100] = 1; 不应该自闭
  // s2[S1122][S0011] = 1; 不应该自闭
  // s2[S1122][S0000] = 1; 不应该自闭

  s2[S1100][S1122] = 1;
  s2[S1100][S1001] = 1;

  s2[S0110][S1001] = 1;

  s2[S0011][S1122] = 1;
  s2[S0011][S1001] = 1;

  // s2[S1221][S1001] = 1; 不应该自闭
  s2[S1221][S0000] = 1;
  s2[S1221][S1100] = 1;
  s2[S1221][S0011] = 1;
  s2[S1221][S1221] = 1;
}

int main(){
  usefile();
  init();
  cin>>n;

  dp[0][S1001] = 1;
  dp[0][S1122] = 1;
  rep(i,1,n){
    rep(stateS,0,6){
      rep(stateE,0,7){
        if(s2[stateS][stateE]){
          dp[i][stateE]+=dp[i-1][stateS];
        }
      }
    }
  }
  // rep(i,0,n){
  //   rep(state,0,7){
  //     cout<<dp[i][state]<<"\t";
  //   }
  //   cout<<endl;
  // }
  cout<<dp[n-1][S0000]*2<<endl;
  return 0;
}

增加高精度

#include <bits/stdc++.h>
typedef long long ll;
#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--)
#define pb push_back


using namespace std;

const string filename = "vans";

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

class hpa{
  int DIGITS = 100'000'000; // 08lld
  vector<ll>vals;
public:
  hpa(){
  }
  hpa(ll v){
    vals.pb(v);
  }
  void print(){
    if(vals.size() == 0){
      printf("0");
      return;
    }
    printf("%lld",vals[vals.size()-1]);
    per(i,0,vals.size()-1){
      printf("%08lld",vals[i]);
    }
  }
  hpa operator +(const hpa &another) const {
    hpa ret;
    rep(i,0,vals.size()){
      ret.vals.pb(vals[i]);
    }
    rep(i,0,another.vals.size()){
      if(i >= ret.vals.size()){
        ret.vals.pb(another.vals[i]);
      }else{
        ret.vals[i]+=another.vals[i];
        if(ret.vals[i] >= DIGITS){
          if(i == ret.vals.size()-1){
            ret.vals.pb(0);
          }
          ret.vals[i+1]+=ret.vals[i]/DIGITS;
          ret.vals[i]%=DIGITS;
        }
      }
    }
    return ret;
  }
};

int n;

const int S1001 = 0;
const int S1122 = 1;
const int S1100 = 2;
const int S0110 = 3;
const int S0011 = 4;
const int S1221 = 5;
const int S0000 = 6;

hpa dp[1010][10];
int s2[10][10];

void init(){
  s2[S1001][S0000] = 1;
  s2[S1001][S1100] = 1;
  s2[S1001][S0110] = 1;
  s2[S1001][S0011] = 1;
  s2[S1001][S1221] = 1;

  s2[S1122][S1001] = 1;
  s2[S1122][S1122] = 1;
  // s2[S1122][S1100] = 1; 不应该自闭
  // s2[S1122][S0011] = 1; 不应该自闭
  // s2[S1122][S0000] = 1; 不应该自闭

  s2[S1100][S1122] = 1;
  s2[S1100][S1001] = 1;

  s2[S0110][S1001] = 1;

  s2[S0011][S1122] = 1;
  s2[S0011][S1001] = 1;

  // s2[S1221][S1001] = 1; 不应该自闭
  s2[S1221][S0000] = 1;
  s2[S1221][S1100] = 1;
  s2[S1221][S0011] = 1;
  s2[S1221][S1221] = 1;
}

int main(){
  usefile();
  init();
  cin>>n;

  dp[0][S1001] = 2;
  dp[0][S1122] = 2;
  rep(i,1,n){
    rep(stateS,0,6){
      rep(stateE,0,7){
        if(s2[stateS][stateE]){
          dp[i][stateE]=(dp[i][stateE]+dp[i-1][stateS]);
        }
      }
    }
  }
  // rep(i,0,n){
  //   rep(state,0,7){
  //     cout<<dp[i][state]<<"\t";
  //   }
  //   cout<<endl;
  // }
  dp[n-1][S0000].print();
  printf("\n");
  return 0;
}

A Rectangular Barn

Mircea Pasoi -- 2003

题目大意

(<=3000)*(<=3000)的矩阵

上面有<=30000 个坏点

求最大不含坏点的矩形面积

题解

因为求的是最大矩形，那么它的四周要么是边界，要么是坏点

证明：反证明

如果存在一条边既没有邻接边界，也没有邻接坏点。

那么对该边延伸，可以得到更大的矩形，矛盾

观察到这个性质后

我们考虑对任意点(i,j)

以 i0<i,其中(i0,j)为距离(i,j)最远的点且线段(i0->i,j)上无坏点

线(i0->i,j)为高，做横向扩张，找左右两侧的最近的坏点或边界，则有以(i,j)搜寻的矩形面积=(i0->i,j) * 该线段左右扩张的最大宽度

这样找到的矩形一定是合法矩形所以这样找到的矩形面积小于等于最大面积
这样一定能找到最大的矩形，因为我们证明了最大矩形一定邻接着坏点或边界，那么该最大矩形上方边界所对应的坏点，正下方的的点在运算过程会计算到

所以O(3000*3000),以所有点计算出一个矩形，每个矩形计算复杂度为O(1),即可

#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 = "rectbarn";

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

int L[3010],R[3010]; // j列当前线段 左右扩展的可行最远距离
int H[3010]; // j列 当前 的线段长度
bool g[3010][3010];
int n,m,ans;
int main(){
  usefile();
  freopen("rectbarn.in","r",stdin);
  freopen("rectbarn.out","w",stdout);
  int k;
  cin>>n>>m>>k;
  while(k--){
    int i,j;
    scanf("%d%d",&i,&j);
    g[i][j]=1;
  }
  rep(j,0,m+1){
    H[j]=0;
    L[j]=1;
    R[j]=m;
  }
  rep(i,1,n+1){
    // 处理所有 坏点
    rep(j,1,m+1){
      if(g[i][j]){
        H[j]=0;
        L[j]=1;
        R[j]=m;
      }
    }
    // 计算所有 左侧 和 右侧 最远
    int lm = 1;
    rep(j,1,m+1){
      if(!g[i][j]){
        H[j]++;
        L[j]=max(L[j],lm);
      } else{
        lm=j+1;
      }
    }
    int rm = m;
    per(j,1,m+1){
      if(!g[i][j]){
        R[j]=min(R[j],rm);
      }else{
        rm=j-1;
      }
    }
    // 计算面积
    rep(j,1,m+1){
      if(!g[i][j]){
        ans=max(ans,(R[j]-L[j]+1)*H[j]);
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}

Cow XOR

Adrian Vladu -- 2005

题目大意

n(<=100,000)个数,数值范围是[0,2^21 - 1]

求连续子区间的最大xor值，输出最大xor值，区间起始点，区间结束点

如果有多个区间满足最大异或，返回结束点index最小的，如果还有多个，返回长度最短的。

题解

首先

我们证明一下题目描述的结果唯一

如果多个子区间异或值相同，且结束点不同，那么只有唯一可以选

如果两个子区间异或值相同，且结束点相同，那么它们一定起始点不同，所以它们长度不同，只有最短可选

综上，题目描述结果唯一

然后

显然

xor[l->r] = xor[1->l-1]^xor[1->r]

所以我们要找最大值，等于找两个前缀异或的最大值

从高位到低位，对所有前缀建立trie树,再for一遍贪心走trie树,贪心规则有和当前位不同的走不同的路径，否则才走相同,（尽量在高位产生1）

空间 O(n*21),时间O(n*21)

空间节点数

s=0;
for i in range(0,22):
    s+=min(2**i,100000)
print(s)

631071 个，然而我开这么大会炸空间，开500000过的（按道理讲这样空间上看是开得有问题，开小了，不过过了测试）

我在实现过程中是找区间左右端点靠的是 lower_bound二分，多用了空间,

然而，我们发现最优区间必定有一个是其前缀值的最小坐标

所以如果枚举i去寻找其期望的前缀值对应的最小坐标，一定能找到最优值,可以优化

通过的，但空间开得不合理的代码,(我之前还用struct来写，虽然阅读上更好理解，但空间更加不够XD)

#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 = "cowxor";

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

int n;
int a[100010];
int p[100010];
int ns[500010][2];

int nsi=0;

int *root = ns[nsi++];

map<int,vector<int> > pv2idx; // 前缀异或 到 下表

void build(int idx){
  int v = p[idx];
  pv2idx[v].push_back(idx); // ordered
  int * po = root;
  per(i,1,21){
    int bit = !!(v&(1<<i));
    if(!po[bit]){
      po[bit] = nsi++;
    }
    po=ns[po[bit]];
  }
  int bit = !!(v&1);
  po[bit] = v;
}

int query(int idx){
  int v = p[idx];
  int * po = root;
  per(i,1,21){
    int bit = !(v&(1<<i));
    if(!po[bit]){
      po = ns[po[bit^1]];
    }else{
      po = ns[po[bit]];
    }
  }
  int bit = !(v&1);
  return po[bit] == 0?po[bit^1]:po[bit];
}

int ans=-1,ansl,ansr;

void setAns(int v1,int l,int r){
  // cout<<"SETANS:"<<v1<<" l:"<<l<<" r:"<<r<<endl;
  if(l > r){
    swap(l,r);
  }
  if(v1 < ans)return;
  if(v1 > ans){
    ans = v1;
    ansl = l;
    ansr = r;
    return ;
  }
  if(r < ansr){
    ansl = l;
    ansr = r;
    return ;
  }
  if(r > ansr){
    return ;
  }
  if(l > ansl){
    ansl = l;
    return ;
  }
}

int main(){
  usefile();
  scanf("%d",&n);
  rep(i,0,n){
    scanf("%d",a+i);
  }
  rep(i,0,n){
    p[i+1]=p[i]^a[i];
  }
  rep(i,0,n+1){
    build(i);
  }
  // for(auto item:pv2idx){
  //   cout<<"--------"<<item.first<<endl;
  //   for(auto z:item.second){
  //     cout<<z<<"\t"<<endl;
  //   }
  //   cout<<endl;
  // }
  rep(i,0,n+1){
    int ret = query(i);
    int reti = lower_bound(pv2idx[ret].begin(),pv2idx[ret].end(),i)-pv2idx[ret].begin();
    // cout<<"find:"<<i<<"["<<p[i]<<"]:"<<ret<<"("<<pv2idx[ret][reti]<<")"<<endl;
    if(ret == p[i]){
      if(i > 0){
        setAns(ret^p[i],i-1,i);
      }
    }else if(reti > 0){
      setAns(ret^p[i],i,pv2idx[ret][reti-1]);
    }else{
      setAns(ret^p[i],i,pv2idx[ret][reti]);
    }
  }
  printf("%d %d %d\n",ans,ansl+1,ansr);
  return 0;
}

USACO 6.1 章节

Postal Vans

题目大意

题解

A Rectangular Barn

题目大意

题解

Cow XOR

题目大意

题解