SRM 405(1-250pt, 1-500pt)

DIV1 250pt

题意：以linux系统中文件系统的路径表示方法为背景，告诉你某文件的绝对路径和当前位置，求相对路径。具体看样例。

解法：模拟题，不多说。每次碰到STL的题自己的代码都会显得很sb...同时速度真的太不够了....

tag:模拟题

  1 // BEGIN CUT HERE
  2 /*
  3  * Author:  plum rain
  4  * score :
  5  */
  6 /*
  7 
  8  */
  9 // END CUT HERE
 10 #line 11 "RelativePath.cpp"
 11 #include <sstream>
 12 #include <stdexcept>
 13 #include <functional>
 14 #include <iomanip>
 15 #include <numeric>
 16 #include <fstream>
 17 #include <cctype>
 18 #include <iostream>
 19 #include <cstdio>
 20 #include <vector>
 21 #include <cstring>
 22 #include <cmath>
 23 #include <algorithm>
 24 #include <cstdlib>
 25 #include <set>
 26 #include <queue>
 27 #include <bitset>
 28 #include <list>
 29 #include <string>
 30 #include <utility>
 31 #include <map>
 32 #include <ctime>
 33 #include <stack>
 34 
 35 using namespace std;
 36 
 37 #define CLR(x) memset(x, 0, sizeof(x))
 38 #define CLR1(x) memset(x, -1, sizeof(x))
 39 #define PB push_back
 40 #define SZ(v) ((int)(v).size())
 41 #define ALL(t) t.begin(),t.end()
 42 #define zero(x) (((x)>0?(x):-(x))<eps)
 43 #define out(x) cout<<#x<<":"<<(x)<<endl
 44 #define tst(a) cout<<#a<<endl
 45 #define CINBEQUICKER std::ios::sync_with_stdio(false)
 46 
 47 typedef vector<int> VI;
 48 typedef vector<string> VS;
 49 typedef vector<double> VD;
 50 typedef pair<int, int> pii;
 51 typedef long long int64;
 52 
 53 const double eps = 1e-8;
 54 const double PI = atan(1.0)*4;
 55 const int maxint = 2139062143;
 56 
 57 VS p, c;
 58 string temp = "../";
 59 
 60 class RelativePath
 61 {
 62     public:
 63         string makeRelative(string pat, string cur){
 64             p.clear(); c.clear();
 65             string s;
 66             for (int i = 0; i < pat.size(); ++ i){
 67                 s.clear();
 68                 while (i < (int)pat.size() && pat[i] != '/'){
 69                     s.PB (pat[i]); ++ i;
 70                 }
 71                 if (s.size()) p.PB (s); 
 72             }
 73             for (int i = 0; i < cur.size(); ++ i){
 74                 s.clear();
 75                 while (i < cur.size() && cur[i] != '/'){
 76                     s.PB (cur[i]); ++ i;
 77                 }
 78                 if (s.size()) c.PB (s);
 79             }
 80 
 81             int t1 = 0, t2 = 0;
 82             while (t1 < p.size() && t2 < c.size()){
 83                 if (p[t1] == c[t2])
 84                     ++ t1, ++ t2;
 85                 else break;
 86             }
 87             string ans; ans.clear();
 88             for (int i = 0; i < c.size()-t2; ++ i) ans += temp;
 89             for (int i = t1; i < p.size(); ++ i){
 90                 if (i != t1) ans.PB ('/');
 91                 ans += p[i];
 92             }
 93             return ans;
 94         }
 95         
 96 // BEGIN CUT HERE
 97     public:
 98     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(); }
 99     private:
