分析

建一个源点，连向所有结点，边的花费为那个结点的花费，图中原有的边花费翻倍，最后跑一遍最短路即可。

code

#include
    
     using namespace std;const int N = 2e5 + 10;const long long INF = 2e18;struct Edge { int to; long long w; };vector
     
       G[N];long long d[N];priority_queue
      
       
        , vector
        
         
           >, greater
          
           
             > > 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
            
             (0, 0)); while(!q.empty()) { pair
             
               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
              
               (d[e.to], e.to)); } } } for(int i = 1; i <= n; i++) printf("%I64d%c", d[i], " \n"[i == n]); return 0;}
              
             
            
           
          
         
        
       
      
     
    

分析

推公式。

过程很详细了。

code

#include
    
     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;}
    

分析

这道题很神奇。

设 \(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
    
     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;}