部分题解后面更行
A Equivalent Prefixes
题解：https://blog.csdn.net/liufengwei1/article/details/96515809
参考代码：
#include<bits/stdc++.h> #define maxl 100010 using namespace std; int n,ans,top; int a[maxl],b[maxl]; int la[maxl],ra[maxl],lb[maxl],rb[maxl]; int s[maxl]; inline bool jug(int mid) { top=0; for(int i=1;i<=mid;i++) { while(top>0 && a[i]<a[s[top]]) ra[s[top]]=i-1,top--; s[++top]=i; la[i]=s[top-1]+1; } while(top>0) ra[s[top]]=mid,top--; top=0; for(int i=1;i<=mid;i++) { while(top>0 && b[i]<b[s[top]]) rb[s[top]]=i-1,top--; s[++top]=i; lb[i]=s[top-1]+1; } while(top>0) rb[s[top]]=mid,top--; for(int i=1;i<=mid;i++) if(la[i]!=lb[i] || ra[i]!=rb[i]) return false; return true; } int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); int l=1,r=n,mid; while(l+1<r) { mid=(l+r)>>1; if(jug(mid)) l=mid; else r=mid; } if(jug(r)) ans=r; else ans=l; printf("%d ",ans); } return 0; }
B Integration
参考代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int mod =1e9+7; const int size=1e3+5; int quick_pow(int a,int b) { int ans=1; while(b) { if(b&1) ans=1LL*ans*a%mod; a=1LL*a*a%mod; b>>=1; } return ans%mod; } int a[size]; int k[size]; int main() { int n; while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { k[i]=1; for(int j=1;j<=n;j++) { if(j==i) continue; k[i]=1LL*k[i]*((1LL*a[j]*a[j]%mod-1LL*a[i]*a[i]%mod+mod)%mod)%mod; } k[i]=quick_pow(k[i],mod-2); } int ans=0; for(int i=1;i<=n;i++) { ans=(ans+1LL*k[i]*500000004%mod*quick_pow(a[i],mod-2)%mod)%mod; } printf("%d ",ans); } }
E ABBA
法一：DP
题意：问给你长度为2*（n+m）的字符串，由n+m个‘A'和’B'组成，要求有n个AB子序列，和m个BA子序列，这样的串有多少种 ？
题解：前n个A必为AB的A，前m个B必为BA的B，因为如果我前n个A中有一个是BA的A,那么我们可以从更后面 随便找一个A给这个B用。
然后DP：定义dp[i][j] : 放了i个A和j个B的合法方案数。
放A：
如果i < n 那么可以直接放这个A，理由如上。
如果i>=n 那么我们要确保这个放的A能给前面的B当做BA中的A用，那么当我 们需要的A是min(j,m)个 已经给了i-n个， 故如果(i-n)<min(j,m) 还可以继续放A.
放B ：
如果j< m 那么可以直接放这个B，
如果j>=m 那么我们要确保这个放的B能给前面的A当做AB中的B用，那么当我 们需要的B是min(i,n)个 已经给了j-m个， 故如果(j-m)<min(i,n) 还可以继续放B.
参考代码：
#include<bits/stdc++.h> using namespace std; #define mod 1000000007 typedef long long ll; const int maxn=3010; int n,m,dp[maxn][maxn]; void add(int &a,int b){a+=b;if(a>=mod)a-=mod;} int main() { while(~scanf("%d%d",&n,&m)) { for(int i=0;i<=n+m;++i) for(int j=0;j<=n+m;++j) dp[i][j]=0; dp[0][0]=1; for(int i=0;i<=n+m;++i) for(int j=0;j<=n+m;++j) { if(i<n||i-n<j) add(dp[i+1][j],dp[i][j]); if(j<m||j-m<i) add(dp[i][j+1],dp[i][j]); } printf("%d ",dp[n+m][n+m]); } return 0; }
法二：下面是数学方法过的。
参考代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int mod=1e9+7; const int size=4e3+5; int fac[size],invfac[size]; int quick_pow(int a,int b) { int ans=1; while(b) { if(b&1) ans=1LL*ans*a%mod; a=1LL*a*a%mod; b>>=1; } return ans%mod; } void init() { fac[0]=1; for(int i=1;i<size;i++) fac[i]=1LL*fac[i-1]*i%mod; invfac[size-1]=quick_pow(fac[size-1],mod-2); for(int i=size-2;i>=0;i--) invfac[i]=1LL*invfac[i+1]*(i+1)%mod; } int combi(int a,int b) { if(a<0) return 0; if(a==0) return 1; return 1LL*fac[b]*invfac[a]%mod*invfac[b-a]%mod; } int main() { int n,m; init(); while(~scanf("%d%d",&n,&m)) { printf("%d ",(1LL*fac[2*(n+m)]*invfac[n+m]%mod*invfac[n+m]%mod-combi(n-1,2*(n+m))+mod-combi(m-1,2*(n+m))+mod)%mod); } }
F Random Point in Triangle
题解：https://blog.csdn.net/liufengwei1/article/details/96481280
参考代码：
#include<bits/stdc++.h> #define maxl 10010 using namespace std; int main() { int x1,y1,x2,y2,x3,y3; while(~scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3)) { long long tmp=1ll*(x2-x1)*(y3-y1)-1ll*(x3-x1)*(y2-y1); if(tmp<0) tmp=-tmp; printf("%lld ",tmp*11); } return 0; }
H XOR
题解：题目的意思是：给你N个数的集合A，然你找一个子集S满足S中的所有元素异或后为0（mod 1000000007）,让你求 ∑|S|.
这题可以转换思路，求每一个元素出现的集合数量，即求每一个元素的贡献。
线性基的性质是用小集合表示大集合，（大集合里面任意元素的异或值都可以在小集合里面得到）。
然后我们将元素分为线性基内外两部分：
线性基外的元素：
根据线性基的性质可以求出 ans1 = 1LL * size * ( 2^(size-1) ) % mod;
线性基内部的元素：
我们枚举每一个元素，然后将剩余元素建立新的线性基，如果这个元素任然可以插入新的线性基，则该元素没有贡献(因为不会出现为零的子集包含该元素)
如果不能插入的话，那么该元素的贡献是 1LL * ( 2 ^ ( size - 1 ) ) % mod;
对于判断是否能插入这个地方，我们可以优化： 在刚开始构建线性基的时候，对于不在线性基里面的元素我们可以记录它可以替代哪些位置，然后后面枚举每一位上面的1是否可以被替代即可。
(上面题解写得不明不白，还是我的题解写得好233https://blog.csdn.net/liufengwei1/article/details/96571038)
参考代码：
#include<bits/stdc++.h> using namespace std; #define mod 1000000007 typedef long long ll; vector<ll> vec; const int maxn=2e5+10; int n; ll a[maxn],LB[64],b[64]; ll pre[maxn]; void Insert() { for(int i=1;i<=n;++i) { bool flag=true; ll x=a[i],m=0; for(int j=60;j>=0;--j) { if(x&(1LL<<j)) { if(!LB[j]) { LB[j]=x; flag=false; b[j]=m^(1LL<<j); break; } x^=LB[j]; m^=b[j]; } } if(flag) vec.push_back(m); } } int main() { pre[0]=1; for(int i=1;i<=100010;++i) pre[i]=2LL*pre[i-1]%mod; while(~scanf("%d",&n)) { memset(LB,0,sizeof(LB)); vec.clear(); for(int i=1;i<=n;++i) scanf("%lld",a+i); Insert(); ll ans=1ll*pre[(int)vec.size()-1]*((int)vec.size())%mod; for(int i=60;i>=0;--i) { int cnt=0; for(auto v:vec) if(v&(1LL<<i)) ++cnt; if(cnt) ans=(ans+pre[(int)vec.size()-1])%mod; } printf("%lld ",ans); } return 0; }
I Points Division
参考代码：
#include <bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std; const int N = 1e5+7; const double eps = 1e-8; const ll mod = 1e9+7; struct Point{ int x,y; ll a,b; friend bool operator < (Point a,Point b){ if(a.x==b.x) return a.y>b.y; return a.x<b.x; } }; Point p[N]; ll h[N]; struct tree{ int l,r; ll lazy,v; }; tree t[N<<2]; void build(int p,int l,int r) { t[p]=(tree){l,r,0,0}; if(l==r) return ; int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); } void pushdown(int p) { if(t[p].lazy) { t[p<<1].v+=t[p].lazy; t[p<<1|1].v+=t[p].lazy; t[p<<1].lazy+=t[p].lazy; t[p<<1|1].lazy+=t[p].lazy; t[p].lazy=0; } } void update(int p,int pos,ll x) { if(t[p].l==t[p].r&&t[p].l==pos) { t[p].v=max(t[p].v,x); return ; } pushdown(p); int mid=(t[p].l+t[p].r)>>1; if(pos<=mid) update(p<<1,pos,x); else update(p<<1|1,pos,x); t[p].v=max(t[p<<1].v,t[p<<1|1].v); } void update1(int p,int l,int r,ll x) { if(l>r) return ; if(l<=t[p].l&&t[p].r<=r) { t[p].v+=x; t[p].lazy+=x; return ; } pushdown(p); int mid=(t[p].l+t[p].r)>>1; if(l<=mid) update1(p<<1,l,r,x); if(mid<r) update1(p<<1|1,l,r,x); t[p].v=max(t[p<<1].v,t[p<<1|1].v); } ll query(int p,int l,int r) { if(l>r) return 0; if(l<=t[p].l&&t[p].r<=r) return t[p].v; int mid=(t[p].l+t[p].r)>>1; pushdown(p); ll res=0; if(l<=mid) res=max(res,query(p<<1,l,r)); if(mid<r) res=max(res,query(p<<1|1,l,r)); return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; while(cin>>n) { int cnt=0; for(int i=1;i<=n;i++) { cin>>p[i].x>>p[i].y>>p[i].a>>p[i].b; h[++cnt]=p[i].y; } sort(p+1,p+1+n); sort(h+1,h+1+cnt); cnt=unique(h+1,h+1+cnt)-(h+1); for(int i=1;i<=n;i++) p[i].y=lower_bound(h+1,h+1+cnt,p[i].y)-h+1; cnt++; build(1,1,cnt); for(int i=1;i<=n;i++) { ll res=query(1,1,p[i].y); update(1,p[i].y,res+p[i].b); update1(1,p[i].y+1,cnt,p[i].b); update1(1,1,p[i].y-1,p[i].a); } cout<<t[1].v<<endl; } return 0; }
J Freaction Comparision
参考代码：
#include<bits/stdc++.h> using namespace std; long long x,y,a,b; int main() { __int128 sum1,sum2; while(~scanf("%lld%lld%lld%lld",&x,&y,&a,&b)) { sum1=x;sum1*=b; sum2=y;sum2*=a; if(sum1<sum2) puts("<"); else if(sum1>sum2) puts(">"); else puts("="); } return 0; }
其他题目后面慢慢更新~