A - Water Station (abc305 a)
題目大意
給定一個數字\(x\)，輸出一個數字，它是最接近\(x\)的 \(5\)的倍數，
解題思路
令\(y = x \% 5\)，如果 \(y \leq 2\)，那答案就是 \(x - y\)，否則就是 \(x + 5 - y\)，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int x;
cin >> x;
int mod = x % 5;
if (mod <= 2)
x -= mod;
else
x += 5 - mod;
cout << x << '\n';
return 0;
}
B - ABCDEFG (abc305 b)
題目大意
給定\(ABCDEFG\)的相鄰距離，給定兩個字母，問它們的距離，
解題思路
累加距離即可，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
array<int, 7> dis{3,1,4,1,5,9};
string a, b;
cin >> a >> b;
if (a > b)
swap(a, b);
int ans = accumulate(dis.begin() + a[0] - 'A', dis.begin() + b[0] - 'A', 0);
cout << ans << '\n';
return 0;
}
C - Snuke the Cookie Picker (abc305 c)
題目大意
二維平面，有一個矩形少了一塊，問這一塊的位置，
解題思路
找到矩形的左上和右下，然后遍歷矩形的每一塊看看是不是少了，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int h, w;
cin >> h >> w;
vector<string> s(h);
for(auto &i : s)
cin >> i;
int sx = h, sy = w, ex = 0, ey = 0;
for(int i = 0; i < h; ++ i)
for(int j = 0; j < w; ++ j){
if (s[i][j] == '#'){
sx = min(sx, i);
sy = min(sy, j);
ex = max(ex, i);
ey = max(ey, j);
}
}
int ansx = 0, ansy = 0;
for(int i = sx; i <= ex; ++ i)
for(int j = sy; j <= ey; ++ j){
if (s[i][j] == '.'){
ansx = i;
ansy = j;
}
}
cout << ansx + 1 << ' ' << ansy + 1 << '\n';
return 0;
}
D - Sleep Log (abc305 d)
題目大意
給定一個睡覺日志\(a\)，從\(0\)開始（題目從\(1\)開始），奇數項表示醒來的分鐘數，偶數項表示開睡的分鐘數，
回答\(q\)組詢問，每組詢問 \(l, r\)，問從第 \(l\)分鐘到第 \(r\)分鐘，共睡了多久，
解題思路
因為分鐘數高達\(10^9\)，因此不能每分鐘的累加，
先對睡覺日志求一遍睡眠時間的前綴和，
對于詢問 \(l, r\)，先找到第一個大于等于其的日志分鐘數位置 \(posl, posr\)，
答案首先加上 \(a[posl] \to a[posr]\)的睡眠分鐘數（前綴和得出），缺少了時間段 \(l \to a[posl]\)和額外的時間段 \(r \to a[posr]\)，判斷其是否是睡眠的時間段，從而加回答案或減去即可，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<LL> a(n);
for(auto &i : a)
cin >> i;
vector<LL> presum(n);
for(int i = 2; i < n; i += 2){
presum[i] = presum[i - 1] + a[i] - a[i - 1];
if (i < n)
presum[i + 1] = presum[i];
}
int q;
cin >> q;
while(q --){
int l, r;
cin >> l >> r;
int posl = lower_bound(a.begin(), a.end(), l) - a.begin();
int posr = lower_bound(a.begin(), a.end(), r) - a.begin();
LL ans = presum[posr] - presum[posl];
if (~posl & 1)
ans += a[posl] - l;
if (~posr & 1)
ans -= a[posr] - r;
cout << ans << '\n';
}
return 0;
}
E - Art Gallery on Graph (abc305 e)
題目大意
給定一張\(n\)個點 \(m\)條邊的無向圖，邊權為\(1\)，有\(k\)個關鍵點，每個關鍵點\(k_i\)可以監視距離不超過 \(h_i\)的點，
一個點若被至少一個關鍵點監視，則稱該點被監視，
升序給出被監視點的標號，
解題思路
題意就是問每個點距離一堆特殊點的距離是否滿足要求，初看沒什么思路，因為\(k\)和\(n\)是同一個數量級，因此不能 \(k\)次 \(BFS\)，但忽然想到了GXOI/GZOI2019 旅行者，里面為了求一些點到一些點的最短距離，額外增加了個起點和終點，這樣求一次最短路就可以了，
同樣的道理，我們可以也增加一個起點\(st\)，該起點與 \(k\)個關鍵點都連邊，至于邊權，因為每個關鍵點的監視距離不一樣，因此為了統一最后的判斷（距離起點 \(st\)的距離），我們設關鍵點中最大的監視距離為 \(maxx\)，則 \(st \to k_i\)的邊權為 \(maxx - h_i\)，這樣最后從起點跑一遍最短路后，與起點距離不超過 \(maxx\)的點都被監視了，
注意這個起點\(st\)是我們額外加的，實際不存在，要防止關鍵點通過起點監視了其他點，因此要設 \(k_i \to st\)的距離為無窮大，
因為增加了額外點和額外邊，邊權不再是\(1\)了，因此不能跑 \(BFS\)，可以跑 \(Dijkstra\)，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9 + 7;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<array<int, 2>>> edge(n + 1);
auto add = [&](int u, int v, int w = 1, int w2 = 1){
edge[u].push_back({v, w});
edge[v].push_back({u, w2});
};
for(int i = 0; i < m; ++ i){
int a, b;
cin >> a >> b;
-- a, -- b;
add(a, b);
}
int st = n;
int mstamina = 0;
vector<array<int, 2>> p(k);
for(auto &i : p){
cin >> i[0] >> i[1];
i[0] --;
mstamina = max(mstamina, i[1]);
}
for(auto &i : p){
add(st, i[0], mstamina - i[1], inf);
}
priority_queue<array<int, 2>> team;
vector<int> dis(n + 1, inf);
team.push({0, st});
dis[st] = 0;
while(!team.empty()){
auto [expect, u] = team.top();
team.pop();
if (dis[u] != -expect)
continue;
for(auto &[v, w] : edge[u]){
if (dis[u] + w < dis[v]){
dis[v] = dis[u] + w;
team.push({-dis[v], v});
}
}
}
vector<int> ans;
for(int i = 0; i < n; ++ i)
if (dis[i] <= mstamina && dis[i] != inf){
ans.push_back(i + 1);
}
cout << ans.size() << '\n';
for(auto &i : ans)
cout << i << ' ';
cout << '\n';
return 0;
}
F - Dungeon Explore (abc305 f)
題目大意
互動題，
一張無向圖，但你不知道具體情況，從 \(1\)出發到 \(n\)，
一開始處于\(1\)號點，
當你處于 \(i\)號點，裁判會告訴你與 \(i\)號點相鄰的點，
你需要決定下一個去的點的編號，
在移動不超過\(2n\)次走到點 \(n\)，
解題思路
其實就是一個\(DFS\)程序，\(DFS\)程序維護點的訪問狀態，每個點最多進堆疊一次出堆疊一次，因此在不超過 \(2n\)次就可以遍歷所有的點，因此也能到達點 \(n\)，
注意回溯的時候也要讀取回溯點的相鄰點情況，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> visit(n + 1, 0);
function<void(int)> dfs = [&](int u){
if (u == n){
exit(0);
}
int k, _;
cin >> k;
vector<int> nxt(k);
for(auto &i : nxt)
cin >> i;
for(auto &i : nxt){
if (!visit[i]){
cout << i << endl;
visit[i] = 1;
dfs(i);
cout << u << endl;
for(int i = 0; i <= k; ++ i)
cin >> _;
}
}
};
visit[1] = 1;
dfs(1);
return 0;
}
G - Banned Substrings (abc305 g)
題目大意
給定\(m\)個 \(ab\)字串，
問有多少種長度為 \(n\)的字串，其子串不包括這 \(m\)個字串，
\(n \leq 10^{18}\)
解題思路
一眼原，找到了兩年前寫的代碼，直接復制粘貼（
對這\(m\)個字串建立 \(AC\)自動機，然后問題就轉換成有多少條長度為 \(n\)的路徑，其不經過一些特殊點，
經典路徑計數問題，\(dp[i][j]\)表示從起點出發，不經過特殊點，走了\(i\)個點，最終到達點 \(j\) 的方案數，轉移就是從\(i-1\)中列舉 \(j\)的相鄰點轉移，
因為 \(n\)很大，且轉移式子是線性的，\(dp\)轉移可以寫成矩陣的形式，快速冪一下就得到結果了，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x) {
int s = 0, c = getchar();
x = 0;
while (isspace(c)) c = getchar();
if (c == 45) s = 1, c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (s) x = -x;
}
template <typename T>
void write(T x, char c = ' ') {
int b[40], l = 0;
if (x < 0) putchar(45), x = -x;
while (x > 0) b[l++] = x % 10, x /= 10;
if (!l) putchar(48);
while (l) putchar(b[--l] | 48);
putchar(c);
}
class AC_automation{
#define N 300
#define M 2
int trans[N][M];
int fail[N];
int sign[N];
int tot;
public:
void insert(const char *s){
int cur = 0;
sign[cur] = 0;
for(int i = 0; s[i]; ++ i){
if (! trans[cur][s[i] - '0']){
trans[cur][s[i] - '0'] = ++ tot;
sign[tot] = 0;
}
cur = trans[cur][s[i] - '0'];
}
sign[cur] = 1;
}
void build(){
queue<int> team;
for(int i = 0; i < M; ++ i){
if (trans[0][i]) team.push(trans[0][i]);
}
int u = 0;
while(! team.empty()){
u = team.front();
team.pop();
for(int j = 0; j < M; ++ j){
if (trans[u][j]){
fail[trans[u][j]] = trans[fail[u]][j];
team.push(trans[u][j]);
}else{
trans[u][j] = trans[fail[u]][j];
}
sign[trans[u][j]] |= sign[fail[trans[u][j]]];
}
}
}
friend LL work(LL);
}AC;
const LL mo = 998244353;
class Matrix{
public:
LL a[300][300];
int n;
Matrix(int ss,int val = 0){
n=ss;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j){
a[i][j] = val;
}
}
Matrix(const Matrix & b){
n = b.n;
for(int i = 0; i < n; ++ i){
for(int j = 0; j < n; ++ j){
a[i][j] = b.a[i][j];
}
}
}
Matrix operator * (const Matrix & b){
Matrix tmp(this->n);
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
for(int k = 0; k < n; ++ k)
tmp.a[i][j] = (a[i][k] * b.a[k][j] % mo + tmp.a[i][j]) % mo;
return tmp;
}
void print(){
for(int i = 0; i < n ; ++ i){
for(int j = 0; j < n; ++ j){
printf("%lld%c",a[i][j],j==n-1?'\n':' ');
}
}
}
};
Matrix qpower(Matrix a, LL b){
Matrix tmp(a.n);
for(int i = 0; i < a.n; ++ i)
tmp.a[i][i] = 1;
while(b){
if (b&1) tmp = tmp * a;
a = a * a;
b >>= 1;
}
return tmp;
}
LL work(LL n){
int cnt = AC.tot;
Matrix ma(cnt+1);
for(int i = 0; i <= cnt; ++ i){
for(int j = 0; j < M; ++ j){
++ ma.a[i][AC.trans[i][j]];
}
}
int qaq = 0;
for(int i = 0; i <= cnt; ++ i){
if (! AC.sign[i]) ++ qaq;
}
Matrix tmp(qaq);
int x = -1, y = 0;
for(int i = 0; i <= cnt; ++ i){
if (AC.sign[i]) continue;
y = 0;
++ x;
for (int j = 0; j <= cnt; ++ j){
if (AC.sign[j]) continue;
tmp.a[x][y] = ma.a[i][j];
++ y;
}
}
// tmp.print();
Matrix qwq = qpower(tmp,n);
LL ans = 0;
for(int i = 0; i < qaq; ++ i)
ans = (ans + qwq.a[0][i]) % mo;
return ans;
}
char s[15];
int main(){
int m;
LL n;
read(n);
read(m);
while(m--){
scanf("%s",s);
for(size_t i = 0; s[i]; ++ i){
switch(s[i]){
case 'a' : s[i] = '0'; break;
case 'b' : s[i] = '1'; break;
}
}
AC.insert(s);
}
AC.build();
LL ans;
ans = work(n);
write(ans,'\n');
return 0;
}
不過本題的字串只包含\(01\)，可以直接矩陣優化 \(dp\)轉移，
Ex - Shojin (abc305 h)
題目大意
給定\(n\)個二元組 \((a,b)\)，
將二元組拆分成\(k\)段，讓每段的代價的和不超過 \(x\)，
問最小的 \(k\)，以及對應的最小代價和，
每段的代價和定義如下：
首先可以對該段的二元組任意排序，然后初始代價 \(x = 0\)，對每個二元組\((a,b)\)依次計算 \(x = ax + b\)，最后的 \(x\)就是該段的代價，
解題思路
<++>
神奇的代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/554848.html
標籤：其他
下一篇：返回列表