DIV1 250pt

The question : call string s yes vector<string> words Of ordered superstring, If it satisfies : There is a sequence of numbers {x0, x1, x2...xm}(m = words.size()), bring words[i] And s In the from xi At the beginning , The length is words[i].size() The string of is the same , And x0 <= x1 <= x2 <= ... <= xm.

Given words, Seek the shortest ordered superstring.words.size() <= 50,words[i].size() <= 50.

solution : Simulation question . Because it's easy to use pointers and my code is too unstable, so wa 了 ....

tag:simulation

 // BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "OrderedSuperString.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 long long int64; const double eps = 1e-;
const double PI = atan(1.0)*;
const int inf = / ; bool ok(string a, string b)
{
for (int i = ; i < min(sz(a), sz(b)); ++ i)
if (a[i] != b[i]) return ;
return ;
} class OrderedSuperString
{
public:
int getLength(vector <string> w){
string s; s.clear();
int idx = ;
for (int i = ; i < sz(w); ++ i){
int match = sz(s);
for (int j = idx; j < sz(s); ++ j)
if (ok(string(s.begin()+j, s.end()), w[i])){
match = j; break;
}
idx = match;
if (sz(s) - match < sz(w[i]))
s += string(w[i].begin()+sz(s)-match, w[i].end());
}
return sz(s);
} // 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(); }
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[] = {"aaaaaaaaaaabaaaaaaaa", "bac", "aaaabacaaa", "ab", "ba", "a", "ca"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, getLength(Arg0)); }
void test_case_1() { string Arr0[] = {"a","a","b","a"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, getLength(Arg0)); }
void test_case_2() { string Arr0[] = {"abcdef", "ab","bc", "de","ef"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, getLength(Arg0)); }
void test_case_3() { string Arr0[] = {"ab","bc", "de","ef","abcdef"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, getLength(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
OrderedSuperString ___test;
___test.run_test(-);
return ;
}
// END CUT HERE

DIV1 600pt

The question : to 3 A positive integer n1, n2, up, To be able to be C(n1+n2, n1) Divisible , And less than or equal to up The largest positive integer of .n1,n2 <= 10^9,up <= 10^5.

solution : First , Enumeration is less than up All the numbers are positive . Now consider , Pair integer k, How to determine if it can be C(n1+n2, n1) Integers .

When the data is too big to be represented directly , And it can't be expressed indirectly by remainder , Consider all its prime factors . Just think about it sqrt(k) All the prime factors within the , perhaps k Prime number .

then , Considering the particularity of combination number ,C(n1+n2, n1) = (n1+n2)! / (n1! * n2!). So let's consider a qualitative factor t, How to find n! How many qualitative factors are there t.

The following figure for 13! There are factors 2 The number of , One X Representing one . That is said ,13 The factorial of contains factors 2 The quantity of is 13/2 + 13/(2^2) + 13/(2^3).

tag:math, number theory, good

 // BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "MagicalSpheres.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 long long int64; const double eps = 1e-;
const double PI = atan(1.0)*;
const int inf = / ;
const int N = ; class MagicalSpheres
{
public:
int64 gao (int x, int m)
{
int64 num = ;
int64 tmp = m;
while (tmp <= x){
num += x / tmp;
tmp *= m;
}
return num;
} int divideWork(int n1, int n2, int up){
for (int i = up; i; -- i){
bool ok = ;
int k = i;
for (int j = ; j*j <= k; ++ j) if (k % j == ){
int t = ;
while (!(k % j))
k /= j, ++ t;
if (gao(n1+n2, j) - gao(n1, j) - gao(n2, j) < t) ok = ;
}
if (k != )
if (gao(n1+n2, k) - gao(n1, k) - gao(n2, k) < ) ok = ;
if (!ok) return i;
}
return ;
} // 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(); }
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 Arg0 = ; int Arg1 = ; int Arg2 = ; int Arg3 = ; verify_case(, Arg3, divideWork(Arg0, Arg1, Arg2)); }
void test_case_1() { int Arg0 = ; int Arg1 = ; int Arg2 = ; int Arg3 = ; verify_case(, Arg3, divideWork(Arg0, Arg1, Arg2)); }
void test_case_2() { int Arg0 = ; int Arg1 = ; int Arg2 = ; int Arg3 = ; verify_case(, Arg3, divideWork(Arg0, Arg1, Arg2)); }
void test_case_3() { int Arg0 = ; int Arg1 = ; int Arg2 = ; int Arg3 = ; verify_case(, Arg3, divideWork(Arg0, Arg1, Arg2)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
MagicalSpheres ___test;
___test.run_test(-);
return ;
}
// END CUT HERE

SRM 409(1-250pt, 1-500pt) More articles about

  1. SRM475 - SRM479(1-250pt,500pt)

    SRM 475 DIV1 300pt The question : Play a game . Give me a chessboard , It has 1×n(1 That's ok n Column , Each column is labeled with 0,1,2..n-1) Lattice of , You can put a chess piece in each grid , And given that one has only three letters WBR, The length is n Of ...

  2. SRM468 - SRM469(1-250pt, 500pt)

    SRM 468 DIV1 250pt The question : Give the dictionary , Search according to certain requirements . solution : Simulation question , Violence is enough . tag:water score: 0.... This is the first time AC Code for : /* * Author: ...

  3. SRM470 - SRM474(1-250pt,500pt)(471-500pt It's the shortest path ,474-500pt Not done )

    SRM 470 DIV1 250pt The question : Yes n A row of rooms , There is a closed door between two adjacent rooms ( common n-1 fan ), Every door is marked with ‘A’-‘P’ The capital letters of . Give a number n, It means the first one n A room . There are two people John and ...

  4. SRM593(1-250pt,500pt)

    SRM 593 DIV1 250pt The question : It's a plane as shown in the figure below , Each hexagon has coordinates . Some of the hexagons are dyed , It is required that two adjacent hexagons with edges cannot be dyed the same color . Given which hexagons need coloring , How many colors do you need at least . solution : ...

  5. topcoder srm 553

    div1 250pt: The question :... solution : Let's say the empty space is 0, Then simulate once to see if you are satisfied , If not , We only need to care about whether the value of the last element at the top of the stack is affected by the blank space , So let's do a simulation . // BEGIN ...

  6. topcoder srm 552

    div1 250pt: The question : use RGB Three colors of the pendulum N The triangle of layers , Ask for different colors next to each other , give RGB The number of , How many can I ask at most solution : The number of the three colors is either the same , Either the two are the same , The other one is one more than them , So it can be divided into ...

  7. topcoder srm 551

    div1 250pt The question : One is the longest 50 String , Each operation can exchange two adjacent characters , ask , Go through the most MaxSwaps After the first exchange , At most, how many identical characters can be concatenated solution : For each character , To name one “ Assembly point ”, Give Way ...

  8. topcoder srm 550

    div1 250pt: The question : There's a robot , From a certain point , He changes direction only when he touches the edge of the terrain or the point he passes , Then go on , Now give us his trajectory , Judge whether his movement is legal , If it's legal , So the smallest surface of the whole terrain ...

  9. topcoder srm 610

    div1 250pt: The question :100*100 Of 01 matrix , Find the largest “ It's like a chess board ” The submatrix of . solution : Enumeration matrix width ( horizontal direction ) The beginning and the end , Then we use the ruler method to find the maximum matrix of each fixed width , Constantly updated ...

Random recommendation

  1. SQL Server Tuning Series 2 ( How to use aggregate syndication (Hint) Guide statement running )

    Preface Last time we analyzed the query Hint Usage of , As the first of the last playful modules in the tuning series . If you are interested, you can click to view :SQL Server Play in tuning series ( How to use query tips (Hint) Guide statement running ) This article continues to play the module ...

  2. IOS Development of —— iOS payment [ Alipay 、 UnionPay 、 WeChat ]

    Alipay iOSsdk The official download sdk Address :https://b.alipay.com/order/productDetail.htm?productId=2013080604609654&tabId ...

  3. java include Contains examples of instructions

    1. Project framework 2. Code (1)top.jsp 2.copyright.jsp 3.index.jsp 4. design sketch : 5. summary I have encountered many problems during this period , For example, I didn't create it at first java Dynamic projects are java ...

  4. NSIS: install 、 Check that the program is running when uninstalling

    original text NSIS: install . Check that the program is running when uninstalling If the program we want to install or upgrade is running , The file will not be replaced successfully , The following code can prompt the user to end the running program . You need to use plug-ins FindProcDLL.dll, Download route ...

  5. PB Program source file structure pbl file pbd file

    Recently, the company gave a set of PB Source code , One 8.0, One 9.0, Let a customer do software integration , I've only heard of it before PB I've seen people write code , To get started quickly , Got it PB The file of , Record the following :pbl by pb The source code file pbd For the compiled file of the program ...

  6. Linux File links to the operating system

    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ title :Linux File link content of the operating system : File link time :2019 year ...

  7. c# Pop up window in the lower right corner

    public partial class Form2 : Form { System.Diagnostics.Stopwatch sth = new System.Diagnostics.Stopwa ...

  8. vbs Get the current host IP

    Function GetIP GetIP = ""        Dim objWMIService, colAdapters, objAdapter    strComputer ...

  9. use go Implement simple bubble sort

    package main import "fmt" func main(){ var arr = [] int { 9 , 6 , 2 , 5 , 8 , 10 , 12 , 1 ...

  10. vsftpd.conf Detailed explanation

    // Anonymous access is not allowed anonymous_enable=NO // Set local user access . Be careful : Mainly for virtual hosting users , If the item is set to NO Then all virtual users will not be able to access local_enable=YES // ...