这场比赛题目难度适中，有2题没有做出来。。
pku2894 Ancient Keyboard直接开个数组来模拟就可以了，数据量再大的话就线段树吧- -
代码：
1
# include <iostream>
2# include <cstring>
3using namespace std;
4int main()
5
{
6
int test;
7 cin>>test;
8 while(test--)
9
{
10 int n;
11 cin>>n;
12 char l;
13 int s,e,c[1001],max=-1,min=0xfffffff;
14 memset(c,0,sizeof(c));
15 while(n--)
16 {
17 cin>>l>>s>>e;
18 for(int i=s;i<e;i++)
19 c[i]++;
20 if(e>max) max=e;
21 if(s<min) min=s;
22
}
23 for(int i=min;i<=max;i++)
24 if(c[i])
25 cout<<(char)(c[i]+64);
26 cout<<endl;
27 }
28 return 0;
29
}
pku2896 Best SMS to Type同样是个没有难度的模拟，细心点就可以了~
1# include <iostream>
2using namespace std;
3inline bool equal(int a,int b)
4{
5 if(a<15&&b<15&&a/3==b/3) return true;
6 else if(a<19&&b<19&&a>=15&&b>=15) return true;
7 else if(a<22&&b<22&&a>=19&&b>=19) return true;
8 else if(a>=22&&b>=22) return true;
9 else return false;
10}
11int main()
12{
13 int test,map[255];
14 map['A']=map['D']=map['G']=map['J']=map['M']=map['P']=map['T']=map['W']=1;
15 map['B']=map['E']=map['H']=map['K']=map['N']=map['Q']=map['U']=map['X']=2;
16 map['C']=map['F']=map['I']=map['L']=map['O']=map['R']=map['V']=map['Y']=3;
17 map['S']=map['Z']=4;
18 map[' ']=1;
19 cin>>test;
20 while(test--)
21 {
22 int t1,t2,total=0;
23 char str[1024];
24 cin>>t1>>t2;
25 cin.get();
26 cin.getline(str,1024);
27 total+=t1*map[str[0]];
28 for(int i=1;str[i]!='\0';i++)
29 if(str[i]!=' '&&str[i-1]!=' '&&equal(str[i]-65,str[i-1]-65))
30 total+=map[str[i]]*t1+t2;
31 else total+=map[str[i]]*t1;
32 cout<<total<<endl;
33 }
34 return 0;
35}
pku2896 Changing Phone Numbers各种数据结构的应用，先按时间排序，然后借助于堆、字典树之类的东西设计一个离线算法应该不难。记得看清题目：
[s+1,e]区间内的规则适用于一个询问。
代码：
1import java.util.*;
2import java.io.*;
3class dic
4{
5 class node
6 {
7 node nxt[]=new node[10];
8 String str;
9 boolean end=false;
10 node()
11 {
12 Arrays.fill(nxt,null);
13 }
14 }
15 node head=new node();
16 void insert(String num,String str)
17 {
18 node p=head;
19 for(int i=0;i<num.length();i++)
20 {
21 if(p.nxt[num.charAt(i)-'0']==null)
22 p.nxt[num.charAt(i)-'0']=new node();
23 p=p.nxt[num.charAt(i)-'0'];
24 }
25 p.end=true;
26 p.str=str;
27 }
28 void erase(String num)
29 {
30 node p=head;
31 for(int i=0;i<num.length();i++)
32 p=p.nxt[num.charAt(i)-'0'];
33 p.end=false;
34 }
35 String get(String num)
36 {
37 node p=head;
38 for(int i=0;i<num.length();i++)
39 {
40 if(p.end) return p.str;
41 p=p.nxt[num.charAt(i)-'0'];
42 }
43 return p.str;
44 }
45}
46public class Main {
47
48 /** *//**
49 * @param argsi
50 */
51
52 static class ins implements Comparable<ins>
53 {
54 int year,type;
55 String name,op;
56 public int compareTo(ins pos)
57 {
58 return year-pos.year;
59 }
60 ins(int year,int type,String name,String op)
61 {
62 this.year=year;
63 this.type=type;
64 this.name=name;
65 this.op=op;
66 }
67 }
68 static class node
69 {
70 int s,e,id;
71 String code;
72 node(int id,int s,int e,String code)
73 {
74 this.s=s;
75 this.e=e;
76 this.code=code;
77 this.id=id;
78 }
79 }
80 static class local
81 {
82 String num;
83 TreeSet<node> list=new TreeSet<node>(new cmp_e());
84 local(String str)
85 {
86 num=str;
87 }
88 void ChangeCode(String code)
89 {
90 String name=antirefer.get(num);
91 antirefer.erase(num);
92 num=code;
93 antirefer.insert(num, name);
94 }
95 void add(node pos)
96 {
97 pos.code=pos.code.substring(num.length());
98 list.add(pos);
99 }
100 void repeat(int pos)
101 {
102 for(node p:list)
103 p.code=p.code.substring(0,pos)+p.code.substring(pos-1);
104 }
105 void swap(int pos)
106 {
107 for(node p:list)
108 p.code=p.code.substring(0,pos-1)+p.code.charAt(pos)+p.code.charAt(pos-1)+p.code.substring(pos+1);
109 }
110 void move(int year)
111 {
112 while(!list.isEmpty()&&list.first().e<year)
113 {
114 list.first().code=num+list.first().code;
115 ans.add(list.pollFirst());
116 }
117
118
119 }
120 }
121 static class cmp_s implements Comparator<node>
122 {
123 public int compare(node a,node b)
124 {
125 return a.s-b.s;
126 }
127 }
128 static class cmp_e implements Comparator<node>
129 {
130 public int compare(node a,node b)
131 {
132 if(a.e!=b.e) return a.e-b.e;
133 else return a.id-b.id;
134 }
135 }
136 static class cmp_id implements Comparator<node>
137 {
138 public int compare(node a,node b)
139 {
140 return a.id-b.id;
141 }
142 }
143 static dic antirefer=new dic();
144 static ArrayList<node> ans=new ArrayList<node>();
145 public static void main(String[] args) throws IOException{
146 Scanner in=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
147 HashMap<String,local> refer=new HashMap<String,local>();
148 ArrayList<ins> list=new ArrayList<ins>();
149 ArrayList<node> ques=new ArrayList<node>();
150 int n=in.nextInt();
151 while((n--)!=0)
152 {
153 String code=in.next(),name=in.next();
154 refer.put(name, new local(code));
155 antirefer.insert(code, name);
156 }
157 n=in.nextInt();
158 while((n--)!=0)
159 list.add(new ins(in.nextInt(),in.nextInt(),in.next(),in.next()));
160 int tc=0;
161 while(true)
162 {
163 int s=in.nextInt(),e=in.nextInt();
164 String code=in.next();
165 if(s==0&&e==0&&code.equals("0")) break;
166 ques.add(new node(tc++,s,e,code));
167 }
168 Collections.sort(list);
169 Collections.sort(ques,new cmp_s());
170 int p=0;
171 for(ins i:list)
172 {
173 while(p<ques.size()&&ques.get(p).s<i.year)
174 {
175 if(antirefer.get(ques.get(p).code)==null)
176 {
177 System.out.println("wa");
178 }
179 refer.get(antirefer.get(ques.get(p).code)).add(ques.get(p));
180 p++;
181 }
182 refer.get(i.name).move(i.year);
183 switch(i.type)
184 {
185 case 1:
186 refer.get(i.name).repeat(Integer.parseInt(i.op));
187 break;
188 case 2:
189 refer.get(i.name).swap(Integer.parseInt(i.op));
190 break;
191 case 3:
192 refer.get(i.name).ChangeCode(i.op);
193 break;
194 };
195
196 }
197 for(;p<ques.size();p++)
198 ans.add(ques.get(p));
199 for(local i:refer.values())
200 i.move(Integer.MAX_VALUE);
201 Collections.sort(ans,new cmp_id());
202 for(node i:ans)
203 System.out.println(i.code);
204
205 }
206
207}
pku2897 Dramatic Multiplications
一道数学题，MS现在权位展开的题目不少- -。这题可以从低位向高位逐位确定。
AP
* K
-------
PA
什么情况无解？出现了循环~。注意！第一位不能为0
代码：
1# include <iostream>
2# include <stack>
3# include <cstring>
4using namespace std;
5bool used[10][10];
6
7int main()
8{
9 int test;
10 cin>>test;
11 while(test--)
12 {
13 int n,k,last,add;
14 bool flag=false;
15 cin>>n>>k;
16 stack<int> ans;
17 memset(used,false,sizeof(used));
18 last=k,add=0;
19 while(!used[last][add])
20 {
21 used[last][add]=true;
22 int nxt=last*n+add;
23 last=nxt%10;
24 add=nxt/10;
25 if(!add&&last==k&&(ans.empty()||ans.top()))
26 {
27 for(;!ans.empty();ans.pop())
28 cout<<ans.top();
29 cout<<k<<endl;
30 flag=true;
31 break;
32 }
33 else ans.push(last);
34 }
35 if(!flag) cout<<0<<endl;
36 }
37 return 0;
38}
pku2898 Entertainment
又是一个模拟的题目，记得POJ上有题叫什么game的和这个一样。用数组模拟就可以了。好久不写BFS，忘了一点，BFS判重的时候是在进队之前~，还有就是，字符输入输出尽量用gets,puts,getchar,putchar
代码：
1# include <cstdio>
2# include <cstring>
3# include <cstdlib>
4# define max(a,b) ((a)>(b)?(a):(b))
5# define min(a,b) ((a)<(b)?(a):(b))
6# define legal(r,c) ((r)>=start&&(r)<n&&(c)>=0&&(c)<m&&!inqueue[r][c])
7using namespace std;
8const int N=1024;
9char map[N][N];
10int n,m,k,start,q[N*N][2],s,e;
11bool inqueue[N][N];
12void bfs(int tr,int tc)
13{
14
15 s=e=-1;
16 q[++e][0]=tr;
17 q[e][1]=tc;
18 memset(inqueue,false,sizeof(inqueue));
19 while(s!=e)
20 {
21 s++;
22 tr=q[s][0];
23 tc=q[s][1];
24 inqueue[tr][tc]=true;
25 if(legal(tr-1,tc)&&map[tr-1][tc]==map[tr][tc])
26 {
27 q[++e][0]=tr-1;
28 q[e][1]=tc;
29 }
30 if(legal(tr+1,tc)&&map[tr+1][tc]==map[tr][tc])
31 {
32 q[++e][0]=tr+1;
33 q[e][1]=tc;
34 }
35 if(legal(tr,tc-1)&&map[tr][tc-1]==map[tr][tc])
36 {
37 q[++e][0]=tr;
38 q[e][1]=tc-1;
39 }
40 if(legal(tr,tc+1)&&map[tr][tc+1]==map[tr][tc])
41 {
42 q[++e][0]=tr;
43 q[e][1]=tc+1;
44 }
45 map[tr][tc]=' ';
46 }
47}
48void MoveLeft()
49{
50 int maxnum=-1;
51 for(int i=start;i<n;i++)
52 {
53 int total=0;
54 for(int j=m-1;j>=0;j--)
55 if(map[i][j]==' ')
56 {
57 for(int k=j+1;k<m;k++)
58 map[i][k-1]=map[i][k],map[i][k]=' ';
59 total++;
60 }
61 maxnum=max(maxnum,m-total);
62 }
63 m=maxnum;
64}
65void MoveDown()
66{
67 int minnum=0xfffffff;
68 for(int j=0;j<m;j++)
69 {
70 int total=0;
71 for(int i=start;i<n;i++)
72 if(map[i][j]==' ')
73 {
74 for(int k=i-1;k>=start;k--)
75 map[k+1][j]=map[k][j],map[k][j]=' ';
76 total++;
77 }
78 minnum=min(minnum,start+total);
79 }
80 start=minnum;
81}
82void print()
83{
84 for(int i=start;i<n;i++)
85 {
86 for(int j=0;j<m;j++)
87 putchar(map[i][j]);
88 putchar('\n');
89 }
90// printf("\n");
91}
92int main()
93{
94 //freopen("e.in","r",stdin);
95 //freopen("ans.txt","w",stdout);
96 int test=0;
97 while(gets(map[0]))
98 {
99 m=strlen(map[0]);
100 for(n=1;;n++)
101 {
102 gets(map[n]);
103 if(map[n][0]>='0'&&map[n][0]<='9')
104 {
105 k=atoi(map[n]);
106 break;
107 }
108 }
109
110 start=0;
111 for(int i=0;i<k;i++)
112 {
113 int tr,tc;
114 scanf("%d%d",&tr,&tc);
115 tr--,tc--;
116
117 bfs(tr+start,tc);
118 // print();
119 // system("pause");
120 MoveLeft();
121 // print();
122 // system("pause");
123 MoveDown();
124 // print();
125 // system("pause");
126
127 }
128 printf("Test case #%d:\n",++test);
129 print();
130 if(k) getchar();
131 //memset(map,0,sizeof(map));
132 }
133}
pku2899 Fortune at El Dorado
经典的二维动态统计：扫描线+树状数组。
这题有点新意的地方就是要枚举扫描线宽度，然后以前动态维护一个树状数组的算法有点不适用了，所以就开了n个树状数组，然后相减即可~复杂度仍然为o(nlogn)，BS这题给出的数据范围，点总数只有100个却写1000个。。1000个点估计没有什么好算法了吧。。
代码：
1# include <cstdio>
2# include <utility>
3# include <cstring>
4# include <functional>
5# include <algorithm>
6using namespace std;
7# define lowbit(bit) ((bit)&-(bit))
8# define N 1001
9struct node
10{
11 int arr[N];
12 int x;
13 void add(int pos)
14 {
15 while(pos<N)
16 arr[pos]++,pos+=lowbit(pos);
17 }
18
19}refer[N];
20int n,aera,c;
21pair<int,int> data[N];
22bool cmp(const pair<int,int> &a,const pair<int,int> &b)
23{
24 return a.first<b.first;
25}
26int sum(int pos,int s,int e)
27{
28 int res=0;
29 while(pos>0)
30 res+=refer[e].arr[pos]-refer[s-1].arr[pos],pos-=lowbit(pos);
31 return res;
32}
33int get(int rank,int s,int e)
34{
35 int begin=1,end=N-1;
36 while(begin<=end)
37 {
38 int mid=(begin+end)/2;
39 if(sum(mid,s,e)>=rank) end=mid-1;
40 else begin=mid+1;
41 }
42 return end+1;
43}
44int main()
45{
46 //freopen("ans.txt","w",stdout);
47 //freopen("f.in","r",stdin);
48 int test;
49 scanf("%d",&test);
50 while(test--)
51 {
52 scanf("%d%d",&n,&aera);
53 for(int i=0;i<n;i++)
54 scanf("%d%d",&data[i].first,&data[i].second);
55 sort(data,data+n,cmp);
56 c=2;
57 memset(refer[1].arr,0,sizeof(refer[1].arr));
58 memset(refer[0].arr,0,sizeof(refer[0].arr));
59 refer[1].x=data[0].first;
60 refer[1].add(data[0].second);
61 for(int i=1;i<n;i++)
62 if(data[i].first==data[i-1].first)
63 refer[c-1].add(data[i].second);
64 else
65 {
66 memcpy(refer[c].arr,refer[c-1].arr,sizeof(refer[c].arr));
67 refer[c].x=data[i].first;
68 refer[c++].add(data[i].second);
69 }
70 int ans=-1;
71 for(int i=1;i<c;i++)
72 for(int j=i;j<c;j++)
73 {
74 int rank=sum(N-1,i,j);
75 int len=refer[j].x-refer[i].x?aera/(refer[j].x-refer[i].x):aera;
76 while(rank)
77 {
78 int p=get(rank,i,j);
79 ans=max(ans,sum(p,i,j)-sum(p-len-1,i,j));
80 rank--;
81 }
82 }
83 printf("%d\n",ans);
84 }
85 return 0;
86}
pku2900 Griddy Hobby
有趣的题目，一条光线从一点45度角射出，不断反弹，直到循环或者射出为止。求包含的最小长方形数目。我用的方法很笨。。将所有的线段模拟出来后然后整个坐标系旋转45度，用上题的动态统计的方法做的。。MS可以直接根据交点数来算。。不过我的那种方法更通用
模拟的时候考虑周全一点，四种向量，8种情况（每一个向量落在不同的边上时旋转地方向不同）
代码：
1# include <set>
2# include <iostream>
3# include <algorithm>
4# include <string>
5# include <vector>
6# include <utility>
7# include <functional>
8# include <cstring>
9# include <queue>
10# define lowbit(bit) ((bit)&-(bit))
11using namespace std;
12struct node
13{
14 int r1,c1,r2,c2;
15 int x1,y1,x2,y2;
16 node(int r1,int c1,int r2,int c2)
17 {
18 this->r1=r1;this->c1=c1;
19 this->r2=r2;this->c2=c2;
20 }
21 void trans()
22 {
23 y1=-(r1-1);
24 y2=-(r2-1);
25 x1=c1-1;
26 x2=c2-1;
27 int tx,ty;
28 tx=x1-y1,ty=x1+y1;
29 x1=tx,y1=ty;
30 tx=x2-y2,ty=x2+y2;
31 x2=tx,y2=ty;
32 if(x1==x2&&y1>y2)
33 swap(y1,y2);
34 if(y1==y2&&x1>x2)
35 swap(x1,x2);
36
37 }
38};
39bool cmp_x1(const node &a,const node &b)
40{
41 return a.x1<b.x1;
42}
43struct cmp_x2
44{
45 bool operator()(const node &a,const node &b) const
46 {
47 return a.x2>b.x2;
48 }
49};
50vector<node> p;
51bool used[1001][1001];
52vector<node> x;
53vector<node> y;
54priority_queue<node,vector<node>,cmp_x2> q;
55int tree[5000];
56int sum(int pos)
57{
58 int res=0;
59 while(pos>0)
60 res+=tree[pos],pos-=lowbit(pos);
61 return res;
62}
63void add(int pos,int one)
64{
65 while(pos<=4000)
66 tree[pos]+=one,pos+=lowbit(pos);
67}
68int main()
69{
70 int test;
71 cin>>test;
72 while(test--)
73 {
74 int r,c,n,m,dir;
75 string tdir;
76 cin>>n>>m>>r>>c>>tdir;
77 if(tdir=="UR") dir=0;
78 else if(tdir=="DR") dir=1;
79 else if(tdir=="DL") dir=2;
80 else dir=3;
81 p.clear();
82 x.clear();
83 y.clear();
84 memset(used,false,sizeof(used));
85 do
86 {
87 used[r][c]=true;
88 int tr,tc;
89 switch(dir)
90 {
91 case 0:
92 tr=r-min(m-c,r-1);
93 tc=c+min(m-c,r-1);
94 if(tr==1) dir=1;
95 else dir=3;
96 break;
97 case 1:
98 tr=r+min(m-c,n-r);
99 tc=c+min(m-c,n-r);
100 if(tc==m) dir=2;
101 else dir=0;
102 break;
103 case 2:
104 tr=r+min(n-r,c-1);
105 tc=c-min(n-r,c-1);
106 if(tr==n) dir=3;
107 else dir=1;
108 break;
109 case 3:
110 tr=r-min(r-1,c-1);
111 tc=c-min(r-1,c-1);
112 if(tc==1) dir=0;
113 else dir=2;
114 break;
115 };
116 p.push_back(node(r,c,tr,tc));
117 r=tr,c=tc;
118 }while(!(r==1&&c==1||r==n&&c==m||r==1&&c==m||r==n&&c==1||used[r][c]));
119 for(int i=0;i<p.size();i++)
120 {
121 p[i].trans();
122 if(p[i].x1==p[i].x2) x.push_back(p[i]);
123 else y.push_back(p[i]);
124 }
125 sort(x.begin(),x.end(),cmp_x1);
126 sort(y.begin(),y.end(),cmp_x1);
127 int j=0;
128 while(!q.empty()) q.pop();
129 memset(tree,0,sizeof(tree));
130 int res=0;
131 int size=x.size();
132 for(int i=0;i<size-1;i++)
133 {
134 while(j<y.size()&&y[j].x1<=x[i].x1)
135 {
136 add(y[j].y1+2000,1);
137 q.push(y[j++]);
138 }
139 while(!q.empty()&&q.top().x2<x[i+1].x1)
140 {
141 add(q.top().y1+2000,-1);
142 q.pop();
143 }
144 res+=sum(min(x[i].y2,x[i+1].y2)+2000)-sum(max(x[i].y1,x[i+1].y1)-1+2000)>=2?sum(min(x[i].y2,x[i+1].y2)+2000)-sum(max(x[i].y1,x[i+1].y1)-1+2000)-1:0;
145 }
146 cout<<res<<endl;
147 }
148 return 0;
149}
pku2903 Joy of Mobile Routing
一道三维向量的题目。首先枚举岔口和发射站的工作省不了的，这里n2m2的复杂度，然后就是判断发射站能不能发射到岔口。
这里MS要详细讨论4种情况：岔口在发射站的左上、右上、左下、右下四种情况，然后上取整和下取整注意下，行列分别验证~总复杂度n3m2，还有向量的方向不能反，必须是从发射站到岔口，应为反过来会有一种很难处理的东西，就是射线根本过不了第一个障碍物，但是到达障碍物对面的时候是比它高的，这样就造成了误判。无权图最短路径不用说了吧，BFS
1# include <cstdio>
2using namespace std;
3# include <algorithm>
4# include <cmath>
5# include <queue>
6# include <cstring>
7# include <utility>
8# include <functional>
9# define N 55
10# define eps 1e-8
11# define equ(a,b) (fabs((a)-(b))<eps)
12# define gt(a,b) (!equ(a,b)&&(a)>(b))
13int h[N][N],len[N][N];
14bool used[N][N];
15int n,m,num,sr,sc,er,ec;
16struct node
17{
18 int r,c,h;
19 bool operator<(const node &pos) const
20 {
21 return h>pos.h;
22 }
23}sta[105];
24int bfs()
25{
26 used[er][ec]=true;
27 if(!used[sr][sc]||!used[er][ec]) return -1;
28 queue<pair<int,int> > q;
29 memset(len,-1,sizeof(len));
30 len[sr][sc]=0;
31 q.push(make_pair<int,int>(sr,sc));
32 while(!q.empty())
33 {
34 pair<int,int> top=q.front();
35 q.pop();
36 if(top.first-1>=0&&used[top.first-1][top.second]&&len[top.first-1][top.second]==-1)
37 {
38 len[top.first-1][top.second]=len[top.first][top.second]+1;
39 q.push(make_pair<int,int>(top.first-1,top.second));
40 }
41 if(top.first+1<=n&&used[top.first+1][top.second]&&len[top.first+1][top.second]==-1)
42 {
43 len[top.first+1][top.second]=len[top.first][top.second]+1;
44 q.push(make_pair<int,int>(top.first+1,top.second));
45 }
46 if(top.second-1>=0&&used[top.first][top.second-1]&&len[top.first][top.second-1]==-1)
47 {
48 len[top.first][top.second-1]=len[top.first][top.second]+1;
49 q.push(make_pair<int,int>(top.first,top.second-1));
50 }
51 if(top.second+1<=m&&used[top.first][top.second+1]&&len[top.first][top.second+1]==-1)
52 {
53 len[top.first][top.second+1]=len[top.first][top.second]+1;
54 q.push(make_pair<int,int>(top.first,top.second+1));
55 }
56 }
57 return len[er][ec]==-1?-1:len[er][ec]*10;
58}
59bool detect(int r,int c,int pos)
60{
61 if(sta[pos].r==r||sta[pos].c==c) return true;
62 double dr=10*(r-sta[pos].r),dc=10*(c-sta[pos].c),dh=-sta[pos].h;
63 bool f1=r>sta[pos].r,f2=c>sta[pos].c;
64 //test row
65 for(int i=f1?sta[pos].r+1:sta[pos].r-1;f1?i<=r:i>=r;f1?i++:i--)
66 {
67 double k=10*(i-sta[pos].r)/dr,nc=sta[pos].c*10+k*dc,nh=sta[pos].h+k*dh;
68 int t1=f1?i-1:i,t2=f2?ceil(nc/10-eps)-1+eps:nc/10+eps;
69 if(gt(h[t1][t2],nh)) return false;
70 }
71 //test col
72 for(int i=f2?sta[pos].c+1:sta[pos].c-1;f2?i<=c:i>=c;f2?i++:i--)
73 {
74 double k=10*(i-sta[pos].c)/dc,nr=sta[pos].r*10+k*dr,nh=sta[pos].h+k*dh;
75 int t1=f1?ceil(nr/10-eps)-1+eps:nr/10+eps,t2=f2?i-1:i;
76 if(gt(h[t1][t2],nh)) return false;
77 }
78 return true;
79}
80int main()
81{
82 int test;
83 scanf("%d",&test);
84 while(test--)
85 {
86 scanf("%d%d",&n,&m);
87 for(int i=0;i<n;i++)
88 for(int j=0;j<m;j++)
89 scanf("%d",&h[i][j]);
90 scanf("%d%d%d%d%d",&sr,&sc,&er,&ec,&num);
91 for(int i=0;i<num;i++)
92 scanf("%d%d%d",&sta[i].r,&sta[i].c,&sta[i].h);
93 //sort(sta,sta+num);
94 for(int i=0;i<=n;i++)
95 for(int j=0;j<=m;j++)
96 {
97 used[i][j]=false;
98 for(int k=0;k<num&&!used[i][j];k++)
99 if(detect(i,j,k)) used[i][j]=true;
100 }
101 /**//*printf("\n");
102 for(int i=0;i<=n;i++)
103 {
104 for(int j=0;j<=m;j++)
105 printf("%d ",used[i][j]);
106 printf("\n");
107 }*/
108 printf("%d\n",bfs());
109 }
110 return 0;
111}
pku2902 Intercepting Missiles
这题我不知道说什么好，就是一个二分匹配模型，但是精度问题搞死我了，一直没能A，有A的请将代码贴在下面，万分感谢