Preface
A. Division
题意：
给定若干组询问(p,q)，找出最大的，整除p的，不被q整除的整数x;
思路：
分解质因数p=\prod_{t=1}^{s}p_t^{\alpha_t}, q=\prod_{t=1}^{s}p_t^{\beta_t},那么x={\max_{1\le i\le t}}({p_i^{\beta_i-1}\prod_{t=1,t\neq i}^{s}p_t^{\alpha_t}});
模板为质因数分解的模板，在质因数分解的过程中同时寻找最大值；
本以为会超时，结果根本没有，可能数据没用毒瘤质数来卡吧；
AC code：
#define local
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=1e9+7;
void solve(){
ll p;
ll q;
cin>>p>>q;
if(p%q!=0) {
cout<<p<<endl;
return;
}
ll ans=0;
for(ll k=2;k*k<=q;k++){
if(q%k!=0) continue;
ll y=1;
while(q%k==0) {
y*=k;
q/=k;
}
ll x=1;
while(p%x==0) x*=k;
x/=k;
ll tmp=p/x*y/k;
if(tmp>ans) ans=tmp;
}
if(q>1) {
ll x=1;
while(p%x==0) x*=q;
x/=q;
ll tmp=p/x;
if(tmp>ans) ans=tmp;
}
cout<<ans<<endl;
return;
}
int main ()
{
#ifdef local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t;
cin>>t;
while(t--) solve();
return 0;
}
B. Logistical Questions
题意：
思路：
AC code：
C. Lucky Array
题意：
思路：
AC code：
D. Is It a Cat?
题意：
模拟题；
注意猫叫声音的结构已经给定，逐个判断每个字母的所在的串是否按顺序出现，同时保证不要有别的字母；
思路：
AC code：
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
bool ismM(char x){
return x=='m'||x=='M';
}
bool iswW(char x){
return x=='w'||x=='W';
}
bool iseE(char x){
return x=='e'||x=='E';
}
bool isoO(char x){
return x=='o'||x=='O';
}
int main ()
{
#ifdef local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t;
cin>>t;
while(t--)
{
int ans=0;
int n;
cin>>n;
string s;
cin>>s;
int cnt=0;
int i=0;
for(i=0;i<n;i++){
if(!ismM(s[0])) break;
if(ismM(s[i])){
if(cnt==0) cnt++;
else{
if(!ismM(s[i-1])) break;
}
}
else if(iseE(s[i])){
if(cnt==1) cnt++;
else{
if(!iseE(s[i-1])) break;
}
}
else if(isoO(s[i])){
if(cnt==2) cnt++;
else{
if(!isoO(s[i-1])) break;
}
}
else if(iswW(s[i])){
if(cnt==3) cnt++;
else{
if(!iswW(s[i-1])) break;
}
}
else break;
}
if(i==n&&cnt==4) ans=1;
if(ans==1) printf("YES\n");
else printf("NO\n");
}
return 0;
}
E. Merge Sort
题意：
思路：
Ac code:
F. Guess the K-th Zero (Hard version)
题意：
思路：
交互题；
Ac code:
G. Sum Over Zero
题意：
给你一个长度为的序列 a[1..n]，现在请你找到这个序列的若干个不相交的合法子段;
对于你选择的一个子段，其为一个合法子段当且仅当子段的区间和非负
对于一个合法的子段，我们记 ，且当子段 为空时， ;
对于你选择的这若干个不相交合法子段，请最大化并输出这个最大值
思路：
Ac code：
H. Watto and Mechanism
题意
给出 个已知字符串，次询问，每次询问给出一个字符串，问上面 个字符串中是否有一个字符串满足恰好有一个字母不同于询问的字符串;
，其中所有字符串的字符属于{'a','b','c'}，且输入总长度不超过
思路
在线询问字符串是否匹配，运用字典树可以高效处理这样的匹配问题；
由于字符串的匹配必须刚好存在一个字符的错误，因此查找算法可以改进为DFS搜索算法，出错之后错误数加1，继续向下搜索，错误数为2则开始回溯，搜到结尾满足条件则返回匹配成功；
建树不做优化的化可能会在Test19出现MLE，但是一开始的思路是手动开栈模拟递归，不太行会有WA;
其实注意到了匹配成功必须有两个字符串长度相等，可以按长度分类建立字典树，但是由于没写过树套树,所以不太敢想；
树套树写了也没过test19, 但是其实数据卡的好可以做到数据点的字符串长度都相同，这样优化就一般了；
最终发现函数传递没有引用，导致递归栈每次都需要把字符串的内容copy一遍，改传引用就过了；
Ac code：
# include <iostream>
# include <vector>
# include <string>
using namespace std;
class Trie {
public:
# define ALPHABET_SIZE 3
# define MAX_CAPACITY 600005
int cnt; int next[MAX_CAPACITY][ALPHABET_SIZE];
bool isEndOfWord[MAX_CAPACITY];
void insert(std::string& s) {
int n = s.length();
int p = 0;
for(int i = 0; i < n; i++) {
int index = s[i] - 'a';
if(next[p][index] == 0) next[p][index] = ++cnt;
p = next[p][index];
}
isEndOfWord[p] = true; }
Trie(std::vector<std::string>&words) {
for(auto &word : words) insert(word);
}
bool find(std::string&s) {
int n = s.length();
int p = 0;
for(int i = 0; i < n; i++) {
int index = s[i] - 'a';
if(next[p][index] == 0) return false;
p = next[p][index];
}
return isEndOfWord[p];
}
bool dfs(std::string& q, int i, int p, int err){
if(err > 1) return false;
if(i == q.length() ) return (err ==1) & isEndOfWord[p];
bool res[ALPHABET_SIZE ]={false};
for(int idx = 0; idx < ALPHABET_SIZE; idx++){
if(next[p][idx] != 0){
res[idx] = dfs(q, i+1, next[p][idx], err + (q[i]- 'a' != idx));
}
}
bool ans = false;
for(int idx = 0; idx < ALPHABET_SIZE; idx++) ans |= res[idx];
return ans;
}
};
int main(){
# ifdef MYIO
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
# endif
int n, m;
cin >> n >> m;
vector<string> patten(n);
vector<string> query(m);
for(int i = 0; i < n; i++) cin >> patten[i];
for(int i = 0; i < m; i++) cin >> query[i];
Trie trie(patten);
for(auto &q : query) {
if(trie.dfs(q, 0, 0, 0)) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
