USACO sec1.1

感觉usaco的每道题都很不错，因为虽然简单但是都有点麻烦，很锻炼编程能力

Your Ride Is Here纯水题

/*
ID: wutao161
PROG: ride
LANG: C++     
*/
#include <iostream>
#include <fstream>
#include <string>
#include <string.h>
using namespace std;

char cmt[7],grp[7];
int sc,sg;

int main() {
    ofstream fout ("ride.out");
    ifstream fin ("ride.in");
    
    while(fin>>cmt>>grp)
    {
        sc=sg=1;
        for(int i=0;i<strlen(cmt);i++)
            sc=sc*(cmt[i]-64)%47;
        for(int i=0;i<strlen(grp);i++)
            sg=sg*(grp[i]-64)%47;
              
        if( sc==sg )
            fout<<"GO"<<endl;
        else
            fout<<"STAY
";
    }
    return 0;
}

View Code

Greedy Gift Givers水题

#include<iostream>
#include<fstream>
#include<map>
#include<string>
#include<vector>
#include<cstring>
using namespace std;

ifstream fin("gift1.in");
ofstream fout("gift1.out");

int n;
string name[10];
string t;
int leftover[10];
int ini[10];
int final[10];


int main(){
    
    map<string,int> s;
    int pos,m,p,gift;
    fin>>n;
    memset(ini,0,sizeof(ini));
    memset(final,0,sizeof(final));
    
    for(int i=0;i<n;i++)
    {
        fin>>name[i];
        s[name[i]]=i;
    }//½«ÈËÃûÓëÆäÐòºÅÒ»Ò»¶ÔÓ¦ 
    
    for(int k=0;k<n;k++){
        fin>>t;
        pos=s[t];
        fin>>m>>p;
        if(!p)
            continue;
        
        ini[pos]=m;
        final[pos] +=  m % p ;
        gift = m/p;
        for(int i=0;i<p;i++)
        {
            fin>>t;
            pos=s[t];
            final[pos]+=gift;
        }
    }
    
    for(int i=0;i<n;i++){
        fout<<name[i]<<" "<<final[i]-ini[i]<<endl;
    }
    
    return 0;
}

View Code

Friday the Thirteenth（日历计算的水题）

/*
ID: wutao161
PROG: friday
LANG: C++         
*/

#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;

int norm[12]={31,28,31,30,31,30,31,31,30,31,30,31};
int leap[12]={31,29,31,30,31,30,31,31,30,31,30,31};
int day[7];//frequency  //monday is 1

int main(){
    
    freopen("friday.in","r",stdin);
    freopen("friday.out","w",stdout); 
    int n;
    cin>>n;

    memset(day,0,sizeof(day));
    
    int s=0;//Ò»ºÅÊÇÐÇÆÚ¼¸      
    int thisyear;
    for(int i=0;i<n;i++)
    {
        thisyear=1900+i;
        if( thisyear % 100 == 0 )
        {
            if( thisyear%400==0 ) //leap
                for(int j=0;j<12;j++){
                    day[(s+5)%7]++;
                    s+=(leap[j]-1)%7+1;
                    s%=7;
                }
            else
                for(int j=0;j<12;j++){
                    day[(s+5)%7]++;
                    s+=(norm[j]-1)%7+1;
                    s%=7;
                }    
        }
        else if( thisyear % 4 != 0 )
        {
            for(int j=0;j<12;j++){
                day[(s+5)%7]++;
                s+=(norm[j]-1)%7+1;
                s%=7;
            }
        }
        else //leap
        {
            for(int j=0;j<12;j++){
                day[(s+5)%7]++;
            //    cout<<(s+5)%7<<" ";
                s+=(leap[j]-1)%7+1;
                s%=7;
            //    cout<<s<<"
";
            }
        }
    }
    
    for(int i=5;i<7;i++)    cout<<day[i]<<" ";
    for(int i=0;i<4;i++)    cout<<day[i]<<" ";
    cout<<day[4]<<endl;
    return 0;
}

View Code

Broken Necklace(约瑟夫环变形模拟)

/*
ID: wutao161
PROG: beads
LANG: C++11
*/
#include<vector>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#include<cmath>
using namespace std;

int nex[350],pre[350];
int n;
bool vis[350];
string s;

void ini(){
    for(int i=0;i<n-1;i++)
        nex[i]=i+1;
    nex[n-1]=0;
    for(int i=1;i<n;i++)
        pre[i]=i-1;
    pre[0]=n-1;
}

int right(int st){
    
    int cnt=0,i=st;
    char bgcolor=s[st];
    while(s[i]==bgcolor || s[i]=='w' )
    {
        //vis[i]=1;
        if(cnt>=n)
            break;
        i=nex[i];
        cnt++;
        if(bgcolor=='w')
            bgcolor=s[i];
    }
    return cnt;
}

int left(int st){
    int cnt=0,i=st;
    char bgcolor=s[st];
    while(s[i]==s[st] || s[i]=='w')
    {
        //if(vis[i])
        //    break;
        if(cnt>=n)
            break;
        i=pre[i];
        cnt++;
        if(bgcolor=='w')
            bgcolor=s[i];
    }
    return cnt;
}

int main(){
    freopen("beads.in","r",stdin);
    freopen("beads.out","w",stdout);
    cin>>n;
    cin>>s;
    int ans=-1000;
    ini();
    for(int i=0;i<n-1;i++)
    {
        ans=max(ans,left(i)+right(i+1));
    }
    if(ans>n)
        ans=n;
    cout<<ans<<endl;
    return 0;
}

/*
DESCRIPTION:
可以利用约瑟夫环的链表思想来处理环 
也可以用队列 
*/

View Code