A：二进制与一

知识点：进制转换、贪心

思路：题目的特殊性质很有帮助。发现 3 是大于等于 2 中最小的二进制全为 1 的数，所以考虑把 n 尽可能拆出更多的 3 一定是最优的。

考虑对余数分类讨论：

• n≡0(mod3)：显然全拆成 3 即可，答案为 2×n/3；
• n≡1(mod3)：考虑拆成 ⌊3n⌋−1 个 3 和两个 2，答案为 2×(⌊n/3⌋−1)+2=2*n/3；
• n≡2(mod3)：考虑拆成 ⌊3n⌋ 个 3 和一个 2，答案为 2×⌊n/3⌋+1。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int t,n;
int main(){
    freopen("binary.in","r",stdin);
    freopen("binary.out","w",stdout); 
    cin>>t;
    while(t--){
        cin>>n;
        if(n%3==0) cout<<n/3*2<<endl;
        else if(n%3==1) cout<<n/3*2<<endl;
        else cout<<n/3*2+1<<endl;
    }
    return 0;
}

B： 前缀逻辑值

知识点：递归

思路：数据只有0或者1，按照树的先序序列进行递归展开。遇到了对应运算符，进行左子树和右子树的展开求解。若遇到了0或者1直接返回即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
string s; 
int x=-1;
bool dfs(){
    x++;
    if(s[x]=='&')return dfs()&dfs();
    else if(s[x]=='|')return dfs()|dfs();
    else if(s[x]=='^')return dfs()^dfs();
    else if(s[x]=='1')return 1;
    else if(s[x]=='0')return 0;
}
int main(){
    freopen("logic.in","r",stdin);
    freopen("logic.out","w",stdout); 
    cin>>s;
    if(dfs())cout<<"true";
    else cout<<"false";
    return 0;
}

C：大师

知识点：动态规划

思路：求解数组中能构成的等差数列的个数，可以考虑dp[i] [j]:代表以a[i]结尾，公差为d的等差数列方案数，由于公差可正可负，那么给公差偏移20000，那么可保证所有j下标大于等于0，直接转移即可

dp[i] [d] = dp[i] [d] + dp[j] [d]+1（以 i 结尾且上一个数是 j 的公差为 d 的等差数列数量是以 j 结尾公差为 d 的等差数列数加一）

最后遍历每一个一i结尾公差为d的dp之和，不要忘记每个数单独考虑一次在累加n即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[1001],dp[1001][40001],ans;
int mod=998244353;
//dp[i][j]以a[i]结尾，公差为d的方案数 
int main(){
    freopen("master.in","r",stdin);
    freopen("master.out","w",stdout); 
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ans+=n;
    for(int i=1;i<=n;i++){
        for(int j=i-1;j>=1;j--){
            int d=a[i]-a[j]+20000;
            dp[i][d]+=dp[j][d]+1;
            dp[i][d]%=mod;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=-20000;j<=20000;j++){
            ans+=dp[i][j+20000];
            ans%=mod;
        }
    }
    cout<<ans;
    return 0;
}

第四题：城市漫步

知识点：深度优先搜索

思路：对于起点到终点的必经路径使用c[i]进行标记，游玩路径使用b[i]进行标记。

第一遍搜索确定必经路径节点，也就是从起点开始搜索，一直搜索到终点，若是终点进行必经路径标记，然后一层一层往上返回进行标记。

第二边搜索确定每个游玩路径b[i]到必经路径的距离，累加在ans里面，若搜索到当前节点是游玩节点并且不是必经节点，那么需要走一个来回对于路径深度*2,然后再一次枚举now的邻接点，若当前节点now是必经路径，那么其邻接点为1的距离深度，若不是，则从当前深度deep+1递归下去即可。

最后ans为此时行走的最短距离。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int t,n,k,x,y,ans;//n总点数 k个景点 x起点 y终点
bool b[N];//b[i]=1说明i号点是目标需要游玩 
bool c[N];//c[i]=1说明i号点是必经之地必须去
vector<int> v[N];//邻接表存图 
//确定起点到终点的路径必经之点 
bool dfs(int fa,int now,int deep){
    if(now==y){
        c[now]=1; 
        ans+=deep;
        return c[now];
    }
    for(int i=0;i<v[now].size();i++){
        int nex=v[now][i];
        if(nex==fa) continue;
        c[now]|=dfs(now,nex,deep+1); 
    }
    return c[now];
}

bool dfs1(int fa,int now,int deep){
    if(b[now]&&!c[now]){
        ans+=deep*2;
        c[now]=1;
    }
    for(int i=0;i<v[now].size();i++){
        int nex=v[now][i];
        if(nex==fa) continue;
        if(c[now]==1){
            dfs1(now,nex,1);
        }else{
            c[now]|=dfs1(now,nex,deep+1); 
        } 
    } 
    return c[now];
}
int main(){
    freopen("city.in","r",stdin);
    freopen("city.out","w",stdout);
    cin>>t;
    while(t--){
        cin>>n>>k>>x>>y;
        ans=0;
        for(int i=1;i<=n;i++){ 
            v[i].clear();
            b[i]=0;
            c[i]=0;
        }
        for(int i=1;i<=k;i++){ 
            int s;cin>>s;
            b[s]=1; 
        }
        for(int i=1;i<n;i++){
            int w,z;cin>>w>>z;
            v[w].push_back(z);
            v[z].push_back(w); 
        } 
        b[x]=1;b[y]=1;
        dfs(0,x,0);
//        cout<<"必经之路: ";
//        for(int i=1;i<=n;i++){
//            if(c[i]) cout<<i<<" ";
//        } cout<<endl;
        dfs1(0,x,0); 
        cout<<ans<<endl;
    } 
    return 0;
}