100     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(); }
101     void verify_case(int Case, const string &Expected, const string &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "	Expected: "" << Expected << '"' << endl; cerr << "	Received: "" << Received << '"' << endl; } }
102     void test_case_0() { string Arg0 = "/home/top/data/file"; string Arg1 = "/home/user/pictures"; string Arg2 = "../../top/data/file"; verify_case(0, Arg2, makeRelative(Arg0, Arg1)); }
103     void test_case_1() { string Arg0 = "/home/user/movies/title"; string Arg1 = "/home/user/pictures"; string Arg2 = "../movies/title"; verify_case(1, Arg2, makeRelative(Arg0, Arg1)); }
104     void test_case_2() { string Arg0 = "/file"; string Arg1 = "/"; string Arg2 = "file"; verify_case(2, Arg2, makeRelative(Arg0, Arg1)); }
105     void test_case_3() { string Arg0 = "/a/b/a/b/a/b"; string Arg1 = "/a/b/a/a/b/a/b"; string Arg2 = "../../../../b/a/b"; verify_case(3, Arg2, makeRelative(Arg0, Arg1)); }
106     void test_case_4() { string Arg0 = "/root/root/root"; string Arg1 = "/root"; string Arg2 = "root/root"; verify_case(4, Arg2, makeRelative(Arg0, Arg1)); }
107 
108 // END CUT HERE
109 
110 };
111 
112 // BEGIN CUT HERE
113 int main()
114 {
115 //    freopen( "a.out" , "w" , stdout );    
116     RelativePath ___test;
117     ___test.run_test(-1);
118        return 0;
119 }
120 // END CUT HERE
View Code

 DIV1 500pt

题意：对于一个边权均为1的强连通图，每两点之间有且仅有一条路。若能从任意点走x步之后回到该点，则称x为幸运数。用一个数列a[](0-based)表示是否是幸运数，如果i为幸运数a[i-1] = 1，否则a[i-1] = 0。可以证明，a[]一定会出现循环，找出最小的循环节和它最早出现的位置。比如“0011011111111”可以表示成"00110111(11)"，也可以表示成 "00110(1)"，但是要返回后者。n <= 30。

解法：首先，给出两个结论：1、若x为幸运数，则x一定是a[]的循环节之一；2、若x，y均为a[]的循环节，则gcd(x, y)也为a[]的循环节；3、若x，y均为循环节，则第一个循环节出现的位置不会在x*y之后。

　　　那么，这道题的数据范围就被限制出来了。循环节最长为30，返回的答案长度最长为900 + 30 + 2。所以，直接暴力2000以内所有的数是否是幸运数，然后再暴力枚举循环节长度和循环起始位置即可。。。。。。

