Codeforces Beta Round #35 (Div. 2)
http://codeforces.com/contest/35
A
这场的输入输出是到文件中的，不是标准的输入输出。。。没注意看，RE了好久。。。
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define lson l,mid,rt<<1
4 #define rson mid+1,r,rt<<1|1
5 #define sqr(x) ((x)*(x))
6 #define pb push_back
7 #define eps 1e-8
8 #define PI acos(-1.0)
9 #define maxn 1000005
10 typedef long long ll;
11 typedef unsigned long long ull;
12
13 /*#ifndef ONLINE_JUDGE
14 freopen("1.txt","r",stdin);
15 #endif */
16
17 ifstream cinn("input.txt");
18 ofstream coutt("output.txt");
19
20 int main(){
21 #ifndef ONLINE_JUDGE
22 // freopen("1.txt","r",stdin);
23 #endif
24 std::ios::sync_with_stdio(false);
25 int u,v;
26 int b;
27
28 int a[15];
29 memset(a,0,sizeof(a));
30 cinn>>b;
31 a[b]=1;
32 for(int i=0;i<3;i++){
33 cinn>>u>>v;
34 swap(a[u],a[v]);
35 }
36 for(int i=1;i<=3;i++){
37 if(a[i]==1){
38 coutt<<i;
39 return 0;
40 }
41 }
42 return 0;
43 }
View Code
B
模拟
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define lson l,mid,rt<<1
4 #define rson mid+1,r,rt<<1|1
5 #define sqr(x) ((x)*(x))
6 #define pb push_back
7 #define eps 1e-8
8 #define PI acos(-1.0)
9 #define maxn 1000005
10 typedef long long ll;
11 typedef unsigned long long ull;
12
13 /*#ifndef ONLINE_JUDGE
14 freopen("1.txt","r",stdin);
15 #endif */
16 string s,t,x[31][31];
17 int n,m,k,i,j,a,b,o,r;
18
19 int main(){
20 // #ifndef ONLINE_JUDGE
21 freopen ("input.txt","r",stdin);
22 freopen ("output.txt","w",stdout);
23 // #endif
24 cin>>n>>m>>k;
25 for (o=1;o<=k;o++){
26 cin>>s;
27 if (s[0]=='+'){
28 cin>>a>>b>>t;
29 while (1){
30 if (x[a][b]==""){
31 x[a][b]=t;
32 break;
33 }
34 else {
35 b++;
36 if (b>m){
37 a++;
38 b=1;
39 if (a>n)
40 break;
41 }
42 }
43 }
44 }
45 else {
46 cin>>t;
47 r=0;
48 for (i=1;i<=n;i++){
49 if (r==1)
50 break;
51 for (j=1;j<=m;j++){
52 if (x[i][j]==t){
53 r=1;
54 break;
55 }
56
57 }
58 }
59 if (r==0){
60 cout<<-1<<" "<<-1<<endl;
61 }
62 else {
63 cout<<i-1<<" "<<j<<endl;
64 x[i-1][j]="";
65 }
66 }
67 }
68 }
View Code
C
bfs
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define lson l,mid,rt<<1
4 #define rson mid+1,r,rt<<1|1
5 #define sqr(x) ((x)*(x))
6 #define pb push_back
7 #define eps 1e-8
8 #define PI acos(-1.0)
9 #define maxn 1000005
10 typedef long long ll;
11 typedef unsigned long long ull;
12
13 /*#ifndef ONLINE_JUDGE
14 freopen("1.txt","r",stdin);
15 #endif */
16 int book[2005][2005];
17 int n,m,k;
18 struct sair{
19 int x,y,step;
20 };
21 int dir[4][2]={0,1,1,0,0,-1,-1,0};
22
23 int main(){
24 // #ifndef ONLINE_JUDGE
25 freopen ("input.txt","r",stdin);
26 freopen ("output.txt","w",stdout);
27 // #endif
28 cin>>n>>m>>k;
29 int x,y;
30 queue<sair>Q;
31 sair s,e;
32 for(int i=1;i<=k;i++){
33 cin>>x>>y;
34 s.x=x,s.y=y,s.step=1;
35 book[x][y]=1;
36 Q.push(s);
37 }
38 int last=1;
39 while(!Q.empty()){
40 s=Q.front();
41 Q.pop();
42 for(int i=0;i<4;i++){
43 e.x=s.x+dir[i][0];
44 e.y=s.y+dir[i][1];
45 if(e.x>=1&&e.x<=n&&e.y>=1&&e.y<=m&&!book[e.x][e.y]){
46 e.step=s.step+1;
47 if(e.step>last) last=e.step;
48 // cout<<last<<endl;
49 book[e.x][e.y]=e.step;
50 Q.push(e);
51 }
52 }
53 }
54 for(int i=1;i<=n;i++){
55 for(int j=1;j<=m;j++){
56 if(book[i][j]==last){
57 cout<<i<<" "<<j<<endl;
58 return 0;
59 }
60 }
61 }
62 }
View Code
D
贪心
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define lson l,mid,rt<<1
4 #define rson mid+1,r,rt<<1|1
5 #define sqr(x) ((x)*(x))
6 #define pb push_back
7 #define eps 1e-8
8 #define PI acos(-1.0)
9 #define maxn 1000005
10 typedef long long ll;
11 typedef unsigned long long ull;
12
13 /*#ifndef ONLINE_JUDGE
14 freopen("1.txt","r",stdin);
15 #endif */
16
17 int n,x;
18 int a[105];
19
20 int main(){
21 // #ifndef ONLINE_JUDGE
22 freopen ("input.txt","r",stdin);
23 freopen ("output.txt","w",stdout);
24 // #endif
25 cin>>n>>x;
26 for(int i=1;i<=n;i++){
27 cin>>a[i];
28 a[i]=a[i]*(n-i+1);
29 }
30 sort(a+1,a+n+1);
31 for(int i=1;i<=n;i++){
32 x-=a[i];
33 if(x<0){
34 cout<<i-1<<endl;
35 return 0;
36 }
37
38 }
39 cout<<n<<endl;
40 }
View Code
E
扫瞄线，可以用线段树写，不过我是用类似模拟的方法写的
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define lson l,mid,rt<<1
4 #define rson mid+1,r,rt<<1|1
5 #define sqr(x) ((x)*(x))
6 #define pb push_back
7 #define eps 1e-8
8 #define PI acos(-1.0)
9 #define maxn 1000005
10 typedef long long ll;
11 typedef unsigned long long ull;
12
13 /*#ifndef ONLINE_JUDGE
14 freopen("1.txt","r",stdin);
15 #endif */
16
17 int n;
18 multiset<int>ms;
19 vector<pair<int,int> >ve,ans;
20
21
22 int main(){
23 // #ifndef ONLINE_JUDGE
24 freopen ("input.txt","r",stdin);
25 freopen ("output.txt","w",stdout);
26 // #endif
27 std::ios::sync_with_stdio(false);
28 cin>>n;
29 int l,r,h;
30 for(int i=0;i<n;i++){
31 cin>>h>>l>>r;
32 ve.push_back(make_pair(l,h));
33 ve.push_back(make_pair(r,-h));
34 }
35 sort(ve.begin(),ve.end());
36 int i=0,j;
37 h=0;
38 ms.insert(h);
39 while(i<ve.size()){
40 j=i;
41 do{
42 if(ve[j].second>0){
43 ms.insert(ve[j].second);
44 }
45 else{
46 ms.erase(ms.find(-ve[j].second));
47 }
48 j++;
49
50 }while(j<ve.size()&&ve[i].first==ve[j].first);
51 if(h!=*ms.rbegin()){
52 ans.push_back(make_pair(ve[i].first,h));
53 ans.push_back(make_pair(ve[i].first,h=*ms.rbegin()));
54 }
55 i=j;
56 }
57 cout<<ans.size()<<endl;
58 for(int i=0;i<ans.size();i++){
59 cout<<ans[i].first<<" "<<ans[i].second<<endl;
60 }
61 }
View Code