首页 > 代码库 > 20161109模拟赛解题报告
20161109模拟赛解题报告
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("\n"); } 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]=‘\0‘; 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]=‘\0‘; 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]=‘\0‘; 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|1using 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\n",(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 longusing 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\n",tx); } else{ K[x]=y;B[x]=z; } } fclose(stdin); fclose(stdout); return 0;}*/
20161109模拟赛解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。