bzoj 1692: [Usaco2006 Dec]队列调换

bzoj4394【Usaco2015 Dec】Bessie

bzoj4397【Usaco2015 Dec】Breed Counting

 

题目大意:

23333,在扒了一天题解之后发现我竟然还能秒题,虽然这是个pj的sb题。。。

把序列(串)反过来,连到原串上,然后求一下后缀数组,答案就是每次比较a1,a2(a1初始为1,a2初始为n+1),输出rank小的一个

Description

After eating too much fruit in Farmer John’s kitchen, Bessie the cow is
getting some very strange dreams! In her most recent dream, she is
trapped in a maze in the shape of an N×M grid of tiles (1≤N,M≤1,000).
She starts on the top-left tile and wants to get to the bottom-right
tile. When she is standing on a tile, she can potentially move to the
adjacent tiles in any of the four cardinal directions.

But wait! Each tile has a color, and each color has a different
property! Bessie’s head hurts just thinking about it:

If a tile is red, then it is impassable.
If a tile is pink, then it can be walked on normally.
If a tile is orange, then it can be walked on normally, but will make
Bessie smell like oranges.
If a tile is blue, then it contains piranhas that will only let Bessie
pass if she smells like oranges.
If a tile is purple, then Bessie will slide to the next tile in that
direction (unless she is unable to cross it). If this tile is also a
purple tile, then Bessie will continue to slide until she lands on a
non-purple tile or hits an impassable tile. Sliding through a tile
counts as a move. Purple tiles will also remove Bessie’s smell.

(If you’re confused about purple tiles, the example will illustrate
their use.)

Please help Bessie get from the top-left to the bottom-right in as few
moves as possible.

 

奶牛Bessie被困在了N*M的网格图迷宫中,她位于左上角(1,1),出口在右下角(N,M)。Bessie只能上下左右行走。

每块地砖都有一个颜色:

如果是红色,那么不可通行。

如果是粉色,那么可以通行。

如果是橙色,那么可以通行,但是会给Bessie带上橘子的气味。

如果是蓝色,那么当且仅当Bessie带着橘子的气味时,才可以通行。

如果是紫色,那么Bessie会保持原有方向滑过去,如果之后仍然是紫色,那么会继续滑。当滑到不是紫色的地砖上或者不可通行的时候,才会停下来。并且这会消除Bessie身上的气味。每一步滑行和走路一样,都需要耗费一单位时间。

请输出Bessie逃到出口所需的最短时间。

 

4397: [Usaco2015 dec]Breed Counting

约翰的表哥罗恩生活在科罗拉多州。他近来打算教他的奶牛们滑雪,但是奶牛们非常害羞,不敢在游人如织的度假胜地滑雪。没办法,他只好自己建滑雪场了.罗恩的雪场可以划分为W列L行(1≤W≤500;1≤L≤500),每个方格有一个特定的高度H(0≤H≤9999)。奶牛可以在相临方格间滑雪,而且不能由低到高滑。为了保证任意方格可以互通,罗恩打算造一些直达缆车。缆车很强大,可以连接任意两个方格,而且是双向的。而且同一个方格也可以造多台缆车。但是缆车的建造费用贵得吓人,所以他希望造尽量少的缆车。那最少需要造多少台呢?

(排个序,然后upper_bound和lower_bound一用就行了(是不是有O(1)的查询方法啊??貌似要离散啊,一样蛋疼。。))

 1 #include<bits/stdc++.h>
 2 #define N 100005<<1
 3 #define LL long long
 4 #define inf 0x3f3f3f3f
 5 using namespace std;
 6 inline int ra()
 7 {
 8     int x=0,f=1; char ch=getchar();
 9     while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
10     while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
11     return x*f;
12 }
13 int p,q,k,n,a[N],v[N],rank[2][N],sa[2][N];
14 void cal_sa(int sa[N], int rank[N], int Sa[N], int Rank[N])
15 {
16     for (int i=1; i<=n; i++) v[rank[sa[i]]]=i;
17     for (int i=n; i>=1; i--)
18         if (sa[i]>k)
19             Sa[v[rank[sa[i]-k]]--]=sa[i]-k;
20     for (int i=n-k+1; i<=n; i++)
21         Sa[v[rank[i]]--]=i;
22     for (int i=1; i<=n; i++)
23         Rank[Sa[i]]=Rank[Sa[i-1]]+(rank[Sa[i-1]]!=rank[Sa[i]] || rank[Sa[i-1]+k]!=rank[Sa[i]+k]);
24 }
25 void work()
26 {
27     p=0,q=1; 
28     for (int i=1; i<=n; i++) v[a[i]]++;
29     for (int i=1; i<=30; i++) v[i]+=v[i-1];
30     for (int i=1; i<=n; i++) sa[p][v[a[i]]--]=i;
31     for (int i=1; i<=n; i++) rank[p][sa[p][i]]=rank[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);
32     for (k=1; k<n; k<<=1,q^=1,p^=1) cal_sa(sa[p],rank[p],sa[q],rank[q]);
33 }
34 int main()
35 {
36     n=ra();
37     for (int i=1; i<=n; i++)
38     {
39         char ch[2]; scanf("%s",ch);
40         a[i]=ch[0]-'A'+1;
41         a[n-i+1+n]=a[i];
42     }
43     n<<=1;
44     work();
45     int a1=1,a2=n/2+1;
46     for (int i=1; i<=n>>1; i++)
47     {
48         if (rank[p][a1]<rank[p][a2]) printf("%c",(char)a[a1++]+'A'-1);
49             else printf("%c",(char)a[a2++]+'A'-1);
50         if (!(i%80)) cout<<endl;
51     }
52     return 0;
53 }

