2019 西电ACM校赛网络赛题解

佚名 6年前 (2019-04-25) 随笔 1702人围观抢沙发百度已收录

今年题目难度有较大提升，总体与往年类似，数学题居多。以下为我通过的部分题解。

A -

我也没去过澳门赌场，不熟悉什么筹码之类。看完题有点懵，但毕竟是签到题。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题目大概是隐含了总筹码数量相同这一条件，然后每个人开始的筹码都是一样的。给你一组每个人手上筹码的局面，然后有q组询问，让你判断现在局面是否合法，其中一个人赢了还是输了。

比较简单，废话不多说直接上代码：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;

ll arr[1010], qi[1010];
int main()
{
    int n, m, q;
    ll total = 0;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>arr[i], total += arr[i];
    cin>>q;

    for(int i=0;i<q;i++)
        cin>>qi[i];

    if(total%n)
        cout<<"you ren chu qian?\n";
    else {
        total /= n;
        for(int i=0;i<q;i++)
            if(arr[qi[i]-1]>total) cout<<"jian hao jiu shou!\n";
            else if(arr[qi[i]-1]<total) cout<<"ji shi zhi sun!\n";
            else cout<<"wei shi bu wan!\n";
    }
    return 0;
}

View Code

B -

感觉太复杂了，一直没做，AC了再来更新吧。大概就是一个思维题。

C -

简单的BFS，开始题目看错了，以为求min(disA+disB)，交上去WA了一发，再看题发现是求min(max(disA, disB));

因为偷懒用一个数组存（i,j)到两地的最大距离，不明不白WA了半天。。。思考问题一定要考虑周全啊！！！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

