• 周五. 12月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

7.22 考试

admin

11月 28, 2021

期望得分:(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,然后模拟完事。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注