我果然是题短了就能做得好- -。Div 2的三道题都短，于是迅速的过掉了250和500，rating涨了150^ ^。
Div 2 250pt
题意：给一个vector<int> A，对其中任意的数x，可以将其变为2^t * x(t为正整数)，判断能不能将A变为所有数全部一样。
解法：我的方法是，将A排序，对第i个，while(A[i] < A[i+1]) A[i] *= 2，如果最终A[i] != A[i+1]，则答案为不能。若对所有的i都可以，则答案为能。
水题就不贴代码了。
Div 2 500pt/ Div 1 250pt
题意：给两个等长的字符串s1和s2，对s1进行操作，每次操作能将s1中某个字符提前到s1中的第一个。问最少进行多少次操作，能将s1变成s2。若不能返回-1。
解法：首先，对s1和s2所含字符的数量进行统计，判断能不能将s1变为s2。
然后，改变后的s1有两种字符，被操作过的字符全部在s1的前部分，没被操作过的字符全部在s1的后部分，而且，对于后部分的字符，相对顺序在s1改变前后并没有改变。
所以，从后往前用i枚举s1的所有字符，同时置一个idx对s2从后往前移动。if (s1[i] == s2[idx]) {-- i; -- idx} else -- i;
这样，idx+1即为答案。
tag:greedy
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "LittleElephantAndString.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back char a[], b[];
int num[][]; class LittleElephantAndString
{
public:
int getNumber(string A, string B){
char x = 'A'; int n = A.size();
for (int i = , j = n-; j >= ; ++ i, -- j){
a[i] = A[j];
b[i] = B[j];
} CLR (num);
for (int i = ; i <= n; ++ i){
num[a[i]-x][] ++;
num[b[i]-x][] ++;
} for (int i = ; i < ; ++ i)
if (num[i][] != num[i][]) return -; int cnt = n - ;
for (int i = n-; i >= ; -- i){
if (A[i] == B[cnt])
-- cnt;
}
if (cnt == n-) return -;
return cnt+;
}
};
Div2 1000pt
题意：给定一个数n，称这样的集合为关于n的好集合：所有元素的值均在n以内，且将所有元素写在黑板上，所需要写的0, 1, 2..9的次数均不超过1次。给定n求好数组的数量。(n <= 10^9)，答案关于1000000007取模。
解法：对于任意给定的数n，首先用dfs求出所有能被放在关于n的好集合中的数，并将他们分好类。分类的方法为，对于数k，将它写在黑板上需要写的数字有a0, a1, a2..at，则它属于类((0 | 1<<a0) | (1<<a1) | ... | (1<<at))。比如1属于类2，10属于类3，123属于类14。
分好类之后，就发现，同一个集合之中，最多一个能出现在关于n的好集合中，且不同集合的数也不一定能同时出现在关于n的好集合中，比如类2和类3(因为都含有1)。
这样的话，就变成了一个01背包问题。设d[i][j]表示前i类中去数，状态为j的情况下能有多少好集合。
注意到，此处第i类所代表的状态也为i，所以状态转移方程为d[i][i|j] += d[i-1][j] * num(类i)。num(类i)表示类i中含有元素的个数。
tag：dp, 背包, good
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "LittleElephantAndSubset.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 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 long long int64;
//
//const double eps = 1e-8;
//const double PI = atan(1.0)*4;
//const int maxint = 2139062143;
const int64 mod = ;
// int n, num;
bool vis[], opt[];
int64 d[<<];
vector<int> a[]; int64 max64(int64 a, int64 b)
{
return a > b ? a : b;
} void dfs(int x, int p)
{
int64 y = (int64)x * + p;
if (y > n) return; int sta = ;
for (int i = ; i <= ; ++ i)
if (vis[i]) sta |= ( << i);
a[sta].PB((int)y); for (int i = ; i <= ; ++ i) if(!vis[i]){
vis[i] = ;
dfs((int)y, i);
vis[i] = ;
}
} bool ok(int a, int b)
{
for (int i = ; i < ; ++ i){
int t1 = a & ( << i), t2 = b & ( << i);
if (t1 && t2) return ;
}
return ;
} class LittleElephantAndSubset
{
public:
int getNumber(int N){
n = N; num = << ;
for (int i = ; i < num; ++ i)
a[i].clear();
CLR (vis); for (int i = ; i <= ; ++ i){
vis[i] = ;
dfs(, i);
vis[i] = ;
} CLR (d);
for (int i = ; i < num; ++ i){
if (a[i].size()) d[i] = (a[i].size() + d[i]) % mod;
for (int j = num-; j >= ; -- j) if (ok(i, j))
d[i|j] = ((d[j]%mod) * ((int64)a[i].size()%mod) + d[i|j]) % mod;
} int ret = ;
for (int i = ; i < num; ++ i)
ret = (d[i] + ret) % mod;
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(); }
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 = ; verify_case(, Arg1, getNumber(Arg0)); }
void test_case_1() { int Arg0 = ; int Arg1 = ; verify_case(, Arg1, getNumber(Arg0)); }
void test_case_2() { int Arg0 = ; int Arg1 = ; verify_case(, Arg1, getNumber(Arg0)); }
void test_case_3() { int Arg0 = ; int Arg1 = ; verify_case(, Arg1, getNumber(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
freopen( "a.out" , "w" , stdout );
LittleElephantAndSubset ___test;
___test.run_test(-);
return ;
}
// END CUT HERE