2017 西南交通大学ACM校赛简易题解

2017/5/15敝队打了一发西南交通大学的校赛，仍然3人一台电脑的方式，最终A掉9题，现场竟然最多才A8题。。。

由于线下打的比赛记录好像全部GG了。所以我花了一下午的时间脑补掉了做出来的9道题，就分享一下我们

做出来的题，写个简易题解。。

A：SB题，直接模拟即可。

#include <bits/stdc++.h>
using namespace std;
int n, w, d, x, sum1, sum2;

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d",&n,&w,&d);
        sum1 = sum2 = 0;
        for(int i=1; i<=n; i++){
            scanf("%d", &x);
            sum1+=x;
        }
        for(int i=1; i<=n; i++){
            scanf("%d", &x);
            sum2+=x;
        }
        if(sum1<=w&&sum2<=d) puts("YES");
        else puts("NO");
    }
    return 0;
}

B：SB题，直接维护一个行列指针并且记录一下最后出现的时间就可以了。

#include <bits/stdc++.h>
using namespace std;

struct node{
    int v,t;
}r[510], c[510];

int main(){
    int T, n, q;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n,&q);
        int clk = 0;
        for(int i=1; i<=q; i++){
            int op,x,y;
            scanf("%d%d%d", &op,&x,&y);
            if(op==1){
                r[x].v=y;
                r[x].t=++clk;
            }
            else{
                c[x].v=y;
                c[x].t=++clk;
            }
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<n; j++){
                if(r[i].v==0&&c[j].v==0){
                    printf("0 ");
                }
                else if(r[i].v!=0&&c[j].v==0){
                    printf("%d ", r[i].v);
                }
                else if(r[i].v==0&&c[j].v!=0){
                    printf("%d ", c[j].v);
                }
                else{
                    if(r[i].t>c[j].t){
                        printf("%d ", r[i].v);
                    }
                    else printf("%d ", c[j].v);
                }
            }
            if(r[i].v==0&&c[n].v==0){
                    printf("0\n");
                }
                else if(r[i].v!=0&&c[n].v==0){
                    printf("%d\n", r[i].v);
                }
                else if(r[i].v==0&&c[n].v!=0){
                    printf("%d\n", c[n].v);
                }
                else{
                    if(r[i].t>c[n].t){
                        printf("%d\n", r[i].v);
                    }
                    else printf("%d\n", c[n].v);
                }
        }
    }
}

C：14年西安赛区的原题。题意就是n个格子排成一行，我们有m种颜色，可以给这些格子涂色，保证相邻的

格子的颜色不同问，最后恰好使用了k种颜色的方案数。

容斥原理

首先，用k种颜色的方案为

从k种颜色方案中减去用k-1种颜色方案

多减去的k-2种颜色方案数

答案就是：

这里线形预处理逆元，快速幂加速即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1000010;
const LL mod = 1e9+7;
LL C[maxn];
LL inv[maxn];
LL powmod(LL a, LL b){
    LL res = 1;
    while(b){
        if(b&1) res=(res%mod*a%mod)%mod;
        a=(a%mod*a%mod)%mod;
        b>>=1;
    }
    return res;
}
int main()
{
    int T;
    LL n, m, k;
    scanf("%d", &T);
    while(T--){
        scanf("%lld%lld%lld", &n,&m,&k);
        LL ans = 1;
        inv[1] = 1;
        for(int i=2; i<=k; i++) inv[i] = (mod-mod/i)*inv[mod%i]%mod;
        C[0] = 1;
        for(int i=1; i<=k; i++) C[i]=(C[i-1]%mod*(k-i+1))%mod*inv[i]%mod;
        for(LL i=k; i>=1; i--){
            ans = ((ans*(m-i+1))%mod*inv[i]%mod)%mod;
        }
        LL ans2 = 0;
        for(LL i=0; i<k; i++){
            ans2 = (ans2 + (C[k-i]%mod*(k-i)%mod)*(powmod(k-i-1,n-1)*(i%2==0?1:-1))%mod)%mod;
        }
        ans = (ans%mod*ans2%mod)%mod;
        if(ans < 0) ans+=mod;
        printf("%lld\n", ans);
    }
    return 0;
}

D：题意：本质上就是问从n个数里面能否选出一些数构成3600的倍数。

解法：首先根据抽屉原理，当n > 3600时，一定有presum[i] == presum[j](mod 3600)这里presum表示前

缀和，那么必然n>3600有解，所以我们考虑一个3600的背包即可。dp[i][j]表示考虑到第i个数，当前容量为

j是否能构成，用bool去转移即可。由于数组太大，所以可以用01背包最常见的滚动数组优化一下即可。对

