DIV1 250pt
题意：给定一个正整数n(n <= 10^18)，如果n = p^q，其中p为质数，q > 1，则返回vector<int> ans = {p, q}，否则返回ans = {}。
解法：首先，看到题的第一想法是，枚举p。而由于n的范围太大，O(10^9)的复杂度不能接受。又想到，如果题目的限制为q > 2，那么枚举的复杂度就降到了O(10^6)，可以接受了。故得到算法，特判n可不可以表示成p ^ 2的形式(注意判定p是不是质数)，然后再从1到10^6枚举看n能不能表示成p^q，其中q > 2。这样，问题能够得到解决，但是编码复杂度比较高，最后我写出来只拿到了160+分。
然后看了题解，枚举q...因为10^18 < 2^60，所以q的范围小于60。然后枚举就行了。注意三点，一、枚举的方法可以直接用pow来对n开方，也可以二分，前者会涉及浮点数但是好写。二、枚举的过程中算多少次方不需要快速幂，直接算容易写而且时间复杂度够。三、计算过程中要注意会不会爆long long，如果快爆long long直接返回-1或者0。
tag:math
解法一：
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "StrongPrimePower.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 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 = ;
const int maxx = ; int all;
bool vis[maxx];
int prm[maxx]; void sieve(int n)
{
int m = (int)sqrt(n+0.5);
CLR (vis); vis[] = vis[] = ;
for (int64 i = ; i <= m; ++ i) if (!vis[i])
for (int64 j = i*i; j <= n; j += i) vis[j] = ; } int primes(int n)
{
sieve(n);
int ret = ;
for (int i = ; i <= n; ++ i)
if (!vis[i]) prm[ret++] = i;
return ret; } bool ok(int64 n)
{
if (n <= ) return (!vis[n]); for (int i = ; i < all; ++ i)
if ((n % prm[i]) == ){
return ;
}
return ;
} int gao1(int64 n)
{
int64 m = (int64)sqrt(n + 0.5);
if (m*m != n) return -; if (ok(m)) return m;
return -;
} pii gao2(int64 n)
{
int ret;
pii tmp;
for (int i = ; i < all; ++ i) if ((n % prm[i]) == ){
ret = ;
while ((n % prm[i]) == ) {
++ ret;
n /= prm[i];
}
if (ret > && n == ){
tmp.first = prm[i];
tmp.second = ret;
return tmp;
}
else{
tmp.first = -;
return tmp;
}
}
tmp.first = -;
return tmp;
} int64 gao(string n)
{
int64 ret = ;
for (int i = ; i < n.size(); ++ i)
ret = ret * + n[i] - '';
return ret;
} class StrongPrimePower
{
public:
vector <int> baseAndExponent(string N){
all = primes();
int64 n = gao(N); int64 tmp = gao1(n);
vector<int> ans;
ans.clear();
if (tmp != -){
ans.PB ((int)tmp); ans.PB ();
return ans;
}
pii t = gao2(n);
if (t.first != -){
ans.PB (t.first); ans.PB (t.second);
return ans;
}
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(); if ((Case == -) || (Case == )) 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() { string Arg0 = ""; int Arr1[] = {, }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, baseAndExponent(Arg0)); }
void test_case_1() { string Arg0 = ""; int Arr1[] = { }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, baseAndExponent(Arg0)); }
void test_case_2() { string Arg0 = ""; int Arr1[] = { }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, baseAndExponent(Arg0)); }
void test_case_3() { string Arg0 = ""; int Arr1[] = { }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, baseAndExponent(Arg0)); }
void test_case_4() { string Arg0 = ""; int Arr1[] = {, }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, baseAndExponent(Arg0)); }
void test_case_5() { string Arg0 = ""; int Arr1[] = {, }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, baseAndExponent(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
StrongPrimePower ___test;
___test.run_test(-);
return ;
}
// END CUT HERE
解法二：
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "StrongPrimePower.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 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 = ; int64 gao(string n)
{
int64 ret = ;
for (int i = ; i < n.size(); ++ i)
ret = ret * + n[i] - '';
return ret;
} int64 mypow(int64 p, int64 n)
{
unsigned long long ret = ;
for (int i = ; i < n; ++ i){
ret *= p;
if (ret > 1e18) return -;
}
return ret;
} bool ok(int y)
{
for (int64 i = ; i*i <= y; ++ i)
if (y % i == ) return ;
return ;
} int gao(int64 n, int num)
{
int x = (int)pow(n, 1.0 / (double)num), y = -;
for (int i = -; i < ; ++ i)
if (mypow(x+i,num) == n && ok(x+i)) y = x + i;
return y;
} class StrongPrimePower
{
public:
vector <int> baseAndExponent(string N){
int64 n = gao(N);
VI ret; ret.clear();
pii ans;
for (int i = ; i < ; ++ i){
int tmp = gao(n, i);
if (tmp == -) continue;
ret.PB (tmp); ret.PB (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(); if ((Case == -) || (Case == )) test_case_5(); }
//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 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() { string Arg0 = ""; int Arr1[] = {}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, baseAndExponent(Arg0)); }
void test_case_1() { string Arg0 = ""; int Arr1[] = { }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, baseAndExponent(Arg0)); }
void test_case_2() { string Arg0 = ""; int Arr1[] = { }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, baseAndExponent(Arg0)); }
void test_case_3() { string Arg0 = ""; int Arr1[] = { }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, baseAndExponent(Arg0)); }
void test_case_4() { string Arg0 = ""; int Arr1[] = {, }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, baseAndExponent(Arg0)); }
void test_case_5() { string Arg0 = ""; int Arr1[] = {, }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, baseAndExponent(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
StrongPrimePower ___test;
___test.run_test(-);
return ;
}
// END CUT HERE
DIV1 500pt
题意：每次翻转操作r(l, r)即是将s中(l, r)的子串反转，比如对abcde进行r(0, 3)即变为cbade。进行一系列翻转变化有一个要求，即r(l1, r1), r(l2, r2), r(l3, r3), r(l4, r4)，需l1<=l2<=l3<=l4，r4>=r3>=r2>=r1。要将string s变为string g，求最少所需翻转次数。
解法：就是一个裸DP，但是我对在字符串上的dp好像一窍不通。。。。。什么时候应该挂点字符串dp的专题来刷了。具体数组设置和状态转移方程可以看官方题解，很简单。点击打开官方题解。
tag:字符串，DP
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "ReversalChain.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 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 = ;
const int inf = maxint; int d[][][][]; class ReversalChain
{
public:
int minReversal(string s, string g){
CLR (d);
int n = s.size();
for (int i = ; i < n; ++ i)
for (int j = ; j < n; ++ j){
if (s[i] == g[j])
d[][i][j][] = d[][i][j][] = ;
else
d[][i][j][] = d[][i][j][] = inf;
} for (int i = ; i <= n; ++ i)
for (int j = ; j < n; ++ j)
for (int k = ; k < n; ++ k){
d[i][j][k][] = d[i][j][k][] = inf;
if (s[j] == g[k]){
d[i][j][k][] = min(d[i][j][k][], d[i-][j+][k+][]);
d[i][j][k][] = min(d[i][j][k][], d[i-][j+][k+][] + );
}
if (s[j+i-] == g[k+i-]){
d[i][j][k][] = min(d[i][j][k][], d[i-][j][k][]);
d[i][j][k][] = min(d[i][j][k][], d[i-][j][k][] + );
}
if (s[j] == g[k+i-]){
d[i][j][k][] = min(d[i][j][k][], d[i-][j+][k][] + );
d[i][j][k][] = min(d[i][j][k][], d[i-][j+][k][]);
}
if (s[j+i-] == g[k]){
d[i][j][k][] = min(d[i][j][k][], d[i-][j][k+][] + );
d[i][j][k][] = min(d[i][j][k][], d[i-][j][k+][]);
}
}
return d[n][][][] == inf ? - : d[n][][][];
} // 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 Arg0 = ""; string Arg1 = ""; int Arg2 = ; verify_case(, Arg2, minReversal(Arg0, Arg1)); }
void test_case_1() { string Arg0 = ""; string Arg1 = ""; int Arg2 = ; verify_case(, Arg2, minReversal(Arg0, Arg1)); }
void test_case_2() { string Arg0 = ""; string Arg1 = ""; int Arg2 = -; verify_case(, Arg2, minReversal(Arg0, Arg1)); }
void test_case_3() { string Arg0 = ""; string Arg1 = ""; int Arg2 = ; verify_case(, Arg2, minReversal(Arg0, Arg1)); }
void test_case_4() { string Arg0 = ""; string Arg1 = ""; int Arg2 = ; verify_case(, Arg2, minReversal(Arg0, Arg1)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
ReversalChain ___test;
___test.run_test(-);
return ;
}
// END CUT HERE