那天打cf前无聊练手
T1.Why Did the Cow Cross the Road
题目大意：N*N的矩阵，从左上角走到右下角，走一步消耗T，每走3步消耗当前所在位置上的权值，求最小消耗
思路：好像很傻逼但我不会做，写BFS写着写着写成SPFA，管他呢，过了就行
#include<cstdio> #include<algorithm> 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 10000000 const 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
http://www.cnblogs.com/ditoly/p/6404238.html
T3.Why Did the Cow Cross the Road III
题目大意：给定长度为2N的序列，1~N各处现过2次，i第一次出现位置记为ai，第二次记为bi，求满足ai<aj<bi<bj的对数。
思路：树状数组维护，从左到右扫一遍，第一次出现就在对应位置加1，第二次出现统计答案并把第一次出现的那个位置减1。
#include<cstdio> #include<iostream> 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<<ans; }
原文：http://www.cnblogs.com/ditoly/p/6404773.html