DIV1 250pt
题意：对于图G，有一些点和边，点中有一些点称为特殊点。问在所有特殊点最终不能处于同一个联通块的条件下，最多能给在图G中添加多少条边。
解法：首先，对于图G，处理出它有哪些联通块，然后，不含有特殊点的联通块要连接到某一个含有特殊点的联通块上。连接哪一个能使添加的边最多呢？当然是连接含有点数最多的含特殊点的联通块。
tag:graph, greedy
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "AddElectricalWires.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 = / ; class AddElectricalWires
{
public:
int f[];
bool v[]; int find(int x)
{
if (x != f[x]) f[x] = find(f[x]);
return f[x];
} int maxNewWires(vector <string> p, vector <int> num){
clr0 (v);
for (int i = ; i < sz(num); ++ i) v[num[i]] = ;
for (int i = ; i < sz(p); ++ i) f[i] = i;
for (int i = ; i < sz(p); ++ i)
for (int j = ; j < sz(p); ++ j) if (p[i][j] == ''){
int t1 = find(i), t2 = find(j);
if ((v[t1] && v[t2]) || (t1 == t2)) continue;
if (!v[t1]) f[t1] = t2;
else f[t2] = t1; }
int ans = , idx = num[];
for (int i = ; i < sz(num); ++ i){
int tmp = ;
for (int j = ; j < sz(p); ++ j)
if (find(j) == num[i]) ++ tmp;
if (tmp > ans)
idx = num[i], ans = tmp;
}
int ret = ;
for (int i = ; i < sz(p); ++ i)
for (int j = i+; j < sz(p); ++ j) if (p[i][j] == ''){
int t1 = find(i), t2 = find(j);
if (t1 == t2){
++ ret; continue;
}
if (v[t1] && v[t2]) continue;
if (!v[t1] && !v[t2]){
++ ret; f[t1] = t2; continue;
}
if (t1 == idx || t2 == idx){
++ ret;
if (t1 == idx) f[t2] = idx;
else f[t1] = idx;
}
}
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(); }
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 Arr1[] = {}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, maxNewWires(Arg0, Arg1)); }
void test_case_1() { string Arr0[] = {"","",""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {,}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, maxNewWires(Arg0, Arg1)); }
void test_case_2() { string Arr0[] = {"",""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, maxNewWires(Arg0, Arg1)); }
void test_case_3() { string Arr0[] = {"","","","",""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {,,,,}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, maxNewWires(Arg0, Arg1)); }
void test_case_4() { string Arr0[] = {"","","","",""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {,}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arg2 = ; verify_case(, Arg2, maxNewWires(Arg0, Arg1)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
AddElectricalWires ___test;
___test.run_test(-);
return ;
}
// END CUT HERE
DIV1 500pt
题意：给定整数k,n和一个数组A[]，要按顺序访问范围为0-(n-1)的数轴上编号为A[i]的点，访问的方法如下。首先，找到一段长度为k的连续的点，(比如编号为x, x+1, x+2...x+k-1)，然后查看缓存中的点，有三种可能：某点在缓存中但这次不需要访问，则移出缓存；某点不在缓存中但这次要访问，访问该点并将它加入缓存；某点在缓存中且要访问，不访问该点但将其留在缓存中。要按顺序访问A[i]中的点，最少需要进行多少次访问操作。
n <= 10^9, k <= n, A.size() <= 50。
注意，如果A[] = {2, 3, 10}，k = 3，n = 1000则只需访问2, 3, 4, 8, 9, 10即可。
解法：本题的关键点在于要注意到一点，要访问A[i]，最优解访问的连续k个点只有两类可能：A[j], A[j]+1...A[j]+k-1和A[j]-k+1, A[j]-k+2...A[j]。(*)
所以，先预处理出可能从哪些点开始访问。然后，由于要按顺序访问A[i]，所以只需要做一遍dp即可。
tag:dp, think
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "ContiguousCache.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 int64 llinf = 1LL<<; class ContiguousCache
{
public:
int64 d[][]; int64 over(int a, int b, int c, int d, int k)
{
if (d < a || c > b) return k;
return max(b, d) - min(a, c) + - k;
} long long minimumReads(int len, int k, vector <int> pos){
vi x;
for (int i = ; i < sz(pos); ++ i){
x.pb (min(pos[i], len-k));
x.pb (max(, pos[i]-k+));
}
x.erase(unique(x.begin(), x.end()), x.end()); for (int i = ; i < sz(pos); ++ i)
for (int j = ; j < sz(x); ++ j) d[i][j] = llinf; for (int i = ; i < sz(x); ++ i) if (x[i] <= pos[] && x[i]+k- >= pos[])
d[][i] = k; for (int i = ; i < sz(pos); ++ i)
for (int j = ; j < sz(x); ++ j) if (x[j] <= pos[i] && x[j]+k- >= pos[i])
for (int t = ; t < sz(x); ++ t) if (d[i-][t] != llinf)
d[i][j] = min(d[i][j], d[i-][t] + over(x[t], x[t]+k-, x[j], x[j]+k-, k)); int64 ret = llinf;
for (int i = ; i < sz(x); ++ i) ret = min(ret, d[sz(pos)-][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(); }
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 long long &Expected, const long long &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 Arr2[] = {, , , }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); long long Arg3 = 7LL; verify_case(, Arg3, minimumReads(Arg0, Arg1, Arg2)); }
void test_case_1() { int Arg0 = ; int Arg1 = ; int Arr2[] = {,,,,,}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); long long Arg3 = 29LL; verify_case(, Arg3, minimumReads(Arg0, Arg1, Arg2)); }
void test_case_2() { int Arg0 = ; int Arg1 = ; int Arr2[] = {, , , , , }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); long long Arg3 = 1987654320LL; verify_case(, Arg3, minimumReads(Arg0, Arg1, Arg2)); }
void test_case_3() { int Arg0 = ; int Arg1 = ; int Arr2[] = {}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); long long Arg3 = 2LL; verify_case(, Arg3, minimumReads(Arg0, Arg1, Arg2)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
ContiguousCache ___test;
___test.run_test(-);
return ;
}
// END CUT HERE