250pt：
题目：有一些盒子（不大于50个），每个盒子里有一些大理石（最多50种颜色），然后给定每个盒子里每种颜色大理石的个数（没有为0），求最少操作几步满足：
1：最多只能一个盒子里有多种颜色，叫做jaker
2：每种颜色最多位于一个一个非jaker的盒子里，且每个非jaker的盒子最多只含有一种颜色：
移动一步可以移动一个盒子任意个石头到另外一个。。
思路：如果我们枚举哪个是jaker，那么对于剩下来的盒子，就剩下要不要移动到jaker里的抉择了。。而且：
1： 如果该盒子有多种颜色，那么一定要移动，全部移动到jaker里就行
2： 如果该盒子有只有一种颜色，那么该颜色用过（就是在前面也有一个只有该颜色的）则必须移动，否者不移动
3：空盒子不移动
code：
// BEGIN CUT HERE
/* */
// END CUT HERE
#line 7 "MarblesRegroupingEasy.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#define M0(a) memset(a, 0, sizeof(a))
using namespace std; #define PB push_back
#define MP make_pair #define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII; int vis[], n, m;
vector<string> a;
int work(int nt){
M0(vis);
int ret = ;
for (int i = ; i < n; ++i)
if (i != nt){
int cnt = , p = -;
for (int j = ; j < m; ++j)
if (a[i][j] != '') ++cnt, p = j;
if (cnt == ) continue;
else if (cnt > ) ret ++;
else {
if (!vis[p]) vis[p] = ;
else ++ret;
}
}
return ret;
} class MarblesRegroupingEasy
{
public:
int minMoves(vector <string> b)
{
n = b.size();
m = b[].size();
a = b;
int ret = ;
for (int i = ; i < n; ++i)
ret = min(ret, work(i));
return ret;
} // BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); if ((Case == -) || (Case == )) test_case_4(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { string Arr0[] = {"",
""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, minMoves(Arg0)); }
void test_case_1() { string Arr0[] = {"",
"",
""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, minMoves(Arg0)); }
void test_case_2() { string Arr0[] = {"",
"",
"",
""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, minMoves(Arg0)); }
void test_case_3() { string Arr0[] = {"",
"",
"",
"",
"",
""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, minMoves(Arg0)); }
void test_case_4() { string Arr0[] = {"",
"",
"",
"",
"",
"",
"",
"",
"",
"",
""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, minMoves(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
MarblesRegroupingEasy ___test;
___test.run_test(-);
// system("pause");
return ;
}
// END CUT HERE
500pt:
题目：给定一些一维坐标里的线段，问把他们可以分成多少个子集，每个，子集符合下面情况：
1：任意一个不再子集里的线段与子集相交
2.子集元素都不相交
思路：
因为坐标最大才100，所以以坐标进行统计（类似dp思想）
直接看代码吗，
不然不好说清楚，代码还是很短的。。
// BEGIN CUT HERE
/* */
// END CUT HERE
#line 7 "IntervalSubsets.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std; #define PB push_back
#define MP make_pair
#define M0(a) memset(a, 0, sizeof(a))
#define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII;
int f[]; class IntervalSubsets
{
public:
int numberOfSubsets(vector <int> start, vector <int> finish)
{
int n = start.size();
M0(f);
f[] = ;
for (int i = ; i <= ; ++i){
int L = -;
for (int j = ; j < n; ++j)
if (finish[j] <= i) L = max(start[j], L);
if (L == -)
f[i] = f[i - ];
else
for (int j = ; j < n; ++j)
if (finish[j] >= L && finish[j] <= i) f[i] += f[start[j] - ];
}
return f[];
} // BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); if ((Case == -) || (Case == )) test_case_4(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { int Arr0[] = {,}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {,}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, numberOfSubsets(Arg0, Arg1)); }
void test_case_1() { int Arr0[] = {,,}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {,,}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, numberOfSubsets(Arg0, Arg1)); }
void test_case_2() { int Arr0[] = {,,,,}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {,,,,}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, numberOfSubsets(Arg0, Arg1)); }
void test_case_3() { int Arr0[] = {,,,,,,,,}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {,,,,,,,,}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, numberOfSubsets(Arg0, Arg1)); }
void test_case_4() { int Arr0[] = {, , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {, , , }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, numberOfSubsets(Arg0, Arg1)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
IntervalSubsets ___test;
___test.run_test(-);
// system("pause");
return ;
}
// END CUT HERE