考虑到这个东西本地就能测正确性所以在哪里交都一样..

$A + 1$ problem

第一个点:

我觉得看懂题了的都能过..? http://uoj.ac/submission/74677

第2/3个点:

其实我果然题意读错了..不然一定是$8$分T_T

模拟高精度加法即可得 http://uoj.ac/submission/74678

第5个点:

我们可以把整个东西像线段树一样建出来..~~似乎我写的是树状数组~~

然后暴力像树状数组一样的查询...查询的复杂度为$O(\log n)$

这样的话..用的跳蚤的复杂度是$O(n \log n)$的,这样能过掉第5个点而不能过掉第4个点

PS:似乎常数大概是1/2,不然的话$17 * 100000 > 1.5*10^6 $而爆炸...

仔细算了下,大概复杂度是$O(2n + 1/2 n \log n)$的?

http://uoj.ac/submission/74739

第4个点:

当然我觉得,也可以再一遍处理把它处理出来,这样能过第4个点而不能过第五个点

要开始写分支了...

还是不算很难写的...

复杂度O(3n),t的复杂度是$O(2\log n)$

http://uoj.ac/submission/74740

所以

那下面就是A+B了

$A + B$ problem

显然暴力还能再过点分..然而不是很想写...毕竟写了也没意义...

感觉之前A+1 problem的办法直接搬过来的话,复杂度瞬间就成了$O(n^2)$的,这并不是我们想要的结果

而且之前枚举进位到的位置也是不可取的,因为..你每一位并不知道它要+1还是+2

而且每一位都算个进位复杂度也爆炸了吧..

思考一发,感觉可以分治

对于A和B,我们分前一半和后一半

我们假设前一半和后一半加好了,然后后一半是否有进位我们也知道了

如果有进位,不就是个A+1 problem了么..

然而这样有几个问题

1,一共有进行$\log n$次分治..每次的复杂度又是$\log n$似乎过不了什么点

2,我们不好判断那个进位的问题,就是如果进位是0我们按A+1 problem一算肯定要炸

我们来思考下怎么优化吧

感觉好无聊把小数据给过掉了..

    if (task_id==1) {
        C[0]=A[0]^1;
        bool c=A[0];
        int i;
        for (i=1;i<n;i++) {
            C[i]=A[i]^c;
            c=C[i]<A[i];
        }
    } else if (task_id==2) {
        C[0]=A[0]^B[0];
        bool c=A[0]&B[0];
        int i;
        for (i=1;i<n;i++) {
            C[i]=A[i]^B[i]^c;
            c=(A[i]&B[i])|((A[i]|B[i])&c);
        }
    } else if (task_id==3) {
        int c=0;
        int i,j;
        for (i=0;i<n;i++) {
            for (j=0;j<=i;j++) {
                c+=A[j]&B[i-j];
            }
            C[i]=c&1;
            c>>=1;
        }

刚才这一大段代码是grader里面的..感觉task_id==3就可以解了?

我发现我自己不会..感觉弃疗了如果哪次把这题过了后面的部分再接着更吧

absi2011的博客

博客

直播玩交互题