牛客小白月赛54 A-F

A - Sum

最容易想到的思路就是拿个堆，每次找最大的两个数相加。但是这么做复杂度暴了（我不会算）。 考虑优化一下。先排个序，每次贪心的选最大的两个相加（为什么是两个呢，因为少的肯定比多的优，先加的比较少的话，就可以再多加几次）。这个过程就相当于从后往前求和，前缀和优化一下就行（后缀和也行，更方便）。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod = 1e7 + 7, N = 2e5 + 5;
ll a[N], sum[N];

void solve () {
    int n;
    ll ans = 0;
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++)    cin >> a[i];
    sort (a + 1, a + n + 1);
    for (int i = 1; i <= n; i ++)    sum[i] = sum[i-1] + a[i];
    
    for (int i = 1; i < n; i ++) {
        ll dx = sum[n] - sum[n-i-1];
        if (dx < 0)     break;
        ans += dx;
    }
    
    cout << max(0ll, ans % mod) << endl;
}

int main () {
    int t;
    cin >> t;
    while (t --) {
        solve ();
    }
}

B - Gaming

题目要求在不取满 $mm$ 个的情况下尽可能大，易得最优可能是取 $m-1m-1$ 个 容易想到的思路就是枚举那个不选的点，然后比较选取权值最小的去掉。 如图：

权值的计算涉及区间覆盖，可以利用差分来做

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e6 + 5;
int n, m, sum[N];

signed main () {
    cin >> n >> m;
    int ans = 0, tot = 0;
    for (int i = 1; i <= n; i++) {
        int l, r, s;
        cin >> l >> r >> s;
        sum[r+1] -= s, sum[l] += s;
        tot += s;
    }

    for (int i = 1; i <= m; i ++) {
        sum[i] += sum[i-1];
        //cout << sum[i] << ' ';
        ans = max (ans, tot - sum[i]);
    }

    cout << ans << endl;
}


//不取某点，枚举该点

C - School

可以先把时间转化为具体的值（统一化单位为 分），然后问题就变为，有 $nn$ 个区间，$mm$ 次询问某点是否在区间内。对于 $nn$ 个区间可以先进行排序，合并等处理，然后二分查找，时间复杂度就可以由 $O(nq)O(nq)$ 变为 $O(qlogn)O(qlogn)$ 要读入优化，不然会超时 注意如果输入的左端点大于右端点就代表跨了 天 ，故要划分为两个区间

#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int, int> pii;
const int N = 1e3 + 5, M = 2e6 + 5;
int n, m, h, q;
vector <int> l, r;

inline int read()
{
	 int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*f;
}

signed main () {
    n = read(), h = read(), m = read(), q = read();
    int maxn = h*m;
    for (int i = 0; i < n; i ++) {
        int a, b, c, d;
        a = read(), b = read(), c = read(), d = read();
        a = a*m + b, c = c*m + d;   
        if (a > c) {
            l.push_back (a), r.push_back (maxn);
            l.push_back (0), r.push_back (c);
        }
        else    l.push_back(a), r.push_back(c);
    }
    
    sort (l.begin(), l.end()), sort (r.begin(), r.end());
    l.erase (unique(l.begin(), l.end()), l.end());
    r.erase (unique(r.begin(), r.end()), r.end());

    int sz = l.size();
    // for (int i = 0; i < sz; i ++)
    //     cout << l[i] << ' ' << r[i] << endl;

    while (q --) {
        int x, y;
        x = read(), y = read();
        x = x*m + y;
        //cout << x << " ";
        int j = lower_bound (r.begin(), r.end(), x) - r.begin();
        //cout << j << endl;
        if (j == sz)    printf("Yes\n");
        else {
            if (l[j] <= x || r[j] == x)     printf("No\n");
            else    printf("Yes\n");
        }
    }
}


//O(qlogn)

D - Word

