usaco20172月月赛

usaco月赛题很健脑啊。。一直坚持没看题解自己做&＃xff0c;感觉收获很大&＃xff0c;希望自己能坚持下去。。

gold 1

给出一个n*n&＃xff08;输入&＃xff09;表格图&＃xff0c;每个格子上都有一个权值&＃xff08;输入&＃xff09;&＃xff0c;现在从左上角走到右下角&＃xff0c;每走一步需要花费t&＃xff08;输入&＃xff09;的代价&＃xff0c;同时&＃xff0c;每走三步需要花费当前所在格子权值的代价&＃xff0c;求最小代价。

用spfa跑&＃xff0c;状态用四位数压缩&＃xff0c;表示为dis[now][step]&＃xff0c;其中step表示当前走的步数%3的值&＃xff0c;now表示当前所在格子&＃xff0c;数组表示当前所用最小花费。

#include
#include
#include
#include
#include
#include
using namespace std;
int get(int x,int y)
{return x*100&＃43;y;
}
bool vis[10050][3];
int dis[10050][3];
int score[10050];
struct state
{int w,s;
};
int n,t;
queue q;
void spfa()
{for(int i&＃61;0;i<10000;i&＃43;&＃43;)dis[i][0]&＃61;dis[i][1]&＃61;dis[i][2]&＃61;0x3f3f3f3f;dis[0][0]&＃61;0;q.push((state){0,0});vis[0][0]&＃61;1;while(!q.empty()){state now&＃61;q.front();vis[now.w][now.s]&＃61;0;q.pop();if(now.w/100!&＃61;0){if(dis[now.w-100][1]>dis[now.w][0]&＃43;t){dis[now.w-100][1]&＃61;dis[now.w][0]&＃43;t;if(!vis[now.w-100][1])vis[now.w-100][1]&＃61;1,q.push((state){now.w-100,1});}if(dis[now.w-100][2]>dis[now.w][1]&＃43;t){dis[now.w-100][2]&＃61;dis[now.w][1]&＃43;t;if(!vis[now.w-100][2])vis[now.w-100][2]&＃61;1,q.push((state){now.w-100,2});}if(dis[now.w-100][0]>dis[now.w][2]&＃43;t&＃43;score[now.w-100]){dis[now.w-100][0]&＃61;dis[now.w][2]&＃43;t&＃43;score[now.w-100];if(!vis[now.w-100][0])vis[now.w-100][0]&＃61;1,q.push((state){now.w-100,0});}}if(now.w/100!&＃61;n-1){if(dis[now.w&＃43;100][1]>dis[now.w][0]&＃43;t){dis[now.w&＃43;100][1]&＃61;dis[now.w][0]&＃43;t;if(!vis[now.w&＃43;100][1])vis[now.w&＃43;100][1]&＃61;1,q.push((state){now.w&＃43;100,1});}if(dis[now.w&＃43;100][2]>dis[now.w][1]&＃43;t){dis[now.w&＃43;100][2]&＃61;dis[now.w][1]&＃43;t;if(!vis[now.w&＃43;100][2])vis[now.w&＃43;100][2]&＃61;1,q.push((state){now.w&＃43;100,2});}if(dis[now.w&＃43;100][0]>dis[now.w][2]&＃43;t&＃43;score[now.w&＃43;100]){dis[now.w&＃43;100][0]&＃61;dis[now.w][2]&＃43;t&＃43;score[now.w&＃43;100];if(!vis[now.w&＃43;100][0])vis[now.w&＃43;100][0]&＃61;1,q.push((state){now.w&＃43;100,0});}}if(now.w%100!&＃61;0){if(dis[now.w-1][1]>dis[now.w][0]&＃43;t){dis[now.w-1][1]&＃61;dis[now.w][0]&＃43;t;if(!vis[now.w-1][1])vis[now.w-1][1]&＃61;1,q.push((state){now.w-1,1});}if(dis[now.w-1][2]>dis[now.w][1]&＃43;t){dis[now.w-1][2]&＃61;dis[now.w][1]&＃43;t;if(!vis[now.w-1][2])vis[now.w-1][2]&＃61;1,q.push((state){now.w-1,2});}if(dis[now.w-1][0]>dis[now.w][2]&＃43;t&＃43;score[now.w-1]){dis[now.w-1][0]&＃61;dis[now.w][2]&＃43;t&＃43;score[now.w-1];if(!vis[now.w-1][0])vis[now.w-1][0]&＃61;1,q.push((state){now.w-1,0});}}if(now.w%100!&＃61;n-1){if(dis[now.w&＃43;1][1]>dis[now.w][0]&＃43;t){dis[now.w&＃43;1][1]&＃61;dis[now.w][0]&＃43;t;if(!vis[now.w&＃43;1][1])vis[now.w&＃43;1][1]&＃61;1,q.push((state){now.w&＃43;1,1});}if(dis[now.w&＃43;1][2]>dis[now.w][1]&＃43;t){dis[now.w&＃43;1][2]&＃61;dis[now.w][1]&＃43;t;if(!vis[now.w&＃43;1][2])vis[now.w&＃43;1][2]&＃61;1,q.push((state){now.w&＃43;1,2});}if(dis[now.w&＃43;1][0]>dis[now.w][2]&＃43;t&＃43;score[now.w&＃43;1]){dis[now.w&＃43;1][0]&＃61;dis[now.w][2]&＃43;t&＃43;score[now.w&＃43;1];if(!vis[now.w&＃43;1][0])vis[now.w&＃43;1][0]&＃61;1,q.push((state){now.w&＃43;1,0});}}}cout<}
int x;
int main()
{freopen("visitfj.in","r",stdin);freopen("visitfj.out","w",stdout);cin>>n>>t;for(int i&＃61;0;i>x,score[get(i,j)]&＃61;x;spfa();
}

gold 2

路两旁各有N只牛&＃xff0c;N个牛棚&＃xff0c;一只牛可以走到所有与自己编号值相差<&＃61;4的牛棚&＃xff0c;问使牛棚间不相交的最大匹配数是多少

dp[i][j]表示第i只牛走到第j个牛棚且1~i的匹配都合法时最大匹配数&＃xff0c;n^2dp即可

#include
#include
#include
#include
#include
#include
using namespace std;
int a[1005],b[1005];
vector tu[1005];
int n,dp[1005][1005];
int main()
{freopen("nocross.in","r",stdin);freopen("nocross.out","w",stdout);scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)cin>>a[i];for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)cin>>b[i];for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;)if(abs(a[i]-b[j])<&＃61;4)tu[i].push_back(j);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)dp[0][i]&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;0;j<&＃61;n;j&＃43;&＃43;){dp[i][j]&＃61;max(dp[i-1][j],dp[i][j]);for(int k&＃61;0;kj)dp[i][f]&＃61;max(dp[i][f],dp[i-1][j]&＃43;1);}}}int ans&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)ans&＃61;max(ans,dp[n][i]);cout<}