了，比赛的时候，队友直接BITSET做的，这个取模之后bitset长度为3600显然是可以的。转移和上面一样。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
typedef long long LL;
int a[maxn];
bool dp[2][8000];
int main(){
    int T, n;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        if(n>3600){
            puts("YES");
        }
        else{
            int now=0, pre=1;
            memset(dp, 0, sizeof(dp));
            dp[0][0] = 1;
            for(int i=1; i<=n; i++){
                swap(now, pre);
                for(int j=0; j<7200; j++){
                    if((j+a[i])%3600==0) dp[now][3600] |= dp[pre][j];
                    else dp[now][(j+a[i])%7200] |= dp[pre][j];
                    dp[now][j] |= dp[pre][j];
                }
            }
            if(dp[now][3600]) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

E：题意：要你把n个点分成n/2个点对，使得这些点对的距离之和最小。

解法：队友比赛想到了正解orz，实际上就是个贪心。我复制一段官方题解：

考虑每条边对答案的贡献

如果一条边两边的点数是偶数，那么这条边可以不使用，否则，这条边对答案贡献一次

最小性证明：略

可行性证明：

若一条边两边点数为偶数，我们可以直接把这条边删掉，然后变成2个相同的子问题

若一条边两边点数为奇数，我们可以把这条边两边的点配对，然后把他们从图中拿掉,对于某一边，会变成多个

子图，点数为奇数的子图个数是偶数个，我们可以把这些奇数的点拿出来配对，然后又变成相同的子问题

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
typedef long long LL;
struct edge{
    int v, len, next;
    edge(){}
    edge(int v, int len, int next):v(v),len(len),next(next){}
}E[maxn];
struct node{
    int u, v, w;
}q[maxn];
int head[maxn], edgecnt;
void init(){
    memset(head, -1, sizeof(head));
    edgecnt=0;
}
void addedge(int u, int v, int w){
    E[edgecnt].v = v, E[edgecnt].next = head[u], E[edgecnt].len = w,head[u] = edgecnt++;
}
int sz[maxn];
void dfs(int x, int fa){
    sz[x]=1;
    for(int i=head[x];~i;i=E[i].next){
        int v = E[i].v;
        if(v==fa) continue;
        dfs(v, x);
        sz[x] += sz[v];
    }
}
int main()
{
    int T, n;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        init();
        for(int i=1; i<n; i++){
            int s, t, l;
            scanf("%d%d%d", &s,&t,&l);
            addedge(s, t, l);
            addedge(t, s, l);
            q[i].u=s,q[i].v=t,q[i].w=l;
        }
        dfs(1, -1);
        LL ans = 0;
        for(int i=1; i<n; i++){
            int mi = min(sz[q[i].u], sz[q[i].v]);
            int mx = n - mi;
            if(mi%2==0&&mx%2==0) continue;
            ans+=1LL*q[i].w;
        }
        printf("%lld\n", ans);
    }
}

F：题意：就是这个序列必须要把一个数a[i]移到i-k之前的位置，并且恰好移动一次，问可能取到的最大权

值，权值的计算就是sigma(i*a[i])。

解法：很容易证明，移到i-k位置是最优的，所以for循环一遍就可以了。过程如下：

将第i个数移到第j位，那么答案会增加

其中pre[x]表示前x个数和。

所以得证，我比赛的时候尝试二分位置的时候就证明了，越靠后的位置值越大，但是两位大佬一直在写斜率优

化，然后他们也过了。ORZ。看来以后有把握的结论，我还是要冲上去才行。免得浪费精力。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[100010];
LL sum[100010];
LL sum2[100010];
int main()
{
    int T,n,k;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n,&k);
        for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
        memset(sum, 0, sizeof(sum));
        memset(sum2, 0, sizeof(sum2));
        for(LL i=1; i<=n; i++) sum[i]=sum[i-1]+i*a[i], sum2[i]=sum2[i-1]+a[i];
        LL ans=0;
        for(int i=k+1; i<=n; i++){
            LL j = i-k;
            LL temp = sum[j-1]+sum[n]-sum[i];
            temp += j*a[i]+(sum2[i-1]-sum2[j-1])+(sum[i-1]-sum[j-1]);
            ans = max(ans, temp);
        }
        cout<<ans<<endl;
    }
    return 0;
}

G：

同F，我们考虑枚举一个右端点，然后考虑他在哪一个左边的点能取到最大值

当我们枚举到点I的时候，假设我们的将他移到J点，那么我们有F(J)=pre[I-1]-pre[J-1]-i*a[i]+j*a[i]

其中I已经作为常量了,那么我们要计算的就是max(G(I)=J*a[i]-pre[J-1]) 我们把G(i)当做一条直线,J为斜率,-

pre[J-1]为截距,我们的问题就变成了再一堆直线里找一条直线使得当前的取值最大

然后J和pre[J-1]又是单调的,我们可以维护一个下凸包,每次在凸包内二分或者三分斜率来寻找这个最大值即可.

至于移动K次的限制,我们只要将每条直线延迟K步后放入凸包即可

DP太弱，感觉不会写。

