首页 > 代码库 > IFROG线上赛做过的题目
IFROG线上赛做过的题目
#6
1068:
找规律
int main(){ int t,n; cin>>t; while(t--){ cin>>n; if(n%3==0)printf("%d\n",n/3); else printf("%d\n",n); }}
1069
二维树状数组
int bit[1234][1234],n;int cha(int x1,int y1,int d){ for(int a=x1;a<=n+1;a+=(a&-a)) for(int b=y1;b<=n+1;b+=(b&-b))bit[a][b]+=d;} int sum(int x,int y){ int ans=0; for(int a=x;a>=1;a-=(a&-a)) for(int b=y;b>=1;b-=(b&-b))ans+=bit[a][b]; return ans; }void solve(){memset(bit,0,sizeof(bit)); n=gi;int q=gi; for(int i=1;i<=q;i++){ char s[3]; scanf("%s",s); if(s[0]==‘Q‘){ int x,y; x=gi;y=gi; printf("%d\n",sum(x,y)); } if(s[0]==‘C‘){ int x1,y1,x2,y2; x1=gi;y1=gi;x2=gi;y2=gi; cha(x2+1,y2+1,1);//puts("!"); cha(x1,y1,1);//puts("!"); cha(x1,y2+1,-1);//puts("!"); cha(x2+1,y1,-1);//puts("!"); } }}int main(){ int t=gi; while(t--){ solve(); if(t)puts(""); }}
#7
1071
观察之后发现在前缀和意义下一次操作只会变换前缀和的顺序,不会产生或改变值出现的次数
int main(){ int t=gi; while(t--){ n=gi; s1[0]=s2[0]=0; for(int i=1;i<=n;i++)a[i]=gi,s1[i]=s1[i-1]+a[i]; for(int i=1;i<=n;i++)b[i]=gi,s2[i]=s2[i-1]+b[i]; sort(s1+1,s1+n+1); sort(s2+1,s2+n+1); string ans="Yes"; for(int i=1;i<=n;i++){ if(s1[i]!=s2[i]){ ans="No";break; } } cout<<ans<<endl; }}
1072
拿一个set一个vector暴力删除子树,由于出现过的结点最多n个,set操作不会超过n次,所以暴力删除
int t,cnt,dep[123456];set<pair<int,int> >s;vector<int>son[123456];void dfs(int x){ for(int i=0;i<son[x].size();i++){ s.erase((make_pair(-dep[son[x][i]],son[x][i]))); dfs(son[x][i]); } son[x].clear();}int main(){ t=gi;int n=0; while(t--){ for(int i=1;i<=n;i++)son[i].clear(); n=gi; memset(dep,0,sizeof(dep)); cnt=1; s.clear(); s.insert(make_pair(-dep[1],1)); for(int i=1;i<=n;i++){ char ch=getchar(); int x=gi; if(ch==‘+‘){ ++cnt; if(s.find(make_pair(-dep[x],x))!=s.end()){ dep[cnt]=dep[x]+1; son[x].push_back(cnt); s.insert(make_pair(-dep[cnt],cnt)); } }else{ dfs(x); s.erase(make_pair(-dep[x],x)); } cout<<s.begin()->second<<"\n"; } } return 0;}
1073
。。
int n,T,a[123456];int ans[123456],_;int main(){ T=gi; while(T--){ int n=gi; map<int,int>m; for(int i=1;i<=n;i++)a[i]=gi,m[a[i]]++; bool flag=1; _=0; for(map<int,int>::iterator it=m.begin();it!=m.end();*it++){ if(it->second>1)flag=0,ans[++_]=it->first; } if(flag)puts("none");else{ for(int i=1;i<_;i++)printf("%d ",ans[i]); printf("%d",ans[_]); puts(""); } }}
1074
能量项链。
int n,e[1234];int f[1234][1234];int main(){ int T=gi; while(T--){ n=gi; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++)e[i]=gi; e[0]=e[n+1]=1; for(int j=2;j<=n+1;j++) for(int i=j-1;i>=0;i--) for(int k=i;k<j;k++) f[i][j]=max(f[i][k]+f[k+1][j]+e[i]*e[k+1]*e[j+1],f[i][j]); cout<<f[0][n]<<endl; }}
IFROG线上赛做过的题目
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。