首页 > 代码库 > 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线上赛做过的题目