昨天到今天又做了四道簡單的題。有開啟了一個新的一頁。
milk: 很簡單的貪心，先選單價便宜的呀。
代碼：
[cpp]
/*
ID: duanjia2
PROG: milk
LANG: C++
*/
#include<iostream>
#include<algorithm>
#include<fstream>
using namespace std;
struct node
{
int p,a;
} s[5005];
bool cmp(node x,node y)
{
return x.p<y.p;
}
int main()
{
ifstream fin("milk.in");
ofstream fout("milk.out");
int n,m,sum,i;
fin>>n>>m;
for(i=0;i<m;i++) fin>>s[i].p>>s[i].a;
sort(s,s+m,cmp);
sum=0;
for( i=0;i<m;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<<sum<<endl;
// system("pause");
return 0;
}
Barn1: 講關牛的一些故事，呵呵。就是說有50個牛欄，其中有的有牛，有的沒，牛欄的門壞了，現在你有m塊木板，要你遮住所有的有牛的牛欄，木板可以是任意長，每個牛欄相當於需要一個單位的木板，問你至少需要多少木板。先假設把50個都遮住了，再來截m-1個最大的空隙。
代碼：
[cpp]
/*
ID: duanjia2
PROG: barn1
LANG: C++
*/
#include<iostream>
#include<algorithm>
#include<fstream>
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<c;i++)
fin>>b[i];
if( m>=c)
fout<<c<<endl;
else{
sort(b,b+c);
for( i=1,j=0;i<c;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<m-1;i++)
ans+=d[i];
fout<<50-ans<<endl;
}
//system("pause");
return 0;
}
calfflac: 最長回文。建議去網上查一下manacher算法，我以前做過，所以本題也是這樣做的。
代碼：
[cpp]
/*
ID: duanjia2
PROG: calfflac
LANG: C++
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<fstream>
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<<len<<endl;
m[0]='@';
for( j=1,i=0;i<len;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<len;i++){
if(i<mx) r[i]=min(r[2*id-i],mx-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<len;i++)
if(mx<r[i])
mx=r[i],id=i;
len=pt[(id+r[id]-3)/2];
fout<<mx-1<<endl;
for( j=pt[(id-r[id])/2];j<=len;j++)
fout<<str[j];
fout<<endl;
// system("pause");
return 0;
}
crypt1: 枚舉的說，看不出哪裡貪心了。得看看別人怎麼做了。
代碼：
[cpp]
/*
ID: duanjia2
PROG: crypt1
LANG: C++
*/
#include<iostream>
#include<algorithm>
#include<string.h>
#include<fstream>
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<n;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++;
}
} www.2cto.com
fout<<cnt<<endl;
// system("pause");
return 0;
}
