solved 4
rank 1
题挺好的，就是没见过这么卡常的。。
A(签到)
题意：有n个盒子，每个盒子里都有若干AB两种糖，甲只能吃A，乙只能吃B，每次至少吃一个，最多把一个盒子里的吃光，没有糖之后就不能吃，吃掉最后一颗糖的获胜，问谁能获胜。
显然一次吃一颗最优，谁的糖多谁赢。
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=1;i<=n;i++) #define LL long long #define pii pair<int,int> #define pb push_back #define mp make_pair const int N =2e3+7; const int mod=1e9+7; int n,k; int main(){ int t,x; cin>>t; while(t--){ cin>>n; int s1=0,s2=0; rep(i,n){ cin>>x; s1+=x; } rep(i,n){ cin>>x; s2+=x; } if(s1>s2)cout<<"BaoBao"<<endl; else cout<<"DreamGrid"<<endl; } //system("pause"); }
00：05（2A）
E(线段树)
题意：询问数列一段区间的乘积，支持区间乘法和区间乘方。
比较裸的线段树，对两种操作打两个tag分别维护，由费马小定理推论: p是质数时，a^(n%(p-1))=a^n(%p)。对指数取模(p-1)即可。
（函数不加inline还T，我写的常数这么大吗。。）
#include<bits/stdc++.h> using namespace std; #define LL long long #define rep(i,n) for(int i=1;i<=n;i++) const int N=1e5+7; const int mod=1e9+7; int n,a[N],tree[N*4],tag1[N*4],tag2[N*4],len[N*4]; inline void update(int node){ tree[node]=1LL*tree[node<<1]*tree[node<<1|1]%mod; } inline int po(int x,int y){ int res=1; while(y){ if(y&1)res=1LL*res*x%mod; y>>=1; x=1LL*x*x%mod; } return res; } inline void maketag(int node,int v,int k){ tree[node]=1LL*po(tree[node],k)*po(v,len[node])%mod; tag1[node]=1LL*po(tag1[node],k)*v%mod; tag2[node]=1LL*tag2[node]*k%(mod-1); } inline void push_down(int node){ maketag(node<<1,tag1[node],tag2[node]); maketag(node<<1|1,tag1[node],tag2[node]); tag1[node]=tag2[node]=1; } inline int query(int node,int L,int R,int l,int r){ if(l>R||r<L)return 1; if(L>=l&&R<=r)return tree[node]; push_down(node); int mid=(L+R)>>1; return 1LL*query(node<<1,L,mid,l,r)*query(node<<1|1,mid+1,R,l,r)%mod; } inline void change(int node,int L,int R,int l,int r,int v,int k){ if(l>R||r<L)return; if(L>=l&&R<=r){ maketag(node,v,k); return ; } if(tag1[node]!=1||tag2[node]!=1)push_down(node); int mid=(L+R)>>1; change(node<<1,L,mid,l,r,v,k); change(node<<1|1,mid+1,R,l,r,v,k); update(node); } void build(int node,int l,int r){ tag1[node]=tag2[node]=1; len[node]=r-l+1; if(l==r){ tree[node]=a[l]; return; } int mid=(l+r)>>1; build(node<<1,l,mid); build(node<<1|1,mid+1,r); update(node); } int main() { int t,q; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&q); rep(i,n)scanf("%d",&a[i]); build(1,1,n); while(q--){ int op,l,r,v; scanf("%d%d%d",&op,&l,&r); if(op==1){ scanf("%d",&v); change(1,1,n,l,r,v,1); } if(op==2){ scanf("%d",&v); change(1,1,n,l,r,1,v); } if(op==3){ printf("%d ",query(1,1,n,l,r)); } } } //system("pause"); }
02：07（3A）
F(模拟）
题意：给出一个多项式做分子和分母的分式，求分式趋近于x0的极限
洛必达法则，一直求导到分子和分母不都为0即可。麻烦的其实只是读入。。注意输出格式。
#include<bits/stdc++.h> using namespace std; #define LL long long #define rep(i,n) for(int i=1;i<=n;i++) const int N=1e5+7; const int mod=1e9+7; int num[2][10],x; LL gcd(LL a,LL b){ if(!b)return a; return gcd(b,a%b); } void getit(string s,int k){ int res=1,ex=-1; for(int i=0;i<s.size();i++){ if(s[i]=='x'){ ex=1; } else if(s[i]=='^'){ ex=s[i+1]-'0'; i++; } else if(s[i]=='-'){ if(ex!=-1){ num[k][ex]=res; res=1; ex=-1;} res=-1; } else if(s[i]>='0'&&s[i]<='9')res*=s[i]-'0',ex=0; else { num[k][ex]=res; res=1; ex=-1; } } if(ex!=-1){ num[k][ex]=res; res=1; ex=0; } // for(int i=0;i<=9;i++)cout<<num[k][i]<<" "; //cout<<endl; } LL getnum(int k){ LL res=1; LL ans=0; for(int i=0;i<=9;i++){ ans+=res*num[k][i]; res*=x; } return ans; } void change(int k){ for(int i=0;i<9;i++){ num[k][i]=num[k][i+1]*(i+1); num[k][i+1]=0; } //for(int i=0;i<=9;i++)cout<<num[k][i]<<" "; //cout<<endl; } string s1,s2; int main(){ int t; scanf("%d",&t); while(t--){ memset(num,0,sizeof(num)); cin>>s1>>s2>>x; getit(s1,0); getit(s2,1); while(getnum(0)==0&&getnum(1)==0){ change(0); change(1); } if(getnum(1)==0)cout<<"INF"<<endl; else if(getnum(0)==0)cout<<0<<endl; else { LL g=gcd(abs(getnum(0)),abs(getnum(1))); if( (getnum(0)>0)!=(getnum(1)>0) )cout<<"-"; if(abs(getnum(1))/g==1)cout<<abs(getnum(0))/g<<endl; else cout<<abs(getnum(0))/g<<"/"<<abs(getnum(1))/g<<endl; } } }
03：06（2A）
J(暴力)
题意：给出两个序列An,Bn，有多少对等长的子序列Ai-j和Bi-j之间的距离小于等于v，两个子序列的距离定义为 ∑ (|ai-bi|^p) （p<=3）
暴力的做法是n^3枚举两个区间起点和最大长度，考虑优化。以Ai和Bj为起点时，因为距离公式的每一项都非负，显然最大长度至少是以Ai-1和Bj-1为起点是的最大长度减一。因此每次暴力的时候记录下最大长度和这一段的距离，之后就可以再次使用。因为区间右端点是单调递增的，也就是长度最多扩大n次。类似于双指针，可以证明复杂度是O(n^2)的。
（不知道为什么时间卡的这么紧。。1e3还多组数据，改了无数遍才卡着过去了)
#include<bits/stdc++.h> using namespace std; #define LL long long #define rep(i,n) for(int i=1;i<=n;i++) const int N=1005; LL a[N],b[N]; int l[N][N]; LL sum[N][N]; LL n,v,p; inline LL f(int i,int j) { LL res=1,x=abs(a[i]-b[j]); rep(i,p)res*=x; return res; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%lld%lld%lld",&n,&v,&p); rep(i,n)scanf("%lld",&a[i]); rep(i,n) scanf("%lld",&b[i]); LL ans=0; rep(i,n) { rep(j,n) { LL now=sum[i-1][j-1]-f(i-1,j-1); int k; for(k=l[i-1][j-1]-1; i+k<=n&&j+k<=n; k++) { if(now+f(i+k,j+k)<=v) now+=f(i+k,j+k); else break; } sum[i][j]=now; l[i][j]=k; ans+=k; } } printf("%lld ",ans); } return 0; }
01：03（9A）