Result The name and year was hidden.1
2
3
4
5
* = Correct
x = Wrong Answer (including possibly empty or missing output file)
Country|Year|Name |Score |helpcross |maxcross |countcross
CHN |····|··········|833 |* x * * x x * x x *|* * * * * * * * * * *|* * * * * * * * * *
Solution Important Information
翻译不保证全部正确，请以原题为准。
Why Did the Cow Cross the Road(helpcross)
Important Information
这是一个233分(10个测试点通过了5个)的题解。
Translate
Description
有$C$头牛，第$i(1 \le i \le C)$牛要在$T_i$时刻过马路，现在有$N$只鸡帮助他们，第$j(1 \le j \le N)$在$[A_j,B_j]$可以提供帮助，请求出最大的牛-鸡配对数，每只鸡只能配对一头牛，每头牛也只能配对一只鸡。
Input Format(helpcross.in)
第一行两个数$C$和$N$，接下来$C$行每行一个$T_i$，再接下来$N$行每行两个数$A_j$和$B_j$。
Output Format(helpcross.in)
输出最大鸡-牛匹配数。
Solution
50%题解：将所有$T_i$和$(A_j,B_j)$升序排序，然后对于每头牛枚举在$(A_j,B_j)$内的鸡，若找到合适的匹配则匹配这只牛和这只鸡，也就是答案自增1，输出答案即可。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <algorithm>
const int MAXN=20000 +5 ;
struct data {int a,b;};
int c,n,t[MAXN];data d[MAXN];
bool comp (data a,data b) return a.a==b.a?a.b<b.b:a.a<b.a;}
int main ()
{
freopen("helpcross.in" ,"r" ,stdin );
freopen("helpcross.out" ,"w" ,stdout );
scanf ("%d %d" ,&c,&n);
for (int i=1 ;i<=c;i++)
scanf ("%d" ,&t[i]);
for (int i=1 ;i<=n;i++)
scanf ("%d %d" ,&d[i].a,&d[i].b);
std ::sort(t+1 ,t+c+1 );
std ::sort(d+1 ,d+n+1 ,comp);
int now=1 ,ans=0 ;
for (int i=1 ;i<=n;i++)
{
while (t[now]<d[i].a)
{
now++;
if (now>c) goto out;
}
if (t[now]>d[i].b) continue ;
ans++;
now++;
}
out:
printf ("%d\n" ,ans);
}
Something want to say
这题这种奇怪的解法都能得50%……
Why Did the Cow Cross the Road II(maxcross) Translate
Description
总共有$N$个灯，坏了$B$个，求最小的修复个数使得至少有$K$个连续的工作的灯。
Input Format(file maxcross.in)
第一行$N,K,B$三个数，接下来$B$行每行一个坏的灯号。
Output Format(file maxcross.out)
输出最小修复个数
Solution
枚举连续的$K$个灯，求这$K$个灯中有多少个坏的，取最小值输出。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <algorithm>
const int MAXN=100000 +5 ;
int n,m,k,ans;bool flag[MAXN];
int main ()
{
freopen("maxcross.in" ,"r" ,stdin );
freopen("maxcross.out" ,"w" ,stdout );
scanf ("%d %d %d" ,&n,&m,&k);
int x;
for (int i=1 ;i<=k;i++)
{
scanf ("%d" ,&x);
flag[x]=1 ;
}
int tot=0 ;
for (int i=1 ;i<=m;i++)
{
tot+=flag[i];
}
ans=tot;
int start=2 ,end=m+1 ;
while (end<=n)
{
tot-=flag[start-1 ];
tot+=flag[end];
ans=std ::min(tot,ans);
start++;
end++;
}
printf ("%d\n" ,ans);
return 0 ;
}
Why Did the Cow Cross the Road III(countcross) Translate
Description
为什么牛过马路？ 那么，一个原因是农夫约翰的农场只有很多道路，使他的母牛不可能在不穿过许多道路的情况下旅行。
Input Format
第一行三个数$N,K,R$，接下来$R$行每行描述一条马路，以$r$ $c$ $r’$ $c’$形式呈现，表示$(r,c)$和$(r’,c’)$间有一条马路。接下来K行每行描述一头奶牛坐标。
Output Format
输出“遥远的”奶牛对数。
Solution
对于每个马路，标记两格子间不能互通。然后求连通块，接着进行比较每对奶牛的块的编号，若不同表示至少要走一个马路。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <queue>
const int MAXN=100 +5 ;
struct point {int x,y;};
bool limit[MAXN][MAXN][MAXN][MAXN];
int vis[MAXN][MAXN],xd[4 ]={-1 ,1 ,0 ,0 },yd[4 ]={0 ,0 ,-1 ,1 };
int x1,y1,x2,y2,n,k,r;point cow[MAXN];
void BFS (int bx,int by,int vid)
{
point temp,tmp;
temp.x=bx;temp.y=by;
vis[bx][by]=vid;
que.push(temp);
while (!que.empty())
{
temp=que.front();que.pop();
for (int i=0 ;i<4 ;i++)
{
tmp=temp;
tmp.x+=xd[i];tmp.y+=yd[i];
if (tmp.x<1 || tmp.y<1 || tmp.x>r || tmp.y>r ||limit[temp.x][temp.y][tmp.x][tmp.y] || vis[tmp.x][tmp.y]) continue ;
que.push(tmp);
vis[tmp.x][tmp.y]=vid;
}
}
}
int main ()
{
freopen("countcross.in" ,"r" ,stdin );
freopen("countcross.out" ,"w" ,stdout );
scanf ("%d %d %d" ,&r,&k,&n);
for (int i=1 ;i<=n;i++)
{
scanf ("%d %d %d %d" ,&x1,&y1,&x2,&y2);
limit[x1][y1][x2][y2]=limit[x2][y2][x1][y1]=1 ;
}
for (int i=1 ;i<=k;i++)
scanf ("%d %d" ,&cow[i].x,&cow[i].y);
int par3=0 ;
for (int i=1 ;i<=r;i++)
for (int j=1 ;j<=r;j++)
if (!vis[i][j]) BFS(i,j,++par3);
int ans=0 ;
for (int i=1 ;i<=k;i++)
for (int j=i+1 ;j<=k;j++)
if (vis[cow[i].x][cow[i].y]!=vis[cow[j].x][cow[j].y]) ans++;
printf ("%d\n" ,ans);
return 0 ;
}