int n, m;
char mp[220][220];
int s1x, s1y, s2x, s2y, k;
bool vis[220][220];
int dis[220][220];
const int dx[]={0, 0, 1, -1};
const int dy[]={1, -1, 0, 0};
struct node{
    int x, y;
    int step;
    node(int xx=0, int yy=0, int s=0):x(xx), y(yy), step(s){}
} sta[220];
void bfs(int t, int x, int y)
{
    vis[x][y] = 1;
    queue<node> q;
    q.push(node(x, y, 0));
    while(q.size()) {
        node now = q.front(); q.pop();
        for(int i=0;i<4;i++) {
            int nx = now.x+dx[i];
            int ny = now.y+dy[i];
            if(nx>=0 && nx<n && ny>=0 && ny<m && !vis[nx][ny] && mp[nx][ny]!='#') {
                vis[nx][ny] = 1;
                if(mp[nx][ny]=='P') {
                    if(t==0) dis[nx][ny] = now.step+1;
                    else if(dis[nx][ny])
                        dis[nx][ny] = max(now.step+1, dis[nx][ny]);
                }
                q.push(node(nx, ny, now.step+1));
            }

        }
    }
}
int main()
{
    while(cin>>n>>m)
    {
        k = 0;
        getchar();
        for(int i=0;i<n;i++) {
            scanf("%s", mp[i]);
            for(int j=0;mp[i][j];j++)
                if(mp[i][j]=='P') sta[k].x = i, sta[k++].y=j;
                else if(mp[i][j]=='X') s1x = i, s1y = j;
                else if(mp[i][j]=='Y') s2x = i, s2y = j;
        }
        memset(dis, 0, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        bfs(0, s1x, s1y);
        memset(vis, 0, sizeof(vis));
        bfs(1, s2x, s2y);

        int x, ans = 10000000;
        for(int i=0;i<k;i++)
            if(dis[sta[i].x][sta[i].y] && dis[sta[i].x][sta[i].y]<ans)
                x = i, ans = dis[sta[x].x][sta[x].y];
        cout<<sta[x].x+1<<' '<<sta[x].y+1<<endl;
    }

    return 0;
}

View Code

D -

这题难点在于读懂题目，然后就是要找规律。直白说比赛安排表类似一个数独，添上一行123...N的表头代表队员编号的话，那么整个表就有N行N列。我们要使每行每列都有1~N，并且要找到一个字典序最小的方案。

第一天我很天真地以为，简单把123...N的排列每次循环左移就能得到字典序最小的安排表。WA了三次后，在纸上排一遍发现还能有更优的排法，排表过程中要用到dfs，复杂度O(2^2N），就扔到一边没管了。过了两天根据Wu找的规律几分钟写了代码就直接AC了，哈哈哈。

#include<iostream>
#include<cstdio>
using namespace std;
int ans[1024][1024];
const int num[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
void pre()
{
    ans[0][0] = ans[1][1] = 1;
    ans[0][1] = ans[1][0] = 2;

    int s = 2;
    while(s<1024) {
        for(int i=s;i<2*s;i++)
        for(int j=0;j<s;j++)
            ans[i][j] = s+ans[i-s][j];

        for(int i=0;i<s;i++)
        for(int j=s;j<2*s;j++)
            ans[i][j] = s+ans[i][j-s];

        for(int i=s;i<2*s;i++)
        for(int j=s;j<2*s;j++)
            ans[i][j] = ans[i-s][j-s];
        s *= 2;
    }
}
int main()
{
    pre();
    for(int i=0;i<32;i++) {
        for(int j=0;j<32;j++)
            printf("%2d ", ans[i][j]);
        cout<<endl;
    }
    int T; cin>>T;
    int n, m, x;
    while(T--)
    {
        scanf("%d %d %d", &n, &m, &x);
        if(m<1||m>num[n]||x<1||x>num[n]-1)
            cout<<"Wrong Query!\n";
        else {
            cout<<ans[x][m-1]<<endl;
        }

    }
    return 0;
}

View Code

E -

一眼扫去这不就是Nim博弈吗？然后就快速写了个Nim和，交上去就WA了。再细看发现结束的规则不一样，取走最后的石子者为败家。想了半天还是不太会博弈，既然状态有限，就写了记忆化搜索，调试好样例交上就AC了。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int s[7][7][7][7][7][7];  // s=0 败  s=1 胜
int solve(int a, int b, int c, int d, int e, int f)
{
    if(a+b+c+d+e+f==1) return 0;
    if(s[a][b][c][d][e][f]!=-1)
        return s[a][b][c][d][e][f];

    for(int i=1;i<=a;i++)
        if(solve(a-i, b, c, d, e, f)==0) return s[a][b][c][d][e][f]=1;
    for(int i=1;i<=b;i++)
        if(solve(a, b-i, c, d, e, f)==0) return s[a][b][c][d][e][f]=1;
    for(int i=1;i<=c;i++)
        if(solve(a, b, c-i, d, e, f)==0) return s[a][b][c][d][e][f]=1;
    for(int i=1;i<=d;i++)
        if(solve(a, b, c, d-i, e, f)==0) return s[a][b][c][d][e][f]=1;
    for(int i=1;i<=e;i++)
        if(solve(a, b, c, d, e-i, f)==0) return s[a][b][c][d][e][f]=1;
    for(int i=1;i<=f;i++)
        if(solve(a, b, c, d, e, f-i)==0) return s[a][b][c][d][e][f]=1;

    return s[a][b][c][d][e][f]=0;

}
int arr[6];
int main()
{
    memset(s, -1, sizeof(s));
    s[0][0][0][0][0][0] = 1;
    int n;
    while(scanf("%d", &n)!=EOF) {
        memset(arr, 0, sizeof(arr));
        for(int i=0;i<n;i++)
            scanf("%d", &arr[i]);

        printf("%s\n", solve(arr[0],arr[1],arr[2],arr[3],arr[4],arr[5])?"orzwym6912":"orzwang9897");
    }
    return 0;
}

View Code

网上查阅了相关的题，理解了这个规则其实同样可以用Nim和来解决，只需要特殊判断全部堆都是1的情况。因为在Nim博弈中，最后一步要取走全部石子，那么本题对于必胜者也可以少取走一颗石子，那么也是必胜。但是如果每堆只有一颗石子，就无法按照Nim博弈的进行最优取法。显然有偶数个为1的堆为必胜态，那么问题就解决了。

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n;
    while(scanf("%d", &n)!=EOF) {
       int ans = 0, k;
        bool flag = 1; int cnt = 0;
        while(n--) {
            scanf("%d", &k);
            if(k==0) continue;

            if(k!=1) flag = 0;
            else cnt++;
            ans ^= k;
        }
        if(!flag)
            printf("%s\n", ans==0?"orzwang9897":"orzwym6912");
        else
            printf("%s\n", cnt&1?"orzwang9897":"orzwym6912");
    }
    return 0;
}

View Code

F -

通过找规律+oeis.org归纳出公式，最后发现了这题主要是得到第二类斯特林数。结果就是s(n, i)*i!/n^m。

那么怎么求s(n, i)呢？查阅资料得知这个跟组合数有相似的递推性质，可以在O(n²)时间内求出s(n, i)。此题n,m<100000,显然不行。

翻了好多篇博客，都提到要用快速傅里叶变换，然后就自闭了。

（待补。。。）

G -

这题就是求有n个不同节点的连通图的种类。

开始自己手算了递推式，样例都算不对，只好百度借鉴了别人的公式。

写好快速幂+组合数WA了好多次，debug很久，一度怀疑幂运算取模出错了，要用那啥费马小定理。最后比对别人的输出才突然注意到三个ll相乘会溢出的重大bug。。。

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;

const ll mod=1000000007;
ll C[1010][1010], f[1010];
ll pow_mod(ll a, ll x)
{
    ll res = 1;
    while(x) {
        if(x&1) res = (res*a)%mod;
        a = (a*a)%mod;
        x >>= 1;
    }
    return res;
}
ll Cn2(int n)
{
    return (ll)n*(n-1)/2;
}
void solve()
{
    for(int i=0;i<1010;i++)
    C[i][i] = C[i][0] = 1;

    for(int i=1;i<1010;i++)
    for(int j=1;j<=i;j++) {
        C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
    }

    f[1] = f[2] = 1;
//    f[3] = 4;
    for(int n=3;n<1010;n++) {
        for(int i=1;i<n;i++)
            f[n] = (f[n] + ((C[n-1][i-1]*f[i])%mod * pow_mod(2, Cn2(n-i))%mod))%mod;

        f[n] = ((pow_mod(2, Cn2(n))-f[n])%mod+mod)%mod;
    }
}

int main()
{
    int T; cin>>T;
    solve();
    while(T--) {
        int m; scanf("%d", &m);
        printf("%lld\n", f[m]);
    }
    return 0;
}

View Code

2的C(n,2)次方我为什么要用组合数。。。

H -

一个简单技巧题被我硬生生用二分法暴力求解，一直TLE到怀疑人生。（虽说复杂度O(T*2ⁿ*logn)很勉强的样子）

由于a1 + a2 + ... + ai <= a(i+1)，那么对于K，我们从后往前查找，如果a(i+1)<=K，不取a(i+1)的话就无法选择前i项使总和为K，所以a(i+1)必选。因此不断往前贪心即可。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
ll arr[44], K;

ll pow2(ll a, int x)
{
    ll res = 1;
    while(x) {
        if(x&1) res *= a;
        a *= a;
        x >>= 1;
    }
    return res;
}

int main()
{
    int T, n; scanf("%d", &T);
    while(T--) {
        scanf("%d %lld", &n, &K);
        for(int i=1;i<=n;i++)
            scanf("%lld", &arr[i]);

        int i=n;
        ll res = 0;
        while(K>0) {
            while(i>=1 && arr[i]>K) i--;
            if(i<1) break;
            else
                K -= arr[i], res += pow2(2, i);
        }
        if(K==0)
            printf("%lld\n", res);
        else
            printf("-1\n");
    }
    return 0;
}

View Code

I -

哈哈不会，据说需要各种暴力+建图。我还是好好掌握prim啊、dijkstra啊这种再来吧。。。

J - 签到题

到了传说中的签到题，好几天都一直没人做。读完题发现就是求解三个球面的交点问题，可以直接联立方程求解。

为了体现出它不是一个数学问题，我尝试用计算几何的思维，二分两平面的交线。WA了十来次才发现连输出要求都没注意。改过后仍然WA。。。

最后还是用数学方法解方程通过的。赛后题解提供了五六种思路，我尝试了两种二分都失败了，改日再研究计算几何。。。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef double db;

const db pi = acos(-1);
struct Point{
    db x, y, z;
    Point(db xx=0, db yy=0, db zz=0):x(xx), y(yy), z(zz) {}
};

db r1, r2;
Point p1, p2;
Point tran(db lon, db lat)
{
    lon = lon/180*pi;
    lat = lat/180*pi;
    return Point(cos(lat)*cos(lon), cos(lat)*sin(lon), sin(lat));
}

int main()
{
    db lon1, lon2, lat1, lat2;
    while(scanf("%lf %lf %lf", &lon1, &lat1, &r1)!=EOF) {
        scanf("%lf %lf %lf", &lon2, &lat2, &r2);


        p1 = tran(lon1, lat1);
        p2 = tran(lon2, lat2);
/*
        r1 = 2*sin(r1/2);
        r2 = 2*sin(r2/2);
          db k1 = 2-r1*r1;  k1 = k1/2;
        db k2 = 2-r2*r2;  k2 = k2/2;
*/
          db k1 = cos(r1);
        db k2 = cos(r2);

        db c1 = (k1*p2.z-k2*p1.z)/(p1.y*p2.z-p2.y*p1.z);
        db c2 = (k2*p1.y-k1*p2.y)/(p1.y*p2.z-p2.y*p1.z);
        db d1 = (p2.x*p1.z-p1.x*p2.z)/(p1.y*p2.z-p2.y*p1.z);
        db d2 = (p1.x*p2.y-p2.x*p1.y)/(p1.y*p2.z-p2.y*p1.z);

        db a = 1+d1*d1+d2*d2, b = c1*d1+c2*d2, c = c1*c1+c2*c2-1;
        db delta = b*b-a*c;
        db x1 = (-b+sqrt(delta))/a;
        db x2 = (-b-sqrt(delta))/a;

        db y1 = c1+d1*x1, y2 = c1+d1*x2, z1 = c2+d2*x1, z2 = c2+d2*x2;
        if(z1<z2) {
            printf("%.7lf %.7lf %.7lf\n", x1, y1, z1);
            printf("%.7lf %.7lf %.7lf\n", x2, y2, z2);
        } else {
            printf("%.7lf %.7lf %.7lf\n", x2, y2, z2);
            printf("%.7lf %.7lf %.7lf\n", x1, y1, z1);
        }
    }
    return 0;
}