A Problem Statement
You are given two distinct points A and B in the two-dimensional plane. Your task is to find any point C with the following properties:
C is different from A and B.
Each coordinate of C is an integer between -100 and 100, inclusive.The distance between A and C is strictly greater than the distance between B and C.You are given four ints: x1, y1, x2, and y2. Point A has coordinates (x1,y1) and point B has coordinates (x2,y2). Find the coordinates (x3,y3) of one possible point C with the above properties. Return these coordinates as a vector <int> with two elements: element 0 is x3 and element 1 is y3. In other words, return the vector <int> {x3,y3}.For the constraints given below it is guaranteed that a valid point C always exists. If there are multiple solutions, return any of them.
Class: PointDistance
Method: findPoint
Parameters: int, int, int, int
Returns: vector <int>
Method signature: vector <int> findPoint(int x1, int y1, int x2, int y2)
(be sure your method is public)
题目类型：暴力枚举
算法分析：直接枚举两个点的坐标并计算即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
// BEGIN CUT HERE // END CUT HERE #line 5 "PointDistance.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 LL long long #define ULL unsigned long long #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; const double EPS = 1e-10; class PointDistance { public: vector <int> findPoint(int x1, int y1, int x2, int y2) { vector <int> res; for (int i = -100; i <= 100; i++) { for (int j = -100; j <= 100; j++) { if (i != x1 && j != y1 && i != x2 && j != y2) { if (sqrt ((i - x1) * (i - x1) + (j - y1) * (j - y1)) > sqrt ((i - x2) * (i - x2) + (j - y2) * (j - y2)) + EPS) { res.push_back(i), res.push_back (j); return res; } } } } return res; } // BEGIN CUT HERE public: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); } 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 vector <int> &Expected, const vector <int> &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } } void test_case_0() { int Arg0 = -1; int Arg1 = 0; int Arg2 = 1; int Arg3 = 0; int Arr4[] = {8, 48 }; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); verify_case(0, Arg4, findPoint(Arg0, Arg1, Arg2, Arg3)); } void test_case_1() { int Arg0 = 1; int Arg1 = 1; int Arg2 = -1; int Arg3 = -1; int Arr4[] = {25, -63 }; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); verify_case(1, Arg4, findPoint(Arg0, Arg1, Arg2, Arg3)); } void test_case_2() { int Arg0 = 0; int Arg1 = 1; int Arg2 = 2; int Arg3 = 3; int Arr4[] = {41, 65 }; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); verify_case(2, Arg4, findPoint(Arg0, Arg1, Arg2, Arg3)); } void test_case_3() { int Arg0 = 5; int Arg1 = -4; int Arg2 = -2; int Arg3 = 5; int Arr4[] = {68, 70 }; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); verify_case(3, Arg4, findPoint(Arg0, Arg1, Arg2, Arg3)); } void test_case_4() { int Arg0 = -50; int Arg1 = -50; int Arg2 = 50; int Arg3 = -50; int Arr4[] = {67, 4 }; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); verify_case(4, Arg4, findPoint(Arg0, Arg1, Arg2, Arg3)); } void test_case_5() { int Arg0 = -50; int Arg1 = 50; int Arg2 = -49; int Arg3 = 49; int Arr4[] = {73, -25 }; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); verify_case(5, Arg4, findPoint(Arg0, Arg1, Arg2, Arg3)); } // END CUT HERE }; // BEGIN CUT HERE int main() { PointDistance ___test; ___test.run_test(-1); return 0; } // END CUT HERE |
B Problem Statement
Cat Noku has just finished writing his first computer program. Noku's computer has m memory cells. The cells have addresses 0 through m-1. Noku's program consists of n instructions. The instructions have mutually independent effects and therefore they may be executed in any order. The instructions must be executed sequentially (i.e., one after another) and each instruction must be executed exactly once.
You are given a description of the n instructions as a vector <string> with n elements. Each instruction is a string of m characters. For each i, character i of an instruction is '1' if this instruction accesses memory cell i, or '0' if it does not.
Noku's computer uses caching, which influences the time needed to execute an instruction. More precisely, executing an instruction takes k^2 units of time, where k is the number of new memory cells this instruction accesses. (I.e., k is the number of memory cells that are accessed by this instruction but have not been accessed by any previously executed instruction. Note that k may be zero, in which case the current instruction is indeed executed in 0 units of time.)
Noku's instructions can be executed in many different orders. Clearly, different orders may lead to a different total time of execution. Find and return the shortest amount of time in which it is possible to execute all instructions.
Definition
Class: OrderOfOperationsDiv2
Method: minTime
Parameters: vector <string>
Returns: int
Method signature: int minTime(vector <string> s)
(be sure your method is public)
题目类型：数位DP
算法分析：dp[i]表示状态为i时的最小运行时间，初始化i != 0, dp[i] = INF，dp[0] = 0。状态转移方程为dp[i|one_instruction] = min (dp[i|one_instruction], dp[i] + differ(i and one_instruction) ^ 2)。最后输出dp[final_state]即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
// BEGIN CUT HERE // END CUT HERE #line 5 "OrderOfOperationsDiv2.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 LL long long #define ULL unsigned long long #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; const int INF = 0x7fffffff; int dp[1<<21], val[66]; class OrderOfOperationsDiv2 { public: int minTime(vector <string> s) { int n = s.size (), m = s[0].size (); int tot = (1 << 21); fill (dp, dp + tot, INF), fill (val, val + 66, 0); dp[0] = 0; int all = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) val[i] |= ((s[i][j] - '0') << j); all |= val[i]; } for (int i = 0; i <= all; i++) { bitset <66> ta (i); for (int j = 0; j < n; j++) if (dp[i] < INF) { int temp = i | val[j]; bitset <66> tb (temp); int tota = ta.count (), totb = tb.count (); if (i != temp) dp[temp] = min (dp[temp], dp[i] + (tota - totb) * (tota - totb)); } } return dp[all]; } // BEGIN CUT HERE public: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) 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[] = { "111", "001", "010" }; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 3; verify_case(0, Arg1, minTime(Arg0)); } void test_case_1() { string Arr0[] = { "11101", "00111", "10101", "00000", "11000" }; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 9; verify_case(1, Arg1, minTime(Arg0)); } void test_case_2() { string Arr0[] = { "11111111111111111111" }; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 400; verify_case(2, Arg1, minTime(Arg0)); } void test_case_3() { string Arr0[] = { "1000", "1100", "1110" }; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 3; verify_case(3, Arg1, minTime(Arg0)); } void test_case_4() { string Arr0[] = { "111", "111", "110", "100" }; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 3; verify_case(4, Arg1, minTime(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE int main() { OrderOfOperationsDiv2 ___test; ___test.run_test(-1); return 0; } // END CUT HERE |
- hdu1003：下一篇 »