|
[算了 考虑了一下 还是不贴了 以免打扰大家思维的乐趣。]
贴几个我自己的代码。
07 创建目录
#include<stdio.h>
#include<map>
#include<string>
using namespace std;
class folder
{
public:
map<string,folder*> Map;
folder(){}
} *root,*p,*q;
int main()
{
int _,t,n,m;
char s[110000];
scanf("%d",&_);
for(t=1; t<=_; t++)
{
scanf("%d%d",&n,&m);
int ans=0;
root=new folder();
for(int i=0; i<n+m; i++)
{
scanf("%s",s);
p=root;
for(int j=0;;)
{
string w="";
for(j++; s[j]!=0 && s[j]!='/'; j++)
w+=s[j];
if(p->Map.find(w)==p->Map.end())
{
p->Map[w]=new folder();
if(i>=n)
ans++;
}
p=p->Map[w];
if(s[j]==0)break;
}
}
printf("Case #%d: %d\n",t,ans);
}
return 0;
}
09 绝对序号
#include<stdio.h>
#define mod 100003
long long int dp[510][510],ans[510];
long long int c[510][510];
void init()
{
for(int i=0; i<=500; i++)
for(int j=0; j<=i; j++)
if(j==0 || j==i)
c[j]=1;
else
c[j]=(c[i-1][j]+c[i-1][j-1])%mod;
for(int i=2; i<=500; i++)
{
dp[1]=ans=1;
for(int j=2; j<i; j++)//the rank of i in that set
{
for(int k=1; k<j; k++)//the rank of j in that set
dp[j]+=dp[j][k]*c[i-j-1][j-k-1]%mod;
dp[j]%=mod;
ans+=dp[j];
}
ans%=mod;
}
}
int main()
{
int _,t,n;
init();
scanf("%d",&_);
for(t=1; t<=_; t++)
{
scanf("%d",&n);
printf("Case #%d: %I64d\n",t,ans[n]);
}
return 0;
}
18 修建栅栏
#include<stdio.h>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
int n;
long long int a[100],l,g;
long long int gcd(long long int x,long long int y){return y?gcd(y,x%y):x;}
int dp[100010];
priority_queue<pair<int,long long int> > q;
int main()
{
int t,_;
scanf("%d",&_);
for(t=1; t<=_; t++)
{
scanf("%I64d%d",&l,&n);
g=0;
for(int i=0; i<n; i++)
{
scanf("%I64d",&a);
g=gcd(g,a);
}
sort(a,a+n);
printf("Case #%d: ",t);
if(l%g)
{
puts("IMPOSSIBLE");
continue;
}
memset(dp,-1,sizeof(dp));
dp[0]=0;
q.push(make_pair(0,0));
n--;
int u=a[n];
while(!q.empty())
{
int c=q.top().first;
long long int l1=-q.top().second;
q.pop();
if(dp[c]!=l1)continue;
for(int i=0; i<n; i++)
{
long long int l2=c+a,cost=dp[c]+1;
if(l2>=u)l2-=u,cost--;
if(dp[l2]==-1 || dp[l2]>cost)
{
dp[l2]=cost;
q.push(make_pair((int)(l2),-dp[l2]));
}
}
}
long long int w=l%a[n];
long long int ans=dp[w]+(l-w)/a[n];
printf("%I64d\n",ans);
fprintf(stderr,"%d\n",t);
}
return 0;
}
[ 本帖最后由 trichromatic 于 2010-12-26 22:00 编辑 ]
|
