posted @
2010-12-23 16:02 小阮 阅读(327) |
评论 (0) |
编辑 收藏
模拟1到359步就可以了。

/**//*
ID: lorelei
TASK: spin
LANG: C++
*/

#include <fstream>

using namespace std;


typedef struct Gap
{
int start;
int span;
}Gap;

int gap_num[5];
int speed[5];
Gap gaps[5][5];

ifstream fin;
ofstream fout;


void move()
{
int i,j;
for(i=0; i<5; ++i)
for(j=0; j<gap_num[i]; ++j)
gaps[i][j].start = (gaps[i][j].start+speed[i])%360;
}

int tmp[360];

bool check()
{
int i,j,k;
for(i=0; i<360; ++i) tmp[i]=0;

for(i=0; i<5; ++i)
for(j=0; j<gap_num[i]; ++j)
for(k=0; k<=gaps[i][j].span; ++k)
tmp[(gaps[i][j].start+k)%360]++;

for(i=0; i<360; ++i)
if(tmp[i]==5)
return true;

return false;
}


int main()
{
int i,j;
fin.open("spin.in");
fout.open("spin.out");


for(i=0; i<5; ++i)
{
fin>>speed[i];
fin>>gap_num[i];
for(j=0; j<gap_num[i]; ++j)
fin>>gaps[i][j].start>>gaps[i][j].span;
}


if(check())
{
fout<<0<<endl;
return 0;
}


for(i=1; i<360; ++i)
{
move();

if(check())
{
fout<<i<<endl;
return 0 ;
}
}
fout<<"none"<<endl;

return 0;
}
posted @
2010-12-23 14:46 小阮 阅读(206) |
评论 (0) |
编辑 收藏
设要付的钱是M,存在一个付钱的上限V,对于0到V是一个多重背包问题(每种货币有限制数量)
对于给多的部分, 即V-M,由于还钱时候,每种货币没有数量限制,是一个完全背包问题。
参考这篇文章,
http://www.cppblog.com/Davidlrzh/articles/135614.html证明了,V 最大为 M + v[i]*v[i] (v[i]是货币中最大价值的一个)
#include <iostream>

using namespace std;

const int MAXN = 25000;
const int MAX = 105;
const int INF = 99999;

int v[MAX], n[MAX];
int f[MAXN], g[MAXN];

int V,N;


void ZeroOnePack(int c, int w, int dp[])
{
for(int v=V; v>=c; --v)
if(dp[v-c]+w < dp[v])
dp[v] = dp[v-c]+w;
return;
}


void CompletePack(int c, int w, int dp[])
{
for(int v=c; v<=V; ++v)
if(dp[v-c]+w < dp[v])
dp[v] = dp[v-c]+w;
return;
}


void MultiplePack(int c, int w, int m, int dp[])
{

if(m*c>=V)
{
CompletePack(c, w, dp);
return;
}
int k=1;

while(k<m)
{
ZeroOnePack(k*c, k, dp);
m-=k;
k*=2;
}
ZeroOnePack(m*c, m, dp);
}

int M;


int main()
{
int i, max=0;
cin>>N>>M;


for(i=1; i<=N; ++i)
{
cin>>v[i];
if(v[i]>max)
max=v[i];
}

for(i=1; i<=N; ++i)
cin>>n[i];

V = M + max*max;

for(i=1; i<V; ++i)
f[i] = INF;

for(i=1; i<=N; ++i)
MultiplePack(v[i], 1, n[i], f);

V = max*max;

for(i=1; i<V; ++i)
g[i] = INF;

for(i=1; i<=N; ++i)
CompletePack(v[i], 1, g);

V = M+max*max;
int min = INF;
for(i=M; i<V; ++i)
if(f[i]+g[i-M]<min)
min = f[i]+g[i-M];

if(min!=INF)
cout<<min<<endl;
else
cout<<-1<<endl;

return 0;
}


