杂题训练 2020.7.2

[USACO1.5]八皇后 Checker Challenge
https://www.luogu.com.cn/problem/P1219

#include <bits/stdc++.h>
using namespace std;
int a[200],b[200],c[200],d[200];
int tot,n;
void queen(int i){
   if(i>n){
        if(tot<=2){
            for(int k=1;k<=n;k++)
                cout<<a[k]<<" ";
            cout<<endl;
        }
        tot++;
   }
   for(int j=1;j<=n;j++){
        if(!b[j]&&!c[i+j]&&!d[i-j+n]){
            a[i]=j;
            b[j]=1;
            c[i+j]=1;
            d[i-j+n]=1;
            queen(i+1);
            b[j]=0;
            c[i+j]=0;
            d[i-j+n]=0;
        }
   }
}
int main(){
    cin>>n;
    queen(1);
    cout<<tot<<endl;
    return 0;
}

考前临时抱佛脚
https://www.luogu.com.cn/problem/P2392

#include <bits/stdc++.h>
using namespace std;
int pj[5],homework[30],dp[3000];
int main(){
    int sum=0,t=0;
    for(int i=1;i<=4;i++) cin>>pj[i];
    for(int i=1;i<=4;i++){
        sum=0;
        for(int j=1;j<=pj[i];j++){
            cin>>homework[j];
            sum+=homework[j];
        }
        for(int j=1;j<=pj[i];j++){
            for(int k=sum/2;k>=homework[j];k--)
                dp[k]=max(dp[k],dp[k-homework[j]]+homework[j]);
        }
        t+=sum-dp[sum/2];
        for(int j=1;j<=sum/2;j++) dp[j]=0;
    }
    cout<<t<<endl;
    return 0;
}

马的遍历
https://www.luogu.com.cn/problem/P1443

#include <bits/stdc++.h>
using namespace std;
const int N=500;
int d[N][N],n,m;
int dx[8]={1,2,2,1,-1,-2,-2,-1},dy[8]={2,1,-1,-2,-2,-1,1,2};
void bfs(int i,int j){
    queue<pair<int,int> >q;
    q.push(make_pair(i,j));
    d[i][j]=0;
    while(q.size()){
        pair<int,int>now=q.front();
        q.pop();
        for(int k=0;k<8;k++){
            int nx=now.first+dx[k];
            int ny=now.second+dy[k];
            if(nx<1||nx>n||ny<1||ny>m||!(d[nx][ny]==-1)) continue;
            else {
                d[nx][ny]=d[now.first][now.second]+1;
                q.push(make_pair(nx,ny));
            }
        }
    }
}
int main(){
    cin>>n>>m;
    int i,j;
    cin>>i>>j;
    memset(d,-1,sizeof(d));
    bfs(i,j);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            printf("%-5d", d[i][j]);
        cout<<endl;
    }
    return 0;
}

奇怪的电梯
https://www.luogu.com.cn/problem/P1135

#include <bits/stdc++.h>
using namespace std;
const int N=250;
int s[N],n,a,b,v[N];
void bfs(int a,int b){
    if(a==b) {cout<<"0";return;}
    queue<pair<int,int> >q;
    q.push(make_pair(a,0));
    while(q.size()){
        pair<int,int> now=q.front();
        v[now.first]=1;
        q.pop();
        if(now.first+s[now.first]<=n||now.first-s[now.first]>=1){
            if(now.first+s[now.first]==b||now.first-s[now.first]==b){
                cout<<now.second+1;
                return;
            }
            else{
                if(now.first+s[now.first]<=n&&!v[now.first+s[now.first]]){
                        q.push(make_pair(now.first+s[now.first],now.second+1));
                        v[now.first+s[now.first]]=1;
                }
                if(now.first-s[now.first]>=1&&!v[now.first-s[now.first]]){
                        q.push(make_pair(now.first-s[now.first],now.second+1));
                        v[now.first-s[now.first]]=1;
                }
            }
        }
    }
    cout<<-1;
}
int main(){
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++) cin>>s[i];
    bfs(a,b);
    return 0;
}