gold 3

(相当于)给出n条端点不重合的线段&＃xff0c;问有多少条线段两两相交&＃xff08;一个包含另一个不算&＃xff09;&＃xff0c;注意这里n<&＃61;100000!

这个题我还是想了好一会的&＃xff08;毕竟人太瓷了&＃xff09;&＃xff0c;先将所有起点全部插入一个树状数组&＃xff0c;再把所有终点全部插入另一个树状数组&＃xff0c;然后按照后端点排序&＃xff0c;对于每个线段&＃xff0c;ans&＃43;&＃61;起点树状数组中值小于该线段起点的个数-终点树状数组中值小于该线段起点的个数&＃xff0c;然后把这个线段的起点&＃xff0c;终点在各自的树状数组中删去&＃xff0c;再处理下一条线段。

#include
#include
#include
#include
#include
using namespace std;
int a[100050],b[100050],n;
int ans&＃61;0,q[100050],z[100050];
struct line
{int q,z;
}per[100050];
int in[200050],in2[200050];
int cmp(line a,line b)
{return a.z&＃61;&＃61;b.z? (a.q>b.q):(a.z>b.z);
}
int lowbit(int x)
{return (x&(-x));
}
void plu(int pos,int num)
{while(pos<&＃61;2*n){in[pos]&＃43;&＃61;num;pos&＃43;&＃61;lowbit(pos);}
}
int sum(int end)
{int sum&＃61;0;while(end>0){sum&＃43;&＃61;in[end];end-&＃61;lowbit(end);}return sum;
}
void plus2(int pos,int num)
{while(pos<&＃61;2*n){in2[pos]&＃43;&＃61;num;pos&＃43;&＃61;lowbit(pos);}
}
int sum2(int end)
{int sum&＃61;0;while(end>0){sum&＃43;&＃61;in2[end];end-&＃61;lowbit(end);}return sum;
}
int main()
{freopen("circlecross.in","r",stdin);freopen("circlecross.out","w",stdout);scanf("%d",&n);for(int i&＃61;1;i<&＃61;2*n;i&＃43;&＃43;){scanf("%d",&a[i]);if(!per[a[i]].q)per[a[i]].q&＃61;i,plu(i,1);elseper[a[i]].z&＃61;i,plus2(i,1);}sort(per&＃43;1,per&＃43;n&＃43;1,cmp);int ans&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){ans&＃43;&＃61;sum(per[i].q-1)-sum2(per[i].q-1);// cout<}

platinum 1

还是路两边各有N只牛&＃xff0c;N个牛棚&＃xff0c;这次牛只回属于自己的牛棚&＃xff0c;但约翰很厉害&＃xff0c;他可以将牛棚中最后任意k间牛棚不变顺序地提到最前面&＃xff0c;如45123可以变成12345&＃xff0c;当然也可以是34512&＃xff0c;同时&＃xff0c;他也可以选择用同样的办法对待这群奶牛&＃xff0c;现在请求出修改后最小路径交叉对 数。

如果枚举k&＃xff0c;那么肯定会爆&＃xff0c;我们可以先处理出第i个奶牛所在牛棚位置&＃xff0c;那么这个序列的最小逆序对数一定就是答案之一&＃xff0c;注意当a[n]移到a[1]时&＃xff0c;逆序对数会增加&＃xff08;a[n]-1&＃xff09;个&＃xff0c;也会减少&＃xff08;n-a[n]&＃xff09;个&＃xff0c;所以可以通过dp来获得修改后最大减少值。如果答案不是这个&＃xff0c;那就是第一步处理改为第i间牛棚所在奶牛位置&＃xff0c;再做上述操作。

为什么会分两种情况呢&＃xff1f;是因为约翰即可选择改左边牛&＃xff0c;也可选择改右边牛棚&＃xff0c;所以都得顾及。

#include
#include
#include
#include
#include
using namespace std;
long long a1[500050],b1[500050],a[500050],b[500050];
long long minn&＃61;0,zhuan,g[500050],minans&＃61;0x7f7f7f7f7f;
long long tmp[500050],ans&＃61;0;
int n;
void merge(int l,int m,int r)
{int i&＃61;l,j&＃61;m&＃43;1,k&＃61;l;while(i<&＃61;m&&j<&＃61;r){if(a[i]>a[j]){tmp[k&＃43;&＃43;]&＃61;a[j&＃43;&＃43;];ans&＃43;&＃61;m-i&＃43;1;}elsetmp[k&＃43;&＃43;]&＃61;a[i&＃43;&＃43;];}while(i<&＃61;m)tmp[k&＃43;&＃43;]&＃61;a[i&＃43;&＃43;];while(j<&＃61;r)tmp[k&＃43;&＃43;]&＃61;a[j&＃43;&＃43;];for(int i&＃61;l;i<&＃61;r;i&＃43;&＃43;)a[i]&＃61;tmp[i];
}
void mergesort(int l,int r)
{if(l}
int main()
{freopen("mincross.in","r",stdin);freopen("mincross.out","w",stdout);scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%lld",&a1[i]),a[a1[i]]&＃61;i;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%lld",&b1[i]),b[i]&＃61;a[b1[i]];for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){g[i]&＃61;g[i-1]&＃43;n-2*b[i]&＃43;1;minn&＃61;min(minn,g[i]);}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)a[i]&＃61;b[i];
// for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
// if(g[i]// zhuan&＃61;i,minn&＃61;g[i];
// for(int i&＃61;1;i<&＃61;n-zhuan;i&＃43;&＃43;)
// a[i]&＃61;b[i&＃43;zhuan];
// for(int i&＃61;n-zhuan&＃43;1;i<&＃61;n;i&＃43;&＃43;)
// a[i]&＃61;b[i&＃43;zhuan-n];mergesort(1,n);minans&＃61;min(ans&＃43;minn,minans);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)a[b1[i]]&＃61;i;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)b[i]&＃61;a[a1[i]];minn&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){g[i]&＃61;g[i-1]&＃43;n-2*b[i]&＃43;1;minn&＃61;min(minn,g[i]);}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)a[i]&＃61;b[i];ans&＃61;0;mergesort(1,n);minans&＃61;min(ans&＃43;minn,minans);cout<}

