xzm2019

北京理工大学第八届程序设计新生赛(热身赛) 题解
Problem A. A+B Problem (I)I don't know I need to say what...
扫描右侧二维码阅读全文
21
2019/12

北京理工大学第八届程序设计新生赛(热身赛) 题解

Problem A. A+B Problem (I)

I don't know I need to say what. But I know there are many teams using BigInteger. They get Time Limit Exceeded and some people get Wrong Answer or Runtime Error because they didn't deal negative numbers well.

However, $-10^{18} \leq a,b \leq 10^{18}$, which means $-2 \times 10^{18} \leq a + b \leq 2 * 10^{18}$. That's ok for long long.

#include <bits/stdc++.h>

using namespace std;

int main() {
    long long a, b;
    scanf("%lld%lld", &a, &b);
    printf("%lld\n", a + b);
    return 0;
}

Problem B. A+B Problem (II)

题目里已经写的很清楚了,在每次输出以后你需要使用fflush(stdout);System.out.flush();让系统收到你的输出,否则会导致TIME LIMIT

#include <bits/stdc++.h>

using namespace std;

int main() {
    long long a, b;
    while (scanf("%lld%lld", &a, &b)==2){
        if (a == -1 && b == -1) return 0;
        printf("%lld\n", a + b);
        fflush(stdout);
    }
}

Problem C. 又到了白色相簿的季节

答案:251463

就是测测评测机压力嘛~大家暴力枚举下嘛~

Problem D. 31点

方法1:

(这是出题人想要的方案)考虑这个游戏的实质就是1-6的选数博弈问题,但是由于每个数字有限,所以会存在一些特殊情况,如$(n,m)=(5,5),(1,1),(1,2)$,只要把这些情况考虑清楚即可,其他时候无脑拼7。完整的情况如下图所示(包括$n=2$的):

  • 先手拿 5

    • 假如后手拿 5,先手接着拿 2,后手再拿 5 先手继续 2……
    • 假如后手拿非 5 的,先手就在下一次拿取中抢占关键点 3、10、17、24、31,抢到之后后手拿 X 先手就拿 7-X
  • 先手拿1:

e61190ef76c6a7eff48bd97bf3faaf51f3de6639.jpg

  • 先手拿2:

b21c8701a18b87d6e36bdd42090828381f30fd46.jpg

对应的程序实现如下:

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

