A - Stair, Peak, or Neither?

水中之水题

void solve(){
    CIN(a);CIN(b);CIN(c);
    if(a<b&&b<c)cout<<"STAIR\n";
    else if(b>a&&b>c)cout<<"PEAK\n";
    else cout<<"NONE\n";
}

B - Upscaling

制表题，水题

string ANS[2]={"##",".."};

void solve(){
    CIN(n);
    FOR(i,1,2*n){
        FOR(j,1,n){
            cout<<ANS[(((i-1)/2+1)+j)%2];
        }
        cout<<ET;
    }
}

C - Clock Conversion

格式转换，水题

void solve(){
    SCIN(s);
    int h=stoi(s.substr(0,2));
    if(h<12){
        if(h==0)cout<<"12"<<s.substr(2)<<" AM\n";
        else cout<<s<<" AM\n";
    }else{
        if(h>12)h-=12;
        if(h>=10)cout<<h<<s.substr(2)<<" PM\n";
        else cout<<0<<h<<s.substr(2)<<" PM\n";
    }
}

D - Product of Binary Decimals

大概思路

暴力打表判断即可

参考代码

bool ans[100005];
int lst[]={10,11,101,111,1001,1011,
            1101,1111,10001,10011,10101,
            11001,10111,11011,11101,11111};
void pre(){
    sort(lst,lst+16);
}
 
void solve(){
    CIN(n);
    while(n>=10){
        bool cg=1;
        rFOR(i,15,0){
            if(n%lst[i]==0){
                n/=lst[i];
                cg=0;
            }
        }
        if(cg)break;
    }
    cout<<ANS[n==1];
}

E - Nearly Shortest Repeating Substring

大概思路

分解质因数，对第一段和第二段跑两遍模拟

参考代码

vector<int> d(int x) {//可以这样分解质因数，然后for(auto& i:dn)遍历，也可以直接FOR(i,1,n)，然后if(n%i)continue;
    vector<int> ans;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            ans.push_back(i);
            if (x / i != i)ans.push_back(x / i);
        }
    }
    sort(ans.begin(), ans.end());
    return ans;
}

void solve() {
    CIN(n); SCIN(s);
    FOR(i,1,n) {
        if (n % i)continue;
        int cnt = 0;
        FOR(j, 0, n - 1) {
            cnt += (s[j] != s[j % i]);
            if (cnt > 1) break;
        }
        if (cnt <= 1) { cout << i << ET; return; }
        cnt = 0;
        FOR(j, 0, n - 1) {
            cnt += (s[j] != s[j % i + i]);
            if (cnt > 1) break;
        }
        if (cnt <= 1) { cout << i << ET; return; }
    }
}

F - 0, 1, 2, Tree!

大概思路

实际上是算术题，先让子树数为2的节点按满二叉树尽可能排满，然后最后一排没排满的节点填上子树数为1的节点，判断最底层节点数是否等于题目提供的“子树数为0的节点个数”，再输出层数即可。

参考代码

int len(int x){return x>0?log2l(x)+1:0;}

void solve(){
    CIN(a);CIN(b);CIN(c);
    if(a==0){
        if(c!=1){cout<<-1<<ET;return;}
        cout<<b<<ET;return;
    }
    int al=len(a);//获得二叉树层数
    int am=(a-(1ll<<(al-1))+1);//获得尽可能填满的二叉树最后一层有多少个“子树数为2”的节点数量
    int br=((1ll<<(al-1))-am);//获得最后一层剩多少个空位
    if(c!=br+am*2){cout<<-1<<ET;return;}//判断子树数为0的节点数量是否满足题意
    if(b<=br){cout<<al<<ET;return;}//如果最后一层填不满，直接输出答案
    b-=br;
    cout<<al+b/(br+am*2)+(b%(br+am*2)!=0)<<ET;//如果能填满，就输出还要加多少层才能填满
}

G - Shuffling Songs

状压DP，可行性DP

大概思路

设dp[i][j]为“已选歌曲状态为i，最后一首为j，这种情况下是否可行” 然后写递推即可。

参考代码

bool dp[1<<16][16];
string a[16],b[16];
vector<int> e[16];
 
void dfs(int state,int now){
    dp[state][now]=1;
    for(auto &i:e[now]){
        if((state&(1<<i))||dp[state|(1<<i)][i])continue;
        dfs(state|(1<<i),i);
    }
}
 
void solve(){
    CIN(n);
    FOR(i,1,(1<<n))FOR(j,0,n){
        dp[i][j]=0;
    }
    FOR(i,0,n-1)e[i].clear();
    FOR(i,0,n-1)cin>>a[i]>>b[i];
 
    FOR(i,0,n-1)FOR(j,0,n-1){//建图优化字符串比较
        if(a[i]==a[j]||b[i]==b[j]){
            e[i].push_back(j);
            e[j].push_back(i);
        }
    }
 
    FOR(i,0,n-1){
        dfs(1<<i,i);
    }
 
    int mx=0;
    FOR(i,1,(1<<n))FOR(j,0,n){//收集答案
        if(dp[i][j])mx=max(mx,__builtin_popcount(i));
    }
    cout<<n-mx<<ET;
}

附录

这里贴上用到的头部和main函数(有更新，for循环没事别开long long，常数大)：

#include<iostream>
#include<vector>
#include<cmath>
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
#define ET '\n'
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(int i=(a);i>=(b);i--)
//双向for循环
#define rep(i,a,b) for(int i=(a);i!=(b)+2*(a<b)-1;i+=2*(a<b)-1)
#define CIN(a) ll a;cin>>a
#define DCIN(a) ld a;cin>>a
#define SCIN(a) string a;cin>>a
#define CA cout<<ans<<ET
#define CY cout<<"YES"<<ET
#define CN cout<<"NO"<<ET
#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a<b)?(a):(b))
//没有C++20就不能用ranges了
//#define PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
//string ANS[2]={"No\n","Yes\n"};
int M=1e9+7;
inline ll MO(ll x){return (x%M+M)%M;}

void solve(){

}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //pre();
    CIN(t);while(t--)
    solve();
    return 0;
}