T1 move

因为每个格子只有两种状态 酷似0 1不是吗
所以我们将4*4的格子压成一个16位的二进制 进行BFS即可
尽管理论上别的BFS方法也是可以的 但是二进制比较好写
并且此题需要剪枝(判重） 把之前搜到的结果用一个[1<<17]的数组存一下就好了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int a,b;
char s[22];
queue<int>q;
int dis[1<<17];
bool vis[1<<17];
int tmp,nmp;
void move(int x,int i)
{
    if(x&(1<<i)) return ;
    int y=x+(1<<i);
    if(vis[y]) return ;
    q.push(y),dis[y]=dis[nmp]+1,vis[y]=1;
    return ;
}
void bfs()
{
    q.push(a);
    vis[a]=true;
    while(q.size())
    {
        nmp=q.front();
        q.pop();
        for(int i=0;i<16;i++)
            if(nmp&(1<<i))
            {
                tmp=(1<<i)^nmp;
                if(i%4>0) move(tmp,i-1);
                if(i%4<3) move(tmp,i+1);
                if(i/4>0) move(tmp,i-4);
                if(i/4<3) move(tmp,i+4);
                if(vis[b]) 
                {
                    printf("%d",dis[b]);
                    return ;
                }
            }
    }
}      
int main()
{
    for(int i=1;i<=4;i++)
    {
        scanf("%s",&s[0]);
        for(int j=0;j<4;j++)
        { 
            a=a*2;
            if(s[j]=='#') a++; 
        }
    }   
    for(int i=1;i<=4;i++)
    {
        scanf("%s",&s[0]);
        for(int j=0;j<4;j++)
        { 
            b=b*2;
            if(s[j]=='#') b++; 
        }
    }    
    bfs();
    return 0;
}

---

T2 puppt

这题方案有很多啊= =
先讲一下std的做法：
如果是奇数的话 很显然就是在i-1的基础上再加一个1 所以
如果是偶数的话 分两种情况讨论
1：分解之后存在1 那么同样是在i-1的基础上再加一个1
2：分解之后不存在1 那么每个分解出来的数都是偶数 将每个分解的数都除以2，刚好是i/2的分解结果，并且可以与之一一对应，这种情况有
所以在偶数的情况下
n的范围是正常递推即可

还有一种方法
因为n的范围是 我们可以注意到 而 那么我们拿出每一项，进行完全背包即可

---

T3 sigma

我们令为的最大奇因数和
我们先把分为奇数与偶数两堆
很显然奇数的最大奇因数和就是本身 所以奇数这堆的和就是一个等差数列求和
再来考虑偶数那堆 显然是
每项除上一个2 就得到了
进行递归处理即可