H：裸的DAG最长路

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int maxm = 1000010;
typedef long long LL;
struct edge{
    int v,len,next;
    edge(){}
    edge(int v, int len, int next):v(v),len(len),next(next){}
}E[maxm];
int head[maxn], edgecnt;
LL dp[maxn];
void add(int s, int t, int l){
    E[edgecnt] = edge(t,l,head[s]);
    head[s]=edgecnt++;
}
void init(){
    memset(head, -1, sizeof(head));
    edgecnt=0;
}
LL dfs(int x){
    if(dp[x]>0) return dp[x];
    dp[x] = 0;
    for(int i=head[x]; ~i; i = E[i].next){
        dp[x] = max(dp[x],dfs(E[i].v)+1LL*E[i].len);
    }
    return dp[x];
}
int main()
{
    int T, n, m;
    scanf("%d", &T);
    while(T--){
        init();
        scanf("%d%d", &n,&m);
        for(int i=1; i<=m; i++){
            int s, t, l;
            scanf("%d%d%d", &s,&t,&l);
            s++,t++;
            add(s, t, l);
        }
        for(int i=1; i<=n; i++) dp[i] = 0;
        for(int i=1; i<=n; i++){
            if(dp[i]>0) continue;
            dfs(i);
        }
        LL ans = 0;
        for(int i=1; i<=n; i++) ans = max(ans, dp[i]);
        printf("%lld\n", ans);
    }
    return 0;
}

I：数学题，不会。感觉自己也补不了。

J：题意：给了一个原序列，然后一种操作是加一个等差数列，公差固定。然后查询一个点的值。直接线段树

维护一个首项公差，然后这个信息本身就具有懒惰标记的特性，直接写个pushdown，这题就做完了。

这一个是队友写的代码。另外一种方法是分快，但是是nsqrt(n)的，复杂度没有线段树棒。我就没写了。

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
typedef long long LL;
const int maxn = 1e5 + 5;
int c[maxn * 4];
int s[maxn * 4];
void push(int id, int L, int R)
{
    if(c[id])
    {
        int mid = L + R >> 1;
        s[id * 2] += s[id];
        s[id * 2] %= MOD;
        c[id * 2] += c[id];
        c[id * 2] %= MOD;
        s[id * 2 + 1] += s[id] + c[id] * (mid - L + 1);
        s[id * 2 + 1] %= MOD;
        c[id * 2 + 1] += c[id];
        c[id * 2 + 1] %= MOD;
        c[id] = 0;
        s[id] = 0;
    }
}
int a[maxn];
void build(int id, int L, int R)
{
    c[id] = s[id] = 0;
    if(L == R)
    {
        c[id] = 0;
        s[id] = a[L];
    }
    else
    {
        int mid = L + R >> 1;
        build(id * 2, L, mid);
        build(id * 2 + 1, mid + 1, R);
    }
}
void SetFlag(int id, int L, int R, int l, int r, int sol, int col)
{
    if(l <= L && R <= r)
    {
        s[id] += sol + (LL)(L - l) * col;
        s[id] %= MOD;
        c[id] += col;
        c[id] %= MOD;
    }
    else
    {
        int mid = L + R >> 1;
        push(id, L, R);
        if(l <= mid)
            SetFlag(id * 2, L, mid, l, r, sol, col);
        if(mid < r)
            SetFlag(id * 2 + 1, mid + 1, R, l, r, sol, col);
    }
}
LL GetSum(int id, int L, int R, int pos)
{
    if(L == R)
    {
        LL ret = s[id];
        s[id] = 0;
        c[id] = 0;
        return ret;
    }
    else
    {
        int mid = L + R >> 1;
        push(id, L, R);
        if(pos <= mid)
            return GetSum(id * 2, L, mid, pos);
        else
            return GetSum(id * 2 + 1, mid + 1, R, pos);
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n, m, d;
        scanf("%d %d %d", &n, &m, &d);
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        build(1, 1, n);
        while(m--)
        {
            int op;
            scanf("%d", &op);
            if(op == 1)
            {
                int x, y;
                scanf("%d %d", &x, &y);
                SetFlag(1, 1, n, x, n, y, d);
            }
            else
            {
                int pos;
                scanf("%d", &pos);
                printf("%lld\n", GetSum(1, 1, n, pos));
            }
        }
    }
    return 0;
}

K：SB题，暴力统计即可。

#include <bits/stdc++.h>
using namespace std;
int a[110], cnt[110];

int main(){
    int T, n, k, q;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &n,&k,&q);
        memset(cnt, 0, sizeof(cnt));
        for(int i=1; i<=n; i++){
            int x;
            scanf("%d", &x);
            cnt[x]++;
        }
        int ans = 0;
        for(int i=1; i+k-1<=100; i++){
            int t = 0;
            for(int j=i; j<=i+k-1; j++){
                t+=cnt[j];
            }
            if(t>=q) ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

打完比赛，多补题，总结才会有收获QAQ。
……