codeforce#937 (div4)题解

E. Nearly Shortest Repeating Substring

给出字符串s，是否存在长度为k的字符串多次拼接后得到的字符串与s最多有一位不同

由题意得，k一定是n的因数，所以暴力枚举就好，求出满足$s[i]==s[i\mathrm{mod}k]$的最大k值。
注意允许有一位的偏差，所以每次只比较两个值并不能确定哪个是正确的，例如上述条件，如果$s[i]$正好为偏差值，那么将会产生多次不满足条件的情况，从而造成误判，所以需要对$i+xk$的序列整体判断，是否满足误差为1的条件

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>

#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)

using namespace std;

typedef long long ll;

string store;
bool check(int);
int main() {
    IOS
    
    int t;
    cin>>t;
    while(t--) {
        int len;
        cin>>len;
        cin>>store;
        
        int ans = len;
        for(int i=1;i*i<=len;i++) {
            if (len%i) continue;
            
            if (check(i)) {
                ans = min(ans, i);
                break;
            }
            if (check(len/i)) ans = min(ans, len/i);
        }
        cout<<ans<<endl;
    }
    
    return 0;
}
bool check(int n) {
    bool diff = false;
    int dif_pos = -1;
    int pos = 0;
    int len = store.length();
    while(pos<len) {
        if (dif_pos >=0 && pos%n == dif_pos%n) {
            pos ++;
            continue;
        }
        if (store[pos] != store[pos%n]) {
            if (diff) {
                return false;
            } else {
                diff = true;
                dif_pos = pos;
            }
        }
        
        pos ++;
    }
    set<char> tmp;
    vector<int> times(26,0);
    if (dif_pos >= 0) {
        pos = dif_pos % n;
        while(pos<len) {
            tmp.insert(store[pos]);
            times[store[pos]-'a'] ++;
            pos += n;
        }
        if (tmp.size() > 2) return false;
        bool is_one = false;
        for(auto c : tmp) {
            if (times[c-'a'] == 1) is_one = true;
        }
        return is_one;
    }
    
    return true;
}

F. 0, 1, 2, Tree!

分别给出二叉树中出度为2，1和0(叶结点)的个数，求这棵树最小高度。根据树的性质，假设树有$n$个节点，那么一定有$n-1$条边，不难得出$a=c-1$

现在出度为2和0的节点排布都已经确定，想要树的高度上升就要看出度为1的节点如何排布了。现在树的最底层，也就是连接叶结点的那一层，所能承载的节点数是最多的，所以直接在这一层添加节点得到的树一定是高度最小的。

注意如下情况，需要将这一层补齐再计算最多能承载多少节点

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>

#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)

using namespace std;

typedef long long ll;

int table[32];
int qe_1(int);
int ge(int);
int main() {
    IOS
    
    table[0] = 1;
    rep(i,1,30) table[i] = table[i-1] * 2;
    
    int t;
    cin>>t;
    while(t--) {
        int a,b,c;
        cin>>a>>b>>c;
        if (a != c-1) {
            cout<<-1<<endl;
            continue;
        }
        if (a==0) {
            cout<<b<<endl;
            continue;
        }
        
        int _ = 0, a_copy = a;
        while(a_copy > 0) {
            if (table[_] == a_copy) {
                a_copy = 0;
                break;
            }
            if (table[_] > a_copy) break;
            a_copy -= table[_];
            _++;
        }
        int base = _;
        int res = a_copy;
        int ans, t;
        if (res == 0) {
            ans = base;
            t = table[base+1];
        } else {
            ans = base;
            t = table[base] + res;
            b -= (table[base] - res);
        }
        
        while(b > 0) {
            ans ++;
            b -= t;
        }
        cout<<ans+1<<endl;
    }
    
    return 0;
}

G. Shuffling Songs

状压dp。因为数据量不大，最多16个，所以不会超内存。记$dp[now][last]$为状态为now，列表最后一个为last时整个列表有多少首歌。其中状态now的二进制列序表示了有哪些歌曲已经加入了(这个和数组中的内容其实是重复，数组开个bool其实也可以，反正也能从now中恢复数量)。
然后就是根据条件看没有添加进来的歌曲和last是否匹配。最后取所有组合中能包含数量最多的，减去总量就是最少能剔除的歌曲

最后补充一下为什么可以循环替换queue。显然这个题用queue去跑更加符合认知。初始状态是每一首歌，从初始状态开始不断加入歌曲直到所有状态都遍历完成，循环似乎不能完美的模拟这样的树状进程。但实际上，采用循环，当我们遍历到11的时候，现在1和10的状态我们都已经遍历过，因为11大于1和10的，所以也能保证在遍历11的时候是所有可能到达11状态的最优

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>

#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1<<17;

struct recrod{
public:
    int now,last,sum;
    void show();
};
void recrod::show() {
    string to_bin = "";
    int tmp = now;
    while(tmp) {
        to_bin += '0'+(tmp%2);
        tmp = tmp >> 1;
    }
    reverse(to_bin.begin(), to_bin.end());
    cout<<"now:"<<to_bin<<" last:"<<last<<" sum:"<<sum<<endl;
}

bool inqeue[maxn+5];
int dp[maxn][16];
vector<pair<int, int> > store;
map<string, int> numMap;
queue<recrod> Q;
inline bool match(const pii&, const pii&);
int main() {
    IOS
    
    int t;
    cin>>t;
    while(t--) {
        numMap.clear();
        store.clear();
        rep(i,0,maxn) rep(j,0,16) dp[i][j] = 0;
        
        int n;
        cin>>n;
        int cnt = 0;
        rep(i,0,n) {
            string commonA,commonB;
            cin>>commonA>>commonB;
            
            if (numMap.find(commonA) == numMap.end())
                numMap[commonA] = cnt ++;
            int a = numMap[commonA];
            if (numMap.find(commonB) == numMap.end())
                numMap[commonB] = cnt ++;
            int b = numMap[commonB];
            
            store.push_back(make_pair(a, b));
        }
        
        int ans = 0;
        rep(dig,0,n) dp[1<<dig][dig] = 1;
        rep(now,1,1<<(n+1)) {
            rep(last, 0,n) {
                if (!dp[now][last]) continue;
                ans = max(ans, dp[now][last]);
                rep(i,0,n) {
                    if (now & (1<<i)) continue;
                    
                    pair<int, int> last_edge = store[last];
                    pair<int, int> now_edge = store[i];
                    if ((last_edge.second == now_edge.second) || (last_edge.first == now_edge.first))
                        dp[now | (1<<i)][i] = dp[now][last] + 1;
                }
            }
        }
        cout<<n-ans<<endl;
    }
    
    return 0;
}
inline bool match(const pii& edge,const pii& e2){
    return edge.first==e2.first || edge.second==e2.second;
}