[CTS2024] 多方计算

C1942huangjiaxu · 2024-03-19 19:27:55 · 题解

题目中要求不能使用全局变量，但因为 CTS 是 IOI 赛制，这里认为在调用 transmit 函数时可以知道 n,m 的值。

先考虑逐位确定答案，具体如下 :

• 第一轮，0 号将 a_0 的第 0 位信息传给 1 号。
• 第二轮，1 号将 0 号的信息加上，可以确定 a_0+a_1 的第 0 位信息，1 号将这个信息传给 2 号，同时这一轮 0 号将第 1 位信息传给 1 号。
• 第 j 轮，i 号将 j-i-1 位的信息传给第 i+1 号。

最后答案的位数是 O(m+\log n) 的，从 0 将信息传到 n 需要 n 秒，所以总共秒数是 m+n+\log n，可以得到 49 分。

参考代码

#include "mpc.h"
int precalc(int n,int m){
    int t=0;
    while((1<<t)<n)++t;
    return n+m+t;
}
bool transmit(player &player, int round,int position){
    int np=round-position-1;
    if(np<0)return 0;
    int o=player.last_message;
    if(o){
        int l=np;
        while(player.memory[l])player.memory[l]=0,++l;
        player.memory[l]=1;
    }
    return player.memory[np];
}

考虑到上述做法中，在第 j+1 轮前，j 号都没有信息可以传给 j+1 号，浪费了很多的时间。

考虑我们同步进行两轮加法，后面一轮不必要从第 0 位开始，但要在第 m+\log n 位结束，相当于是我们从 \log n 的位置砍掉了一个三角形，这样前一轮的答案就变为 O(m+\log\log n) 位了，总共秒数是 n+m+\log\log n ，可以获得 80 分。

参考代码

#include "mpc.h"
int N,M;
int precalc(int n,int m){
    N=n,M=m;
    return n+m+4;
}
bool transmit(player &player, int round,int position){
    int np=round-position-1,o=player.last_message,lp;
    if(np<0)np=np+M+11;
    if(np<0)return 0;
    if(o){
        lp=np;
        while(player.memory[lp])player.memory[lp]=0,++lp;
        player.memory[lp]=1;
    }
    bool u=player.memory[np];
    if(position!=N)player.memory[np]=0;
    return u;
}

既然两次不够，考虑同时进行三轮加法，把最后面的三角形往后移，中间再从 O(\log\log n) 的位置砍一刀，这样就可以通过了，对参数的限制不是特别严格。

参考代码

#include "mpc.h"
const int B=8,C=4;
int N,M;
int precalc(int n,int m){
    N=n,M=m;
    return n+m+3;
}
bool transmit(player &player, int round,int position){
    int np=round-position-1,o=player.last_message,lp;
    if(np<0){
        if(np>=-B)np=np+M+C;
        else np=np+M+B+11;
    }
    if(np<0)return 0;
    if(o){
        lp=np;
        while(player.memory[lp])player.memory[lp]=0,++lp;
        player.memory[lp]=1;
    }
    bool u=player.memory[np];
    if(position!=N)player.memory[np]=0;
    return u;
}