Problem M. Walking Plan

PS: 题目编号是乱排的, 请不要介意…

题意

给定一个 n 个点,m 条边的有向图,q 次询问 s 到 t 经过至少 k 条边的最短路。
2 ≤ n ≤ 50, 1 ≤ m, k ≤ 10000, 1 ≤ q ≤ 100000.

分析:

这道题…一眼看出就是矩乘题, 但是确实是出的非常好的题目
比如之前的一道题: 沼泽鳄鱼
我们对于这道题也可以采用类似的方法!

  • G[i][j] 表示i一步到j的最短路
  • f[t][i][j]表示i到j恰好经过t条边的最短路

不难发现它具有这样的性质: f[t][i][j] = min(f[t − 1][i][k] + G[k][j])
考虑以下也可以得出 f_t=G^t , 只不过这种乘法是取min而不是相加, 那么我们考虑可以利用分块思想

矩阵A_i表示G^{100i}, B_i表示G^i.
那么对于一个走k的边的询问就是可以走

final=A^{\frac k{100}}*B^{k \ mod\ 100}

那么至少是k条我们就可以将B矩阵通过Floyd跑出至少是经过k条边的B_k然后就好了
具体看代码…

代码:

#pragma GCC optimize(2)
#define R register
#define P pair<int, int>
#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long LL;

const int N = 55, M = 105;
const int INF = 0x3f3f3f3f; 

int T, n, m, x, y, z, s, t, K, a[M][N][N], b[M][N][N], g[N][N], f[N][N];

inline void Min(int &x, int y) { if(y < x) x = y; }
inline void multi(int a[][N], int b[][N], int c[][N])
{
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j++)
        {
            f[i][j] = INF;
            for(int k = 1; k <= n; k++) Min(f[i][j], a[i][k] + b[k][j]);
        }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) c[i][j] = f[i][j];
}
inline void Floyd()
{
    for(int i = 1; i <= n; i++) Min(g[i][i], 0);
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                Min(g[i][j], g[i][k] + g[k][j]);
}
int main()
{
    scanf("%d", &T);
    for(int _ = 1; _ <= T; _ ++)
    {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) g[i][j] = INF;
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &x, &y, &z);
            Min(g[x][y], z);
        }
        for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) b[0][i][j] = a[0][i][j] = (i == j) ? 0 : INF;
        for(int i = 1; i <= 100; i++) 
            multi(a[i - 1], g, a[i]);
        for(int i = 1; i <= 100; i++)
            multi(b[i - 1], a[100], b[i]);
        Floyd();
        for(int used = 0; used <= 100; used++)
        {
            for(int i = 1; i <= n; i++)  for(int j = 1; j <= n; j ++) f[i][j] = INF;
            for(int i = 1; i <= n; i++) 
                for(int j = 1; j <= n; j++)
                    for(int k = 1; k <= n; k++)
                        Min(f[i][j], b[used][i][k] + g[k][j]);
            for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) b[used][i][j] = f[i][j];
        }
        int Q; scanf("%d", &Q);
        for(int i = 1; i <= Q; i++)
        {
            scanf("%d%d%d", &s, &t, &K);
            int A = K % 100, B = K / 100, res = INF;
            for(int j = 1; j <= n; j ++) Min(res, b[B][s][j] + a[A][j][t]);
            printf("%d\n", (res == INF) ? -1 : res);
        }
    }
    return 0;
}

Problem L. Visual Cube

直接大力模拟就好了…

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
#define P pair<int, int>
#define R register
using namespace std;
typedef long long LL;
typedef double db;

const int N = 250;
const LL MOD = 1000000007, INF = 0x3f3f3f3f;

