• 7.22 考试


    期望得分:(60+?)+10+60

    实际得分:60+0+50

    A. 方程的解

    这是一道特判题。

    很容易想到60分的解法(其实就是qj)。

    不考虑ZenMeZheMeDuo

    测试点分治:

    对于a==b==1  c-1

    对于a+b==c  1

    对于a b c<=1000  直接暴枚x,然后代入求y验证

    对于接下来的分,就要用到只有一堆特判和exgcd了。

    其实我打了exgcd,说下错因: 我没弄清exgcd求得是怎样一组特解,于是我当时手模了几个点,发现当a>b时可以求出y的最大值(然而只是巧合),然后就没了。

    exgcd求得是一组解,但不‘特’,所以要求出最小非负整数解的话,假设d是gcd(a,b),x是求出的解,x0是所求最小非负整数解,则x0=(x%(b/d)+(b/d))%(b/d);

    然后x0不一定是解题中需要的最小正整数解x1,判下若x0==0 则x1+=(b/d);

    代入x1可以算出y1(y最大值)

    同理(解的间隔为a/d)我们可以算出y2(y最小值)。然后用pa大神的方法,判下y1<y2无解。若有解可知$ans= lfloor (y1-y2)/(a/d) floor $

    之后是极其恶心的特判,详细的还是看代码吧(没人看的别做梦了,只有你自己!),懒得写了额。

      1 #include<cstdio>
      2 #include<cmath>
      3 #include<algorithm>
      4 #define ll long long
      5 #define reg register
      6 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
      7 using namespace std;
      8 inline ll read();
      9 const ll ma=65535;
     10 ll a,b,c;
     11 void sol_1()        //a==b==1
     12 {
     13     if(c<=1) puts("0");
     14     else if(c-1<=ma) printf("%lld
    ",c-1);
     15     else puts("ZenMeZheMeDuo");
     16 }
     17 void sol_2()        //<=10^3
     18 {
     19     ll ans=0;
     20     F(x,1,1000)
     21     {
     22         if(a*x>=c) break;
     23         ll t=c-a*x;
     24         if(t%b) continue;
     25         ++ans;
     26     }
     27     if(ans<=ma) printf("%lld
    ",ans);
     28     else puts("ZenMeZheMeDuo");
     29 }
     30 void sol_3()        //a+b==c
     31 {
     32     puts("1");
     33 }
     34 ll x,y;
     35 ll exgcd(ll a,ll b)
     36 {
     37     if(!b)
     38     {
     39         x=1;
     40         y=0;
     41         return a;
     42     }
     43     ll g=exgcd(b,a%b);
     44     ll tx=x;
     45     x=y;
     46     y=tx-a/b*y;
     47     return g;
     48 }
     49 void sol_4()
     50 {
     51     ll d=exgcd(a,b);
     52     if(c%d)
     53     {
     54         puts("0");
     55         return;
     56     }
     57     x*=(c/d);
     58     y*=(c/d);
     59     if((a>0&&b<0)||(a<0&&b>0))
     60     {
     61         puts("ZenMeZheMeDuo");
     62         return;
     63     }
     64     ll x1=(x%(b/d)+(b/d))%(b/d);
     65     ll y1=(c-a*x1)/b;
     66     if(x1==0)
     67     {
     68         x1+=(b/d); y1-=(a/d);
     69     }
     70     /*if(y1<=0)
     71     {
     72         puts("0");
     73         return;
     74     }*/
     75     ll y2=(y%(a/d)+(a/d))%(a/d);
     76     ll x2=(c-b*y2)/a;
     77     if(y2==0)
     78     {
     79         x2-=(b/d); y2+=(a/d);
     80     }
     81     /*if(x2<=0)
     82     {
     83         puts("0");
     84         return;
     85     }*/
     86     if(y1-y2<0)
     87     {
     88         puts("0");
     89         return;
     90     }
     91     ll ans=(y1-y2)/(a/d)+1;
     92     if(ans<=ma) printf("%lld
    ",ans);
     93     else puts("ZenMeZheMeDuo");
     94 }
     95 int main()
     96 {
     97 //    freopen("data.in","r",stdin);
     98 //    freopen("data.out","w",stdout);
     99     int T=read();
    100     while(T--)
    101     {
    102         a=read(); b=read(); c=read();
    103         if(c<0) a=-a,b=-b,c=-c;
    104         if(a<b) a^=b^=a^=b;
    105         if(a==1&&b==1)
    106         {
    107             sol_1();
    108             continue;
    109         }
    110         if(a+b==c)
    111         {
    112             sol_3();
    113             continue;
    114         }
    115         if(a>0&&b>0&&c>0&&a<=1000&&b<=1000&&c<=1000)
    116         {
    117             sol_2();
    118             continue;
    119         }
    120         if(c==0)
    121         {
    122             if((a>0&&b<0)||(a<0&&b>0))
    123             {
    124                 puts("ZenMeZheMeDuo");
    125                 continue;
    126             }
    127             if((a>0&&b>0)||(a<0&&b<0))
    128             {
    129                 puts("0");
    130                 continue;
    131             }
    132             if(a==0&&b==0)
    133             {
    134                 puts("ZenMeZheMeDuo");
    135                 continue;
    136             }
    137         }
    138         if(a==0&&b==0&&c)
    139         {
    140             puts("0");
    141             continue;
    142         }
    143         if(a&&b==0)
    144         {
    145             if(c%a||c/a<=0)
    146             {
    147                 puts("0");
    148                 continue;
    149             }
    150             else
    151             {
    152                 puts("ZenMeZheMeDuo");
    153                 continue;
    154             }
    155         }
    156         if(a==0&&b)
    157         {
    158             if(c%b||c/b<=0)
    159             {
    160                 puts("0");
    161                 continue;
    162             }
    163             else
    164             {
    165                 puts("ZenMeZheMeDuo");
    166                 continue;
    167             }
    168         }
    169         sol_4();
    170     }
    171 }
    172 inline ll read()
    173 {
    174     ll x=0,f=1;
    175     char tc=getchar();
    176     while(tc<'0'||tc>'9')
    177     {
    178         if(tc=='-') f=-1;
    179         tc=getchar();
    180     }
    181     while(tc>='0'&&tc<='9')
    182     {
    183         x=x*10+tc-48;
    184         tc=getchar();
    185     }
    186     return f*x;
    187 }
    View Code

    B. visit

    这是一道孤儿题(以至于放错题)

    换了题后去码了T1,然后来看T2

    说实话首先想到了矩阵快速幂,后来刚想码一想不对啊,这是二维模型,所以矩阵的大小是$(100 imes 100)^2$然后就弃了。

    又想到了dp,但是我当时nc了,看着列出的dp[t][i][j]=dp[t-1][i][j-1]+dp[t-1][i][j+1]+dp[t-1][i-1][j]+dp[t-1][i+1][j] 居然认为有后效性?因为我忘了t这一维。。。然后就想起学长曾经讲过的一道类似的但是可以原地不动的题,做法是系数递推,然而我除了知道这个学术名词外没别的了。。。

    后来就只能打了个nc bfs 0分。。。

    正解:组合数学

    用skyh的思路。我们只要枚举其中一个方向上的移动,就可以推知其他方向,然后我们就有了$O(n)$枚举+组合数学的方法。

    i是上下方向走的步数

    $ans= sumlimits_{i=n}^{T-m} C_T^i imes C_i^{ frac {i-n} {2}} imes C_{T-i}^{frac {T-i-m} {2}}$   2|i-n  &&  2|T-i-m

    对于$frac {i-n} {2}$可以这样理解:

    i-n是向上多走的步数,由对称性可知再向下回来需要$frac {i-n} {2}$  那么柿子就没问题了

    接下来是如何计算。

    因为mod不全是质数,那么费马小定理,逆元递推统统失效,组合数不可直接求不来。

    我们观察到对于全部数据mod为若干不同质数的乘积,我们可以把mod分解质因数然后分别用质因子 lucas算上面的柿子,最后会得到类似于

    $x equiv a_1(mod m_1) \ x equiv a_i (mod m_i) \ .\.\.$

    的方程组,其中m互质。这不就是crt嘛!然后合并一波得解。

    细节:

    质因数分解用试除法

    可知质因数上限远不到有$log(sqrt{mod})$ ,这样就确保了复杂度

    所以lucas需要的阶乘直接打表到min(T,p[i])即可$C_{n \% p[i]}^{m \% p[i]}$上下一定<p[i]

    C. 光

    这是一道STL综合模拟题。

    暴力可得60pts,当时考试暴力dfs怕爆栈设了29000层上限,然后就50了。。。

    听XR说题面给了自开栈,然后就试了一波20w层,也没问题。。。

    正解:

    首先要知道以下几个性质:

    • x+y+dir(两个方向)的奇偶性不变,我们只要知道了坐标,就能推之两个方向
    • 光线一定能回到起点,这个去看wd大神的证明
    • 如果出现了2 4情况,则光路走了两遍

    暴力有很多块是空心的,从而局限了复杂度,那么我们是否能直接找到下一个障碍呢?

    可知在同一条直线上x+y 或 x-y 为定值,例如x-y=z的情况,那么z就可以代表这条直线。

    所以我们可以建两个桶set,用于存储/ 两个方向的所有直线上的障碍物x坐标,对于x-y会有负值加上FIX=10w即可

    接下来是模拟: 假设我们在(x,y)方向为dir

    那么根据dir分类讨论

    由当前x可以在桶里$O(logk)$二分出前趋或后继nx,即下一个障碍物,然后算出ny,然后模拟完事。

  • 相关阅读:
    倒排索引压缩
    记一次java内存溢出的解决过程
    [译]ES读写文档时shard-replication模型
    [转载]抓包工具Charles乱码解决办法
    Mac 快捷键整理(不定期更新)
    高效能人士执行的四原则(2017-12-15)
    scala sbt 添加国内镜像
    maven工程小红叉处理方法
    系统管理中 bash shell 脚本常用方法总结
    scala 2.11报错error: not found: type Application
  • 原文地址:https://www.cnblogs.com/hzoi-yzh/p/11234529.html
一二三 - 开发者的网上家园