100+100+100+80+100=480
重復局面
題目大意
依次給定\(n\)個國際象棋局面,依次回答每個局面是第幾次出現,
解題思路
拿map記錄下每個局面,統計計數即可,
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin >> n;
map<string, int> qwq;
while(n--){
string s;
for(int i = 0; i < 8; ++ i){
string a;
cin >> a;
s += a;
}
qwq[s] ++;
cout << qwq[s] << '\n';
}
return 0;
}
矩陣運算
題目大意
給定\(n \times d\)的矩陣 \(q, k, v\),一個 \(n\)維向量 \(w\),計算 \((w \cdot (q \times k^{T})) \times v\) 的結果,
\(n \leq 10^4, d \leq 20\)
解題思路
\(q \times k^{T}\)的結果是 \(n \times n\)的矩陣,因為計算結果可能會超出 \(int\)范圍, \(10^8\)的 \(long long\)記憶體有 \(700MB+ \geq 512MB\),因此不能按此計算,
注意矩陣乘法具有結合律,而且點乘 \(\cdot\)不會影響此處的結果,因此我們可以改為算 \(w \cdot q \times (k^{T} \times v)\) ,這樣\(k^{T} \times v\)只有 \(d \times d\)的大小,完全可以儲存和計算,
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n, d;
cin >> n >> d;
vector<vector<LL>> q(n, vector<LL>(d, 0)), k(n, vector<LL>(d, 0)), v(n, vector<LL>(d, 0));
vector<LL> w(n, 0);
for(auto &i : q)
for(auto &j : i)
cin >> j;
for(auto &i : k)
for(auto &j : i)
cin >> j;
for(auto &i : v)
for(auto &j : i)
cin >> j;
for(auto &i : w)
cin >> i;
vector<vector<LL>> tmp(d, vector<LL>(d, 0)), tmp2(n, vector<LL>(d, 0));
for(int i = 0; i < n; ++ i)
for(int j = 0; j < d; ++ j)
for(int z = 0; z < d; ++ z){
tmp[j][z] += k[i][j] * v[i][z];
}
for(int i = 0; i < d; ++ i)
for(int j = 0; j < n; ++ j)
for(int z = 0; z < d; ++ z){
tmp2[j][z] += q[j][i] * tmp[i][z];
}
for(int i = 0; i < n; ++ i)
for(int j = 0; j < d; ++ j)
tmp2[i][j] *= w[i];
for(int i = 0; i < n; ++ i)
for(int j = 0; j < d; ++ j)
cout << tmp2[i][j] << " \n"[j == d - 1];
return 0;
}
解壓縮
題目大意
給定了一個壓縮后的資料,以及解壓的規則,輸出解壓后的資料,
解題思路
就按照規則模擬即可,注意大端模式和小端模式的資料決議,
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define LOWER 3
#define CONST_VAL 0
#define BACK_SHORT 1
#define BACK_LONG 2
LL get_num(char c){
if (isdigit(c))
return c - '0';
else
return c - 'a' + 10;
}
LL get_sz(const string& s, int& pos, int len){
LL sum = 0;
for(int i = pos; i < pos + len; ++ i){
sum = sum * 16 + get_num(s[i]);
}
pos += len;
return sum;
}
LL get_sz_small(const string& s, int& pos, int len){
LL sum = 0;
LL ji = 1;
for(int i = pos; i < pos + len;){
sum = sum + ji * get_sz(s, i, 2);
ji <<= 8;
}
pos += len;
return sum;
}
string get_string(const string& s, int& pos, int len){
string tmp = s.substr(pos, len);
pos += len;
return tmp;
}
bool up_zero(LL num){
return !((num >> 7) & 1);
}
LL remove_up(LL num){
if (up_zero(num))
return num;
else
return num ^ (1 << 7);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin >> n;
n = (n + 7) / 8;
string s;
for(int i = 0; i < n; ++ i){
string a;
cin >> a;
s += a;
}
int id = 0;
LL sz = 0;
LL ji = 1;
while(true){
int sign = get_sz(s, id, 2);
sz += ji * remove_up(sign);
ji *= 128;
if (up_zero(sign)){
break;
}
}
string ans;
while(ans.size() < sz * 2){
int sign = get_sz(s, id, 2);
if ((sign & LOWER) == CONST_VAL){
int len = (sign >> 2);
if (len < 60){
++ len;
ans += get_string(s, id, len * 2);
}else{
len = get_sz_small(s, id, (len - 60 + 1) * 2);
++ len;
ans += get_string(s, id, len * 2);
}
}else if ((sign & LOWER) == BACK_SHORT){
int len = ((sign >> 2) & 7) + 4;
int o = ((sign >> 5) << 8) + get_sz(s, id, 2);
len *= 2;
o *= 2;
if (o >= len){
ans += ans.substr(ans.size() - o, len);
}else{
int pos = ans.size() - o;
string tmp;
while(len){
tmp += ans[pos];
pos ++;
if (pos == ans.size())
pos -= o;
-- len;
}
ans += tmp;
}
}else if ((sign & LOWER) == BACK_LONG){
int len = (sign >> 2) + 1;
int o = get_sz_small(s, id, 4);
len *= 2;
o *= 2;
if (o >= len){
ans += ans.substr(ans.size() - o, len);
}else{
int pos = ans.size() - o;
string tmp;
while(len){
tmp += ans[pos];
pos ++;
if (pos == ans.size())
pos -= o;
-- len;
}
ans += tmp;
}
}
}
for(int i = 0; i < ans.size(); ++ i){
if (i && i % 16 == 0)
cout << '\n';
cout << ans[i];
}
return 0;
}
電力網路
題目大意
給定一張\(n\)個點 \(m\)條邊的無向連通圖,要求給每個點規定一個顏色,共有\(k\)種顏色可選,使得總代價最小,
總代價包括點的代價和邊的代價,點的代價即選定該點的顏色對應的代價,邊的代價由每條邊兩點顏色決定,以矩陣形式給出,
五個子任務:
- 點數\(\leq 6\),顏色數 \(\leq 10\)
- 點數 \(\leq 10^4\),顏色數 \(\leq 10\),一棵樹
- 點數 \(\leq 10^4\),顏色數 \(\leq 10\),一棵基環樹
- 點數 \(\leq 10^4\),顏色數 \(\leq 10\),一個圖,但去掉其中的某個點\(D\)及其連邊,變成一棵樹,且與點\(D\)相連的點都是以某個點 \(S\)為根的葉子
- 點數 \(\leq 10^4\),顏色數 \(\leq 10\),一個圖,但度數\(> 2\)的點數 \(\leq 6\)
解題思路
第一個子任務,直接暴力,列舉每個點的顏色然后求代價的最小值,復雜度為\(O(k^n + n + m)\)
第二個子任務,設\(dp[i][j]\)表示 點\(i\) 的顏色為\(j\)的最小代價,列舉兒子的顏色,樹形\(dp\)轉移,復雜度為\(O(nk^2)\)
第三個子任務,找到環上的任意一條邊\((u, v)\),列舉 \(u\)的顏色(消除后效性),然后以 \(v\)為根( \(u\)也行)做上述樹形 \(dp\)即可,復雜度為\(O(nk^3)\),如何找到環上一條邊,跑一下并查集即可,
第四個子任務,找到點\(D\),然后列舉點\(D\)的顏色(同樣消除后效性),然后以不與點\(D\)有連邊的點\(s\)做上述樹形 \(dp\)即可,復雜度為\(O(nk^3)\),如何找到點\(D\),首先統計每個點的度數,點\(D\)的度數\(d\)滿足 \(m - d = n - 2\)(資料可能水了,有這個條件就夠了,感覺單滿足這個條件還不夠,可能會存在把 點\(D\)去掉后不聯通),然后與點 \(D\)相連的點的度數都為 \(2\)(為葉子)
第五個子任務,如果全部度數\(<= 2\),那么隨便列舉一個點的顏色,然后上述樹形 \(dp\)即可,否則找到度數\(> 2\)的點,剩下的都是度數為\(2,1\)的點,它們僅可能形成一條鏈(不可能是環),然后\(C_6^2\)列舉每條鏈,再花 \(O(k)\)列舉每條鏈的一端顏色,做一遍上述樹形 \(dp\),然后再列舉每個度數 \(> 2\)的顏色,求最小值,復雜度為 \(O(k^6 + nk^3)\),但感覺不太好寫,也沒時間寫了(
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n, k, m;
cin >> n >> m >> k;
vector<vector<int>> pcost(n, vector<int>(k));
for(auto &i : pcost)
for(auto &j : i)
cin >> j;
vector<vector<array<int, 2>>> edge(n);
vector<array<int, 2>> edges(m);
vector<vector<int>> ecost(m, vector<int>(k * k));
for(int i = 0; i < m; ++ i){
int u, v;
cin >> u >> v;
edges[i] = {u, v};
edge[u].push_back({v, i});
edge[v].push_back({u, i});
for(auto &j : ecost[i])
cin >> j;
}
if (n <= 6 && k <= 10){
vector<int> used(n);
LL ans = inf;
LL tmp = 0;
function<void(int)> dfs = [&](int x){
if (x == n){
LL back = tmp;
for(int i = 0; i < m; ++ i){
int u = edges[i][0], v = edges[i][1], id = i;
int r = used[u] * k + used[v];
tmp += ecost[id][r];
}
ans = min(ans, tmp);
tmp = back;
return;
}
for(int i = 0; i < k; ++ i){
tmp += pcost[x][i];
used[x] = i;
dfs(x + 1);
tmp -= pcost[x][i];
}
};
dfs(0);
cout << ans << '\n';
}else if (m == n - 1){
vector<vector<LL>> dp(n, vector<LL>(k, 0));
function<void(int, int)> dfs = [&](int u, int fa){
for(auto e : edge[u]){
int v = e[0], id = e[1];
if (v == fa)
continue;
dfs(v, u);
for(int i = 0; i < k; ++ i){
LL tmp = inf;
for(int j = 0; j < k; ++ j){
int L = i, R = j;
if (u != edges[id][0])
swap(L, R);
int r = L * k + R;
tmp = min(tmp, dp[v][j] + pcost[v][j] + ecost[id][r]);
}
dp[u][i] += tmp;
}
}
};
dfs(0, 0);
LL ans = inf;
for(int i = 0; i < k; ++ i)
ans = min(ans, dp[0][i] + pcost[0][i]);
cout << ans << '\n';
}else if (m == n){
vector<int> id(n);
iota(id.begin(), id.end(), 0);
int ignore = 0;
function<int(int)> findfa = [&](int x){
return x == id[x] ? x : id[x] = findfa(id[x]);
};
for(int i = 0; i < m; ++ i){
int u = edges[i][0], v = edges[i][1];
int fu = findfa(u), fv = findfa(v);
if (fu == fv){
ignore = i;
break;
}
id[fu] = fv;
}
vector<vector<LL>> dp(n, vector<LL>(k, 0));
LL ans = inf;
int fixed = edges[ignore][0], st = edges[ignore][1];
for(int col = 0; col < k; ++ col){
for(auto &i : dp)
fill(i.begin(), i.end(), 0);
function<void(int, int)> dfs = [&](int u, int fa){
for(auto e : edge[u]){
int v = e[0], id = e[1];
if (v == fa || id == ignore)
continue;
dfs(v, u);
for(int i = 0; i < k; ++ i){
if (u == fixed && i != col)
continue;
LL tmp = inf;
for(int j = 0; j < k; ++ j){
if (v == fixed && j != col)
continue;
int L = i, R = j;
if (u != edges[id][0])
swap(L, R);
int r = L * k + R;
tmp = min(tmp, dp[v][j] + pcost[v][j] + ecost[id][r]);
}
dp[u][i] += tmp;
}
}
};
dfs(st, st);
for(int i = 0; i < k; ++ i){
int L = i, R = col;
if (st != edges[ignore][0])
swap(L, R);
int r = L * k + R;
ans = min(ans, dp[st][i] + pcost[st][i] + ecost[ignore][r]);
}
}
cout << ans << '\n';
}else{
vector<int> du(n);
for(int i = 0; i < m; ++ i){
int u = edges[i][0], v = edges[i][1];
++ du[u];
++ du[v];
}
int target = 0;
for(int i = 0; i < n; ++ i){
if (m - du[i] == n - 2){
target = i;
break;
}
}
vector<int> forbid(n, 0);
for(auto &e : edge[target]){
int v = e[0];
forbid[v] = 1;
}
int st = 0;
while(st == target || forbid[st])
++ st;
vector<vector<LL>> dp(n, vector<LL>(k, 0));
LL ans = inf;
for(int col = 0; col < k; ++ col){
for(auto &i : dp)
fill(i.begin(), i.end(), 0);
function<void(int, int)> dfs = [&](int u, int fa){
for(auto e : edge[u]){
int v = e[0], id = e[1];
if (v == fa)
continue;
if (v != target)
dfs(v, u);
for(int i = 0; i < k; ++ i){
LL tmp = inf;
for(int j = 0; j < k; ++ j){
if (v == target && j != col)
continue;
int L = i, R = j;
if (u != edges[id][0])
swap(L, R);
int r = L * k + R;
if (v == target){
tmp = min(tmp, 1ll * ecost[id][r]);
}else{
tmp = min(tmp, dp[v][j] + pcost[v][j] + ecost[id][r]);
}
}
dp[u][i] += tmp;
}
}
};
dfs(st, st);
for(int i = 0; i < k; ++ i){
ans = min(ans, dp[st][i] + pcost[st][i] + pcost[target][col]);
}
}
cout << ans << '\n';
}
return 0;
}
閃耀回圈
題目大意
給定\(n\)個字串\(s_i\) 以及一個字串\(t\),對于每個字串\(s_i\),回答以下問題 :
依次選擇若干個串\(s_j, s_k, s_l, ...\),組成串 \(s_i,s_j,s_k,s_l,...\),要求前一串的末尾字母和后一串的開頭字母相同,第一個串的開頭字母和最后一個串的末尾字母相同,字串 \(t\)的每個字母都在這些串組成的大串出現過,求最小代價,
代價為每個串的長度 \(-1\)的和,
\(|t| \leq 10\)
解題思路
對于每個串,能夠提供的資訊就是首末字母和包含的字串\(t\)的字母情況,
建一張圖,點是每個字母,對于一個串 \(s_i = a...b\),連一條邊 \(b \to a\),邊權有兩個,一個是串長度 \(-1\),另一個是包含的字串 \(t\)的字母情況,因為 \(|t| \leq 10\),可以二進制位壓縮成一個數,
然后設 \(dis[i][j][k]\)表示最侄訓到點 \(i\),當前在點 \(j\),已經獲得到的字串 \(t\)的字母情況為 \(k\),最終到點 \(i\)且字母情況為滿(即包括了 \(t\)的所有字母)的最小代價,
然后從 \(dis[i][i][(1 << |t|) - 1] = 0\)開始 \(dijkstra\)搜,列舉另邊,不斷消去第三維的值,
對于每個串\(s_i\)的資訊\(a, b, sign\)(包含串 \(t\)字母的情況),答案就是\(dis[a][b][c] + |s_i| - 1\),但由于我們是從終點開始搜的,對于第三維是能消去就先消去,但最后求答案是從起點考慮,雖然說經過了這條邊,包含串 \(t\)的字母情況變成 \(sign\),但其中有的字母可以后面的串得到,從終點搜到這里會已經消去,因此這里的\(c\)應該遍歷\(sign\)的所有子集,取最小值,
狀態數是\(O(2^{10} \times 26 \times 26)\),但每個狀態的連邊實際上是有 \(O(n)\)的數量集,轉移代價可能比較大,但或許實際上沒那么大(或者資料水了),就過了,
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
string t;
cin >> n >> t;
vector<int> id(26, -1);
int cnt = 0;
for(auto &i : t){
id[i - 'a'] = cnt;
++ cnt;
}
vector<vector<array<int, 3>>> edge(26);
vector<array<int, 4>> query(n);
for(int i = 0; i < n; ++ i){
string s;
cin >> s;
int st = s.front() - 'a';
int ed = s.back() - 'a';
int sign = 0;
int len = s.size() - 1;
for(auto &i : s){
if (id[i - 'a'] != -1){
sign |= (1 << id[i - 'a']);
}
}
edge[ed].push_back({st, len, sign});
query[i] = {st, ed, sign, len};
}
int up = (1 << cnt);
vector<vector<vector<LL>>> dis(26, vector<vector<LL>>(26, vector<LL>(up, inf)));
for(int i = 0; i < 26; ++ i){
dis[i][i][up - 1] = 0;
priority_queue<array<LL, 3>> team;
team.push({0, i, up - 1});
while(!team.empty()){
array<LL, 3> top = team.top();
team.pop();
LL distance = -top[0];
int u = top[1], sign = top[2];
if (dis[i][u][sign] != distance)
continue;
for(auto &e : edge[u]){
int v = e[0], len = e[1], si = e[2];
int nxtsign = (sign ^ (sign & si));
if (dis[i][v][nxtsign] > distance + len){
dis[i][v][nxtsign] = distance + len;
team.push({-dis[i][v][nxtsign], v, nxtsign});
}
}
}
}
for(int i = 0; i < n; ++ i){
LL ans = inf;
int sign = query[i][2];
for(int s = sign; s; s = (s - 1) & sign)
ans = min(ans, dis[query[i][0]][query[i][1]][s]);
ans = min(ans, dis[query[i][0]][query[i][1]][0]);
if (ans == inf)
ans = -1;
else
ans += query[i][3];
cout << ans << '\n';
}
return 0;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/553661.html
標籤:其他
上一篇:馬斯克要用人工智能對抗人工智能
下一篇:返回列表