Input

The first line has two integers N and M, representing the number of rows
and columns of the maze.

The next NN lines have MM integers each, representing the maze:

The integer ‘0’ is a red tile
The integer ‘1’ is a pink tile
The integer ‘2’ is an orange tile
The integer ‘3’ is a blue tile
The integer ‘4’ is a purple tile

The top-left and bottom-right integers will always be ‘1’.

Description

Farmer John’s N cows, conveniently numbered 1…N, are all standing in a
row (they seem to do so often that it now takes very little prompting
from Farmer John to line them up). Each cow has a breed ID: 1 for
Holsteins, 2 for Guernseys, and 3 for Jerseys. Farmer John would like
your help counting the number of cows of each breed that lie within
certain intervals of the ordering.

 

给定一个长度为N的序列,每个位置上的数只可能是1,2,3中的一种。

有Q次询问,每次给定两个数a,b,请分别输出区间[a,b]里数字1,2,3的个数。

 

 

 1 #include <bits/stdc++.h>
 2 #define LL long long
 3 #define inf 1e60
 4 using namespace std;
 5 inline int ra()
 6 {
 7     int x=0,f=1; char ch=getchar();
 8     while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
 9     while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
10     return x*f;
11 }
12 
13 const int maxn=100005;
14 
15 int a[maxn],n,m;
16 int main()
17 {
18     n=ra(); m=ra(); for (int i=1; i<=n; i++) a[i]=ra();
19     sort(a+1,a+n+1);
20     while (m--)
21     {
22         int x=ra(),y=ra();
23         y=upper_bound(a+1,a+n+1,y)-a;
24         x=lower_bound(a+1,a+n+1,x)-a;
25         printf("%d\n",y-x);
26     }
27     return 0;
28 }

 

Output

A single integer, representing the minimum number of moves Bessie must
use to cross the maze, or -1 if it is impossible to do so.

Input

The first line of input contains NN and QQ (1≤N≤100,000 1≤Q≤100,000).
The next NN lines contain an integer that is either 1, 2, or 3, giving
the breed ID of a single cow in the ordering.
The next QQ lines describe a query in the form of two integers a,b
(a≤b).

思路:

 

Sample Input

4 4
1 0 2 1
1 1 4 1
1 0 4 0
1 3 1 1

Output

For each of the QQ queries (a,b), print a line containing three numbers:
the number of cows numbered a…b that are Holsteins (breed 1), Guernseys
(breed 2), and Jerseys (breed 3).

要保证任意方格可以互通,只要让每个方格都能到旁边所有方格,且旁边所有方格都能到这个方格。将可以互达的方格看成一个集合,显然集合中所有方格的高度相同。将每个集合看成一个点,从高的点向低的点连一条有向边。那么入度为0的点就需要从别的点建造一台缆车。同样出度为0的点也需要向别的点建造一台缆车。统计入度为0的点的个数和出度为0的点的个数,由于一台缆车能解决一个出度为0的点和一个入度为0的点,所以答案就是其中较大值。

Sample Output

10

Sample Input

6 3
2
1
1
3
2
1
1 6
3 3
2 4

代码:

HINT

 

In this example, Bessie walks one square down and two squares to the
right (and then slides one more square to the right). She walks one
square up, one square left, and one square down (sliding two more
squares down) and finishes by walking one more square right. This is a
total of 10 moves (DRRRULDDDR).

 

Sample Output

3 2 1
1 0 0
2 0 1

图片 1图片 2

Source

BFS,建图比较麻烦(详见代码)

 

 

这是标程

 

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int dr[] = {-1, 0, 1, 0};
int dc[] = {0, -1, 0, 1};

struct state {
  int r;
  int c;
  int ld;
  bool smell;

  state(int r, int c, int ld, bool smell) :
      r(r), c(c), ld(ld), smell(smell) {
  }

  int pack() {
    return (smell ? 1 : 0) + 2 * (ld + 1) + 10 * c + 10000 * r;
  }

  static state unpack(int x) {
    return state(x / 10000, (x / 10) % 1000,
                 (x / 2) % 5 - 1, x & 1);
  }
};

int getcell(const vector >& A, int r, int c) {
  if (r < 0 || r >= A.size() || c < 0 || c >= A[r].size()) {
    return 0;
  }
  return A[r][c];
}

