A - 涂色 AtCoder - agc004_a
sb题 看长宽高是否能被2整除,是则能平均分,否则差一层
唯一的问题就是用wth/maxL会wa,猜测可能是爆ll了
B - 旅游 LibreOJ - 10078
最短路+dfs
spfa得到要访问的景区间的距离,dfs每一个顺序
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #include <bits/extc++.h>
// #include <bits/stdc++.h>
#define Buff std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define inf LONG_LONG_MAX
#define Inf INT_MAX
#define endl "\n"
#define Endl "\n"
#define String string
// #define Debug
using namespace std;
// using namespace __gnu_pbds;
const int Maxn = 1e7 + 10;
const ll Mod = 1e9 + 7;
int n, m;
int targets[8];
int eachDis[8][8];
bool vis[8];
int finAns = 2e9;
vector<int> g[Maxn];
vector<int> w[Maxn];
int spfa(int strNode, int targetNode)
{
queue<int> qN;
qN.push(strNode);
unordered_map<int, int> dis;
unordered_map<int, bool> inQ;
for (int i = 1; i <= n; i++)
dis[i] = 2e9;
inQ[strNode] = true;
dis[strNode] = 0;
while (!qN.empty())
{
int nowNode = qN.front();
qN.pop();
for (int i = 0; i < g[nowNode].size(); i++)
{
int nextNode = g[nowNode][i];
int nextDis = dis[nowNode] + w[nowNode][i];
if (nextDis < dis[nextNode])
{
dis[nextNode] = nextDis;
if (!inQ[nextNode])
qN.push(nextNode);
}
}
}
return dis[targetNode];
}
void dfs(int nowNode, int nowAns, int deep)
{
// cout << nowNode << " " << nowAns << " " << deep << endl;
if (deep == 5)
finAns = min(finAns, nowAns);
for (int i = 1; i <= 5; i++)
{
if (vis[i])
continue;
vis[i] = true;
dfs(i, nowAns + eachDis[nowNode][i], deep + 1);
vis[i] = false;
}
}
int main()
{
Buff;
#ifdef Debug
freopen("temp.in", "r", stdin);
freopen("temp.out", "w", stdout);
#endif
cin >> n >> m;
targets[0] = 1;
for (int i = 1; i <= 5; i++)
cin >> targets[i];
for (int i = 1; i <= m; i++)
{
int t1, t2, t3;
cin >> t1 >> t2 >> t3;
g[t1].push_back(t2);
g[t2].push_back(t1);
w[t1].push_back(t3);
w[t2].push_back(t3);
}
for (int i = 0; i <= 5; i++)
for (int j = i + 1; j <= 5; j++)
eachDis[i][j] = eachDis[j][i] = spfa(targets[i], targets[j]);
for (int i = 1; i <= 5; i++)
{
vis[i] = true;
dfs(i,eachDis[0][i],1);
vis[i] = false;
}
cout << finAns << endl;
return 0;
}
C - 序列 POJ - 3061
尺取板子题
E - 模拟 POJ - 1208
按照题意模拟即可
我认为需要注意的
- 当a和b在同一堆上时跳过
- 可以而外增加一堆作为中转
F - 橘子 POJ - 3321
dfs序+树状数组的板子(大概
G - 机器 CodeForces - 1296C
可以把LR当作+1 -1 把UD当成+1e6 -1e6
计算前缀和,判断该数是否在之前出现过,可以采用map实现
H - 签到 CodeForces - 1343B
签到构造
I - 房子 LightOJ - 1047
用一个二维的数组进行dp
void work()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> costR[i] >> costG[i] >> costB[i];
map<int, int> F[4];
F[1][1] = costR[1];
F[2][1] = costG[1];
F[3][1] = costB[1];
for (int i = 2; i <= n; i++)
{
F[1][i] = min(F[2][i - 1], F[3][i - 1]) + costR[i];
F[2][i] = min(F[1][i - 1], F[3][i - 1]) + costG[i];
F[3][i] = min(F[2][i - 1], F[1][i - 1]) + costB[i];
}
cout << "Case " << ++cnt << ": ";
cout << min(F[1][n],min(F[2][n],F[3][n])) << Endl;
}
J - 暴力 计蒜客 - T1217
sb暴力,但是他没说n*m的范围导致一直没敢交
(可恶 下次直接莽一发再说
L - 游戏 CodeForces - 1327C
先把所有点挪到左上角,再S型走一遍,总次数为n+m+n*m-1
需要注意细节处理
(开始以为棋子不能重复也不会掉下去,还以为是什么奇奇怪怪的方法
Q.E.D.