tag：think, good

  1 // BEGIN CUT HERE
  2 /*
  3  * Author:  plum rain
  4  * score :
  5  */
  6 /*
  7 
  8  */
  9 // END CUT HERE
 10 #line 11 "AllCycleLengths.cpp"
 11 #include <sstream>
 12 #include <stdexcept>
 13 #include <functional>
 14 #include <iomanip>
 15 #include <numeric>
 16 #include <fstream>
 17 #include <cctype>
 18 #include <iostream>
 19 #include <cstdio>
 20 #include <vector>
 21 #include <cstring>
 22 #include <cmath>
 23 #include <algorithm>
 24 #include <cstdlib>
 25 #include <set>
 26 #include <queue>
 27 #include <bitset>
 28 #include <list>
 29 #include <string>
 30 #include <utility>
 31 #include <map>
 32 #include <ctime>
 33 #include <stack>
 34 
 35 using namespace std;
 36 
 37 #define clr0(x) memset(x, 0, sizeof(x))
 38 #define clr1(x) memset(x, -1, sizeof(x))
 39 #define pb push_back
 40 #define sz(v) ((int)(v).size())
 41 #define all(t) t.begin(),t.end()
 42 #define zero(x) (((x)>0?(x):-(x))<eps)
 43 #define out(x) cout<<#x<<":"<<(x)<<endl
 44 #define tst(a) cout<<a<<" "
 45 #define tst1(a) cout<<#a<<endl
 46 #define CINBEQUICKER std::ios::sync_with_stdio(false)
 47 
 48 typedef vector<int> VI;
 49 typedef vector<string> VS;
 50 typedef vector<double> VD;
 51 typedef pair<int, int> pii;
 52 typedef map<int, int> mpii;
 53 typedef long long int64;
 54 
 55 const double eps = 1e-8;
 56 const double PI = atan(1.0)*4;
 57 const int inf = 2139062143 / 2;
 58 const int N = 2000;
 59 
 60 int n;
 61 int con[5000], tcon[5000];
 62 
 63 class AllCycleLengths
 64 {
 65     public:
 66         string findAll(vector <string> arc){
 67             n = sz(arc);
 68             clr0 (con);
 69             set<int> st;
 70             VI a, b;
 71             for (int i = 0; i < n; ++ i){
 72                 b.clear(); a.clear(); a.pb (i);
 73                 int times = 0;
 74                 while (times <= N){
 75                     ++ times;
 76                     set<int> st;
 77                     for (int j = 0; j < sz(a); ++ j)
 78                         for (int k = 0; k < n; ++ k)
 79                             if (arc[a[j]][k] == 'Y' && !st.count(k)){
 80                                 b.pb (k); st.insert(k);
 81                             }
 82                     for (int j = 0; j < sz(b); ++ j)
 83                         if (b[j] == i) con[times] = 1;
 84                     a = b; b.clear();
 85                 }
 86             }
 87 
 88             for (int rec = 1; rec < 31; ++ rec){
 89                 int pos = -1, end = -1;
 90                 for (int i = 1; i <= N / 2; ++ i){
 91                     int ok = 0, flag = i + rec, times = 0;
 92                     while (times < 1000 && flag + rec < N){
 93                         ok = 1;
 94                         for (int t = 0; t < rec; ++ t)
 95                             if (con[i+t] != con[flag+t]){
 96                                 ok = 0; break;
 97                             }
 98                         if (!ok) break;
 99                         ++ times; flag += rec;
100                     }
101                     if (ok){
102                         pos = i; end = pos + rec - 1;
103                         break;
104                     }
105                 }
106                 if (pos == -1) continue;
107                 out (pos);
108 
109                 string ret; ret.clear();
110                 for (int i = 1; i <= end; ++ i){
111                     if (i == pos) ret.pb ('(');
112                     ret.pb (con[i] + '0');
113                 }
114                 ret.pb (')');
115                 return ret;
116             }
117             return "(0)";
118         }
119         
120 // BEGIN CUT HERE
121     public:
122     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(); }
123     //void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0();}
124     private:
125     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(); }
126     void verify_case(int Case, const string &Expected, const string &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "	Expected: "" << Expected << '"' << endl; cerr << "	Received: "" << Received << '"' << endl; } }
127     void test_case_0() { string Arr0[] = {"NNNNNNNNNNNNNNNNNNNNNNYNN", "NNNNNNNNNNNYNNNNNNNNNNNNN", "NNNNNNNNNNNNYNNNNNNNNNNNN", "NNNNNNNYNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNYNNNNNNNNNNN", "NNNNNNYNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNYNNN", "NNNNNNNNNNNNNNNNNNNNNNNNY", "NNYNNNNNNNNNNNYNNNNNNNNNN", "NNNNNNNNNNNNNNNYNNNNNNNNN", "YNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNYNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNYN", "NNNNNNNNYNNNNNNNNNNNNNNNN", "NNYNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNYNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNYNNNN", "NNNYNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNYNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNYNNNNNNNN", "NYNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNYNNNNNNN", "NNNNNNNNNNNNNNNNNNNYNNNNN", "NNNNNYNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNYNNNNNN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "0010010110110(1)"; verify_case(0, Arg1, findAll(Arg0)); }
128     //void test_case_0() { string Arr0[] = {"NYNN", "NNYY", "NNNY", "YNNN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "00110(1)"; verify_case(0, Arg1, findAll(Arg0)); }
129     void test_case_1() { string Arr0[] = {"NY", "YN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "(01)"; verify_case(1, Arg1, findAll(Arg0)); }
130     void test_case_2() { string Arr0[] = {"NYYYY", "NNYYY", "NNNYY", "NNNNY", "YNNNN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "0(1)"; verify_case(2, Arg1, findAll(Arg0)); }
131     void test_case_3() { string Arr0[] = {"NYNNN", "NNYNN", "NNNYN", "NNNNY", "YNNYN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "010(1)"; verify_case(3, Arg1, findAll(Arg0)); }
132 
133 // END CUT HERE
134 
135 };
136 
137 // BEGIN CUT HERE
138 int main()
139 {
140     //freopen( "a.out" , "w" , stdout );    
141     AllCycleLengths ___test;
142     ___test.run_test(-1);
143        return 0;
144 }
145 // END CUT HERE
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/plumrain/p/srm_405.html