E. Nearly Shortest Repeating Substring
给出字符串s，是否存在长度为k的字符串多次拼接后得到的字符串与s最多有一位不同
由题意得，k一定是n的因数，所以暴力枚举就好，求出满足
s
[
i
]
=
=
s
[
i
m
o
d
k
]
s[i] == s[i \mod k]
s[i]==s[imodk]的最大k值。
注意允许有一位的偏差，所以每次只比较两个值并不能确定哪个是正确的，例如上述条件，如果
s
[
i
]
s[i]
s[i]正好为偏差值，那么将会产生多次不满足条件的情况，从而造成误判，所以需要对
i
+
x
k
i+xk
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 n个节点，那么一定有 n − 1 n-1 n−1条边，不难得出 a = c − 1 a = c - 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个，所以不会超内存。记
d
p
[
n
o
w
]
[
l
a
s
t
]
dp[now][last]
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;
}
![[答疑]关于《评“状态和事件本质相同”》的6个疑问](https://img-blog.csdnimg.cn/img_convert/c938d2f127070df8cbc8a5a222dd8acd.png)