platinum 2

问题同gold2&＃xff0c;但n的范围已经变成了100000&＃xff0c;这就需要我们去优化。

开始想了好一会都没想到怎么优化&＃xff0c;不知道为什么在看机房别人打游戏时突然想到了&＃xff08;手动滑稽&＃xff09;&＃xff1a;因为在枚举i以前的状态时&＃xff0c;我们只关心这个状态的最后一个位置在哪&＃xff0c;以及这个的匹配数&＃xff0c;而且这个“”最后一个位置“只要比当前小就好了&＃xff0c;我们并不关心他们的&＃xff0c;那为什么不用一棵线段树&＃xff0c;维护区间最大值来优化转移呢&＃xff1f;

#include
#include
#include
#include
#include
#define mid (l&＃43;r)/2
#define lson rt*2
#define rson rt*2&＃43;1
using namespace std;
int a[100050],b[100050],loc[100050],n,all[100050][10],f[100050][10];
int dp[100050][15];
struct node
{int maxx,flag;
}tree[400050];
void pushup(int rt)
{tree[rt].maxx&＃61;max(tree[rson].maxx,tree[lson].maxx);
}
void pushdown(int rt)
{if(tree[rt].flag){tree[rson].flag&＃61;tree[lson].flag&＃61;tree[rt].flag;tree[rt].flag&＃61;0;tree[lson].maxx&＃61;tree[lson].flag;tree[rson].maxx&＃61;tree[rson].flag;}
}
void ins(int rt,int l,int r,int L,int R,int v)
{if(L>r||l>R)return ;if(L<&＃61;l&&r<&＃61;R){tree[rt].maxx&＃61;v,tree[rt].flag&＃61;v;return ;}pushdown(rt);ins(lson,l,mid,L,R,v);ins(rson,mid&＃43;1,r,L,R,v);pushup(rt);
}
int query(int rt,int l,int r,int L,int R)
{if(L>r||l>R)return 0;if(L<&＃61;l&&r<&＃61;R)return tree[rt].maxx;pushdown(rt);return max(query(lson,l,mid,L,R),query(rson,mid&＃43;1,r,L,R));
}
int main()
{freopen("nocross.in","r",stdin);freopen("nocross.out","w",stdout);scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d",&a[i]);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d",&b[i]),loc[b[i]]&＃61;i;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(a[i]>&＃61;5)all[i][1]&＃61;loc[a[i]-4];if(a[i]>&＃61;4)all[i][2]&＃61;loc[a[i]-3];if(a[i]>&＃61;3)all[i][3]&＃61;loc[a[i]-2];if(a[i]>&＃61;2)all[i][4]&＃61;loc[a[i]-1];all[i][5]&＃61;loc[a[i]];if(a[i]<&＃61;n-4)all[i][6]&＃61;loc[a[i]&＃43;4];if(a[i]<&＃61;n-3)all[i][7]&＃61;loc[a[i]&＃43;3];if(a[i]<&＃61;n-2)all[i][8]&＃61;loc[a[i]&＃43;2];if(a[i]<&＃61;n-1)all[i][9]&＃61;loc[a[i]&＃43;1];}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;9;j&＃43;&＃43;){if(all[i][j])f[i][j]&＃61;query(1,0,n,0,all[i][j]-1);}for(int j&＃61;1;j<&＃61;9;j&＃43;&＃43;){if(all[i][j]){int ms&＃61;query(1,0,n,all[i][j],all[i][j]);if(ms}

platinum 3

这是这套题中对我而言最有纪念意义的题了。

还是两边N只牛N个牛棚&＃xff0c;这次牛们只能一一对应回自己的棚&＃xff0c;问有多少对线路相交而且牛的编号差距小于k&＃xff08;输入&＃xff09;。

这是一道三位偏序问题&＃xff0c;要用CDQ分治&＃xff0c;我先是想了半个多小时才发现这是三维偏序问题。。之前一直没写出来过cdq分治&＃xff0c;只是知道其思想&＃xff0c;而这道题则是我第一次实践&＃xff0c;能够在没看题解的情况下自己YY出做法和cdq分治并AC&＃xff0c;对我这个蒟蒻而言已经是很有纪念意义了。。。。

这次用结构体存两个量&＃xff0c;第i个表示第i个牛棚&＃xff0c;第一个量所对应的牛棚牛棚编号&＃xff0c;第二个量表示所对应牛的位置。

solve(l,r)时&＃xff0c;先将(l,mid)(mid&＃43;1,r)按照对应牛位置排序&＃xff0c;因为要求的是逆序对&＃xff0c;所以这样排序的话对于左区间的点直接查看已经插入了那些点&＃xff08;这些点一定是编号在它前面的&＃xff09;&＃xff0c;然后像归并排序那样依次看左右两个区间谁小&＃xff0c;如果右边小&＃xff0c;那么把1插入到它的对应编号即可&＃xff0c;如果左边小&＃xff0c;&＃xff08;设此时编号为x&＃xff09;ans便&＃43;&＃61;sum(x-k-1)&＃43;(sum(n)-sum(x&＃43;k))&＃xff0c;顺便注意判一下边界&＃xff0c;同时每次solve完树状数组要清零即可。

#include
#include
#include
#include
#include
#define mid (l&＃43;r)/2
using namespace std;
const int N&＃61;100050;
long long a1,b1[N],a[N],b[N];
int n,k;
long long in[N];
long long ans&＃61;0;
struct node
{long long w,h;
}line[N];
int cmp(node a,node b)
{return a.w}
long long lowbit(int x)
{return x&(-x);
}
void plu(int pos,long long num)
{while(pos<&＃61;2*n){in[pos]&＃43;&＃61;num;pos&＃43;&＃61;lowbit(pos);}
}
long long sum(int end)
{long long sum&＃61;0;while(end>0){sum&＃43;&＃61;in[end];end-&＃61;lowbit(end);}return sum;
}
void solve(int l,int r)
{if(l&＃61;&＃61;r)return ;solve(l,mid);solve(mid&＃43;1,r);sort(line&＃43;l,line&＃43;mid&＃43;1,cmp);sort(line&＃43;mid&＃43;1,line&＃43;r&＃43;1,cmp);int i&＃61;l,j&＃61;mid&＃43;1;while(i<&＃61;mid&&j<&＃61;r){if(line[i].wk)ans&＃43;&＃61;sum(line[i].h-k-1);if(line[i].h<&＃61;n-k)ans&＃43;&＃61;sum(n)-sum(line[i].h&＃43;k);i&＃43;&＃43;;}else{plu(line[j].h,1);j&＃43;&＃43;;}}while(i<&＃61;mid){if(line[i].h>k)ans&＃43;&＃61;sum(line[i].h-k-1);if(line[i].h<&＃61;n-k)ans&＃43;&＃61;sum(n)-sum(line[i].h&＃43;k);i&＃43;&＃43;;}while(j<&＃61;r)plu(line[j].h,1),j&＃43;&＃43;;for(int i&＃61;mid&＃43;1;i<&＃61;r;i&＃43;&＃43;)plu(line[i].h,-1);
}
int main()
{freopen("friendcross.in","r",stdin);freopen("friendcross.out","w",stdout);scanf("%d%d",&n,&k);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%lld",&a1),a[a1]&＃61;i;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%lld",&b1[i]),b[i]&＃61;a[b1[i]];for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)line[i].w&＃61;b[i],line[i].h&＃61;b1[i]; solve(1,n); cout<}