D. Buy a Ticket
分析
建一个源点,连向所有结点,边的花费为那个结点的花费,图中原有的边花费翻倍,最后跑一遍最短路即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const long long INF = 2e18;
struct Edge { int to; long long w; };
vector<Edge> G[N];
long long d[N];
priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > q;
int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
int u, v;
long long w;
scanf("%d%d%I64d", &u, &v, &w);
G[u].push_back(Edge{v, 2 * w});
G[v].push_back(Edge{u, 2 * w});
}
for(int i = 0; i < n; i++) {
long long x;
scanf("%I64d", &x);
G[0].push_back(Edge{i + 1, x});
}
fill(d, d + N, INF);
d[0] = 0;
q.push(pair<long long, int>(0, 0));
while(!q.empty()) {
pair<long long, int> now = q.top(); q.pop();
if(d[now.second] < now.first) continue;
for(Edge e : G[now.second]) {
if(now.first + e.w < d[e.to]) {
d[e.to] = now.first + e.w;
q.push(pair<long long, int>(d[e.to], e.to));
}
}
}
for(int i = 1; i <= n; i++) printf("%I64d%c", d[i], " \n"[i == n]);
return 0;
}
E. Max History
分析
推公式。
过程这里很详细了。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
const int MOD = 1e9 + 7;
int a[N];
long long qpow(long long x, long long k) {
long long res = 1;
while(k) {
if(k & 1) res = res * x % MOD;
x = x * x % MOD;
k >>= 1;
}
return res;
}
int main() {
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a, a + n);
long long x = 1, ans = 0;
for(int i = 0; i < n; i++) x = x * (i + 1) % MOD;
for(int i = 0; i < n - 1; i++) {
if(a[i] == a[n - 1]) break;
ans = (ans + (a[i] * x % MOD) * qpow(n - (lower_bound(a, a + n, a[i]) - a), MOD - 2) % MOD) % MOD;
}
cout << ans << endl;
return 0;
}
F. Erasing Substrings
分析
这道题很神奇。
设 \(n\) 为字符串长, \(m\) 为不超过 \(n\) 的最大的 \(2\) 的倍数。
那么最后答案长度为 \(n-m+1\),组成答案的这些字符中,第一个字符一定是在原子符串区间 \([0,m-1]\) 内取到的,第二个在区间 \([1,m]\) 内取到的,后面同理。
\(f[i]\) 为 \(1\) 则表示可以转移到 \(i\) 这个状态,其中 $ 0\leq i < m$,二进制位为 \(1\) 对应某个长度的删除操作已经执行过了。
每次右移一个字符,然后我们选择要转移到的状态,因为前面已经有一个字符成为答案中的一个字符了,所以比较的时候应该是 \(s[i + j]\) 而不是 \(s[j]\)。
每次我们都要更新出下次可以转移到的合法状态,如果现在的状态是 \(1001\) ,即前面已经删过了长度为 \(1\) 和 \(8\) 的子串,我们可以转移到 \(1001, 1101, 1011, 1111\) ,即我们可以选择删掉长度为 \(2\) 或 \(4\) 的子串,或者不删,直接取接下来的字符。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N], g[N];
char ans[N];
int main() {
string s;
cin >> s;
int n = s.length();
int m = 1;
while(m <= n) m <<= 1; m >>= 1;
for(int i = 0; i < m; i++) f[i] = 1;
for(int i = 0; i <= n - m; i++) {
ans[i] = 'z';
for(int j = 0; j < m; j++) {
if(f[j] && s[i + j] < ans[i]) ans[i] = s[i + j];
}
memset(g, 0, sizeof g);
for(int j = 0; j < m; j++) {
if(!g[j] && f[j] && ans[i] == s[i + j]) {
int w = m - 1 - j;
for(int k = w; k; k = w & (k - 1)) g[m - 1 - k] = 1;
g[m - 1] = 1;
}
}
for(int j = 0; j < m; j++) f[j] = g[j];
}
ans[n - m + 1] = 0;
printf("%s", ans);
return 0;
}