A:消失之物
背包變種，設n為物品數量，nums[i]為物品的重量，dp1[i][j] 為前i個物品放入容量為j的背包中的方案數目，那么顯然有：
dp1[i][j] = sum{dp1[i-1][j-nums[i]]};
那么所有的物品放入容量為j的數目是dp1[n][j]；
令dp2[i][j]為除去第i個物品，放入容量為j的背包中的方案數目：
dp2[i][j] = dp1[n][j] - dp2[i][j-nums[i]]，表示從選擇所有物品裝的方案中，篩去包含i物品的方案數
代碼：
#include <stdio.h>
#include <string.h>
const int N = 2002;
int dp[N];
int dp2[N];
int n,m;
int nums[N];
void ZeroOnePage()
{
}
void Test()
{
for(int i = 1; i<= n; ++i)
{
scanf("%d",&nums[i]);
}
memset(dp,0,sizeof(dp));
memset(dp2,0,sizeof(dp2));
dp[0] = 1;
for(int i = 1; i <= n; ++i)//前i個物品
{
for(int j = m; j >= nums[i]; --j)
{
dp[j] = (dp[j] + dp[j - nums[i]])%10;
}
}
for(int j = 0; j <= m; ++j)
dp2[j] = dp[j];
for(int i = 1; i <= n; ++i)//前i個物品
{
for(int j = nums[i]; j <= m; ++j)
{
dp2[j] = ((dp[j] - dp2[j - nums[i]])%10 + 10)%10;
}
for(int j = 1; j <= m; ++j)
{
printf("%d",dp2[j]);
}
printf("\n");
for(int j = 0; j <= m; ++j)
dp2[j] = dp[j];
}
}
int main()
{
while(scanf("%d %d",&n,&m) != EOF)
{
Test();
}
return 0;
}F：永遠挑戰
最短路SPFA
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int INF = 1 << 25;
const int N = 100005;
struct Edge
{
int to;
int weight;
friend bool operator < (const Edge& _e1,const Edge& _e2)
{
return _e1.weight < _e2.weight;
}
};
vector<Edge> vecGraph[N];
map<int,int> Map;
int n,m;
void Input()
{
for(int i = 0; i < n; ++i)
{
vecGraph[i].clear();
}
Map.clear();
int a,b,w;
Edge edge1;
for(int i = 0; i < m; ++i)
{
scanf("%d %d %d",&(a),&(b),&(w));
--(a);
--(b);
edge1.to = b;
edge1.weight = w;
Map[a*N+b] = w;
vecGraph[a].push_back(edge1);
}
//debug
/**//*for(int i = 0 ; i < p; ++i)
{
printf("%d: ",i);
for(int j = 0 ; j < vecGraph[i].size(); ++j)
printf("%d(%d) ",vecGraph[i][j].to,vecGraph[i][j].weight);
printf("\n");
}*/
}
int distances[N];
bool visited[N];
void SPFA(const int _s,int &_ans)
{
queue<int> Queue;
Queue.push(_s);
bool IsInQueue[N];
for(int i = 0; i < n; ++i)
{
distances[i] = INF;
IsInQueue[i] = false;
}
int to;
Edge tmpEdge;
IsInQueue[_s] = true;
distances[_s] = 0;
int curState;
//do
while(!Queue.empty())
{
curState = Queue.front();
Queue.pop();
for(int i = 0; i < vecGraph[curState].size(); ++i)
{
to = vecGraph[curState][i].to;
map<int,int>::iterator iter = Map.find(curState*N+to);
if(iter != Map.end() && distances[to] > distances[curState] + iter->second)
{
distances[to] = distances[curState] + iter->second;
if(!IsInQueue[to])
{
IsInQueue[to] = true;
Queue.push(to);
}
}
}
IsInQueue[curState] = false;
}
_ans = distances[n-1];
}
void solve()
{
int ans = INF;
SPFA(0,ans);
printf("%d\n",ans);
}
void Test()
{
Input();
solve();
}
int main()
{
while(scanf("%d %d",&n,&m) != EOF)
Test();
return 0;
}
G：吉他英雄
置換群計數
#include <stdio.h>
#include <algorithm>
using namespace std;
int nums[60];
int n;
void Test()
{
scanf("%d",&n);
int sum = 0;
for(int i = 0; i < n; ++i)
{
scanf("%d",&nums[i]);
sum += nums[i];
}
sort(nums,nums+n);
double ans = sum + nums[n-2];
ans /= 2;
printf("%.6lf\n",ans);
}
int main()
{
int tc = 0;
scanf("%d",&tc);
for(int i = 0; i < tc;++i)
{
Test();
}
return 0;
}
I:我愛你啊
狀態機，從前面一直按順序匹配則可
#include <stdio.h>
#include <string.h>
char chs[10] = "luvletter";
char context[100005];
int len;
int cnt;
void runState(char* _context,int _begin)
{
int state = 0;
int i = _begin;
int pos[9] = {0};
while(i < len)
{
if(_context[i] == chs[state])
{
pos[state] = i;
++state;
if(state == 9)
{
cnt++;
state = 0;
}
}
++i;
}
}
int main()
{
int tc = 0;
//freopen("data2.txt","r",stdin);
scanf("%d",&tc);
for(int i = 0; i < tc; ++i)
{
while(gets(context),len = strlen(context),len == 0);
int k = 0;
cnt = 0;
runState(context,0);
printf("%d\n",cnt);
}
if(tc == 0)
printf("0\n");
return 0;
}
J：隨機種子
首先要滿足條件2：
a 的十進制表示包含0到9，而且數的范圍是10^16，故先構造一數滿足此條件：
設d為數字X的長度，那么有：
1234567890*10^d，
這樣可以在10^d內湊數字，而且進一步知道，一個數X在一個長度為X的區間里面，必然能找到一個被X整除的數，故此可構造空間
[1234567890*10^d，1234567890*10^d+ X - 1]
然后枚舉測試
#include <stdio.h>
#include <string.h>
#include <math.h>
const long long K = 1234567890;
int getLen(int _value)
{
int cnt = 0;
while(_value > 0)
{
++cnt;
_value /= 10;
}
return cnt;
}
void getAns(int _x)
{
int d = getLen(_x);
long long begin = K*(int)(pow(10.0,(double)d));
long long end = begin + _x -1;
for(long long j = begin; j <= end; ++j)
{
if(j % _x == 0)
{
printf("%lld\n",j);
return;
}
}
printf("-1\n");
}
int main()
{
//freopen("data5.txt","w",stdout);
int tc;
int X;
scanf("%d",&tc);
for(int i = 0; i < tc; ++i)
{
scanf("%d",&X);
if(X == 0)
{
printf("-1\n",X);
continue;
}
getAns(X);
}
return 0;
}
posted on 2011-04-11 15:59
bennycen 閱讀(1896)
評論(3) 編輯 收藏 引用 所屬分類:
算法題解