NOIp2018集训test-9-5(pm)

老张说：这套题太简单啦，你们最多两个小时就可以AK啦！

题 1 数数

我看到T1就懵了，这就是老张两个小时可以AK的题的T1？？

然后我成功地T1写了1h+，后面1h打了t2.t3暴力，就很开心。

等差数列中的一个数B+A*N，发现A非常小，让人浮想联翩，把这个等差数列中每个数模A，得到的结果就是B%A而且很小，就可以数位dp。f[i][j][0/1]表示长度为i的二进制数，模A等于j，前i位有没有达到上界的方案数，g[i][j][0/1]表示这种情况下的答案。转移什么的看代码吧，就是基础的数位dp。

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 typedef long long LL;

 typedef double db;

 using namespace std;

 int T,A,lim[],n;

 LL B,N,f[][][],g[][][],pr[],ans; 

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 LL find(LL up) {

     if(!up) return ;

     memset(f,,sizeof(f));

     memset(g,,sizeof(g));

     Rep(i,,) if(up&(1LL<<i)) { n=i; break; }

     For(i,,n) lim[n-i]=(up&pr[i])?:;

     f[][][]=;

     For(i,,n) {

         For(j,,A-) if(f[i][j][]||f[i][j][]) {

             f[i+][(j*+)%A][]+=f[i][j][];

             g[i+][(j*+)%A][]+=g[i][j][]+f[i][j][];

             f[i+][j*%A][]+=f[i][j][];

             g[i+][j*%A][]+=g[i][j][];

             if(lim[i]==) {

                 f[i+][j*%A][]+=f[i][j][];

                 g[i+][j*%A][]+=g[i][j][];

             }

             else {

                 f[i+][j*%A][]+=f[i][j][];

                 g[i+][j*%A][]+=g[i][j][];

                 f[i+][(j*+)%A][]+=f[i][j][];

                 g[i+][(j*+)%A][]+=g[i][j][]+f[i][j][];

             }

         }

     }

     return g[n+][B%A][]+g[n+][B%A][];

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("count.in","r",stdin);

     freopen("count.out","w",stdout);

 #endif

     read(T);

     pr[]=;

     For(i,,) pr[i]=(pr[i-]<<);

     while(T--) {

         read(A); read(B); read(N);

         LL ans=find(B+A*N)-find(max(0LL,B+A-));

         printf("%lld\n",ans);

     }

     Formylove;

 }

 /*

 2

 10000 5641654165416 100077775545

 9980 14244264416 10420477545

 */

题 2 旅游

考试的时候写了个暴力，只有20分，结果发现把题读错了，a,b都为0的点才不能经过，改过后就直接A了？？数据大概是用脚造的

暴力就是把a离散，显然答案就是每种a中选一个点的序列。暴力枚举每种a的每一个点和它的前一种a中的每一个点转移。

正解我还没看懂，但是二维树状数组那个大概明白了，就是把绝对值拆开，按几种正负分别建树状数组，按a排序后，把a小的一部分加入树状数组，转移都会是一段区间，可以直接查询。

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,m,a[N][N],b[N][N],ls[N*N],sz;

 LL f[N][N],ans; 

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 struct node {

     int x,y;

     node(){}

     node(int x,int y):x(x),y(y){}

 }p[N*N];

 vector<node>vc[N*N];

 LL dis(node A,node B) { return abs(A.x-B.x)+abs(A.y-B.y);}

 #define ANS

 int main() {

 #ifdef ANS

     freopen("tour.in","r",stdin);

     freopen("tour.out","w",stdout);

 #endif

     read(n); read(m);

     For(i,,n) For(j,,m) read(a[i][j]),ls[++ls[]]=a[i][j];

     For(i,,n) For(j,,m) read(b[i][j]);

     sort(ls+,ls+ls[]+);

     sz=unique(ls+,ls+ls[]+)-(ls+);

     For(i,,n) For(j,,m) {

         if(b[i][j]==&&a[i][j]==) continue;

         a[i][j]=lower_bound(ls+,ls+sz+,a[i][j])-ls;

         vc[a[i][j]].push_back(node(i,j));

         f[i][j]=b[i][j];

         vc[a[i][j]].push_back(node(i,j));

     }

     For(i,,sz) {

         int up1=vc[i].size(),up2=vc[i-].size();

         For(j,,up1-) For(k,,up2-) {

             node t1=vc[i][j],t2=vc[i-][k];

             f[t1.x][t1.y]=max(f[t1.x][t1.y],f[t2.x][t2.y]+dis(t1,t2)+b[t1.x][t1.y]);

             ans=max(ans,f[t1.x][t1.y]);

         }

     }

     printf("%lld\n",ans);

     Formylove;

 }

题 3 做梦

注意读题，每次散步总时间不能超过m，就是每次离开起点到回到起点的时间间隔不超过m。

最后只有半个小时有点方，然后脑子就很乱，都知道是dp然后矩阵优化就是没搞对，dp还瞎弄了个两维的，只得了暴力分。

预处理每一次散步的方案，定义f[i][j][k]表示从i点走k步走到j点的方案数（点从1到m），可以用floyd求出。

然后每次散步走了x步，方案数就是f[1][1][x-2]*2（第一步从0走到1或-1，再不经过0地走x-2步走回1或-1，最后一步走回0）

g[i]表示散步总步数为i的方案数，也就是n==i的答案。

$g[n]=\sum_{i=2}^{m} g[n-i]*2*f[1][1][i-2]$

这是个线性递推，矩阵加速即可。

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=,p=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,m;

 LL f[N][N][N],g[N],ans;

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 struct jz {

     LL a[N][N];

     friend jz operator *(const jz&A,const jz&B) {

         jz rs;

         For(i,,m) For(j,,m) {

             rs.a[i][j]=;

             For(k,,m)

                 (rs.a[i][j]+=A.a[i][k]*B.a[k][j]%p)%=p;

         }

         return rs;

     }

 }bs,rs;

 void ksm(int b) {

     while(b) {

         if(b&) rs=rs*bs;

         bs=bs*bs;

         b>>=;

     }

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("dream.in","r",stdin);

     freopen("dream.out","w",stdout);

 #endif

     read(n); read(m);

     For(i,,m) f[i][i-][]=,f[i][i+][]=,f[i][i][]=;

     For(k,,m) For(i,,m) For(j,,m) {

         if(j->=) f[i][j][k]=f[i][j-][k-];

         if(j+<=*m+) (f[i][j][k]+=f[i][j+][k-])%=p;

     }

     g[]=;

     For(s,,m) For(j,,m) if(s>=j)

         g[s]=(g[s]+g[s-j]*2LL*f[][][j-]%p)%p;

     For(i,,m) For(j,,m) {

         if(i==j) rs.a[i][j]=;

         else rs.a[i][j]=;

         bs.a[i][j]=;

     }

     For(i,,m) bs.a[m-i+][m]=*f[][][i-];

     For(i,,m-) bs.a[i+][i]=;

     ksm(n-);

     For(i,,m)

         ans=(ans+rs.a[i][]*g[i]%p)%p;

     printf("%lld\n",ans);

     Formylove;

 }

巴特西

NOIp2018集训test-9-5(pm)

最新文章

热门文章