[USACO] Chapter1-Getting started(入门)

Greedy Gift Givers (gift1) 

 

/*
	ID:123ldss2
	PROG: gift1
	LANG: C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<fstream>
#include<cmath>
#include <algorithm>
using namespace std;
const int inf=1<<28;
const int nMax=1005;
const int mMax=40000;

class nodea{
public:
    int id;
    nodea *p[130];
    nodea(){
        int i;
        id=-1;
        for(i=0;i<130;i++)p[i]=NULL;
    }
};
nodea *root;
int cnt;

int getnum(char *s){
    int i;
    nodea *r=root;
    int l=strlen(s);
    for(i=0;i<l;i++){
        if(r->p[s[i]]==NULL){
            r->p[s[i]]=new nodea();
        }
        r=r->p[s[i]];
    }
    if(r->id==-1){
        r->id=cnt;
        cnt++;
    }
    return r->id;
}
int sum[100];
char name[200][200];
int main(){
    freopen ( "gift1.in", "r", stdin );
    freopen ( "gift1.out", "w", stdout );
    char str[100];
    int n,i,j,a,b,c,d;
    while(scanf("%d",&n)!=EOF){
        root=new nodea();
        memset(sum,0,sizeof(sum));
        cnt=1;
        for(i=1;i<=n;i++){
            scanf("%s",name[i]);
            getnum(name[i]);
        }
        for(i=1;i<=n;i++){
            scanf("%s",str);
            a=getnum(str);
            scanf("%d%d",&b,&c);

            //sum[a]-=b;
            int money;
            if(c!=0){
                money=b/c;
            }
            for(j=1;j<=c;j++){
                scanf("%s",str);
                d=getnum(str);
                sum[d]+=money;
            }

            sum[a]-=money*c;
        }
        for(i=1;i<=n;i++){
            printf("%s %d\n",name[i],sum[i]);
        }
    }
    return 0;
}

/*
    ID:123ldss2
    PROG: friday
    LANG: C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int play(int i){
	if(i%4!=0||(i%100==0&&i%400!=0)){
	return 0;
	}
	else return 1;
}
int common[12]={31,28,31,30,31,30,31,31,30,31,30,31};
int nocommon[12]={31,29,31,30,31,30,31,31,30,31,30,31};
int days(int year,int month,int day){
	int a=0,i,aaa=0;
	for(i=0;i<year;i++){
		if(play(i)==1){
			a++;
		}
	}
	aaa=year*365+a;
    if(play(i)==0){
		for(i=0;i<month-1;i++){
		aaa+=common[i];
		}
		aaa+=day;
	}
	else{
		for(i=0;i<month-1;i++){
			aaa+=nocommon[i];
		}
		aaa+=day;
	}
	return aaa;
}
int num[8];
int main(){
    freopen("friday.in","r",stdin );
    freopen("friday.out","w",stdout );
    int year,n,month,day,i,aaa;
	while(scanf("%d",&n)!=EOF){
	    memset(num,0,sizeof(num));
	    for(year=1900;year<=1900+n-1;year++){
	        for(month=1;month<=12;month++){
                aaa=days(year,month,13);
                aaa=(aaa+5)%7;
                num[aaa]++;
	        }
	    }
	    cout<<num[6]<<" ";
	    for(i=0;i<5;i++){
	        cout<<num[i]<<" ";
	    }
	    cout<<num[5]<<endl;
	}
    return 0;
}

 

/*
    ID:123ldss2
    PROG: barn1
    LANG: C++
*/
#include<iostream>
#include<cstring>
#include<fstream>
#include<cstdio>
#include <algorithm>
using namespace std;
const int nMax=1000;
int dis[nMax],pos[nMax];
int main(){
    int m,s,c,i,j,a,b,n,ans;
    freopen ( "barn1.in", "r", stdin );
    freopen ( "barn1.out", "w", stdout );
    while(scanf("%d%d%d",&m,&s,&c)!=EOF){
        for(i=0;i<c;i++){
            scanf("%d",&pos[i]);
        }
        if(m>=c){
            cout<<c<<endl;
            continue;
        }
        sort(pos,pos+c);
        ans=pos[c-1]-pos[0];
        for(i=0;i<c-1;i++){
            dis[i]=pos[i+1]-pos[i];
        }
        sort(dis,dis+c-1);
        b=m;
        m--;
        a=c-2;
        while(m--&&a>=0){
            ans-=dis[a];
//            cout<<"dis"<<dis[a];
//            cout<<" ans"<<ans<<endl;
            a--;
        }
        cout<<ans+b<<endl;
    }
    return 0;
}

