安装
使用 go install
(推荐)
使用 go 1.23 或更高版本:
go install github.com/air-verse/air@latest
使用方法
只需执行 air
命令
air
文档
GitHub URL: https://github.com/air-verse/air
README: https://github.com/air-verse/air/blob/master/README-zh_cn.md
go install
(推荐)使用 go 1.23 或更高版本:
go install github.com/air-verse/air@latest
只需执行 air
命令
air
GitHub URL: https://github.com/air-verse/air
README: https://github.com/air-verse/air/blob/master/README-zh_cn.md
url: https://www.luogu.com.cn/problem/P1074
tag:
NOIP2009 提高组,搜索,剪枝,位运算,NOIP提高组,2009
思路:
a[10][10]
:存储数独棋盘,ai表示第i行第j格的数字(0表示空格)r[10]
:行约束,r[i]的二进制第k位表示第i行能否填数字k+1(1表示可用)c[10]
:列约束,c[j]的二进制第k位表示第j列能否填数字k+1e[5][5]
:九宫格约束,ex的二进制第k位表示第x行第y列九宫格能否填k+1p[1<<11]
:位掩码到数字的映射,p[1<<k]=k+1(快速获取候选数字)o[1<<10]
:预计算二进制中1的个数,o[mask]表示mask的候选数字个数ans
:存储最终的最大得分gs()
:根据位置计算得分,边缘得分低,中心得分高(计算公式:值*(6+距边缘距离))init()
:初始化约束为全可用状态,预处理o[]和p[]的映射关系dfs()
:采用最小候选数优先的回溯算法,通过位运算快速枚举候选值参考: https://www.luogu.com.cn/article/gerq24ll
ps: 好强大的位运算思路,爱了爱了。
代码:
#include <iostream>
using namespace std;
int a[10][10], r[10], c[10], e[5][5], p[1 << 11], ans = -1;
int o[1 << 10];
int gs(int i, int j)
{
return a[i][j] * (6 + min(min(i, 8 - i), min(j, 8 - j)));
}
void init()
{
for (int i = 0; i < 9; i ++) r[i] = c[i] = e[i / 3][i % 3] = (1 << 9) - 1;
for (int i = 0; i < (1 << 9); i ++)
{
int t = i;
while (t)
{
t &= t -1;
o[i] ++;
}
}
for (int i = 0; i < 9; i ++) p[1 << i] = i + 1;
}
void dfs(int cnt, int sum)
{
if (cnt == 0)
{
ans = max(ans, sum);
}
int mi = 10, x, y;
for (int i = 0; i< 9; i++)
for (int j = 0; j < 9; j ++)
{
if (!a[i][j])
{
int t = r[i] & c[j] & e[i / 3][j / 3];
if (o[t] < mi)
{
mi = o[t], x = i, y = j;
}
}
}
int t = r[x] & c[y] & e[x / 3][y / 3];
while (t)
{
int l = (t & -t);
t -= l;
a[x][y] = p[l];
r[x] -= l, c[y] -= l, e[x / 3][y / 3] -= l;
dfs(cnt -1, sum + gs(x, y));
a[x][y] = 0;
r[x] += l, c[y] += l, e[x / 3][y / 3] += l;
}
}
int main()
{
init();
int cnt = 0, sum = 0;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j ++)
{
cin >> a[i][j];
if (a[i][j])
{
r[i] -= 1 << a[i][j] - 1;
c[j] -= 1 << a[i][j] - 1;
e[i / 3][j / 3] -= 1 << a[i][j] -1;
sum += gs(i, j);
}else cnt ++;
}
dfs(cnt, sum);
cout << ans << endl;
return 0;
}
url: https://www.luogu.com.cn/problem/P2476
tag:
SCOI2008,动态规划,搜索,记忆化搜索
思路:
开一个6维的数组来表示状态(因为每种情况有多种,所以不能用压位bit),分别表示足够涂1, 2, 3, 4, 5块木头的颜色有几种,最后一维表示上一种颜色的种类。然后用记忆化搜索来做。参考: https://www.luogu.com.cn/article/fhusu9wq
代码:
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll MOD = 1e9 + 7;
int n, t[6];
ll dp[16][16][16][16][16][6];
ll dfs(int a, int b, int c, int d, int e, int last)
{
if (dp[a][b][c][d][e][last] != -1) return dp[a][b][c][d][e][last];
if (a + b + c + d + e == 0) return 1;
ll res = 0;
if (a) res += (a - (last == 2)) * dfs(a - 1, b, c, d, e, 1);
if (b) res += (b - (last == 3)) * dfs(a + 1, b - 1, c, d, e, 2);
if (c) res += (c - (last == 4)) * dfs(a, b + 1, c - 1, d, e, 3);
if (d) res += (d - (last == 5)) * dfs(a, b, c + 1, d - 1, e, 4);
if (e) res += e * dfs(a, b, c, d + 1, e - 1, 5);
dp[a][b][c][d][e][last] = res % MOD;
return dp[a][b][c][d][e][last];
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++)
{
int a;
cin >> a;
t[a] ++;
}
memset(dp, -1, sizeof dp);
ll ans = dfs(t[1], t[2], t[3], t[4], t[5], 0);
cout << ans << endl;
return 0;
}
url: https://www.luogu.com.cn/problem/P1278
tag:
记忆化搜索,状压DP
思路:
记忆化搜索,dfs两个参数一个是当前的字母,另外一个是当前的状态。f[x, y] 表示当以字符串x开头是状态为y时最大的字符串长度。
代码:
#include <iostream>
#include <vector>
using namespace std;
string st[18];
vector<int> v[210];
int f[17][1 << 17];
int n, ans;
int dfs(int x, int y)
{
if (f[x][y]) return f[x][y];
int res = 0;
for (auto i : v[st[x][st[x].size() - 1]])
if (!((y>>(i - 1) & 1))) res = max(res, dfs(i, y | 1 << (i - 1)));
return f[x][y] = res + st[x].size();
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++) cin >> st[i], v[st[i][0]].push_back(i);
for (int i = 1; i <= n; i ++) ans = max(ans, dfs(i, (1 << (i - 1))));
cout << ans << endl;
return 0;
}
url: https://www.luogu.com.cn/problem/P2966
tag:
USACO09DEC,最短路,排序,USACO,2009
思路:
多次询问,点的数据范围小,所以可以用floyd,如果没有点权,那么这道题就是经典的多源汇最短路。为了处理这个点权,我们可以将每一个节点按照点权的大小从小到大排序,然后对于每一个中间节点都是按照从小到大来遍历,这样计算点权的时候,每次中间节点k一定是最大的,所以求点权的最大值时,只要在i,j,k也就是起点终点和用来更新的中间节点之间选择一个较大的即可。
代码:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 300;
int n, m, q;
int ans[N][N], dist[N][N];
struct node {
int val, idx;
} Node[N];
bool cmp (node &a, node &b)
{
return a.val < b.val;
}
int main()
{
cin >> n >> m >> q;
for (int i = 1; i <= n; i ++)
{
cin >> Node[i].val;
Node[i].idx = i;
}
sort(Node + 1, Node + n + 1, cmp);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
dist[i][j] = (i == j) ? 0 : 0x3f3f3f3f;
memset(ans, 0x3f, sizeof ans);
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
dist[u][v] = dist[v][u] = min(dist[v][u], w);
}
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
dist[Node[i].idx][Node[j].idx] = min(dist[Node[i].idx][Node[j].idx], dist[Node[i].idx][Node[k].idx] + dist[Node[k].idx][Node[j].idx]);
ans[Node[i].idx][Node[j].idx] = min(ans[Node[i].idx][Node[j].idx], dist[Node[i].idx][Node[j].idx] + max({Node[i].val, Node[j].val, Node[k].val}));
}
while (q --)
{
int a, b;
cin >> a >> b;
cout << ans[a][b] << endl;
}
return 0;
}