int main() {
  ios_base::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  vector > A(N, vector(M));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      cin >> A[i][j];
    }
  }
  queue q;
  vector D(10000000, -1);

  int s = state(0, 0, -1, false).pack();
  q.push(s);
  D[s] = 0;

  while (!q.empty()) {
    state st = state::unpack(q.front());
    q.pop();
//    cout<< 这是我的程序,有两个点WA...不知道为什么 #include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define maxn 1100
#define maxm 20000100
using namespace std;
int n,m,a[maxn][maxn],d[maxm];
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
struct node
{
 int x,y,dir,sme;
}now,nxt;
queue q;
inline int read()
{
 int x=0,f=1;char ch=getchar();
 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 return x*f;
}
inline int num(node tmp)
{
 return tmp.sme+2*(tmp.dir+1)+10*(tmp.x-1)+10000*(tmp.y-1);
}
int main()
{
 n=read();m=read();
 F(i,1,n) F(j,1,m) a[i][j]=read();
 memset(d,-1,sizeof(d));
 now=(node){1,1,-1,0};
 d[num(now)]=0;
 q.push(now);
 while (!q.empty())
 {
  now=q.front();q.pop();
  cout<<n||ty<1||ty>m) continue;
   if (a[tx][ty]!=0&&a[tx][ty]!=3)
   {
    nxt=(node){tx,ty,now.dir,a[tx][ty]==2};
    if (d[num(nxt)]!=-1) continue;
    d[num(nxt)]=d[num(now)]+1;
    q.push(nxt);
    continue;
   }
  }
  F(i,0,3)
  {
   int tx=now.x+dx[i],ty=now.y+dy[i];
   if (tx<1||tx>n||ty<1||ty>m) continue;
   if (a[tx][ty]==0||(a[tx][ty]==3&&!now.sme)) continue;
   int ts=a[tx][ty]==2?1:(a[tx][ty]==4?0:now.sme);
   nxt=(node){tx,ty,i,ts};
   if (d[num(nxt)]!=-1) continue;
   d[num(nxt)]=d[num(now)]+1;
   q.push(nxt);
  }
 }
 printf("-1\n");
 return 0;
}
<

<

 

 

<<

Dec】Bessie Description After
eating too much fruit in Farmer Johns kitchen, Bessie the cow is getting
some very strange dreams! In her most recent dream, she…

HINT

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline char Nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    if(p1==p2){
        p2=(p1=buf)+fread(buf,1,100000,stdin);
        if(p1==p2)return EOF;
    }
    return *p1++;
}
inline void Read(int& x){
    char c=Nc();
    for(;c<'0'||c>'9';c=Nc());
    for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=Nc());
}
int a[4]={0,0,-1,1};
int b[4]={1,-1,0,0};
int i,j,k,n,m,h[501][501],f[501][501],x,y,Num;
bool In[250000],Out[250000];
inline void Dfs(int x,int y){
    if(f[x][y])return;
    f[x][y]=Num;
    for(int i=0;i<4;i++)
    if(a[i]+x>0&&a[i]+x<=n)
    for(int j=0;j<4;j++)
    if(b[j]+y>0&&b[j]+y<=m&&h[x][y]==h[x+a[i]][y+b[i]])Dfs(x+a[i],y+b[i]);
}
int main()
{
    Read(m);Read(n);
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    Read(h[i][j]);
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    if(!f[i][j])Num++,Dfs(i,j);
    if(Num==1)return putchar('0'),0;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++){
        if(i<n&&f[i][j]!=f[i+1][j])
        if(h[i][j]>h[i+1][j])Out[f[i][j]]=In[f[i+1][j]]=1;else In[f[i][j]]=Out[f[i+1][j]]=1;
        if(j<m&&f[i][j]!=f[i][j+1])
        if(h[i][j]>h[i][j+1])Out[f[i][j]]=In[f[i][j+1]]=1;else In[f[i][j]]=Out[f[i][j+1]]=1;
    }
    for(i=1;i<=Num;i++){
        if(!In[i])x++;
        if(!Out[i])y++;
    }
    printf("%d\n",x>y?x:y);
    return 0;
}

Source

#include #include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i–)
#define ll long long
#define pa pair
#define maxn 100005
#define inf 1000000000
using namespace std;
int n,m,x,y,sum[4][maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<‘0’||ch>’9′){if (ch==’-‘) f=-1;ch=getchar();}
while (ch>=’0’&&ch<=’9′){x=x*10+ch-‘0’;ch=getchar();}
return x*f;
}
int main()
{
n=read();m=read();
F(i,1,n)
{
F(j,1,3) sum[j][i]=sum[j][i-1];
x=read();
sum[x][i]++;
}
F(i,1,m)
{
x=read();y=read();
printf(“%d %d
%d\n”,sum[1][y]-sum[1][x-1],sum[2][y]-sum[2][x-1],sum[3][y]-sum[3][x-1]);
}
}
 

 

 

Dec】Breed Counting 4397:
[Usaco2015 dec]Breed Counting Description Farmer Johns N cows,
conveniently numbered 1N, are all standing in a row (they seem to
do…

bzoj3388

 

相关文章