USACO(含training section)水题合集[5/未完待续]

时间：2022-12-05 20:49:41

(1) USACO2.1 Ordered Fractions

　　枚举 排序即可，注意1/1

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=,L=1e5;

struct fr{

    int a,b;

    fr(int q=,int w=):a(q),b(w){}

}f[L];

int n,cnt=;

inline bool cmp(fr &x,fr &y){

    return (double)x.a/x.b<(double)y.a/y.b;

}

inline int gcd(int a,int b){

    return b==?a:gcd(b,a%b);

}

int main(){

    cin>>n;

    for(int i=;i<=n;i++)

        for(int j=i+;j<=n;j++)

            if(gcd(i,j)==)

                f[++cnt]=fr(i,j);

    sort(f+,f++cnt,cmp);

    for(int i=;i<=cnt;i++)

        printf("%d/%d\n",f[i].a,f[i].b);

    cout<<"1/1";

}

(2) USACO1.5Number Triangles

　　基础DP

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

using namespace std;

int r,d[][],a[][];

int dp(int i,int j){

    if(d[i][j]>=) return d[i][j];

    return d[i][j]=a[i][j]+(i==r?:max(dp(i+,j),dp(i+,j+)));

}

int main(){

    scanf("%d",&r);//cin>>r;

    memset(d,-,sizeof(d));

    for(int i=;i<=r;i++)

        for(int j=;j<=i;j++) scanf("%d",&a[i][j]);//cin>>a[i][j];

    int ans=-;

    cout<<dp (,);

}

(3) USACO1.2 Transformations

　　模拟

#include <iostream>

using namespace std;

const int N=;

int n;

char a[N][N],r[N][N],t[N][N];

bool ro90(char a[N][N]){

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            if(a[i][j]!=r[j][n-i+]) return false;

    return true;

}

bool ro180(char a[N][N]){

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            if(a[i][j]!=r[n-i+][n-j+]) return false;

    return true;

}

bool ro270(char a[N][N]){

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            if(a[i][j]!=r[n-j+][i]) return false;

    return true;

}

void img(char a[N][N],char t[N][N]){

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            t[i][n-j+]=a[i][j];

}

bool check(char r[N][N],char t[N][N]){

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            if(r[i][j]!=t[i][j]) return false;

    return true;

}

int solve(){

    if(ro90(a)) return ;

    if(ro180(a)) return ;

    if(ro270(a)) return ;

    img(a,t);

    if(check(r,t)) return ;

    if(ro90(t)) return ;

    if(ro180(t)) return ;

    if(ro270(t)) return ;

    if(check(r,t)) return ;

    return ;

}

int main(int argc, const char * argv[]) {

    cin>>n;

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)cin>>a[i][j];

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)cin>>r[i][j];

    cout<<solve();

}

(4) USACO1.4Mother's Milk

　　dfs，六种倒水方法，fill简化

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

int vis[N][N][N];

int l[],ta,tb,tc;

int ans[N];

inline void fill(int &a,int &b,int num){

    int tmp=min(l[num]-a,b);

    a+=tmp;

    b-=tmp;

}

void dfs(int a,int b,int c){//printf("%d %d %d\n",a,b,c);

    if(vis[a][b][c]) return;

    if(a==) ans[c]=true;

    vis[a][b][c]=;

    ta=a;tb=b;tc=c;//

    fill(ta,tb,);dfs(ta,tb,tc);

    ta=a;tb=b;tc=c;//

    fill(ta,tc,);dfs(ta,tb,tc);

    ta=a;tb=b;tc=c;//

    fill(tb,ta,);dfs(ta,tb,tc);

    ta=a;tb=b;tc=c;//

    fill(tb,tc,);dfs(ta,tb,tc);

    ta=a;tb=b;tc=c;//

    fill(tc,ta,);dfs(ta,tb,tc);

    ta=a;tb=b;tc=c;//

    fill(tc,tb,);dfs(ta,tb,tc);

}

int main(){

    cin>>l[]>>l[]>>l[];

    dfs(,,l[]);

    for(int i=;i<=l[];i++) if(ans[i]) cout<<i<<" ";

}

（5）USACO迷宫

　　裸DFS

#include<iostream>

using namespace std;

int n,m,t,sx,sy,fx,fy,ans=;int x,y;

int e[][],vis[][],dx[]={-,,,},dy[]={,,,-};

void dfs(int x,int y){

    if(x<||y<||x>n||y>m) return;

    if(e[x][y]) return;

    if(x==fx&&y==fy) {ans++;return;}

    if(vis[x][y]) return;

    vis[x][y]=;

    for(int i=;i<;i++) dfs(x+dx[i],y+dy[i]);

    vis[x][y]=;

}

int main(){

    cin>>n>>m>>t>>sx>>sy>>fx>>fy;

    for(int i=;i<t;i++) {cin>>x>>y;e[x][y]=;}

    dfs(sx,sy);

    cout<<ans;

}

相关文章