那天打cf前无聊练手

 

T1.Why Did the Cow Cross the Road

题目大意：N*N的矩阵，从左上角走到右下角，走一步消耗T，每走3步消耗当前所在位置上的权值，求最小消耗

思路：好像很傻逼但我不会做，写BFS写着写着写成SPFA，管他呢，过了就行（大致就是每个点拆成三个，就能知道什么时候要加上额外的权值）

#include
     
      #include
      
       using namespace std;char B[1<<26],*S=B,C;int X;inline int read(){    while((C=*S++)<'0'||C>'9');    for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=X*10+C-'0';    return X;}#define MN 100#define MQ 10000000const int o[4][2]={
   {
   0,1},{
   0,-1},{
   1,0},{-1,0}};int a[MN+5][MN+5],qx[MQ],qy[MQ],qt[MQ],qn,f[MN+5][MN+5][3];int main(){    freopen("visitfj.in","r",stdin);    freopen("visitfj.out","w",stdout);    fread(B,1,1<<26,stdin);    int n,t,i,j,x,y,p,w;    n=read();t=read();    for(i=1;i<=n;++i)for(j=1;j<=n;++j)a[i][j]=read();    for(f[1][1][0]=qx[0]=qy[0]=1,i=0;i<=qn;++i)for(j=0;j<4;++j)    {        x=qx[i]+o[j][0];y=qy[i]+o[j][1];w=f[qx[i]][qy[i]][qt[i]]+t;        if((p=qt[i]+1)>2)p=0,w+=a[x][y];        if(!x||x>n||!y||y>n)continue;        if(f[x][y][p]&&w>=f[x][y][p])continue;        f[x][y][p]=w;qx[++qn]=x;qy[qn]=y;qt[qn]=p;    }    printf("%d",min(f[n][n][0],min(f[n][n][1],f[n][n][2]))-1);}
      
     

 

T2.Why Did the Cow Cross the Road II

参见我写的铂金组题解T2

 

T3.Why Did the Cow Cross the Road III

题目大意：给定长度为2N的序列，1~N各处现过2次，i第一次出现位置记为ai，第二次记为bi，求满足ai<aj<bi<bj的对数。

思路：树状数组维护，从左到右扫一遍，第一次出现就在对应位置加1，第二次出现统计答案并把第一次出现的那个位置减1。

#include
     
      #include
      
       using namespace std;char B[1<<26],*S=B,C;int X;inline int read(){    while((C=*S++)<'0'||C>'9');    for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0';    return X;}#define MN 100000#define lb(x) (x&-x)int s[MN+5],a[MN+5];void inc(int x,int z){
   for(;x<=MN;x+=lb(x))s[x]+=z;}int sum(int x){
   int r=0;for(;x;x-=lb(x))r+=s[x];return r;}int main(){    freopen("circlecross.in","r",stdin);    freopen("circlecross.out","w",stdout);    fread(B,1,1<<26,stdin);    int n=read()<<1,i,x;long long ans=0;    for(i=1;i<=n;++i)        if(a[x=read()])ans+=sum(i)-sum(a[x]),inc(a[x],-1);        else inc(a[x]=i,1);    cout<