DIV1 250pt
题意：以linux系统中文件系统的路径表示方法为背景，告诉你某文件的绝对路径和当前位置，求相对路径。具体看样例。
解法：模拟题，不多说。每次碰到STL的题自己的代码都会显得很sb...同时速度真的太不够了....
tag:模拟题
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "RelativePath.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <set>
#include <queue>
#include <bitset>
#include <list>
#include <string>
#include <utility>
#include <map>
#include <ctime>
#include <stack> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define CLR1(x) memset(x, -1, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define ALL(t) t.begin(),t.end()
#define zero(x) (((x)>0?(x):-(x))<eps)
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef pair<int, int> pii;
typedef long long int64; const double eps = 1e-;
const double PI = atan(1.0)*;
const int maxint = ; VS p, c;
string temp = "../"; class RelativePath
{
public:
string makeRelative(string pat, string cur){
p.clear(); c.clear();
string s;
for (int i = ; i < pat.size(); ++ i){
s.clear();
while (i < (int)pat.size() && pat[i] != '/'){
s.PB (pat[i]); ++ i;
}
if (s.size()) p.PB (s);
}
for (int i = ; i < cur.size(); ++ i){
s.clear();
while (i < cur.size() && cur[i] != '/'){
s.PB (cur[i]); ++ i;
}
if (s.size()) c.PB (s);
} int t1 = , t2 = ;
while (t1 < p.size() && t2 < c.size()){
if (p[t1] == c[t2])
++ t1, ++ t2;
else break;
}
string ans; ans.clear();
for (int i = ; i < c.size()-t2; ++ i) ans += temp;
for (int i = t1; i < p.size(); ++ i){
if (i != t1) ans.PB ('/');
ans += p[i];
}
return ans;
} // 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 string &Expected, const string &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 Arg0 = "/home/top/data/file"; string Arg1 = "/home/user/pictures"; string Arg2 = "../../top/data/file"; verify_case(, Arg2, makeRelative(Arg0, Arg1)); }
void test_case_1() { string Arg0 = "/home/user/movies/title"; string Arg1 = "/home/user/pictures"; string Arg2 = "../movies/title"; verify_case(, Arg2, makeRelative(Arg0, Arg1)); }
void test_case_2() { string Arg0 = "/file"; string Arg1 = "/"; string Arg2 = "file"; verify_case(, Arg2, makeRelative(Arg0, Arg1)); }
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(, Arg2, makeRelative(Arg0, Arg1)); }
void test_case_4() { string Arg0 = "/root/root/root"; string Arg1 = "/root"; string Arg2 = "root/root"; verify_case(, Arg2, makeRelative(Arg0, Arg1)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
RelativePath ___test;
___test.run_test(-);
return ;
}
// END CUT HERE
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
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "AllCycleLengths.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <set>
#include <queue>
#include <bitset>
#include <list>
#include <string>
#include <utility>
#include <map>
#include <ctime>
#include <stack> using namespace std; #define clr0(x) memset(x, 0, sizeof(x))
#define clr1(x) memset(x, -1, sizeof(x))
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(t) t.begin(),t.end()
#define zero(x) (((x)>0?(x):-(x))<eps)
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<a<<" "
#define tst1(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef pair<int, int> pii;
typedef map<int, int> mpii;
typedef long long int64; const double eps = 1e-;
const double PI = atan(1.0)*;
const int inf = / ;
const int N = ; int n;
int con[], tcon[]; class AllCycleLengths
{
public:
string findAll(vector <string> arc){
n = sz(arc);
clr0 (con);
set<int> st;
VI a, b;
for (int i = ; i < n; ++ i){
b.clear(); a.clear(); a.pb (i);
int times = ;
while (times <= N){
++ times;
set<int> st;
for (int j = ; j < sz(a); ++ j)
for (int k = ; k < n; ++ k)
if (arc[a[j]][k] == 'Y' && !st.count(k)){
b.pb (k); st.insert(k);
}
for (int j = ; j < sz(b); ++ j)
if (b[j] == i) con[times] = ;
a = b; b.clear();
}
} for (int rec = ; rec < ; ++ rec){
int pos = -, end = -;
for (int i = ; i <= N / ; ++ i){
int ok = , flag = i + rec, times = ;
while (times < && flag + rec < N){
ok = ;
for (int t = ; t < rec; ++ t)
if (con[i+t] != con[flag+t]){
ok = ; break;
}
if (!ok) break;
++ times; flag += rec;
}
if (ok){
pos = i; end = pos + rec - ;
break;
}
}
if (pos == -) continue;
out (pos); string ret; ret.clear();
for (int i = ; i <= end; ++ i){
if (i == pos) ret.pb ('(');
ret.pb (con[i] + '');
}
ret.pb (')');
return ret;
}
return "(0)";
} // 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(); }
//void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0();}
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 string &Expected, const string &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[] = {"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[]))); string Arg1 = "0010010110110(1)"; verify_case(, Arg1, findAll(Arg0)); }
//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)); }
void test_case_1() { string Arr0[] = {"NY", "YN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arg1 = "(01)"; verify_case(, Arg1, findAll(Arg0)); }
void test_case_2() { string Arr0[] = {"NYYYY", "NNYYY", "NNNYY", "NNNNY", "YNNNN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arg1 = "0(1)"; verify_case(, Arg1, findAll(Arg0)); }
void test_case_3() { string Arr0[] = {"NYNNN", "NNYNN", "NNNYN", "NNNNY", "YNNYN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arg1 = "010(1)"; verify_case(, Arg1, findAll(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
//freopen( "a.out" , "w" , stdout );
AllCycleLengths ___test;
___test.run_test(-);
return ;
}
// END CUT HERE