DIV1 250pt
题意：给定一个vector<int>A，若能从里面选出一些数，使得他们按位或的值为x，则称x为吉利数。给定k，问最少要从A里面去掉多少个数，才能使k变为不吉利数。
解法：按位考虑。如果A中某元素A[i]，将A[i]和k转化成二进制形式，如果某一位A[i]为1而k的为0，则一定不选选取掉A[i]，把所有这样的A[i]全部从A中删掉。然后，维护ans，枚举所有k二进制为1的位，计A中有t个元素该位为1，则ans = min(ans, t)。
A.size() <= 50，A[i] <= 10^9
tag：按位或
Ps：我的代码写的太复杂了。。。
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "ORSolitaire.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 = ; int num[];
bool v[]; bool ok(int x, int y)
{
while (y){
int t1 = x & , t2 = y & ;
if (!t2 && t1) return ;
x >>= ; y >>= ;
}
return !x;
} void gao(int x)
{
int p = ;
while (x){
num[p++] += (x & );
x >>= ;
}
} class ORSolitaire
{
public:
int getMinimum(vector <int> nb, int x){
int sz = nb.size();
CLR (num); CLR (v);
for (int i = ; i < sz; ++ i){
v[i] = ok(nb[i], x);
if (v[i]) gao(nb[i]);
} int p = ;
int ans = ;
while (x){
if (x & )
ans = min(ans, num[p]);
x >>= ;
++ p;
}
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 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 Arr0[] = {, , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, getMinimum(Arg0, Arg1)); }
void test_case_1() { int Arr0[] = {, , , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, getMinimum(Arg0, Arg1)); }
void test_case_2() { int Arr0[] = {, , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, getMinimum(Arg0, Arg1)); }
void test_case_3() { int Arr0[] = {,,,,,,,,,,}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, getMinimum(Arg0, Arg1)); }
void test_case_4() { int Arr0[] = {, , , , , , , , , , , , , , , , , , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, getMinimum(Arg0, Arg1)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
ORSolitaire ___test;
___test.run_test(-);
return ;
}
// END CUT HERE
DIV1 600pt
题意：有一个矩阵每位只可能为1或0，每次操作可以将某一为的0变1或者1变0，求最少操作次数，使得操作以后，该矩阵有rnum行为回文，有cnum列为回文。
矩阵行数 <= 14，列数 <= 14，行数列数均为偶数。
解法：枚举行，dp列。用O(2^14)的复杂度枚举哪些行为对称行。处理列的时候，把关于中间对称的两列一起处理，每对列都可以看成4种物品，两列都不对称，左列对称右列不对称，右列对称左列不对称，都对称，然后用背包处理就行了。
tag:dp, 背包, good
// BEGIN CUT HERE
/* */
// END CUT HERE
#line 7 "PalindromeMatrix.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#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 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-;
const double PI = atan(1.0)*;
const int maxint = ; inline int MyMod( int a , int b ) { return (a%b+b)%b;} VS a;
bool v[];
int d[][]; int gao(int sta, int n, int m, int cnum)
{
int nmid = (n - ) >> , mmid = (m - ) >> ;
clr0 (v);
for (int i = ; i < n; ++ i)
if (sta & ( << i)) v[i] = ; int c[][];
for (int i = ; i <= mmid; ++ i){
clr0 (c[i]);
for (int j = ; j <= nmid; ++ j){
int ii = m - - i, jj = n - - j;
int t0 = ;
if (a[jj][i] == '') ++ t0;
if (a[jj][ii] == '') ++ t0;
if (a[j][i] == '') ++ t0;
if (a[j][ii] == '') ++ t0;
if (v[j] && v[jj]){
c[i][] += (a[j][i] != a[j][ii]) + (a[jj][i] != a[jj][ii]);
int tmp = min(t0, - t0);
for (int j = ; j < ; ++ j) c[i][j] += tmp;
}
if (v[j] && !v[jj]){
c[i][] += (a[j][i] != a[j][ii]);
if (a[j][i] == a[j][ii]){
c[i][] += (a[j][i] != a[jj][i]);
c[i][] += (a[j][i] != a[jj][ii]);
}
else{
++ c[i][]; ++ c[i][];
}
c[i][] += min(t0, -t0);
}
if (!v[j] && v[jj]){
c[i][] += (a[jj][i] != a[jj][ii]);
if (a[jj][i] == a[jj][ii]){
c[i][] += (a[j][i] != a[jj][ii]);
c[i][] += (a[j][ii] != a[jj][ii]);
}
else{
++ c[i][]; ++ c[i][];
}
c[i][] += min(t0, -t0);
}
if (!v[j] && !v[jj]){
int t1 = (a[j][i] != a[jj][i]), t2 = (a[j][ii] != a[jj][ii]);
c[i][] += t1; c[i][] += t2; c[i][] += t1 + t2;
}
}
} clr1 (d);
d[][] = c[][]; d[][] = min(c[][], c[][]); d[][] = c[][];
for (int i = ; i <= mmid; ++ i)
for (int j = ; j <= m; ++ j){
if (d[i-][j] >= ) d[i][j] = d[i-][j] + c[i][];
if (j && d[i-][j-] >= ) d[i][j] = min(d[i][j]>= ? d[i][j] : n*m+, d[i-][j-] + min(c[i][], c[i][]));
if (j >= && d[i-][j-] >= ) d[i][j] = min(d[i][j]>= ? d[i][j] : n*m+, d[i-][j-] + c[i][]);
} int ret = n * m + ;
for (int i = cnum; i <= m; ++ i){
if (d[mmid][i] == -) continue;
ret = min (ret, d[mmid][i]);
}
return ret;
} class PalindromeMatrix
{
public:
int minChange(vector <string> A, int rnum, int cnum){
a = A;
int n = sz(a), m = sz(a[]);
int ans = n * m + , cnt = << n;
for (int i = ; i < cnt; ++ i)
if (__builtin_popcount(i) >= rnum) ans = min(ans, gao(i, n, m, cnum));
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(); if ((Case == -) || (Case == )) test_case_6(); }
//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 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[] = {""
,""
,""
,""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; int Arg3 = ; verify_case(, Arg3, minChange(Arg0, Arg1, Arg2)); }
void test_case_1() { string Arr0[] = {""
,""
,""
,""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; int Arg3 = ; verify_case(, Arg3, minChange(Arg0, Arg1, Arg2)); }
void test_case_2() { string Arr0[] = {""
,""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; int Arg3 = ; verify_case(, Arg3, minChange(Arg0, Arg1, Arg2)); }
void test_case_3() { string Arr0[] = {""
,""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; int Arg3 = ; verify_case(, Arg3, minChange(Arg0, Arg1, Arg2)); }
void test_case_4() { string Arr0[] = {""
,""
,""
,""
,""
,""
,""
,""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; int Arg3 = ; verify_case(, Arg3, minChange(Arg0, Arg1, Arg2)); }
void test_case_5() { string Arr0[] = {""
,""
,""
,""
,""
,""
,""
,""
,""
,""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; int Arg3 = ; verify_case(, Arg3, minChange(Arg0, Arg1, Arg2)); }
void test_case_6() { string Arr0[] = {""
,""
,""
,""
,""
,""
,""
,""
,""
,""
,""
,""
,""
,""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; int Arg3 = ; verify_case(, Arg3, minChange(Arg0, Arg1, Arg2)); } // END CUT HERE };
//by plum rain
// BEGIN CUT HERE
int main()
{
//freopen( "a.out" , "w" , stdout );
PalindromeMatrix ___test;
___test.run_test(-);
return ;
}
// END CUT HERE