[ 每 日 一 题]AcWing 3800. 奇数还是偶数

前言

基础优化— 反向思维 (太久没做了 都忘了 阿巴阿巴)

思路

对于一个数的奇偶性 我们只需要看个位数即可

因为k比较大 所以我们只能考虑个位数

然后就普通的走一遍模拟

但是仔细思考会发现 我们这个复杂度是 O(k* k *t) 1e11的级别去了 （但是写的时候一直没发现 脑中给自己下了一个 O(t * k) 的 想法 ）

那么怎么样才能少一层k呢 ?

按照dp的思想 把之前的 用来推现在的

也就是我们可以 通过 k(1) -> k(2) 所以我们就没必要每次都 求 b(k-1)…

总结

好久没写代码了 (虽然多校有再写 但是没补) 都忘记要先确定时间复杂度再做题了 QAQ 下次记得看准时间复杂度

CODE

#include 
using namespace std;
typedef long long  ll;
const int N = 1e5+10;
int a[N];
void solve()
{
   int b,k;
   cin>>b>>k;
   int ans = 0 ;
   int t = 1;
   
   for(int i = 0 ;i>a[i];

   
   ///将公式反过来了
   for(int i  = 0;i