int T, a, b, c, n, m;
char s[N][N];
signed main()
{
    scanf("%d", &T);
    for(int _ = 1; _ <= T; _++)
    {
        scanf("%d%d%d", &a, &b, &c);
        n = ((c + b) << 1) + 1;
        m = ((a + b) << 1) + 1;
        for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) s[i][j] = '!';
        for(int i = 1 + 2 * b; i <= n ; i ++)
        {
            int flag = 1;
            for(int j = 1; j <= 2 * a + 1; j ++)
            {
                if(i & 1)
                {
                    if(flag) s[i][j] = '+', flag ^= 1;
                    else s[i][j] = '-', flag ^= 1;
                }
                else
                {
                    if(flag) s[i][j] = '|', flag ^= 1;
                    else s[i][j] = '.', flag ^= 1;
                }
            }
        }
        int empty = 2 * b;
        for(int pp = n; pp >= n - 2 * b + 1; pp--)
        {
            int up = pp;
            int row = n - pp + 1, col = m - (n - pp);
            for(int i = 1; i <= empty; i++) s[row][i] = '.';
            for(int i = 1; i <= empty; i++) s[n - i + 1][col] = '.';

            if(! (empty & 1))
            {
                int flag = 1;
                for(int i = empty + 1; i <= col; i++)
                {
                    if(flag) s[row][i] = '+', flag ^= 1;
                    else s[row][i] = '-', flag ^= 1;
                }
                flag = 1;
                for(int i = row + 1; i <= n && s[i][col] == '!'; i ++)
                {
                    if(flag) s[i][col] = '|', flag ^= 1;
                    else s[i][col] = '+', flag ^= 1;
                }
            }
            else
            {
                int flag = 1;
                for(int i = empty + 1; i <= col; i++)
                {
                    if(flag) s[row][i] = '/', flag ^= 1;
                    else s[row][i] = '.', flag ^= 1;
                }
                flag = 1;
                for(int i = row + 1; i <= n && s[i][col] == '!'; i ++)
                {
                    if(flag) s[i][col] = '.', flag ^= 1;
                    else s[i][col] = '/', flag ^= 1;
                }
            }
            empty --;
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
                cout <<s[i][j];
            puts("");
        }
    }
    return 0;
}

A. Ascending Rating

题意

给定一个序列 {a_n},对于每个长度为 m 的连续子区间,
求出区间 a 的最大值以及从左往右扫描该区间时 a 的最大值的
变化次数。(1 ≤ m ≤ n ≤ 107)

分析

我们其实可以用单调队列来维护, 不难发现, 当我们将序列从右往左加入队列并且维护的是一个严格上升的单调队列的时候, 队尾元素其实就是区间最大值, 而且队列里元素的个数就是这个[l, l + m – 1] 区间的cnt大小.
(不得不说, 单调队列被标算艹爆了…)

代码:

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
const int N = 10005000;
typedef long long LL;

int T, n, m, k;
LL p, q, t, r, MOD, head, tail, G[N], a[N];

signed main()
{
  scanf("%d", &T);
  for(int _ = 1; _ <= T; _++)
  {
    head = 1, tail = 0;
    LL A = 0, B = 0;
    scanf("%d%d%d%lld%lld%lld%lld", &n, &m, &k, &p, &q, &r, &MOD);
    for(int i = 1; i <= k; i++) scanf("%lld", a + i);
    for(int i = k + 1; i <= n; i++) a[i] = (p * a[i - 1] + q * i + r) % MOD;
    for(int i = n; i >= 1; i--)
    {
      while(head <= tail && G[head] > i + m - 1) head++;
      while(head <= tail && a[G[tail]] <= a[i]) tail--;
      G[++tail] = i;
      if(i <= n - m + 1)
        {
          A += a[G[head]] ^ (LL)i;
          B += (tail - head + 1) ^ (LL)i;
        }
    }
    printf("%lld %lld\n", A, B);
  }
  return 0;
}

I. Random Sequence

题意:

给定一个正整数序列 {a_n},每个数在 [1, m] 之间,有些数
已知,有些数未知。
求未知数随机填的情况下以下值的期望:

\prod_{i=1}^{n-3}v[gcd(a_i,a_{i+1},a_{i+2},a_{i+3})]

(4 ≤ n ≤ 100, 1 ≤ m ≤ 100)

分析:

感觉这种题就是套路题
直接贴一发标程的思路, 我的数组是滚动的! 如下:

f_{i,x,y,z} 表示考虑前 i 个位置,
a_i = x, gcd(a_i, a_{i−1}) = y, gcd(a_i, a_{i−1}, a_{i−2}) = z 的期望
枚举 a_{i+1} 的值转移即可
时间复杂度 \Theta(nmS),其中 S 表示 (x, y, z) 的状态数。
显然合法状态中 y|x, z|y,当 m = 100 时 S = 1471

