嗯。。。。今天的500确实比较好
DIV1 250
模拟。。。略
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "CubeWalking.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 = / ;
int temp[][] = {{, -}, {, }, {, }, {-, }}; class CubeWalking
{
public:
string finalPosition(string mov){
int n = sz(mov);
int x = , y = , dic = ;
for (int i = ; i < n; ++ i){
if (mov[i] == 'L') dic = (dic + ) % ;
else if (mov[i] == 'R') dic = (dic + ) % ;
if (mov[i] == 'W') x = (x + temp[dic][] + ) % , y = (y + temp[dic][] + ) % ;
}
if (x == && y == ) return "GREEN";
if (!x && y == ) return "BLUE";
if (!y && x == ) return "BLUE";
if (y == && x == ) return "BLUE";
if (x == && y == ) return "BLUE";
return "RED";
} // 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 string &Expected, const string &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 = "LLRR"; string Arg1 = "GREEN"; verify_case(, Arg1, finalPosition(Arg0)); }
void test_case_1() { string Arg0 = "WWWWWWWWWWWW"; string Arg1 = "GREEN"; verify_case(, Arg1, finalPosition(Arg0)); }
void test_case_2() { string Arg0 = "WLWRW"; string Arg1 = "RED"; verify_case(, Arg1, finalPosition(Arg0)); }
void test_case_3() { string Arg0 = "WWLLWRWLWLLRWW"; string Arg1 = "BLUE"; verify_case(, Arg1, finalPosition(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
CubeWalking ___test;
___test.run_test(-);
return ;
}
// END CUT HERE
DIV1 500
题意：给定一个有n个点的带权图，有一个蚂蚁要从点0到点1，它每秒走stp步，最多能走tim秒，走的时间可以少于tim秒，但一定要是整数秒。问，若蚂蚁得分为它通过的边权之和(通过某边两次则得两次分)，则求最大得分，若不能用整数秒走到1并停下，输出IMPOSSIBLE。
n <= 50, stp <= 100, tim <= 10^9。
解法：首先，如果要求一定要走tim，那就很简单了，用矩阵乘法快速幂可以解决。
至于走的时间可以少于tim，处理方法就是加一条1到1，长度为1s，边权为0的自环。
然后，首先用矩阵乘法快速幂算出用时1s，从i点走到j点得分最高为多少。再赋值A[1][1] = max(A[1][1], 0)(若A[1][1]大于0则不用赋值)，然后再调用矩阵乘法快速幂即可。
tag:graph, matrix, 快速幂, good
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "AntOnGraph.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 long long int64;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef int64 mtx[][]; const double eps = 1e-;
const double PI = atan(1.0)*;
const int inf = / ;
const int64 temp = - (1LL<<); class AntOnGraph
{
public:
int dit[], n;
void mtx_eql(mtx &a, mtx b)
{
for (int i = ; i < n; ++ i) for (int j = ; j < n; ++ j) a[i][j] = b[i][j];
}
void mtx_mul(mtx &a, mtx b)
{
mtx ret;
for (int i = ; i < n; ++ i)
for (int j = ; j < n; ++ j){
ret[i][j] = temp;
for (int k = ; k < n; ++ k)
if (a[i][k] != temp && b[k][j] != temp)
ret[i][j] = max(ret[i][j], a[i][k] + b[k][j]);
} mtx_eql(a, ret);
}
void mtx_pow(mtx &an, int64 num)
{
if (num == ) return; mtx ret; mtx_eql(ret, an);
-- num; while (num){
if (num & ) mtx_mul(ret, an);
num >>= ;
mtx_mul(an, an);
} mtx_eql(an, ret);
} string gao(int64 x)
{
int len = ;
bool u = ;
if (x < ) x = - x, u = ; while (x){
dit[len++] = x % ;
x /= ;
} if (!len) return "";
string ret; ret.clear();
if (u) ret.pb ('-');
for (int i = len-; i >= ; -- i) ret.pb (dit[i] + '');
return ret;
}
string maximumBonus(vector <string> p0, vector <string> p1, vector <string> p2, int stp, int tim){
n = sz(p1);
int cnt = ;
mtx an;
for (int i = ; i < n; ++ i)
for (int j = ; j < n; ++ j){
cnt = * (p0[i][j]-'') + * (p1[i][j] - '') + p2[i][j] - '';
if (cnt == ) an[i][j] = temp;
else an[i][j] = cnt - ;
} mtx_pow(an, (int64)stp);
if (an[][] < ) an[][] = ; mtx_pow(an, (int64)tim);
if (an[][] == temp) return "IMPOSSIBLE";
else return gao(an[][]);
} // 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 string &Expected, const string &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[]))); string Arr1[] = {"",""}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); string Arr2[] = {"",""}; vector <string> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); int Arg3 = ; int Arg4 = ; string Arg5 = ""; verify_case(, Arg5, maximumBonus(Arg0, Arg1, Arg2, Arg3, Arg4)); }
void test_case_1() { string Arr0[] = {"",""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arr1[] = {"",""}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); string Arr2[] = {"",""}; vector <string> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); int Arg3 = ; int Arg4 = ; string Arg5 = "IMPOSSIBLE"; verify_case(, Arg5, maximumBonus(Arg0, Arg1, Arg2, Arg3, Arg4)); }
void test_case_2() { string Arr0[] = {"","","",""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arr1[] = {"","","",""}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); string Arr2[] = {"","","",""}; vector <string> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); int Arg3 = ; int Arg4 = ; string Arg5 = ""; verify_case(, Arg5, maximumBonus(Arg0, Arg1, Arg2, Arg3, Arg4)); }
void test_case_3() { string Arr0[] = {"","","",""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arr1[] = {"","","",""}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); string Arr2[] = {"","","",""}; vector <string> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); int Arg3 = ; int Arg4 = ; string Arg5 = "-5"; verify_case(, Arg5, maximumBonus(Arg0, Arg1, Arg2, Arg3, Arg4)); }
void test_case_4() { string Arr0[] = {"","","",
"","","",
"","","",
"","",""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arr1[] = {"","","",
"","","",
"","","",
"","",""}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); string Arr2[] = {"","","",
"","","",
"","","",
"","",""}; vector <string> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); int Arg3 = ; int Arg4 = ; string Arg5 = ""; verify_case(, Arg5, maximumBonus(Arg0, Arg1, Arg2, Arg3, Arg4)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
AntOnGraph ___test;
___test.run_test(-);
return ;
}
// END CUT HERE