Codeforces Beta Round #49 (Div. 2)

Codeforces Beta Round #49 (Div. 2)

http://codeforces.com/contest/53

A

#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 eb emplace_back
#define maxn 1000005
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull;

string s[105];

int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
    #endif
    std::ios::sync_with_stdio(false);
    string str;
    cin>>str;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    string ans=str;
    int flag=0;
    for(int i=1;i<=n;i++){
        if(s[i].find(str)==0){
            if(!flag) ans=s[i],flag=1;
            else ans=min(ans,s[i]);
        }
    }
    cout<<ans<<endl;
}

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 eb emplace_back
#define maxn 1000005
#define rep(k,i,j) for(int k=i;k<j;k++)
#define eps 1e-8
typedef long long ll;
typedef unsigned long long ull;


///w/h>=0.8&&w/h<=1.25

ll num[35];
ll h,w;

int sgn(double x){
    if(x<0) return -1;
    if(x<eps) return 0;
    return 1;
}
vector<double>tmp;

bool Check1(ll mid,ll h){
    double zhi=(mid*1.0)/(h*1.0);
    if(sgn(zhi-0.8)>=0&&sgn(1.25-zhi)>=0) return true;
    return false;
}

bool Check2(ll h,ll mid){
    double zhi=(mid*1.0)/(h*1.0);
    if(sgn(zhi-0.8)>=0&&sgn(1.25-zhi)>=0) return true;
    return false;
}

int main(){
    #ifndef ONLINE_JUDGE
     //   freopen("input.txt","r",stdin);
    #endif
    std::ios::sync_with_stdio(false);
    cin>>h>>w;
    num[0]=1;
    ll l,r,mid;
    ll ans=0;
    ll ansh,answ;
    for(int i=1;i<=30;i++) num[i]=num[i-1]*2;
    for(int i=0;i<=30;i++){
        if(h>=num[i]){
            l=ll(ceil(num[i]*0.8));

            if(ll(num[i]*1.25)<=w) r=num[i]*1.25;
            else r=w;
         //   if(h==5&&w==5) cout<<l<<" "<<r<<endl;
            if(l>r) continue;
            while(l<=r){
                mid=l+r>>1;
                if(Check1(mid,num[i])) l=mid+1;
                else r=mid-1;
            }
            if(ans<=r*num[i]){
                ans=r*num[i];
                ansh=num[i],answ=r;
            }
        }
    }
    for(int i=0;i<=30;i++){
        if(w>=num[i]){
           /* l=ll(ceil(num[i]/0.8));
            if(ll(num[i]/1.25)<=w) r=num[i]*1.25;
            else r=h;*/
            l=ceil(num[i]*1.0/1.25);
            r=min(h,ll(num[i]*1.0/0.8));
          //  cout<<l<<" "<<r<<endl;
           // if(h==5&&w==5) cout<<l<<" "<<r<<endl;
            if(l>r) continue;
            while(l<=r){

                mid=l+r>>1;//cout<<mid<<endl;
                if(Check2(num[i],mid)) l=mid+1;
                else r=mid-1;
            }
            if(ans<=r*num[i]){
                ans=r*num[i];
                answ=num[i],ansh=r;
            }
        }
    }
    if(ansh<answ){
        if(answ<=h) swap(ansh,answ);
    }
    cout<<ansh<<" "<<answ<<endl;
}

C

找规律

#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 eb emplace_back
#define maxn 1000005
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull;



int main(){
    #ifndef ONLINE_JUDGE
     //   freopen("input.txt","r",stdin);
    #endif
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int L=1,R=n;
    for(int i=1;i<=n;i++){
        if(i%2){
            cout<<L++<<" ";
        }
        else{
            cout<<R--<<" ";
        }
    }

}

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 eb emplace_back
#define maxn 1000005
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull;

int a[305],b[305];
vector<pair<int,int> >ve;

int main(){
    #ifndef ONLINE_JUDGE
     //   freopen("input.txt","r",stdin);
    #endif
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    int j;
    for(int i=1;i<=n;i++){
        if(a[i]!=b[i]){
            for(j=i+1;j<=n;j++){
                if(a[i]==b[j]){
                    break;
                }
            }
            for(;j>i;j--){
                ve.pb(make_pair(j-1,j));
                swap(b[j],b[j-1]);
            }
        }
    }
    cout<<ve.size()<<endl;
    for(int i=0;i<ve.size();i++){
        cout<<ve[i].first<<" "<<ve[i].second<<endl;
    }
}

E

状压DP

这题思路很奇妙，有些细节还没理解清楚

参考博客：https://www.luogu.org/problemnew/solution/CF53E

#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 eb emplace_back
#define maxn 1000005
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull;

int n,m,k;
int g[25][25];
int dp[1055][1055];
int ans;

int main(){
    #ifndef ONLINE_JUDGE
     //   freopen("input.txt","r",stdin);
    #endif
    std::ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    int u,v,x;
    rep(i,0,m){
        cin>>u>>v;
        u--,v--;
        x=(1<<u)|(1<<v);
        g[u][v]=g[v][u]=1;
        dp[x][x]=1;
    }
    rep(i,0,1<<n){
        rep(j,0,1<<n){
            if(i&j==j&&dp[i][j]){
                rep(k,0,n){
                    rep(w,0,n){
                        if (g[k][w]&&(i&(1<<k))&&(~i&(1<<w))&&(!(((j&(~(1<<k)))|(1<<w))>>(w+1)))){
                            dp[i|(1<<w)][(j&(~(1<<k)))|((1<<w))]+=dp[i][j];
                        }
                    }
                }
            }
        }
    }
    int nn=(1<<n)-1;
    rep(i,0,1<<n){
        if(__builtin_popcount(i)==k){
            ans+=dp[nn][i];
        }
    }
    cout<<ans<<endl;
}