USACO Section 1.3(一)

昨天到今天又做了四道简单的题。有开启了一个新的一页。

milk: 很简单的贪心，先选单价便宜的呀。

代码：

[cpp]
/*
ID: duanjia2
PROG: milk
LANG: C++
*/

#include
#include
#include
using namespace std;
struct node
{
int p,a;
} s[5005];
bool cmp(node x,node y)
{
return x.p }
int main()
{
ifstream fin("milk.in");
ofstream fout("milk.out");
int n,m,sum,i;
fin>>n>>m;
for(i=0;i>s[i].p>>s[i].a;
sort(s,s+m,cmp);
sum=0;
for( i=0;i if(n>=s[i].a)
n-=s[i].a,sum+=s[i].p*s[i].a;
else{
sum+=n*s[i].p;
break;
}
}
fout< // system("pause");
return 0;
}

Barn1: 讲关牛的一些故事，呵呵。就是说有50个牛栏，其中有的有牛，有的没，牛栏的门坏了，现在你有m块木板，要你遮住所有的有牛的牛栏，木板可以是任意长，每个牛栏相当于需要一个单位的木板，问你至少需要多少木板。先假设把50个都遮住了，再来截m-1个最大的空隙。
代码：

[cpp]
/*
ID: duanjia2
PROG: barn1
LANG: C++
*/
#include
#include
#include
using namespace std;
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
ifstream fin("barn1.in");
ofstream fout("barn1.out");
int m,s,c,i,j,ans;
int b[205],d[200];
fin>>m>>s>>c;
for(i=0;i fin>>b[i];

if( m>=c)
fout< else{
sort(b,b+c);
for( i=1,j=0;i if( b[i]-b[i-1]>1)
d[j++]=b[i]-b[i-1]-1;
sort(d,d+j,cmp);
ans=b[0]-1+50-b[c-1];

for( i=0;i ans+=d[i];

fout<<50-ans< }
//system("pause");
return 0;
}

calfflac: 最长回文。建议去网上查一下manacher算法，我以前做过，所以本题也是这样做的。
代码：

[cpp]
/*
ID: duanjia2
PROG: calfflac
LANG: C++
*/
#include
#include
#include
#include
using namespace std;
int main()
{
ifstream fin("calfflac.in");
ofstream fout("calfflac.out");
int i,id,mx,len,pt[20005],j,r[20005];
char str[200005],s[20005],m[50005],ch;

memset(pt,0,sizeof(pt));
for( i=0,j=0;str[i]=fin.get(),str[i]>0;i++){
if( str[i]>='a'&&str[i]<='z')
s[j]=str[i],pt[j++]=i;
if( str[i]>='A'&&str[i]<='Z')
s[j]=str[i]-('A'-'a'),pt[j++]=i;
}
s[j]='\0'; len=j;
// cout< m[0]='@';
for( j=1,i=0;i m[j++]='#';
m[j++]=s[i];
}
m[j++]='#', m[j]='\0';
len=j;

//manacher算法。
memset(r,0,sizeof(r));
mx=0,id=0;
for( i=1;i
if(i else r[i]=1;

while(m[i+r[i]]==m[i-r[i]]) r[i]++;

if( r[i]+i>mx){
mx=r[i]+i;
id=i;
}
}
mx=0;
for( i=1;i if(mx mx=r[i],id=i;
len=pt[(id+r[id]-3)/2];
fout< for( j=pt[(id-r[id])/2];j<=len;j++)
fout< fout<
// system("pause");
return 0;
}

crypt1: 枚举的说，看不出哪里贪心了。得看看别人怎么做了。
代码：

[cpp]
/*
ID: duanjia2
PROG: crypt1
LANG: C++
*/

#include
#include
#include
#include
using namespace std;
int f[10];
bool Judge(int n)
{
while( n){
if(!f[n%10]) return false;
n/=10;
}
return true;
}
int main()
{
ifstream fin("crypt1.in");
ofstream fout("crypt1.out");
int i,j,n,cnt;
fin>>n;
memset(f,0,sizeof(f));
for( i=0;i fin>>j;
f[j]=1;
}
cnt=0;
for( i=111;i<=999;i++){
if( Judge(i)){
for( j=11;j<=99;j++)
if( Judge(j) && i*j<10000 && (j%10)*i<1000 && (j/10)*i<1000 && Judge( i*(j%10) ) && Judge(i*(j/10) ) && Judge(i*j) )
cnt++;