A.02 表示法
这题放在 ABC D 题我可能不会奇怪，但是它放模拟赛 T1 了
赛时代码
#include<bits/stdc++.h>
using namespace std;
class num_string{
private:
string x;
inline void devided_2(){
string ans="";int now=0;
for(int i=0;i<=(int)x.length()-1;++i){
now=now*10+x[i]-'0';
if(now<2){
if(!ans.empty()) ans.push_back('0');
continue;
}
ans.push_back(now/2+'0');
now%=2;
}
if(ans.empty()) ans.push_back('0');
x=ans;
}
public:
num_string(string A){x=A;}
inline num_string operator >>(int _x){
num_string a(x);
while(_x--){a.devided_2();}
return a;
}
inline num_string operator >>=(int _x){
*this=*this>>_x;
return *this;
}
friend ostream& operator <<(ostream& out,num_string&A){
out<<A.x;
return out;
}
friend istream& operator >>(istream& in,num_string&A){
in>>A.x;
return in;
}
string& operator()(){return x;}
num_string to_bit(){
num_string an(x);
string ans="";
while(an().size()!=1 or an()[0]!='0'){
ans.push_back((an().back()-'0')%2+'0');
an>>=1;
}
std::reverse(ans.begin(),ans.end());
return num_string(ans);
}
};
num_string a("");
template<typename T>
std::string to_string(T x){
std::string res;bool f=false;
if(x<0){
f=true;
x*=-1;
}
while(x){
res.push_back((int)(x%10)+'0');
x/=10;
}
reverse(res.begin(),res.end());
if(f) res.push_back('-');
if(res.empty()) res.push_back('0');
return res;
}
void solve(num_string x){
x=x.to_bit();
bool flag=false;
for(int i=0;i<=(int)x().size()-1;++i){
if(x()[i]=='1'){
if(flag) putchar('+');
int w=(int)x().size()-1-i;
if(w==1){
cout<<"2";
}
else if(w==0){
cout<<"2(0)";
}
else{
cout<<"2(";
solve(to_string(w));
cout<<")";
}
flag=true;
}
}
}
int main(){
freopen("pow.in","r",stdin);
freopen("pow.out","w",stdout);
// freopen("code/by/t1.in","r",stdin);
// freopen("out.out","w",stdout);
cin>>a;
solve(a);
}
hdk::bitset 一解
#include<bits/stdc++.h>
#include<bitset.h>
#include<tool.h>
#include<hdk_string.h>
using namespace std;
hdk::bitset::bitset<10000>b;
void solve(hdk::string x){
b.operator=<2>(x);x=b;
bool flag=false;
for(int i=0;__array_of(x)){
if(x[i]=='1'){
if(flag) putchar('+');
int w=x.size()-1-i;
if(w==1) cout<<"2";
else if(w==0) cout<<"2(0)";
else{
cout<<"2(";
solve(hdk::tool::to_string(w));
cout<<")";
}
flag=true;
}
}
}
int main(){
cin>>a;solve(a);
}
B.子串的子串
\(n^2q\log\)
哈希，暴力枚举子区间判断即可
和 \(n^2q\) 一个分
\(n^2+q\)
考虑对一段区间 DP 求差分
设差分数组为 \(f_{l,r}\)，先考虑我们怎么求，我们可以根据一个区间的子区间求前缀和来得到：
\[f_{l,r}=f_{l+1,r}+f{l,r-1}-f_{l+1,r-1}+1 \]这是经典的二位前缀和方法，后面加的那个 \(1\) 是它自己这个子串（显然，没有字符串能和它相等）
然后我们会发现 \([l,r]\) 会被子区间覆盖，所以要长度从大往小求前缀和，防止被覆盖
然后是差分怎么求的问题
假设右边那段红色的区间为 \([l,r]\)，左边找到了一个和它相同的字符串，那么我们就将前面那个字符串的贡献减掉 \(1\)（在差分数组上做这个相当于给整个黑色大区间的贡献减掉 \(1\)，是对的）
那么为什么我们要减掉的是前面的那个而不是后面的那个呢
假设我们减掉后面那个，然后用如下的方式来计算前缀和
for(int i=n;i>=1;--i){
for(int j=i;j<=n;++j){
f[i][j]+=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+1;
}
}
\(1:1+1-1+1-2=0\)
\(2:1+1-1+1-1=1\)
\(3:0+1-(-1)+1=3\)
可以发现小区间答案错了，先遍历的字符串反而没有贡献
然而如果我们放在前面
那么就有
\(1:1+1-1+1-1=1\)
\(2:1+1-1+1-2=0\)
\(3:1+0-(-1)+1=3\)
不知道出题人咋想到的
#include<bits/stdc++.h>
using namespace std;
int n,q;
string a;
unsigned long long num=233;
unsigned long long __hash[3001];
unsigned long long base[3001];
void prework(){
base[0]=1;
for(int i=1;i<=n;++i){
base[i]=base[i-1]*num;
__hash[i]=__hash[i-1]*num+a[i];
}
}
inline unsigned long long _hash(int l,int r){
return __hash[r]-__hash[l-1]*base[r-l+1];
}
int f[3001][3001];
unordered_map<unsigned long long,int>mp;
int main(){
scanf("%d %d",&n,&q);
cin>>a;a=" "+a;
prework();
for(int len=1;len<=n;++len){
mp.clear();
for(int i=1;i+len-1<=n;++i){
int j=i+len-1;
f[mp[_hash(i,j)]][j]--;
mp[_hash(i,j)]=i;
}
}
for(int i=n;i>=1;--i){
for(int j=i;j<=n;++j){
f[i][j]+=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+1;
}
}
while(q--){
int l,r;
cin>>l>>r;
cout<<f[l][r]<<"\n";
}
}
C.魔法咒语
正序插入一颗字典树，如果字典树上某一个节点不存在某个字母 \(\alpha\)，则可以将所有字符串的所有后缀中以 \(\alpha\) 结尾的字符串拼到后面，这样可以保证不会重复
证明：假设最后拼成的子串 \(A=B+C\)，为了防止重复，钦定使 \(B\) 尽可能长，则就是上述 “字典树上某一个节点不存在某个字母 \(\alpha\)” 的限制条件，不妨设 \(S'=\alpha+C\)，实际上我们开这个 cnt 找的是 \(S'\)，为了恰好能拼上，因此需要找倒序状态下以 \(\alpha\) 结尾的字符串
然而当一个词的长度为 \(1\)，那么它完全没办法通过这种办法被拼出来，所以需要特判
知道思路以后就水了
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct trie1{
int tot=0;
int to[400001][26];
void insert(string x){
int pos=0;
for(int i=0;i<=(int)x.length()-1;++i){
if(!to[pos][x[i]-'a']){
to[pos][x[i]-'a']=++tot;
}
pos=to[pos][x[i]-'a'];
}
}
}tr1;
struct trie2{
int tot=0;
int to[400001][26];
int cnt[26];
void insert(string x){
reverse(x.begin(),x.end());
int pos=0;
for(int i=0;i<=(int)x.length()-1;++i){
if(!to[pos][x[i]-'a']){
to[pos][x[i]-'a']=++tot;
cnt[x[i]-'a']++;
}
pos=to[pos][x[i]-'a'];
}
}
}tr2;
int n,ans;
string s[400001];
bool vis[26],flag[26];
signed main(){
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
cin>>n;
for(int i=1;i<=n;++i){
cin>>s[i];
tr1.insert(s[i]);
tr2.insert(s[i]);
vis[s[i].back()-'a']=true;
if(s[i].length()==1 and flag[*s[i].begin()-'a']==false){
ans++;
flag[*s[i].begin()-'a']=true;
}
}
for(int i=1;i<=tr1.tot;++i){
for(int j=0;j<=25;++j){
if(tr1.to[i][j]==0){
ans+=tr2.cnt[j];
}
else ans+=vis[j];
}
}
cout<<ans<<'\n';
}
D.表达式
部分分分块就能算
类似的思想（即若 \(f=g(h)\)，则 \(f(x)=g(h(x))\)），尝试把操作放到线段树上
当 \(P\) 很小的时候，直接对 \(x\mod p\) 维护值就行了
否则，观察到题中的 \(P\) 都可以分解成很小的质数乘积，所以拆开做然后 CRT 就行
注意 CRT 要求模数互质，\(100\) 不能拆完，否则就有重复的数了，拆成 \(25\times 4\) 比较好
在补了
标签：std,num,string,04,int,44,long,联训,include From： https://www.cnblogs.com/HaneDaCafe/p/18454113