int num[7]={0,4,4,4,4,4,4};
int sum=0;
void play()
{
    while (sum!=31)
    {
        int x=31-sum;
        x%=7;
        assert(num[x]);
        printf("%d\n",x);
        num[x]--; sum+=x;
        fflush(stdout);
        scanf("%d",&x);
        if (x<=0) return;
        num[x]--; sum+=x;
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    num[n]--; num[m]--;
    sum=n+m;
    if ((n==5&&m!=5)||(n==1&&m>=3))
    {
        play();
        return 0;
    }
    if (n==5&&m==5)
    {
        while (1)
        {
            printf("2\n");
            fflush(stdout);
            num[2]--; sum+=2;
            int x;
            scanf("%d",&x);
            if (x<=0) return 0;
            num[x]--; sum+=x;
            if (x!=5)
            {
                play();
                break;
            }
        }
    }
    if (n==1)
    {
        bool flag=(m==2);
        while (1)
        {
            printf("6\n");
            fflush(stdout);
            num[6]--; sum+=6;
            int x;
            scanf("%d",&x);
            if (x<=0) return 0;
            num[x]--; sum+=x;
            if (x>=3)
            {
                play(); break;
            }
            if (x==2)
            {
                if (flag)
                {
                    play(); break;
                }
                flag=true;
                continue;
            }
        }
    }
    return 0;
}

方法2:

不过验题人发现,这题步数很少,直接暴力搜索,把所有情况搜到,找到所有的必胜情况即可,为了代码的美观,可以使用状压等技巧

#include<stdio.h>
#include<string.h>
int state[5*5*5*5*5*5];
int nextplay[5*5*5*5*5*5];
int go(int nowstate){
    if(state[nowstate])return state[nowstate];
    int a[7],sum=0;
    for(int i=1,temp=nowstate;i<=6;i++){
        a[i]=temp%5;
        sum+=a[i]*i;
        temp/=5;
    }
    if(sum==31)return state[nowstate]=-1;
    if(sum>31)return state[nowstate]=1;
    for(int i=1,temp=1;i<=6;i++){
        if(a[i]<4&&go(nowstate+temp)==-1){
            nextplay[nowstate]=i;
            return state[nowstate]=1;
        }
        temp*=5;
    }
    return state[nowstate]=-1;
}
int w[7];
int main() {
    w[1]=1;
    for(int i=2;i<=6;i++)
        w[i]=w[i-1]*5;
    int nowstate=0;
    int n,m;
    scanf("%d",&n);
    nowstate+=w[n];
    int x;
    while(~scanf("%d",&x)){
        nowstate+=w[x];
        go(nowstate);
        printf("%d\n",nextplay[nowstate]);
        fflush(stdout);
        nowstate+=w[nextplay[nowstate]];
    }
    return 0;
}

Problem E. 管道设计

很显然,你可以用三个水龙头将其设计为$1:1$的输出,如下图所示

找到$c+d \leq 2^n$的最小的$n$,使用$1:1$的输出分配建立一颗深度为$n$的二叉树,其最底层有$2^n$个叶子节点,我们将其中$c$个叶子节点连向$-1$,$d$个连向$-2$,剩余的回流,最后形成的就是$c:d$的了。

为了减少输出,我们需要把相同输出的$1:1$输出进行合并或简化。

#include <bits/stdc++.h>

using namespace std;

// The main idea for the solution works in two stages:
//  - first: we construct a 1:1 splitter from the c:d splitter as follows
//
//        |
//   /----|----\
//  /    / \    \
//  c   c   d   d
//  |  /     \  |
//  \-/|     |\-/
//     d     c
//     |     |
//
//           To see that this acts as a 1:1 splitter, consider just the
//           output of the second layer. It produces for outputs with ratios
//           c^2:c*d:d*c:d^2. The middle two are equal, and if we lead the
//           the outer two back to the root, effectively all input is thus split
//           in half.
//
//  - next: We construct the desired ratio by building a binary tree (using
//          the above 1:1 splitter) that sends:
//            a/2^n to output A
//            b/2^n to output B
//            (2^n-a-b)/2^n back to the root.
//          this is done by repeatedly splitting the unused leaves in half,
//          sending output to A, B or the root in each layer to the maximum
//          extent possible. Again, this works because the output is forced to
//          have the right ratio, and anything that doesn't is simply
//          reprocessed.
int main() {
    long long a, b, c, d;
    
    cin >> c >> d >> a >> b;
    
    long long denom = a+b;
    
    long long pow2 = 1;
    while (pow2 < denom) pow2 *= 2;
    
    long long feedback = pow2-denom;
    
    vector<pair<int, int>> splitters;
    
    queue<int> endpoints;
    
    // Setup initial 50-50 split
    splitters.push_back({1,2});
    splitters.push_back({0,-5});
    splitters.push_back({-5,0});
    endpoints.push(2*1+1);
    endpoints.push(2*2);
    
    long long cur = pow2/2;
    
    while (a != 0 || b != 0 || feedback != 0) {
        queue<int> nextendpoints;
        
        while (a >= cur) {
            a -= cur;
            int ep = endpoints.front();
            endpoints.pop();
            
            // Patch output of selected endpoint to -1
            int idx = ep/2;
            if (ep % 2 == 1)
                splitters[idx].second = -1;
            else
                splitters[idx].first = -1;
        }
        
        while (b >= cur) {
            b -= cur;
            int ep = endpoints.front();
            endpoints.pop();
            
            // Patch output of selected endpoint to -2
            int idx = ep/2;
            if (ep % 2 == 1)
                splitters[idx].second = -2;
            else
                splitters[idx].first = -2;
        }
        
        while (feedback >= cur) {
            feedback -= cur;
            int ep = endpoints.front();
            endpoints.pop();
            
            // Patch output of selected endpoint to 0
            int idx = ep/2;
            if (ep % 2 == 1)
                splitters[idx].second = 0;
            else
                splitters[idx].first = 0;
        }
        
        // Further split remaining endpoints (there will be at most 2!)
        while (!endpoints.empty()) {
            int ep = endpoints.front();
            endpoints.pop();
            
            int nidx = splitters.size();
            
            // Patch output of selected endpoint to nidx
            int idx = ep/2;
            if (ep % 2 == 1)
                splitters[idx].second = nidx;
            else
                splitters[idx].first = nidx;
            
            // Create new 50-50 splitter
            splitters.push_back({nidx+1,nidx+2});
            splitters.push_back({nidx, -5});
            splitters.push_back({-5, nidx});
            nextendpoints.push(2*(nidx+1)+1);
            nextendpoints.push(2*(nidx+2));
        }
        
        // Do bookkeeping
        endpoints.swap(nextendpoints);
        cur /= 2;
    }
    
    // Output all splitters
    cout << splitters.size() << endl;
    for (auto s : splitters) {
        cout << s.first << " " << s.second << endl;
    }
}

我觉得上面那个写的有点长,我们还是看下一个吧

#include <stdio.h>

typedef long long ll;
#define prt( x, y )    printf("%lld %lld\n",(x),(y))
void connect( ll a, ll x, ll y ) {
    prt( 3*a+1, 3*a+2 );
    prt( 3*a, x < 0 ? x : 3*x );
    prt( y < 0 ? y : 3*y, 3*a );
}

int main() {
    ll x[3], s, N = 2, B[3] = {0,0,1}, C[6], D;
    scanf( "%lld %lld", x+1, x );
    scanf( "%lld %lld", x+1, x );
    s = x[0]+x[1]-1;
    while( s >>= 1 ) N <<= 1; 
    x[2] = N-x[0]-x[1]; 
    printf( "%d\n", 3*(__builtin_popcountll(x[0])+__builtin_popcountll(x[1])+__builtin_popcountll(x[2])-1) );
    for( ll k = N>>1; B[1] < B[2]; k >>= 1 ) {
        B[0] = B[1];
        B[1] = B[2];
        D = 0;
        for( ll i = 0; i < 3; ++i ) {
            if( x[i] >= k ) {
                x[i] -= k;
                C[D++] = i-2;
            }
        }
        while( D < 2*(B[1]-B[0]) ) C[D++] = B[2]++;
        for( ll i = 0; i < B[1]-B[0]; ++i )
            connect( B[0]+i, C[2*i], C[2*i+1] );
    }
}
Last modification:December 21st, 2019 at 09:53 pm
If you think my article is useful to you, please feel free to appreciate

Comment here is closed