代码

My Code:

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define R register
#define P pair<int, int>
using namespace std;
typedef double db;
typedef long long LL;

const int N = 105, INF = 0x3f3f3f3f; 
const LL MOD = 1000000007;

int T, n, m, a[N], G[N][N], inv, ans, v[N], f[2][N][N][N];

LL gcd(LL x, LL y) { return (!y) ? x : gcd(y, x % y); }
LL Pow(LL a, LL b)
{
    LL res = 1;
    while(b)
    {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res % MOD;
}
void init()
{
    for(int i = 1; i <= 100; i++)
        for(int j = 1; j <= 100; j++) 
            G[i][j] = gcd(i, j);
}
int main()
{
    init();
    scanf("%d", &T);
    for(int _ = 1; _ <= T; _++)
    {
        scanf("%d%d", &n, &m); ans = 0;
        inv = Pow(m, MOD - 2);
        for(int i = 1; i <= n; i++) scanf("%d", a + i);
        for(int i = 1; i <= m; i++) scanf("%d", v + i);
        for(int x = 1; x <= m; x++)
                for(int y = x; y <= m; y += x)
                    for(int z = y; z <= m; z += y) 
                        f[0][x][y][z] = f[1][x][y][z] = 0;
        if(a[1]) f[1][a[1]][a[1]][a[1]] = 1; 
        else for(int i = 1; i <= m; i++) f[1][i][i][i] = inv;

        for(R int pp = 1; pp <= n; pp++)
        {
            int i = (pp & 1), j = i ^ 1;
            for(int x = 1; x <= m; x++)
                for(int y = x; y <= m; y += x)
                    for(int z = y; z <= m; z += y) f[j][x][y][z] = 0;
            for(int x = 1; x <= m; x++)
                for(int y = x; y <= m; y += x)
                    for(int z = y; z <= m; z += y) if(f[i][x][y][z])
                    {
                        if(!a[pp + 1]) 
                        {
                            for(int mark = 1; mark <= m; mark ++)
                            {
                                LL add = (pp >= 3) ? v[G[x][mark]] : 1;
                                (f[j][ G[y][mark] ][ G[z][mark] ][mark] += 1LL * inv * f[i][x][y][z] % MOD * add % MOD) %= MOD;
                            }
                        }
                        else 
                        {
                            LL add = (pp >= 3) ? v[ G[x][a[pp + 1]] ] : 1;
                            ( f[j][G[y][a[pp + 1]]][G[z][a[pp + 1]]][a[pp + 1]] += 1LL * f[i][x][y][z] * add % MOD) %= MOD;
                        }
                        if(pp == n) ans = (ans + f[i][x][y][z]) % MOD;
                    }
        }
        printf("%d\n", ans);
    }
    return 0;
}

Standard Code:

#include<cstdio>
const int N=110,M=1500,P=1000000007;
int T,n,m,i,j,k,x,y,cnt,gcd[N][N],v[N],a[N],id[N][N][N],g[M][N],w[M][N],f[N][M],ans;
int getgcd(int a,int b){return b?getgcd(b,a%b):a;}
int po(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)t=1LL*t*a%P;return t;}
inline void up(int&a,int b){a=a+b<P?a+b:a+b-P;}
int main(){
  scanf("%d",&T);
  while(T--){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(i=1;i<=m;i++)scanf("%d",&v[i]);
    for(i=1;i<=m;i++)for(j=1;j<=m;j++)gcd[i][j]=getgcd(i,j);
    cnt=0;
    for(i=1;i<=m;i++)for(j=i;j<=m;j+=i)for(k=j;k<=m;k+=j)id[i][j][k]=++cnt;
    for(i=1;i<=m;i++)for(j=i;j<=m;j+=i)for(k=j;k<=m;k+=j){
      x=id[i][j][k];
      for(y=1;y<=m;y++){
        g[x][y]=id[gcd[j][y]][gcd[k][y]][y];
        w[x][y]=v[gcd[i][y]];
      }
    }
    for(i=1;i<=n;i++)for(j=1;j<=cnt;j++)f[i][j]=0;
    for(i=1;i<=m;i++)for(j=1;j<=m;j++)for(k=1;k<=m;k++){
      if(a[1]&&i!=a[1])continue;
      if(a[2]&&j!=a[2])continue;
      if(a[3]&&k!=a[3])continue;
      up(f[3][id[gcd[gcd[i][j]][k]][gcd[j][k]][k]],1);
    }
    for(i=3;i<n;i++)for(j=1;j<=cnt;j++)if(f[i][j])for(k=1;k<=m;k++){
      if(a[i+1]&&k!=a[i+1])continue;
      up(f[i+1][g[j][k]],1LL*f[i][j]*w[j][k]%P);
    }
    ans=0;
    for(j=1;j<=cnt;j++)up(ans,f[n][j]);
    for(i=1;i<=n;i++)if(!a[i])ans=1LL*ans*po(m,P-2)%P;
    printf("%d\n",ans);
  }
}

