Ⅰ.LYK loves string
通过限定元素的先后可以将 \(10^10\) 优化成 \(10!\) ，再加一些剪枝就可以过了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n, m, k, ans;
int f[15], g[15];
map<string, int> H;
void dfs(int fl, int sum, int tot, string now){
if(sum > m || tot > k || g[n - fl + 1] + sum < m) return ;
if(fl > n){
if(sum != m) return ;
ans = (ans + f[tot]) % mod;
return ;
}
for(int i = tot + 1; i; --i){
char y = i + 'a' - 1;
string x = ""; x += y;
int t = 0;
if(!H[x]) ++t;
++H[x];
if(now.size()){
for(int j = now.size() - 1; j >= 0; --j){
x = now[j] + x;
if(!H[x]) ++t;
++H[x];
}
}
string pre = now;
x.clear();
x += y;
now += x;
dfs(fl + 1, sum + t, tot + (i == tot + 1), now);
now = pre;
--H[x];
if(now.size()){
for(int j = now.size() - 1; j >= 0; --j){
x = now[j] + x;
--H[x];
}
}
}
}
signed main(){
// freopen("string.in", "r", stdin);
// freopen("string.out", "w", stdout);
n = read(), m = read(), k = read();
int x = k - 1; f[1] = k;
for(int i = 2; i <= min(n, k); ++i) f[i] = f[i - 1] * x % mod, x --;
x = n - 1; g[1] = n;
for(int i = 2; i <= n; ++i) g[i] = g[i - 1] + x, x --;
dfs(1, 0, 0, "");
printf("%lld\n", ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}
Ⅱ.LYK loves graph
分层图最短路，因为有些连通块不能一笔画，会漏解。所以有些情况往回走可以不加代价。具体看代码。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e2 + 67;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n, m, k, ans = 0x3f3f3f3f3f3f3f3f;
int c[N][N], a[N][N], dis[N * N * 7];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int id(int i, int j, int floor){
return (i - 1) * m + j + (floor - 1) * n * m;
}
struct node{
int dis, x, y, k;
bool operator < (const node &A) const{return dis > A.dis;}
};
bitset<300> col[N * N * 7], mp[N * N * 7];
priority_queue<node> pq;
bool vis[N * N * 7];
bool check(int x, int y){
if(x < 1 || x > n || y < 1 || y > m) return false;
return true;
}
void solve(int sx, int sy, int sk){
while(!pq.empty()) pq.pop();
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n * m * k; ++i) col[id(sx, sy, sk)].reset(), mp[id(sx, sy, sk)].reset();
dis[id(sx, sy, sk)] = a[sx][sy];
pq.push((node){a[sx][sy], sx, sy, sk});
col[id(sx, sy, sk)][c[sx][sy]] = 1;
mp[id(sx, sy, sk)][id(sx, sy, 1)] = 1;
while(!pq.empty()){
node now = pq.top(); pq.pop();
int id1 = id(now.x, now.y, now.k), id2;
if(vis[id1]) continue;
vis[id1] = 1;
if(now.k == k){
ans = min(ans, dis[id1]);
continue;
}
for(int i = 0; i < 4; ++i){
int x = now.x + dx[i];
int y = now.y + dy[i];
if(!check(x, y) || c[x][y] == -1) continue;
if(col[id1][c[x][y]]){
id2 = id(x, y, now.k);
if(dis[id2] > dis[id1] + a[x][y]){
if(mp[id1][id(x, y, 1)]) dis[id2] = dis[id1];
else dis[id2] = dis[id1] + a[x][y];
col[id2] = col[id1];
mp[id2] = mp[id1]; mp[id2][id(x, y, 1)] = 1;
pq.push((node){dis[id2], x, y, now.k});
}
}else{
id2 = id(x, y, now.k + 1);
if(dis[id2] > dis[id1] + a[x][y]){
dis[id2] = dis[id1] + a[x][y];
col[id2] = col[id1]; col[id2][c[x][y]] = 1;
mp[id2] = mp[id1]; mp[id2][id(x, y, 1)] = 1;
pq.push((node){dis[id2], x, y, now.k + 1});
}
}
}
}
}
signed main(){
// freopen("graph.in", "r", stdin);
// freopen("graph.out", "w", stdout);
n = read(), m = read(), k = read();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
c[i][j] = read();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
a[i][j] = read();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(c[i][j] != -1) solve(i, j, 1);
printf("%lld\n", ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}
Ⅲ.LYK loves rabbits
