2016-11-09试题解题报告
By shenben
本解题报告解析均为100分解题思路。
T1
模拟即可。
我怕极限数据5000(n,m)*100000(k)。
如果用二维数组。空间勉强撑住，时间上够呛。
因此用2个一位数组分别代表行和列。
这样每次修改是O(1)的。
查询是O（nm）(只查询一次)
总时间复杂度：O(nmk)
T2
搜索
一开始想偏了。
倒着由“a”往前推。结果小样例过了，大样例差太多。
于是另辟蹊径。
观察到数据范围很小。
直接枚举答案序列不就好了。
对于每个序列再判断一下是否可以通过某种脱水缩合过程，最终使序列变成“a”
若可以，则该答案序列为合法答案；否则，不是。
然后对合法答案记一下数，就好了。
时间复杂度：6的排列，也就30-50W的样子。加上检验的话……
O(<100W)
T3
线段树
一开始也想到了线段树，可是不知道怎么维护。
果断暴力……25分
对于一个式子,以他为例
f2[f[1]]=k2(k1+b1)+b2=(k1*k2)+(k2*b1+b2)
这样，对于线段树的维护一目俩然。
首先，叶子节点一定是 ki,bi（废话）
然后，他的父亲节点 k=k1*k2,b=k2*b1+b2;
最后用套线段树模板（连懒惰标记都不用写）就好了。
时间复杂度：O(nlogn+mlogn)
T1代码（100分）：
#include<cstdio> #include<iostream> using namespace std; inline const int read(){ register int x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } const int N=1e5+10; int n,m,k,xx[N],yy[N]; #define name "word" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); n=read();m=read();k=read(); for(int i=1,opt,pos;i<=k;i++){ opt=read();pos=read(); if(opt==1){ xx[pos]=i; } else{ yy[pos]=i; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ printf("%d ",max(xx[i],yy[j])); } printf(" "); } fclose(stdin); fclose(stdout); return 0; }
T2代码（100分）：
#include<cstdio> #include<iostream> using namespace std; const int N=41; char q[N],a[N],b[N],c[N]; bool flag; int n,m,ans; void DFS(int x){ if(flag) return ; if(x==n&&q[x]=='a'){ flag=1; return ; } for(int i=1;i<=m;i++){ if(q[x]==a[i]&&q[x+1]==b[i]){ q[x+1]=c[i]; DFS(x+1); q[x+1]=b[i]; } } } void check(){ flag=0; DFS(1); if(flag) ans++; } void dfs(int x){ if(x>n){ check(); return ; } for(int i=0;i<6;i++){ q[x]=char(i+'a'); dfs(x+1); } } #define name "merge" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); cin>>n>>m; for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>c[i]; dfs(1); printf("%d",ans); fclose(stdin); fclose(stdout); return 0; } /*想复杂了 #include<cstdio> #include<cstdlib> #include<vector> #include<string> #include<algorithm> #include<iostream> #include<map> using namespace std; int ans; int n,m; map<string,char>ys; map<string,bool>check; void dfs(int len,string s){ if(len==n){ if(!check.count(s)){ check[s]=1; ans++; cout<<s<<endl; } return ; } string s1; char s2[4]; int l1=s.length(); for(char tl,tr,j='a';j<='f';j++){ if(l1==1){ tl=s1[0]; for(int k=0;k<=l1;k++){ s1=s; s1.insert(k,1,j); s2[0]=s1[0]; s2[1]=s1[1]; s2[2]=' '; if(!ys.count(s2)) continue; if(ys[s2]!=tl) continue; dfs(len+1,s1); } } else{ for(int k=0;k<l1;k++){ s1=s; tl=s1[k]; if(k<l1-1)tr=s1[k+1]; s1.insert(k,1,j); s2[0]=s1[0]; s2[1]=s1[1]; s2[2]=' '; if(!ys.count(s2)) continue; if(k==0){ if(ys[s2]!=tl) continue; } else if(ys[s2]!=tl&&ys[s2]!=tr) continue; dfs(len+1,s1); } s1=s; tr=s1[l1-1]; s1.insert(l1,1,j); s2[0]=s1[0]; s2[1]=s1[1]; s2[2]=' '; if(!ys.count(s2)) continue; if(ys[s2]!=tr) continue; dfs(len+1,s1); } } } char c; int main(){ //freopen("sh.txt","r",stdin); string s1,s2; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ cin>>s1>>c; ys[s1]=c; } dfs(1,"a"); printf("%d",ans); return 0; } */
T3代码（100分）：
#include<cstdio> #define ll long long #define lc k<<1 #define rc k<<1|1 using namespace std; inline const ll read(){ register ll x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } inline const char in(){ for(register char ch=getchar();;ch=getchar()) if(ch>='A'&&ch<='Z') return ch; } const int N=2e5+10; const int M=N<<2; const ll mod=1e9+7; ll n,m,K[M],B[M]; void insert(int k,int l,int r,int pos,int vk,int vb){ if(l==r){ K[k]=vk; B[k]=vb; return ; } int mid=l+r>>1; if(pos<=mid) insert(lc,l,mid,pos,vk,vb); else insert(rc,mid+1,r,pos,vk,vb); K[k]=K[lc]*K[rc]%mod;B[k]=(K[rc]*B[lc]%mod+B[rc])%mod; } ll queryk(int k,int l,int r,int x,int y){ if(x==l&&y==r) return K[k]; int mid=l+r>>1; if(y<=mid) return queryk(lc,l,mid,x,y); else if(x>mid) return queryk(rc,mid+1,r,x,y); else{ ll k1,k2; k1=queryk(lc,l,mid,x,mid); k2=queryk(rc,mid+1,r,mid+1,y); return (k1*k2%mod); } } ll queryb(int k,int l,int r,int x,int y){ if(x==l&&y==r) return B[k]; int mid=l+r>>1; if(y<=mid) return queryb(lc,l,mid,x,y); else if(x>mid) return queryb(rc,mid+1,r,x,y); else{ ll k2,b1,b2; k2=queryk(rc,mid+1,r,mid+1,y); b1=queryb(lc,l,mid,x,mid); b2=queryb(rc,mid+1,r,mid+1,y); return (k2*b1%mod+b2)%mod; } } char c; int main(){ freopen("fx.in","r",stdin); freopen("fx.out","w",stdout); n=read();m=read(); for(ll i=1,x,y;i<=n;i++){ x=read();y=read(); insert(1,1,n,i,x,y); } for(ll i=1,x,y,z,k1,b1;i<=m;i++){ c=in();x=read();y=read();z=read(); if(c=='Q'){ k1=queryk(1,1,n,x,y); b1=queryb(1,1,n,x,y); printf("%I64d ",(k1*z%mod+b1)%mod); } else{ insert(1,1,n,x,y,z); } } fclose(stdin); fclose(stdout); return 0; } /*暴力25分存档 #include<cstdio> #include<algorithm> #define ll long long using namespace std; inline const ll read(){ register ll x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } inline const char in(){ for(register char ch=getchar();;ch=getchar()) if(ch>='A'&&ch<='Z') return ch; } const ll N=1e5+10; const ll mod=1e9+7; ll n,m,K[N],B[N]; char c; int main(){ freopen("fx.in","r",stdin); freopen("fx.out","w",stdout); n=read();m=read(); for(ll i=1;i<=n;i++) K[i]=read(),B[i]=read(); for(ll i=1,tx,x,y,z;i<=m;i++){ c=in();x=read();y=read();z=read(); if(c=='Q'){ tx=(K[x]*z+B[x])%mod; for(ll j=x+1;j<=y;j++){ tx=(K[j]*tx+B[j])%mod; } printf("%I64d ",tx); } else{ K[x]=y;B[x]=z; } } fclose(stdin); fclose(stdout); return 0; } */
