posted @
2010-12-23 16:02 小阮 阅读(314) |
评论 (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 小阮 阅读(200) |
评论 (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 小阮 阅读(302) |
评论 (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 小阮 阅读(151) |
评论 (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 小阮 阅读(340) |
评论 (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 小阮 阅读(386) |
评论 (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 小阮 阅读(188) |
评论 (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 小阮 阅读(484) |
评论 (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 小阮 阅读(127) |
评论 (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 小阮 阅读(134) |
评论 (0) |
编辑 收藏