首页 > 代码库 > Fixed Point 解题报告

Fixed Point 解题报告

2024-07-17 10:46:35   224人阅读

题目总结：

这种数论动规的关键点是在“与上届相等的数的处理”上，只要这个弄懂了，这种题应该就都会做了。

因为和上届相等的数最多只有一个，所以我用一个equal来记录是否有满足条件的上届。而其他小于上届的数用f数组储存。

策略只有取1和取0。

小于上届的数可以随便取。

equal的状态转移要好好想想：

当前位为1：取1则equal保留，取0则equal可以转移到f数组。

当前位为0：取0则equal保留。取1就比上届大了，舍去。

 

一般性总结：

1.打草稿分析样例很有效果。

2.直接用不加证明的结论这种习惯不好。这道题中以及Coprime Sequence中已经深有体会。

 1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 #include <cstring> 5 #define FOR(i,l,r) for(int i=(l);i<=(r);i++) 6 #define FORD(i,r,l) for(int i=(r);i>=(l);i--) 7 #define rep(i,n) for(int i=0;i<(n);i++) 8 using namespace std; 9 typedef long long LL;10 typedef unsigned int ui;11 ui get2[33];12 13 LL f[33][33];14 LL gao(ui R, ui c, int k, int flag)15 {16     memset(f,0,sizeof(f));17     LL equal=1; int gs0=0;18     FORD (z,31,0)19     {20         //021         if (flag>=0 || !(c&get2[z]))22         {23             FOR (i,1,32-z) f[z][i]=f[z+1][i-1];24             if (R&get2[z]) f[z][gs0+1]+=equal;25         }26         //127         if (flag<=0 || (c&get2[z]))28         {29             FOR (i,0,31-z) f[z][i]+=f[z+1][i];30         }31         if ((R&get2[z]) && !(flag<=0 || (c&get2[z]))) equal=0;32         if (!(R&get2[z]) && !(flag>=0 || !(c&get2[z]))) equal=0;33         gs0+=!(R&get2[z]);34     }35     LL ret=0;36     FOR (i,0,32) if (abs(32-i-i)<=k) ret+=f[0][i];37     if (abs(32-gs0*2)<=k) ret+=equal;//~~38     return ret;39 }40 41 ui L,R,c; int k;42 LL gao0(int flag)43 {44     LL ret=gao(R,c,k,flag);45     if (L) ret-=gao(L-1u,c,k,flag);46     return ret;47 }48 49 int main()50 {51     get2[0]=1; for (int i=1;i<=32;i++) get2[i]=get2[i-1]<<1;52 53     int T; scanf("%d",&T);54     LL ans1,ans2,ans3;55     FOR (z,1,T)56     {57         scanf("%u%u%u%d",&L,&R,&c,&k);58         ans1=gao0(1);59         if (c!=0) ans2=0; else ans2=gao0(0);60         ans3=gao0(-1);61         printf("Case %d: %lld %lld %lld\n",z,ans1,ans2,ans3);62     }63     return 0;64 }
Fixed Point 代码

 


联系
我们