可以把每一个单词都看成一个点，两点之间能连边的条件为有且仅有一个字符不同。那么就可以按照这个思路去构造图，然后跑最短路即可。 注意路径记录（有人不会QAQ）

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
const int N = 2005;
int n, m, dis[N], path[N];
string s[N];
bool vis[N];
int a[N][N];

bool match (string a, string b) {
    int dif = 0;
    for (int i = 0; i < m; i ++)
        if (a[i] != b[i])   dif ++;
    if (dif == 1)   return true;
    return false;
}

int dijkstra () {
    for (int i = 0; i <= n; i ++) {
        dis[i] = a[0][i];
        vis[i] = false;
        path[i] = -1;
    }
    vis[0] = true;
    dis[0] = 0;
    for (int i = 0; i <= n; i ++) {
        int p, minn = 0x3f3f3f3f;
        for (int j = 0; j <= n; j ++) {
            if (!vis[j] && dis[j] < minn) {
                p = j;
                minn = dis[j];
            }
        }

        vis[p] = true;
        for (int j = 0; j <= n; j++) {
            if (dis[p] + a[p][j] < dis[j]) {
                dis[j] = minn + a[p][j];
                path[j] = p;
            }
        }
    }

    if (dis[n] == 0x3f3f3f3f)
        return -1;
    return dis[n]-1;
}

void print () {
    stack<int> q;
    int j = n;
    while (path[j] != -1) {
        q.push(j), j = path[j];
    }
    q.push (j);
    cout << s[0] << endl;
    while (!q.empty()) {
        cout << s[q.top()] << endl;
        q.pop();
    }
}

int main () {
    memset (a, 0x3f, sizeof a);
    memset (path, -1, sizeof path);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)   cin >> s[i];
    n ++;
    cin >> s[0] >> s[n];

    if (s[0] == s[n]) {
        cout << 0 << endl;
        cout << s[0] << endl << s[n] << endl;
        return 0;
    }
    
    for (int i = 0; i <= n; i ++) {
        a[i][i] = 0;
        for (int j = i + 1; j <= n; j++) {
            if (s[i] != s[j] && match(s[i], s[j]))
                a[i][j] = a[j][i] = 1;
        }
    }

    int t = dijkstra ();
    cout << t << endl;
    if (t != -1) {
        print();
    }
        
}

//图论
//能转化的建一条边，跑最短路

E - Slash

朴素的线性dp，多一维记录当前匹配的长度 $f[i][j][k]f[i][j][k]$: (i,j)处匹配了k的长度 转移就看拿当前新匹配出的还是原有答案

#include <bits/stdc++.h>

using namespace std;
const int N = 105;
int n, m, len;
string s, t[N];
int f[N][N][N], ans[N][N]; //(i,j)处匹配了k的长度,(i,j)处的答案记录

int main () {
    memset (f, -1, sizeof f);
    memset (ans, -1, sizeof ans);
    cin >> n >> m >> s;
    len = s.size();
    s = ' ' + s;
    for (int i = 1; i <= n; i++) {
        string tt;
        cin >> tt;
        t[i] = ' ' + tt;
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            for (int k = 1; k <= len; k++) {
                if (t[i][j] != s[k])    continue; //不匹配
                if (k == 1) f[i][j][k] = max (0, max (ans[i-1][j], ans[i][j-1])); //新开一段
                else    f[i][j][k] = max (f[i][j][k], max (f[i-1][j][k-1], f[i][j-1][k-1])); //往这一段后面接
                if (k == len)   f[i][j][k] ++; //成了一段
            }
        ans[i][j] = max (f[i][j][len], max (ans[i-1][j], ans[i][j-1])); //新匹配出的与旧的比较
        }

    cout << ans[n][m] << endl;
}


//朴素的dp

F - Traveling

借用一下官方题解的图

