ARC061C. Many Formulas *1089
首先预处理出原数区间 \([i,j]\) 所代表的真实数字。然后注意到 \(|s| \leq 10\)，所以直接爆搜回溯最后判断即可。或者状压枚举也可以，反正非常简单。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
string s;
LL Sum[11][11], n, ans = 0;
bool vis[11];
void DFS(LL step)
{
if(step == n)
{
LL last = 1;
for(LL i = 1; i < n; i ++)
{
if(!vis[i]) continue;
ans += Sum[last][i];
last = i + 1;
}
ans += Sum[last][n];
return;
}
vis[step] = true;
DFS(step + 1);
vis[step] = false;
DFS(step + 1);
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> s; n = s.length(); s = ' ' + s;
for(LL i = 1; i <= n; i ++)
{
Sum[i][i] = (s[i] - '0');
for(LL j = i + 1; j <= n; j ++)
Sum[i][j] = Sum[i][j - 1] * 10 + (s[j] - '0');
}
DFS(1);
cout << ans << '\n';
return 0;
}
ARC061D. Snuke's Coloring *1682
注意到我们可以先不管 \(0\) 有多少个。最后可以容斥原理计算出一个染色格子都不包含的个数。注意到一个染色格子只会影响到相邻 \(9\) 个 \(3\times 3\) 方格。我们枚举每个格子 \(i\)，枚举这相邻的 \(9\) 个 \(3\times 3\) 方格，然后计算对答案的贡献。
但是这样子会算重。我们考虑怎么重。显然，包含染色格子个数为 \(i\) 的 \(3\times 3\) 方格的答案会是真实答案的 \(i\) 倍。因为里面的每个染色格子都会把它计算一遍。
然后最后容斥算出不包含染色个数的格子数量即可。形式化的说，就是 \((H-2)\times (W-2) - \sum ans_i\)。然后就做完了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN = 100005;
LL H, W, n, ans[10], X[MAXN], Y[MAXN];
map<pair<LL, LL>, bool> mp;
void Solve(LL sx, LL sy, LL ex, LL ey)
{
if(sx <= 0 || sy <= 0 || ex > H || ey > W) return;
LL cnt = 0;
for(LL i = sx; i <= ex; i ++)
for(LL j = sy; j <= ey; j ++)
if(mp.count(make_pair(i, j))) cnt ++;
ans[cnt] ++;
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> H >> W >> n;
for(LL i = 1; i <= n; i ++)
{
cin >> X[i] >> Y[i];
mp[make_pair(X[i], Y[i])] = true;
}
for(LL i = 1; i <= n; i ++)
{
Solve(X[i] - 2, Y[i] - 2, X[i], Y[i]);
Solve(X[i] - 2, Y[i] - 1, X[i], Y[i] + 1);
Solve(X[i] - 2, Y[i], X[i], Y[i] + 2);
Solve(X[i] - 1, Y[i] - 2, X[i] + 1, Y[i]);
Solve(X[i] - 1, Y[i] - 1, X[i] + 1, Y[i] + 1);
Solve(X[i] - 1, Y[i], X[i] + 1, Y[i] + 2);
Solve(X[i], Y[i] - 2, X[i] + 2, Y[i]);
Solve(X[i], Y[i] - 1, X[i] + 2, Y[i] + 1);
Solve(X[i], Y[i], X[i] + 2, Y[i] + 2);
}
for(LL i = 1; i <= 9; i ++) ans[i] /= i;
ans[0] = (H - 2) * (W - 2);
for(LL i = 1; i <= 9; i ++) ans[0] -= ans[i];
for(LL i = 0; i <= 9; i ++) cout << ans[i] << '\n';
return 0;
}
ARC061E. Snuke's Subway Trip *2502
不知道为什么洛谷评了绿，感觉题还挺有质量的。
考虑虚点建图。对于同一颜色连通块的点是可以免费互相到达的。所以我们可以考虑将它们连向一个虚点，进去的边权为 \(0\)，出来的边权为 \(1\)，因为切换连通块需要代价。这个可以过程用并查集维护。
然后我们发现我们建出了一个只含有 \(0/1\) 边权的图。我们要跑最短路。于是我们在新图上跑 \(0/1\) BFS，答案就是 \(dist_n\)，然后我们就做完了。实现过程有点复杂。
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1000001;
int n, m, fa[MAXM], cnt, tmp[MAXM], Dist[MAXM];
bool vis[MAXM];
vector<pair<int, int> > E[MAXM];
struct Edge
{
int v, w;
};
vector<Edge> Adj[MAXM];
int find(int x)
{
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void BFS01()
{
vis[1] = true;
deque<int> q;
q.push_front(1);
while(!q.empty())
{
int u = q.front();
q.pop_front();
for(int i = 0; i < (int)Adj[u].size(); i ++)
{
int v = Adj[u][i].v, w = Adj[u][i].w;
if(vis[v]) continue;
if(w == 0)
{
vis[v] = true;
Dist[v] = Dist[u];
q.push_front(v);
}
else
{
vis[v] = true;
Dist[v] = Dist[u] + 1;
q.push_back(v);
}
}
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m; cnt = n;
for(int i = 1; i <= m; i ++)
{
int u, v, w;
cin >> u >> v >> w;
E[w].push_back(make_pair(u, v));
}
for(int i = 1; i < MAXM; i ++)
{
set<int> s;
for(int j = 0; j < (int)E[i].size(); j ++)
{
s.insert(E[i][j].first);
s.insert(E[i][j].second);
}
for(auto kv : s) fa[kv] = kv;
for(int j = 0; j < (int)E[i].size(); j ++)
{
int fu = find(E[i][j].first), fv = find(E[i][j].second);
fa[fu] = fv;
}
for(auto kv : s) if(find(kv) == kv) tmp[kv] = ++ cnt;
for(auto kv : s)
{
Adj[kv].push_back(Edge{tmp[find(kv)], 0});
Adj[tmp[find(kv)]].push_back(Edge{kv, 1});
}
}
BFS01();
if(vis[n]) cout << Dist[n] << '\n';
else cout << -1 << '\n';
return 0;
}
这场 F 也是巨大不可做题，不补了。
标签：061,Atcoder,int,题解,LL,vis,kv,MAXM,find From： https://www.cnblogs.com/FracturedAngel/p/18562139