原题链接：https://vjudge.net/contest/148523#overview
B - Cow Multiplication
题目
Paste_Image.png
分析
新定义一种乘法规则，然后给你两个数让你算。用字符串读入然后直接模拟过程就好。
ac代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
using namespace std;
string a, b;
int main(){
cin >> a >> b;
int ans = 0;
for(int i = 0; i < a.size(); ++i){
for(int j = 0; j < b.size(); ++j){
ans += ((a[i] - '0') * (b[j] - '0'));
}
}
cout << ans << endl;
return 0;
}
C - Treats for the Cows
题目
Paste_Image.png
Paste_Image.png
分析
给你一组数，只能从两边取，每次取得到的钱为数的value * （第几次的次数），然后让你求最大能得到多少钱。一开始想贪心，但并没有想到好的贪法，只能老老实实的动态规划做喽。
开一个（long long）n*n的数组记录dp状态。
dp[i][j] = max(dp[i][j], dp[i - 1][j] + (n - (j - i + 1)) * a[i - 1]);
dp[i][j] = max(dp[i][j], dp[i][j + 1] + (n - (j - i + 1)) * a[j + 1]);
ac代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#define inf 1e17
typedef long long ull;
using namespace std;
const int maxn = 2e3 + 5;
int a[maxn], n;
ull dp[maxn][maxn];
void init(){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d", a + i);
}
}
void solve(){
memset(dp, 0, sizeof(dp));
for(int i = 0; i < n; ++i){
for(int j = n - 1; j >= i; --j){
if(i > 0){
dp[i][j] = max(dp[i][j], dp[i - 1][j] + (n - (j - i + 1)) * a[i - 1]);
}
if(j < n - 1){
dp[i][j] = max(dp[i][j], dp[i][j + 1] + (n - (j - i + 1)) * a[j + 1]);
}
}
}
ull ans = 0;
/*for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
printf("%lld ", dp[i][j]);
}
cout << endl;
}*/
for(int i = 0; i < n; ++i){
ans = max(ans, dp[i][i] + a[i] * n);
}
printf("%lld", ans);
}
int main(){
init();
solve();
return 0;
}
D - Silver Cow Party
题目
Paste_Image.png
Paste_Image.png
分析
给一个有向图，指定一个点，让求所有点到该点的最短路再回去的最短路花费的和的最大值。
一开始我直接floyd-warshall跑t了，改成两边dijkstra就好了，一边正的，一边反的，然后遍历求解。
这个题写的时候有点急，代码写的好丑。
ac代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
typedef long long ull;
using namespace std;
const int inf = 1e9 + 7;
const int maxn = 1e3 + 5;
const int maxm = 1e5 + 5;
int road[maxn][maxn], n, m, x;
int d1[maxn], d2[maxn];
bool used[maxn];
void solve(){
scanf("%d%d%d", &n, &m, &x);
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
road[i][j] = inf;
if(i == j) road[i][j] = 0;
}
}
for(int i = 0; i < m; ++i){
int t1, t2, t3;
scanf("%d%d%d", &t1, &t2, &t3);
road[t1][t2] = t3;
}
/* for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
printf("%11d", road[i][j]);
}
printf("\n");
}*/
fill(d1 + 1, d1 + n + 1, inf);
fill(d2 + 1, d2 + n + 1, inf);
memset(used, 0, sizeof(used));
d1[x] = 0;
while(1){
int v = -1;
for(int u = 1; u <= n; ++u){
if(!used[u] && (v == -1 || d1[u] < d1[v])) v = u;
}
if(v == -1) break;
used[v] = 1;
for(int u = 1; u <= n; ++u){
//printf("%d: %d\n", u, d1[u]);
d1[u] = min(d1[u], d1[v] + road[v][u]);
//printf("%d: %d\n", u, d1[u]);
}
}
memset(used, 0, sizeof(used));
d2[x] = 0;
while(1){
int v = -1;
for(int u = 1; u <= n; ++u){
if(!used[u] && (v == -1 || d2[u] < d2[v])) v = u;
}
if(v == -1) break;
used[v] = 1;
for(int u = 1; u <= n; ++u){
d2[u] = min(d2[u], d2[v] + road[u][v]);
}
}
/* for(int i = 1; i <= n; ++i){
printf("%d %d\n", d1[i], d2[i]);
}*/
int ans = 0;
for(int i = 1; i <= n; ++i){
ans = max(ans, d1[i] + d2[i]);
}
cout << ans << endl;
}
int main(){
solve();
return 0;
}
E - The Moronic Cowmpouter
题目
Paste_Image.png
分析
把一个树转换成-2进制，刚看到题一脸懵逼，后来找找就发现可以找规律，用一个num[]数组去记录位数，
1 = 1
2 = -2 + 4
4 = 4
...
-1 = 1 - 2
-2 = -2
-4 = 4 - 8
...
然后num数组并不一定是个都是1和0的数组，需要进位，进位的标准是
if(num[i] > 1)
则num[i] -= 2; ++num[i+1]; ++num[i+2];
完美ac。
ac代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
typedef long long ull;
using namespace std;
int n;
int num[60];
void print_ans(){
//cout << " 1" << endl;
for(int i = 0; i < 60; ++i){
while(num[i] > 1){
num[i] -= 2;
++num[i + 1];
++num[i + 2];
}
}
int text = 1;
for(int i = 60 - 1; i >= 0; --i){
if(!text){
printf("%d", num[i]);
}
else{
if(num[i] != 0){
text = 0;
printf("%d", num[i]);
}
}
}
}
int main(){
cin >> n;
if(n == 0){
printf("0");
}
else if(n >= 0){
memset(num, 0, sizeof(num));
int i = 0;
while(n != 0){
if(n % 2 != 0){
if(i % 2 == 0){
++num[i];
}
else {
++num[i];
++num[i + 1];
}
}
n /= 2;
++i;
}
print_ans();
}
else{
memset(num, 0, sizeof(num));
int i = 0;
while(n != 0){
if(n % 2 != 0){
if(i % 2 != 0){
++num[i];
}
else {
++num[i];
++num[i + 1];
}
}
n /= 2;
++i;
}
print_ans();
}
return 0;
}