看减去dn之后di的奇偶性 偶:过去再回来 奇:选出奇数点中最小的那个边作为中转，对半分构造 剩余奇数点减去该点di就是偶数，转化为过去再回来 图示为满足题目要求能构造出的最小边数，那么剩下来的需要建的边，就可以在没有边的两点间建一条长为1e9的边（不会影响最短路）

输出规范：不能有重边，且前面的点编号必须比后面的大

注意亿点点小细节：

1. $maxnmaxn$ 完全图最大边数 $n\ast (n-1)\mathrm{/}2n*(n-1)/2$ 会爆 $intint$
2. $d_1\mathrm{\ne }{d}_{n}d\_1\backslash neq\; d\_n$ 端点距离不相等，必不可能
3. 图没法联通
4. 有边的差值为奇数的点，但是$d_n=0d\_n=0$，无法构造
5. 至少需要的边数 $tottot$ 大于 $mm$，无法构造
6. 最后构造多余边的时候记得 更新$mm$的值 不过也只有我这种苯人才会犯这样的错误吧！！

上代码~

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
const int N = 3e5 + 5, inf = 1e9;
int n, m, d[N], tot;
vector <pii> odd, even;

int main () {
    //ios::sync_with_stdio (0);cin.tie(0);cout.tie(0);
    scanf ("%d%d", &n, &m);
    long long maxn = 1ll * n*(n-1)/2; //3e5*3e5会爆int
    for (int i = 1; i <= n; i ++)   scanf ("%d", &d[i]);
    if (d[1] != d[n] || m > maxn || m < n-1) {
        printf ("No\n");
        return 0;
    }
    for (int i = 2; i < n; i ++) {
        d[i] -= d[n];
        if (d[i] < 0 || (d[i] % 2 == 1 && d[n] == 0)) {
            printf ("No\n");
            return 0;
        }

        if (d[i] & 1)   odd.push_back ({d[i] + d[n], i});
        else    even.push_back({d[i], i});
    }
    int sz1 = odd.size(), sz2 = even.size();

    tot = sz1 + 1 + sz2 + 1; //最小奇点有两条边 + 1-n的那条边
    if (sz1 == 0)   tot = sz2 + 1;
    //cout << tot << endl;
    if (tot > m) {
        printf ("No\n");
        return 0;
    }
    set <pii> s; //存已构造好的边
    //tot < m的话可以多建几条无穷的边
    printf ("Yes\n");
    printf ("1 %d %d\n", n, d[n]);
    s.insert ({1, n});
    for (auto i : even) {
        int dist = i.first / 2, id = i.second;
        printf ("1 %d %d\n", id, dist);
        s.insert ({1, id});
    }

    if (sz1) {
        sort (odd.begin(), odd.end());
        int base = odd[0].first, st = odd[0].second;
        int half1 = base / 2, half2 = base - half1;
        printf ("1 %d %d\n", st, half1);
        printf ("%d %d %d\n", st, n, half2);
        s.insert ({1, st}), s.insert ({st, n});
        
        for (int i = 1; i < sz1; i ++) {
            int dist = odd[i].first, id = odd[i].second;
            dist -= base, dist /= 2;
            if (st > id) {
                printf ("%d %d %d\n", id, st, dist);
                s.insert ({id, st});
            }
            else {
                printf ("%d %d %d\n", st, id, dist);
                s.insert ({st, id});
            }
        }
    }

    m -= tot;
    for (int i = 1; i <= n && m > 0; i ++)
        for (int j = i + 1; j <= n && m > 0; j ++) {
            if (s.count({i, j}))    continue;
            m --; //就是这里漏了！！！无语
            printf ("%d %d %d\n", i, j, inf);
        }

}

//看-dn之后di的奇偶性
//偶:过去再回来
//奇:选出奇数点中最小的那个边作为中转，对半分构造，
//剩余奇数点减去该点di就是偶数，转化为过去再回来

//输出规范：不能有重边，且前面的点编号必须比后面的大