posted @
2010-12-23 13:10 小阮 阅读(308) |
评论 (0) |
编辑 收藏
多重背包问题, 参考<<背包问题9讲>>
#include <iostream>

using namespace std;

const int MAXN = 120005;
const int MAX = 15;

int c[MAX] , n[MAX];
int f[MAXN];

int N,V;


inline int max(int a, int b)
{
return a>b? a: b;
}


void ZeroOnePack(int c, int w)
{
for(int v=V; v>=c; v--)
f[v] = max(f[v], f[v-c]+w);
return;
}


void CompletePack(int c, int w)
{
for(int v=c; v<=V; ++v)
f[v] = max(f[v], f[v-c]+w);
return;
}


void MultiplePack(int c, int w, int m)
{

if(m*c>=V)
{
CompletePack(c, w);
return ;
}
int k=1;

while(k<m)
{
ZeroOnePack(k*c, k*w);
m -= k;
k*=2;
}
ZeroOnePack(m*c, m*w);
return ;
}


int main()
{
int i;

while(cin>>V&&cin>>N)
{
if(!V&&!N) continue;

for(i=0; i<=V; ++i) f[i]=0;

for(i=1; i<=N; ++i)
cin>>n[i]>>c[i];

for(i=1; i<=N; ++i)
MultiplePack(c[i], c[i], n[i]);

cout<<f[V]<<endl;
}
return 0;
}
posted @
2010-12-23 11:05 小阮 阅读(156) |
评论 (0) |
编辑 收藏
DP
f[i][j] 表示长度为i 的01串,1的个数不多于j的个数。
则对于第i位是0还是1,可分为两个子状态 f[i][j] = f[i-1][[j] + f[i-1][j-1]

/**//*
ID: lorelei3
TASK: kimbits
LANG: C++
*/

#include <fstream>

using namespace std;

long long N,L,I;
long long f[100][100];


int main()
{

int i,j;

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

fin>>N>>L>>I;

for(i=0; i<=N; ++i)
f[0][i] = f[i][0] = 1;

for(i=1; i<=N; ++i)
for(j=1; j<=N; ++j)
f[i][j] = f[i-1][j] + f[i-1][j-1];

for(i=N; i>=1; --i)

if(I>f[i-1][L])
{
fout<<"1";
I -= f[i-1][L];
--L;
}else
fout<<"0";

fout<<endl;
return 0;
}

posted @
2010-12-22 13:03 小阮 阅读(346) |
评论 (0) |
编辑 收藏

/**//*
ID: lorelei3
TASK: zerosum
LANG: C++
*/

#include <fstream>
#include <iostream>

using namespace std;


const int num[] =
{1, 2, 3, 4, 5, 6, 7, 8, 9};

const char op[3] =
{' ', '+' , '-'};
char ans[8];
int n,N;

ifstream fin;
ofstream fout;


int solve()
{
int sum = 0, last=1, flag=1;
for(int i=0, j=1; i<n-1; ++i, ++j)

if(ans[i] == op[1])
{
sum += last;
flag = 1;
last = num[j];

}else if(ans[i] == op[2])
{
sum += last;
flag = -1;
last = -num[j];

}else if(ans[i] == op[0])
{
last *=10;
last += flag*num[j];
}
sum += last;
return sum;
}


void output()
{
fout<<1;

for(int i=0; i<n-1; ++i)
{
fout<<ans[i]<<num[i+1];
}
fout<<endl;
}



void dfs(int k)
{

if(k==n-1)
{
int sum = solve();

if(sum==0)
{
// solve();
output();
}
}else

for(int i=0; i<3; ++i)
{
ans[k] = op[i];
dfs(k+1);
}
}


int main()
{
fin.open("zerosum.in");
fout.open("zerosum.out");
fin>>n;
dfs(0);
return 0;
}
posted @
2010-12-21 10:18 小阮 阅读(392) |
评论 (0) |
编辑 收藏

/**//*
ID: lorelei3
TASK: nocows
LANG: C++
*/

#include <fstream>

using namespace std;

const int K = 105;
const int N = 205;
const int MOD = 9901;

int dp[K][N];
int s[K][N];

int k,n;


int main()
{

int i,j,m,c;

ifstream in("nocows.in");
ofstream out("nocows.out");

in>>n>>k;

dp[1][1]=1;


for(i=2; i<=k; ++i)
{
for(j=1; j<=n; j+=2)

for(m=1; m<=j-1-m; m+=2)
{
if(m==j-1-m) c=1;
else c=2;

dp[i][j] += c* ( dp[i-1][m]*s[i-2][j-1-m] +
dp[i-1][j-1-m]*s[i-2][m] +
dp[i-1][m]*dp[i-1][j-1-m] );
dp[i][j] %= MOD;
}

for(j=0; j<=n; ++j)
{
s[i-1][j] += dp[i-1][j] + s[i-2][j];
s[i-1][j] %= MOD;
}
}

out<<dp[k][n]<<endl;
return 0;
}
posted @
2010-12-21 10:17 小阮 阅读(193) |
评论 (0) |
编辑 收藏

/**//*
ID: lorelei3
TASK: prefix
LANG: C++
*/

#include <fstream>
#include <string>

using namespace std;

const int MAXL = 200;
const int MAXN = 100000;

string prim[MAXL+1];
int d[MAXL+1];
int m;
int ans;
string s;


int main()
{
int i,j,k, length;
string t;
ifstream in("prefix.in");
ofstream out("prefix.out");


for(i=0; ;i++)
{
in>>t;
if(t == ".") break;
prim[i]=t;
d[i]=t.length();
}
m = i;

while(in>>t)
s.append(t);
length = s.length();


for(i=0; i<length; ++i)
{


for(j=0; j<m; ++j)
{
if(i+d[j]>length) continue;

else
{
bool f = false;
for(k=0; k<d[j]; ++k)

if(s[i+k] != prim[j][k])
{
f = true;
break;
}
if(!f) ans = ans>i+d[j] ? ans : i+d[j];

}
}
if(i+1>ans) break;
}

out<<ans<<endl;

return 0;
}


posted @
2010-12-21 10:16 小阮 阅读(487) |
评论 (1) |
编辑 收藏
每次相乘的结果去掉尾部的0 之后, mod 10000, 仅保留五位.

/**//*
ID: lorelei3
TASK: fact4
LANG: C++
*/

#include <fstream>

using namespace std;

int n;


int main()
{

unsigned long res = 1;
ifstream fin("fact4.in");
ofstream fout("fact4.out");

fin>>n;



for(int i=2; i<=n; ++i)
{
res *= i;
while(res%10==0)
res /=10;
res %= 100000 ;
}

fout<< res%10 <<endl;
return 0;
}
posted @
2010-12-21 10:14 小阮 阅读(133) |
评论 (0) |
编辑 收藏
其实类似可重背包问题, f[i] = min {f[i-cost[j]] + 1}
i表示背包容量,
cost[j]表示 第j种物品的消耗.

/**//*
ID: lorelei
TASK: stamps
LANG: C++
*/

#include <fstream>

using namespace std;

const int MAXF = 2000000;
const int MAXN = 55;
const int INF = 0x7FFFFFFF;

int f[MAXF], cost[MAXN];
int N, K;


int main()
{
int i,j;

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

fin>>K>>N;

f[0] = 0 ;

for(i=1; i<MAXF; ++i)
f[i] = INF;

for(i=1; i<=N; ++i)
fin>>cost[i];


for(j=1; j<MAXF; ++j)
{

for(i=1; i<=N; ++i)
{
if(cost[i]<=j && f[j-cost[i]]+1 < f[j])
f[j] = f[j-cost[i]]+1;
}

if(f[j]>K)
{
fout<<j-1<<endl;
break;
}
}
return 0;
}


posted @
2010-12-20 11:14 小阮 阅读(137) |
评论 (0) |
编辑 收藏