H. Monster Hunter

题意:

不讲了, 看题面吧…

分析:

那么我们会发现, 将怪兽分为以下种类:
1. a=b

可以轻松发现, 打第一种怪物是加血的, 而打第二种怪物是最后会扣血的, 那么对于第一类Monster, 我们也发现肯定是从a小的开始, 而对于第二种Monster, 我们考虑打(i, j) 还是(j, i)更优

不妨令b_j \leq b_i, 有

(i,j):=min(-a_i, -a_i+b_i-a_j) \ (1)\\
(j,i):=min(-a_j,-a_j+b_j-a_i) \ (2)

对其进行放缩, 有:

-a_i+b_j-a_j\leq-a_i+b_i-a_j \ and-a_j-a_i+b_j\leq-a_i

那么我们是不是可以说(1)式完全优于(2)式, 因为一式的两项均大于2式的第二项,而由于是取min操作, 那么二式是不大于一式的, 于是我们发现第二种怪物只与b的值有关, 于是对其大到小排序

那么对于整个序列, 我们发现不一定能够取到, 因为考虑到父亲是否有被取走, 但是一定是父亲取完直接去打最优序列中的Monster最优, 于是可以合并它与它的父亲,当做一个节点!

用个堆来维护这些元素, 并且使用并查集维护父亲是否有被取走, 最后答案就是root节点的a值.

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = (int) (1e5) + 50;

int T, n, x, y, f[N], vis[N], del[N];
vector<int> G[N];
struct node
{
    LL a, b; int id;
    bool operator < (const node &x) const
    {
        int sy1 = a < b, sy2 = x.a < x.b;
        if(sy1 != sy2) return sy1 < sy2;
        if(sy1) return a > x.a;
        return b < x.b;
    } 
    void operator += (const node &x)
    {
        LL aa = max(a, a - b + x.a), bb = b + x.b - a - x.a + aa;
        a = aa, b = bb; 
    }
}a[N];
typedef pair<node, int> P; // node and time
priority_queue<P> Q;

void dfs(int u, int fa)
{
    f[u] = fa;
    for(int i = 0; i < (int) G[u].size(); i++)
    {
        int v = G[u][i]; if(v == fa) continue;
        dfs(v, u);
    }
}
int Find(int x)
{
    return del[f[x]] ? f[x] = Find(f[x]) : f[x];
}
int main()
{
    // freopen("data.in", "r", stdin);
    scanf("%d", &T);
    for(int _ = 1; _ <= T; _ ++)
    {
        scanf("%d", &n);
        for(int i = 2; i <= n; i++) scanf("%lld%lld", &a[i].a, &a[i].b), a[i].id = i;
        for(int i = 1; i <= n; i++) 
        {
            G[i].clear();
            vis[i] = del[i] = 0;
        }
        for(int i = 2; i <= n; i++)
        {
            scanf("%d%d", &x, &y);
            G[x].push_back(y), G[y].push_back(x);
        }
        dfs(1, 0); a[1] = (node){0, 0, 1};
        for(int i = 2; i <= n; i++) Q.push(P(a[i], 0));
        while(!Q.empty())
        {
            P now = Q.top(); Q.pop();
            int u = now.first.id;
            if(del[u]) continue;
            if(vis[u] != now.second) continue;
            del[u] = 1;
            int fx = Find(u);
            a[fx] += a[u];
            if(fx > 1) Q.push(P(a[fx], ++vis[fx]));
        }   
        printf("%lld\n", a[1].a);
    }
    return 0;
}

Leave a Reply