看到题目就绷不住了。今天事故挺多的，心里活动也很复杂。
在一道题上浪费太多时间了……明知道做不出来还挺不甘……挺怪的。虽然中场改题面但T3其实依旧水但被T1绑住了，不知是不是对当时摆烂的后悔或弥补.果然时间是守恒的
原
数位DP.
数位DP刚好要做原题，但摆了没做。发现这一事实的时候心情挺复杂的……以后学知识点刷题不能摆！！！不能摆！！！不知道为什么一直在死磕这题。
1~9的最小公倍数为2520，状压出现过那些数，算每次选之后组成的数是啥，并对2520取模。合法取模后不会变成不合法。
要交CF能不取模就不取模，能不ll就不ll。
Code
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll mod=2520;
constexpr auto SIZE(1<<20);
char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
#define flush() (fwrite(out,1,p3-out,stdout))
#define putchar(x) (p3==out+SIZE&&(flush(),p3=out),*p3++=(x))
class Flush{public:~Flush(){flush();}}_;
inline ll read(){
ll x(0);bool f(0);char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar()) f^=ch=='-';
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f?x=-x:x;
}
inline void write(ll x){
x<0?x=-x,putchar('-'):0;static short Sta[50],top(0);
do{Sta[++top]=x%10;x/=10;}while(x);
while(top) putchar(Sta[top--]|48);
putchar('\n');
}
ll T;
int a[25],len;
ll dp[25][2530][270];
inline int get(int x){
return x<2?0:(1<<(x-2));
}
ll dfs(int x,int limit,ll num,int sta){
if(x<=0){
for(ll i=2;i<=9;i++){
if((sta&get(i))&&num%i!=0){
return 0;
}
}
return 1;
}
if(!limit&&dp[x][num][sta]!=-1)
return dp[x][num][sta];
int res=limit?a[x]:9;
ll sum=0;
for(int i=0;i<=res;i++){
sum+=dfs(x-1,limit&&i==res,(num*10+i)%mod,sta|get(i));
}
if(!limit)
dp[x][num][sta]=sum;
return sum;
}
inline ll solve(ll x){
if(x==0)
return 1;
len=0;
while(x){
a[++len]=x%10;
x/=10;
}
return dfs(len,1,0,0);
}
signed main(){
T=read();
memset(dp,-1,sizeof(dp));
while(T--){
ll l=read(),r=read();
write(solve(r)-solve(l-1));
}
return 0;
}
神
AC自动机套数据结构
统计挺板子的，直接统计有多少以它结尾的就好。修改也就修改标记就好。
但暴力统计会变成\(n^2\)的所以我们有数据结构维护一下，运用欧拉序统计答案就好。
CF线段树会又T又M.
Code
#include<cstdio>
#include<string>
#include<iostream>
#include<queue>
#include<cstring>
#include<map>
#define lc (k<<1)
#define rc (k<<1|1)
#define ll long long
using namespace std;
const int N=1e5+5;
const int M=1e6+5;
int n,m;
int t[M][6],tot,fail[M];
int root[N];
vector <int> v[M];
void insert(string s,int j){
int len=s.size();
int now=0;
for(int i=0;i<len;i++){
if(!t[now][s[i]-'a']){
t[now][s[i]-'a']=++tot;
}
now=t[now][s[i]-'a'];
}
root[j]=now;
}
void build(){
queue <int> q;
for(int i=0;i<4;i++){
if(t[0][i]){
v[0].push_back(t[0][i]);
q.push(t[0][i]);
}
}
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=0;i<4;i++){
if(t[now][i]){
fail[t[now][i]]=t[fail[now]][i];
v[fail[t[now][i]]].push_back(t[now][i]);
q.push(t[now][i]);
}else{
t[now][i]=t[fail[now]][i];
}
}
}
}
int in[M],out[M],dfntot;
ll sum[M<<2];
void dfs(int x,int fa){
in[x]=++dfntot;
for(int i=0;i<v[x].size();i++){
dfs(v[x][i],x);
}
out[x]=++dfntot;
}
int lowbit(int x){
return x&(-x);
}
ll c[M<<1];
void update(int x,ll val){
while(x<=dfntot){
c[x]+=val;
x+=lowbit(x);
}
}
ll query(int x){
ll ans=0;
while(x){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
void solve(){
string s;
cin>>s;
int len=s.size();
int now=0;
ll ans=0;
for(int i=0;i<len;i++){
now=t[now][s[i]-'a'];
// printf("%d ",in[now]);
ans+=query(in[now]);
}
cout<<ans<<endl;
}
bool vis[N];
signed main(){
freopen("in","r",stdin);
// freopen("eldenring.in","r",stdin);
// freopen("eldenring.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
string s;
vis[i]=1;
insert(s,i);
}
// for(int i=1;i<=n;i++){
// printf("%d ",root[i]);
// }
build();
dfs(0,0);
// for(int i=1;i<=tot;i++){
// printf("%d %d\n",in[i],out[i]);
// }
for(int i=1;i<=n;i++){
sum[in[root[i]]]++;
sum[out[root[i]]]--;
}
// for(int i=1;i<=dfntot;i++){
// printf("%d ",sum[i]);
// }
for(int i=1;i<=dfntot;i++){
update(i,sum[i]);
}
for(int i=1;i<=m;i++){
char opt;
cin>>opt;
if(opt=='?'){
solve();
}else if(opt=='+'){
int x;
cin>>x;
if(!vis[x]){
vis[x]=1;
update(in[root[x]],1);
update(out[root[x]],-1);
}
}else if(opt=='-'){
int x;
cin>>x;
if(vis[x]){
vis[x]=0;
update(in[root[x]],-1);
update(out[root[x]],1);
}
}
}
return 0;
}
启
最水的一道……
若选 \(i\) 比 选 \(j\) 好 则 $ a_i-b_j>a_j-b_i 则 a_i+b_i>a_j+b_j$
按和排序就好.
Code
···cpp
n=read();
for(int i=1;i<=n;i++){
a[i].a=read(),a[i].b=read();
a[i].sum=a[i].a+a[i].b;
}
sort(a+1,a+1+n,cmp);
int ans1=0,ans2=0;
int now=1;
for(int i=1;i<=n;i++){
if(now==1){
ans1+=a[i].a;
}else{
ans2+=a[i].b;
}
now^=1;
}
printf("%lld ",ans1-ans2);
···
动
$ f_i=min(f_j+a_i*b_j) $
set启发式合并/李超线段树维护凸包/甚至还有神奇的淀粉质和CDQ分治
参考：
(https://www.cnblogs.com/CQzhangyu/p/8456770.html)(https://www.cnblogs.com/Itst/p/10328668.html)
Code
咕……