Codeforces Beta Round #35 (Div. 2)

Codeforces Beta Round #35 (Div. 2)

http://codeforces.com/contest/35

A

这场的输入输出是到文件中的，不是标准的输入输出。。。没注意看，RE了好久。。。

#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eps 1e-8
#define PI acos(-1.0)
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull;

/*#ifndef ONLINE_JUDGE
        freopen("1.txt","r",stdin);
#endif */

ifstream cinn("input.txt");
ofstream coutt("output.txt");

int main(){
    #ifndef ONLINE_JUDGE
     //   freopen("1.txt","r",stdin);
    #endif
    std::ios::sync_with_stdio(false);
    int u,v;
    int b;

    int a[15];
    memset(a,0,sizeof(a));
    cinn>>b;
    a[b]=1;
    for(int i=0;i<3;i++){
        cinn>>u>>v;
        swap(a[u],a[v]);
    }
    for(int i=1;i<=3;i++){
        if(a[i]==1){
            coutt<<i;
            return 0;
        }
    }
    return 0;
}

B

模拟

#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eps 1e-8
#define PI acos(-1.0)
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull;

/*#ifndef ONLINE_JUDGE
        freopen("1.txt","r",stdin);
#endif */
string s,t,x[31][31];
int n,m,k,i,j,a,b,o,r;

int main(){
  //  #ifndef ONLINE_JUDGE
        freopen ("input.txt","r",stdin);
        freopen ("output.txt","w",stdout);
   // #endif
    cin>>n>>m>>k;
    for (o=1;o<=k;o++){
        cin>>s;
        if (s[0]=='+'){
            cin>>a>>b>>t;
            while (1){
                if (x[a][b]==""){
                    x[a][b]=t;
                    break;    
                }
                else {
                    b++;
                    if (b>m){
                        a++;
                        b=1;
                        if (a>n)
                            break;
                    }
                }
            }
        }
        else {
            cin>>t;
            r=0;
            for (i=1;i<=n;i++){
                if (r==1)
                    break;
                for (j=1;j<=m;j++){
                    if (x[i][j]==t){
                        r=1;
                        break;
                    }

                }  
            }
            if (r==0){
                cout<<-1<<" "<<-1<<endl;
            }
            else {
                cout<<i-1<<" "<<j<<endl;
                x[i-1][j]="";
            }
        }
    }
}

C

bfs

#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eps 1e-8
#define PI acos(-1.0)
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull;

/*#ifndef ONLINE_JUDGE
        freopen("1.txt","r",stdin);
#endif */
int book[2005][2005];
int n,m,k;
struct sair{
    int x,y,step;
};
int dir[4][2]={0,1,1,0,0,-1,-1,0};

int main(){
  //  #ifndef ONLINE_JUDGE
        freopen ("input.txt","r",stdin);
        freopen ("output.txt","w",stdout);
   // #endif
    cin>>n>>m>>k;
    int x,y;
    queue<sair>Q;
    sair s,e;
    for(int i=1;i<=k;i++){
        cin>>x>>y;
        s.x=x,s.y=y,s.step=1;
        book[x][y]=1;
        Q.push(s);
    }
    int last=1;
    while(!Q.empty()){
        s=Q.front();
        Q.pop();
        for(int i=0;i<4;i++){
            e.x=s.x+dir[i][0];
            e.y=s.y+dir[i][1];
            if(e.x>=1&&e.x<=n&&e.y>=1&&e.y<=m&&!book[e.x][e.y]){
                e.step=s.step+1;
                if(e.step>last) last=e.step;
            //    cout<<last<<endl;
                book[e.x][e.y]=e.step;
                Q.push(e);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(book[i][j]==last){
                cout<<i<<" "<<j<<endl;
                return 0;
            }
        }
    }
}

D

贪心

#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eps 1e-8
#define PI acos(-1.0)
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull;

/*#ifndef ONLINE_JUDGE
        freopen("1.txt","r",stdin);
#endif */

int n,x;
int a[105];

int main(){
  //  #ifndef ONLINE_JUDGE
        freopen ("input.txt","r",stdin);
        freopen ("output.txt","w",stdout);
   // #endif
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]=a[i]*(n-i+1);
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        x-=a[i];
        if(x<0){
            cout<<i-1<<endl;
            return 0;
        }
        
    }
    cout<<n<<endl;
}

E

扫瞄线，可以用线段树写，不过我是用类似模拟的方法写的

#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eps 1e-8
#define PI acos(-1.0)
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull;

/*#ifndef ONLINE_JUDGE
        freopen("1.txt","r",stdin);
#endif */

int n;
multiset<int>ms;
vector<pair<int,int> >ve,ans;


int main(){
  //  #ifndef ONLINE_JUDGE
        freopen ("input.txt","r",stdin);
        freopen ("output.txt","w",stdout);
   // #endif
    std::ios::sync_with_stdio(false);
    cin>>n;
    int l,r,h;
    for(int i=0;i<n;i++){
        cin>>h>>l>>r;
        ve.push_back(make_pair(l,h));
        ve.push_back(make_pair(r,-h));
    }
    sort(ve.begin(),ve.end());
    int i=0,j;
    h=0;
    ms.insert(h);
    while(i<ve.size()){
        j=i;
        do{
            if(ve[j].second>0){
                ms.insert(ve[j].second);
            }
            else{
                ms.erase(ms.find(-ve[j].second));
            }
            j++;

        }while(j<ve.size()&&ve[i].first==ve[j].first);
        if(h!=*ms.rbegin()){
            ans.push_back(make_pair(ve[i].first,h));
            ans.push_back(make_pair(ve[i].first,h=*ms.rbegin()));
        }
        i=j;
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++){
        cout<<ans[i].first<<" "<<ans[i].second<<endl;
    }
}