A：字符串hash+kmp
#include <iostream> #include <cstdio> #include <string> #include <map> using namespace std; typedef unsigned long long ull; typedef long long ll; const int maxn = 1e6+5; const int mod = 998244353; string s[maxn]; map<ull,int> hush; ull base = 233; void store(int x) { int len = s[x].length()-1; ull now = 0 , lev = 1; for(int i=len;i>=1;--i,lev=lev*base) { now = now + lev * (s[x][i]-'a'+1); ++hush[now]; } } int ne[maxn]; ll cnt[maxn]; ll pro(int x) { int len = s[x].length()-1; ne[1] = 0; for(int i=2,j=0;i<=len;++i) { while(j>=1&&s[x][j+1]!=s[x][i]) j=ne[j]; if(s[x][j+1]==s[x][i]) ++j; ne[i]=j; } ull now = 0; for(int i=1;i<=len;++i) { now = now * base + s[x][i]-'a'+1; cnt[i] = hush[now]; cnt[ne[i]] -= cnt[i]; } ll res = 0; for(int i=1;i<=len;++i) { res = (res + (ll)i*i%mod*cnt[i]%mod)%mod; } return res; } int main() { // freopen("in.txt","r",stdin); ios::sync_with_stdio(false); int n; cin>>n;; for(int i=1;i<=n;++i) cin>>s[i] , s[i]="0"+s[i] ,store(i); ll ans = 0; for(int i=1;i<=n;++i) ans = (ans + pro(i))%mod; cout<<ans; return 0; }
B：计算几何+stl
#include<bits/stdc++.h> using namespace std; #define ll long long #define N 2005 #define mk make_pair #define db double int n,x[N],y[N]; vector<pair<db,db>> v; inline void add(int x1,int y1,int x2,int y2,int x3,int y3){ ll A=x2*y3-x3*y2; ll B=1ll*(x2*x2+y2*y2)*(y1-y3)+1ll*(x3*x3+y3*y3)*(y2-y1); ll C=1ll*(x2*x2+y2*y2)*(x3-x1)+1ll*(x3*x3+y3*y3)*(x1-x2); if(A==0)return; double x=-B/2.0/A,y=-C/2.0/A; v.push_back(mk(x,y)); //cout<<x<<" "<<y<<' '; } #define eps 1e-12 int sign(db a,db b){ return abs(a-b)<=eps; } int main(){ cin>>n; for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) add(0,0,x[i],y[i],x[j],y[j]); ll ans=0; sort(v.begin(),v.end()); int len=0; for(int i=0;i<v.size();i++){ if(i==0){len++;continue;} if(sign(v[i].first,v[i-1].first) && sign(v[i].second,v[i-1].second))len++; else ans=max(ans,1ll*len),len=1; } ans=max(ans,1ll*len); for(ll i=1;i<=n*n;i++) if(i*(i-1)/2==ans){ ans=i;break; } cout<<ans<<' '; }
G：预处理+dp+bitset优化
#include<bits/stdc++.h> using namespace std; #define N 200005 bitset<40005> S[N],cnt; int n,A[N],m,B[N],C[N],pos[N]; #define ll long long ll read() { char ch = getchar(); ll x = 0, f = 1; while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } struct Node{ int b,id; }p[N]; int cmp(Node a,Node b){ return a.b<b.b; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)A[i]=read(); for(int i=1;i<=m;i++)B[i]=read(),p[i].id=i,p[i].b=B[i],C[i]=B[i]; sort(p+1,p+1+m,cmp); sort(C+1,C+1+m); int tot=m; for(int i=1;i<=n;i++){ int p=upper_bound(C+1,C+1+tot,A[i])-C-1; pos[i]=p; } for(int i=1;i<=tot;i++){ S[i]=S[i-1]; S[i][p[i].id]=1; } int ans=0; bitset<40005>now,I; I[m]=1; cnt[m]=(A[n]>=B[m]); if(cnt[1])ans++; for(int i=n-1;i>=1;i--){ cnt>>=1; cnt[m]=1; cnt&=S[pos[i]]; if(cnt[1])ans++; //swap(now,cnt); } cout<<ans<<' '; }
H：线段树区间合并+分类讨论
#include<bits/stdc++.h> using namespace std; #define N 200005 int tot,n,op[N],x[N],t[N]; multiset<int>ss; struct Node{ int len,mi,mx,num;//最小间隔,最左端值,最右端值,元素个数 }s[N<<2]; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 Node merge(Node a, Node b){ if(a.num==0)return b; if(b.num==0)return a; Node res; res.mi=a.mi;res.mx=b.mx; res.num=a.num+b.num; res.len=min(a.len,b.len); res.len=min(res.len,b.mi-a.mx); return res; } void build(int l,int r,int rt){ if(l==r){ s[rt].len=0x3f3f3f3f; s[rt].mi=0x3f3f3f3f; s[rt].mx=0; s[rt].num=0; return; } int m=l+r>>1; build(lson);build(rson); s[rt]=merge(s[rt<<1],s[rt<<1|1]); } void add(int pos,int l,int r,int rt){//在某点插入一个点 if(l==r){ s[rt].num++; if(s[rt].num>=2) s[rt].len=0; s[rt].mi=s[rt].mx=t[pos]; return; } int m=l+r>>1; if(pos<=m)add(pos,lson); else add(pos,rson); s[rt]=merge(s[rt<<1],s[rt<<1|1]); } void del(int pos,int l,int r,int rt){//在某点删掉一个点 if(l==r){ s[rt].num--; if(s[rt].num==0) s[rt]={0x3f3f3f3f,0x3f3f3f3f,0,0}; else if(s[rt].num==1) s[rt].len=0x3f3f3f3f; return; }int m=l+r>>1; if(pos<=m)del(pos,lson); else del(pos,rson); s[rt]=merge(s[rt<<1],s[rt<<1|1]); } Node query(int L,int R,int l,int r,int rt){//查询区间 if(L<=l && R>=r)return s[rt]; int m=l+r>>1; Node res={0x3f3f3f3f,0x3f3f3f3f,0,0}; if(L<=m)res=merge(res,query(L,R,lson)); if(R>m)res=merge(res,query(L,R,rson)); return res; } int solve1(int x){ int a,b; auto it=ss.upper_bound(x); if(it==ss.begin())return 0; it--;b=*it; if(it==ss.begin())return 0; it--;a=*it; if(a+b>x)return 1; return 0; } int solve2(int x){ auto it=ss.lower_bound(x); if(it==ss.end())return 0; int pos=lower_bound(t+1,t+1+tot,*it)-t; Node res=query(pos,tot,1,tot,1); if(res.len<x)return 1; int tmp=*it; if(it!=ss.begin())it--; else return 0; if(tmp-*it<x)return 1; return 0; } int main(){ cin>>n; for(int i=1;i<=n;i++)scanf("%d%d",&op[i],&x[i]); memcpy(t,x,sizeof x); sort(t+1,t+1+n); tot=unique(t+1,t+1+n)-t-1; build(1,tot,1); for(int i=1;i<=n;i++){ if(op[i]==1){ ss.insert(x[i]); int pos=lower_bound(t+1,t+1+tot,x[i])-t; add(pos,1,tot,1); }else if(op[i]==2){ ss.erase(ss.find(x[i])); int pos=lower_bound(t+1,t+1+tot,x[i])-t; del(pos,1,tot,1); }else if(op[i]==3){ //先以x为最大边，去ss里找两个前驱 if(solve1(x[i])){ puts("Yes");continue; } //x不是最大边 if(solve2(x[i])){ puts("Yes");continue; } puts("No"); } } }