/*
    ID:123ldss2
    PROG: calfflac
    LANG: C++
*/
#include<iostream>
#include<cstring>
#include<fstream>
#include<cstdio>
using namespace std;
const int nMax=200000;
int p[nMax];
char str1[nMax];
void build(char *str,int len) {  //abc-->@#a#b#c#
    int i=0,j;
    str1[0]='@';//开始加入另特殊字符
    str1[1]='#';
    j=2;
    for(i=0;i<len;i++ ){//在每个字符两边都插入一个特殊字符
        str1[j++]=str[i];
        str1[j++]='#';
    }
    str1[j]='\0';
}

int ps;
int manacher(){
    int idd,mxx=0,maxx=0,record;
    memset(p,0,sizeof(p));
    for(int i=strlen(str1);i>=0;i--){
        if( mxx>i )
            p[i]=min(mxx-i, p[2*idd-i]);
        else p[i]=1;
        while(str1[i+p[i]]==str1[i-p[i]])
            p[i]++;

        if( i+p[i]>mxx ){
            mxx=i+p[i];
            idd=i;
        }

        if( p[i]>maxx){
            maxx=p[i]-1;//P[id］-1就是该回文子串在原串中的长度
            record=i;
            ps=record;
        }
    }
    return maxx;
}
int main(){
    char c;
    int len,a,b,n,i;
    int pos[nMax];
    char str[nMax],abc[nMax];
    len=n=0;
    freopen ( "calfflac.in", "r", stdin );
    freopen ( "calfflac.out", "w", stdout );
//    cin>>str;
//    cout<<str<<endl;
    while(scanf("%c",&c)!=EOF){
        str[len]=c;
        if((c>='a'&&c<='z')||(c>='A'&&c<='Z')){
            if(c>='a'&&c<='z'){
                abc[n]=c;
            }
            else{
                abc[n]=c+'a'-'A';
            }
            pos[n]=len;
            n++;
        }
        len++;
    }
    abc[n]='\0';
    //cout<<endl<<abc<<endl;
    build(abc,n);
    a=manacher();   //回文串长度
    cout<<a<<endl;
  //  cout<<ps<<"ps"<<endl;
    if(ps%2==1){
        ps=ps/2-1;
      //  cout<<ps<<endl;
        for(i=pos[ps-a/2+1];i<=pos[ps+a/2];i++){
            cout<<str[i];
        }cout<<endl;
    }
    else{
        ps=ps/2-1;
     //   cout<<ps<<endl;
        for(i=pos[ps-a/2];i<=pos[ps+a/2];i++){
            cout<<str[i];
        }cout<<endl;
    }

    return 0;
}

  /*

    ID:bbezxcy1
    PROG: beads
    LANG: C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char str[500],str1[1500];
bool vis[3000];
int n;
int getnum(int loc)
{
    memset(vis,0,sizeof(vis));
    int a=0,b=0,i;
    for(i=loc;i>loc-n;i--)
    {
        if(str1[i]==str1[loc]||str1[i]=='w')
        {
            a++;
            vis[i]=vis[i+n]=vis[i+n*2]=1;
        }
        else
        {
            break;
        }
    }
    for(i=loc+1;i<=loc+n;i++)
    {
        if((str1[i]==str1[loc+1]||str1[i]=='w')&&!vis[i])
        {
            b++;
        }
        else
        {
            break;
        }

    }
    return a+b;
}
int main()
{
    int i,j,ans,b,c;
    freopen("beads.in","r",stdin);
    freopen("beads.out","w",stdout);
    while(scanf("%d",&n)!=EOF)
    {
        ans=0;
        scanf("%s",str);
        for(i=0;i<n;i++){
            str1[i]=str[i];
            str1[i+n]=str[i];
            str1[i+n*2]=str[i];
        }str1[n*3]='\0';
       // cout<<getnum(23)<<endl;;
        for(i=0;i<n;i++)
        {
            if(str1[i+n]=='w')
            {
                str1[i+n]='b';
                ans=max(ans,getnum(i+n));
                str1[i+n]='r';
                ans=max(ans,getnum(i+n));
                str1[i+n]='w';
            }
            else
            {
                ans=max(ans,getnum(i+n));
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}