Day1 ： POJ 1029 False coin + POJ 1011 Sticks
计划中的一环：模拟题第一道
题目描述：
The "Gold Bar"bank received information from reliable sources that in their last group of N coins exactly one coin is false and differs in weight from other coins (while all other coins are equal in weight). After the economic crisis they have only a simple balance available (like one in the picture). Using this balance, one is able to determine if the weight of objects in the left pan is less than, greater than, or equal to the weight of objects in the right pan.
In order to detect the false coin the bank employees numbered all coins by the integers from 1 to N, thus assigning each coin a unique integer identifier. After that they began to weight various groups of coins by placing equal numbers of coins in the left pan and in the right pan. The identifiers of coins and the results of the weightings were carefully recorded.
You are to write a program that will help the bank employees to determine the identifier of the false coin using the results of these weightings.
Input
The first line of the input file contains two integers N and K, separated by spaces, where N is the number of coins (2<=N<=1000 ) and K is the number of weightings fulfilled (1<=K<=100). The following 2K lines describe all weightings. Two consecutive lines describe each weighting. The first of them starts with a number Pi (1<=Pi<=N/2), representing the number of coins placed in the left and in the right pans, followed by Pi identifiers of coins placed in the left pan and Pi identifiers of coins placed in the right pan. All numbers are separated by spaces. The second line contains one of the following characters: '<', '>', or '='. It represents the result of the weighting:
'<' means that the weight of coins in the left pan is less than the weight of coins in the right pan,
'>' means that the weight of coins in the left pan is greater than the weight of coins in the right pan,
'=' means that the weight of coins in the left pan is equal to the weight of coins in the right pan.
Output
Write to the output file the identifier of the false coin or 0, if it cannot be found by the results of the given weightings.
Sample Input
5 3
2 1 2 3 4
<
1 1 4
=
1 2 5
=Simple Output
3解释： 刚开始想简单了，只是觉得用f数组标记0/1，初始全部置为0，表示都有可能是假硬币
‘=’的话，把称的两堆变成1，表示不可能是假硬币
‘<’‘>'的话，把没有称的变成1，表示不可能是假硬币
交上以后就WA了，后来师兄说可能会有逻辑上的问题，
例如： 5 3
2 1 2 3 4 >
2 1 3 2 5 <
2 2 3 1 5 < 成功把之前的代码卡掉了555~
所以可以发现，一旦硬币i在之前在重的一堆里，后来在轻的一堆里，那么他一定不是假硬币，反之亦然，所以记录一下之前的大小状态就OK，绿啦
PS：我写的代码自己都看不下去啦（但是我还是要贴上啦啦啦啦）
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
int n,k,m;
int a[10000],b[10000];
char ch;
int f[100000];
bool ff[100000];
int main()
{
scanf("%d%d",&n,&k);
memset(f,0,sizeof(f));
for(int i = 0;i < k; ++i)
{
scanf("%d",&m);
memset(ff,0,sizeof(ff));
for(int j = 0;j < m; ++j) scanf("%d",&a[j]);
for(int j = 0;j < m; ++j) scanf("%d",&b[j]);
cin>>ch;
if(ch == '=')
{
for(int j = 0;j < m; ++j)
f[a[j]] = f[b[j]] = 1;
}
else
{
for(int j = 0;j < m; ++j)
{
ff[a[j]] = 1;
ff[b[j]] = 1;
if(ch == '<')
{
if(f[a[j]] == -2) f[a[j]] = 1;
if(!f[a[j]]) f[a[j]] = -1;
if(f[b[j]] == -1) f[b[j]] = 1;
if(!f[b[j]]) f[b[j]] = -2;
}
else
{
if(f[b[j]] == -2) f[b[j]] = 1;
if(!f[b[j]]) f[b[j]] = -1;
if(f[a[j]] == -1) f[a[j]] = 1;
if(!f[a[j]]) f[a[j]] = -2;
}
}
for(int j = 1;j <= n; ++j)
if(!ff[j]) f[j] = 1;
}
}
bool t = 0;
bool tt = 1;
int x;
for(int i = 1;i <= n; ++i)
{
if(f[i] != 1)
{
if(t == 1) tt = 0;
x = i;
t = 1;
}
}
if(t && tt) printf("%d\n",x);
else printf("0\n");
return 0;
}
搜索第一题（这个题剪枝特别多，真恶心~~~)
题目描述
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output
The output should contains the smallest possible length of original sticks, one per line.
Sample Input
9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0
Sample Output
6 5
把自己TLE的代码粘上（其实想到了一部分剪枝，但是无奈依旧T）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N = 1e5;
int n,a[10000],s,l;
bool flag,f[100000];
bool cmp(int x,int y)
{
return x > y;
}
bool check()
{
for(int i = 0;i < n; ++i)
if(!f[i]) return 0;
return 1;
}
void dfs(int x,int t,int k)
{
if(flag) return;
if(k * x == s && check())
{
flag = 1;
return;
}
if(t == x) dfs(x,0,k + 1);
for(int i = 0;i < n; ++i)
{
if(!f[i] && t + a[i] <= x)
{
f[i] = 1;
dfs(x,t + a[i],k);
f[i] = 0;
}
}
}
int main()
{
while(scanf("%d",&n))
{
if(!n) break;
l = 0;
s = 0;
for(int i = 0;i < n; ++i)
{
scanf("%d",&a[i]);
l = max(l,a[i]);
s += a[i];
}
sort(a,a + n,cmp); //从大到小排序，好像并没有优化到，可能是我写的不好
flag = 0;
for(int i = l; i <= s; ++i) //优化1，答案的范围在最小的木棍长度到木棍总长度之间
if(s % i == 0) //优化2，只有能整除才有可能拼成一样长的木棍
{
memset(f,0,sizeof(f));
dfs(i,0,0);
if(flag)
{
printf("%d\n",i);
break;
}
}
}
return 0;
}
------------------------------------------------
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N = 1e5;
int n,a[10000],s,l;
bool flag,f[100000];
bool cmp(int x,int y)
{
return x > y;
}
bool check(int x)
{
int sum = 0;
for(int i = 0;i < n; ++i) if(!f[i]) sum += a[i];
if(sum != x) return 0;
return 1;
}
void dfs(int x,int t,int k,int cnt)
{
if(flag) return; //优化4，找到结果立刻返回
if((k + 1) * x == s && check(x)) //优化9，看剩下的长度之和是不是等于x
{
flag = 1;
return;
}
if(cnt > n) return;
if(t == x) dfs(x,0,k + 1,0);
for(int i = cnt;i < n; ++i) //优化5，从上一个状态开始枚举
{
if(!f[i] && t + a[i] <= x)
{
f[i] = 1;
dfs(x,t + a[i],k,i + 1);
f[i] = 0;
}
}
}
int main()
{
while(scanf("%d",&n))
{
if(!n) break;
l = 0;
s = 0;
for(int i = 0;i < n; ++i)
{
scanf("%d",&a[i]);
l = max(l,a[i]);
s += a[i];
}
sort(a,a + n,cmp); //优化5，从大到小排序
flag = 0;
for(int i = l; i <= s; ++i) //优化1，2,答案的范围在最小的木棍长度到木棍总长度之间
if(s % i == 0) //优化3，只有能整除才有可能拼成一样长的木棍
{
memset(f,0,sizeof(f));
dfs(i,0,0,0);
if(flag)
{
printf("%d\n",i);
break;
}
}
}
return 0;
}
做法：枚举可能的长度len，判断是否可行
好吧，后来迫于无奈去看了题解，发现剪枝有10(假设答案为len,a[i]表示小木棍长度）
1) len <= sum (sum = Σa[i]) （最优性）
2）len >= max(a[i]) （最优性）
由1） 2）确定枚举区间
3) （sum % len）== 0 sum一定能整除len （最优性）
4) 找到结果后立马返回 （这个及以下剪枝均为可行性剪枝）
5) 一根长木棍比几根短木棍拼成的相同长度的木棍用处小，短的木棍更灵活，从大到小对木棍长度排序
6) 用第i根木棍时，从i + 1 往后接，因为根据5），前面的已经被用过了。
7) 从最长的开始搜，如果拼不出len，直接返回，换下一个len继续判断
8）搜到的几根长度之和>len,直接返回
9）判断剩下的几根能否组成相同长度，可以省去一部分搜索
10）相同长度的木棍不要搜索多次，可以提前返回
看的头都疼了555~~~
TLE重复了N次啊，心疼自己QAQ
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int Max = 65;
int sticks[Max]; //存储每根棍子的长度
int note[Max]; //记录当前下标的棍子是否用过
int sticks_len; //要合成的棍子的长度
int sticks_num; // 长度为sticks_len下一共有多少根棍子
int sticks_sum; //所有棍子的总长度
int num;
int dfs(int n, int k, int cnt) { //n为正在合并的棍子的长度，k为当前要处理的木棍的下标，cnt为已经合成好的棍子的数量
if (cnt == num) return 1;
if (n == sticks_len) //已经合并好一根棍子，继续合下一根
return dfs(0,0,cnt+1);
int i,pre = 0; //i是木棍的下标，pre保存重复木棍
for (i = k; i < sticks_num; i++) {
if (note[i] == 0 && n+sticks[i] <= sticks_len && sticks[i] != pre) { //如果当前选择棍子的长度是pre，则下一根选择的棍子的长度要小于pre，降低运行时间
pre = sticks[i];
note[i] = 1;
if (dfs(n+sticks[i], i+1, cnt))
break;
note[i] = 0;
if (k == 0)//如果第一根棍子(最长的那根)不能参与合成，那么其余的棍子也无法合成
return 0;
}
}
if (i == sticks_num)
return 0;
else
return 1;
}
int main() {
while (cin >> sticks_num, sticks_num != 0) {
sticks_sum = 0;
for (int i = 0; i < sticks_num; i++) {
cin >> sticks[i];
sticks_sum += sticks[i];
}
sort(sticks, sticks+sticks_num, greater<int>());
for (sticks_len = sticks[0]; sticks_len <= sticks_sum/2; sticks_len++) { //循环遍历，原棍子长度等于总长度或小于等于总长度的两倍
if (sticks_sum%sticks_len == 0) { //总长度肯定是原棍子长度的倍数
num = sticks_sum/sticks_len;
memset(note, 0, sizeof(int)*sticks_num); //初始化记录数组，所有棍子都没用过
if (dfs(0,0,0)) break;
}
}
if (sticks_len > sticks_sum/2)
cout << sticks_sum << endl;
else
cout << sticks_len << endl;
}
return 0;
}