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
需要注意细节处理
(开始以为棋子不能重复也不会掉下去,还以为是什么奇奇怪怪的方法