信息工程大学第五届超越杯程序设计竞赛（同步赛）

本文主要是介绍信息工程大学第五届超越杯程序设计竞赛（同步赛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

赛后补题！！！

M-Monika's game

题意

将数字n进行拆分，求每次拆分之后乘积之和的最大值。

思路

每次都将数字x拆分为1和x-1，则1+2+3+......+n-1=n*(n-1)/2。

代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
using namespace std;
const int N=1e5+9;
int main()
{int t;scanf("%d",&t);long long x;for(int i=1;i<=t;i++) {scanf("%lld",&x);printf("%lld\n",x*(x-1)/2);}return 0;
}

F-不规则的轮回

题意

给定n个数对，每个数对中若 x > y , x = x -y ;若 x < y , y = y - x;求所询问的数对出现的次数。

思路

在进行操作的同时记录每对数对出现的次数。

代码

#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,int> mp;
int main()
{int t;cin>>t;int x,y;for(int i=1;i<=t;i++){cin>>x>>y;while(x!=y){mp[{x,y}]++;if(x>y)x-=y;elsey-=x;}mp[{x,y}]++;} int q;cin>>q;while(q--){cin>>x>>y;cout<<mp[{x,y}]<<endl;}return 0;
}

D-实验室有多少人

题意

给出n个人到达和离开实验室的时间，统计实验室一天最多有多少人。

思路

将n个人到达的时间和离开的时间都进行标记，到达标记为1，离开标记为2，按升序排列，若遇到1则说明实验室人数+1，否则实验室人数-1。

代码

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N=1e6+9;
bool cmp(PII x,PII y)
{if(x.first==y.first) return x.second<y.second;return x.first<y.first; 
}
int main()
{int n;cin>>n;int x,y;vector<PII> a;for(int i=1;i<=n;i++){cin>>x>>y;a.push_back({x,1});a.push_back({y,2});}sort(a.begin(),a.end(),cmp);int ans=0,res=0;for(auto i:a){if(i.second==1) res++;else res--;ans=max(ans,res);}cout<<ans<<endl;return 0;
}

C-财政大臣

题意

以1号城市为树的根，城市之间相连接：

操作1：以u为根结点的子树中每个值都增加x

操作2：以u为根结点的子树中每个值都减少x

思路

每个节点最终的值：根节点的变化+自身的变化+自身的初始值

将每次以u为根结点的变化都记录下来，最终直接相加即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
vector<int>a[N];
int b[N],c[N];
void check(int u,int fa)
{c[u]+=c[fa];int x;for(int i=0;i<a[u].size();i++){x=a[u][i];if(x==fa) continue;check(x,u);}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,q;cin>>n>>q;int x,y;for(int i=1;i<n;i++){cin>>x>>y;a[x].push_back(y);a[y].push_back(x);}for(int i=1;i<=n;i++){cin>>b[i];}int op,u,v;for(int i=1;i<=q;i++){cin>>op>>u>>v;if(op==1){c[u]+=v;}elsec[u]-=v;}check(1,0);for(int i=1;i<=n;i++){cout<<b[i]+c[i]<<" ";}cout<<endl;return 0;	
} 

E-在雾中寻宁静

题意

给定每个子结点的根结点，每次都将以u为根的子树染成v颜色。

思路

记录染色的先后顺序，子节点的颜色为最终其父结点或自身的颜色变化。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
vector<int> a[N];
int b[N];
pair<int,int> c[N];
void check(int x)
{for(int i=0;i<a[x].size();i++){int j=a[x][i];if(c[j].first<c[x].first){c[j]=c[x];	}check(j);}
}
int main()
{int n;scanf("%d",&n);int x;for(int i=1;i<n;i++){scanf("%d",&x);a[x].push_back(i+1);}int q,u,v;scanf("%d",&q);for(int i=1;i<=q;i++){scanf("%d%d",&u,&v);c[u].first=i;c[u].second=v;}check(1);for(int i=1;i<=n;i++)printf("%d ",c[i].second);printf("\n");return 0;
}

G-完美数字

题意

末尾至少有k个0的数为完美数，若子区间内数字的乘积是完美数，则该区间为完美区间，统计完美区间的个数。

思路

末尾有0的数必定含有2和5，统计2和5的个数，若最小个数>=k，则为完美数，完美数所在的区间都为完美区间。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+9;
int a[N],b[N],c[N];
int check(int n,int x)
{int res=0;while(n%x==0){n/=x;res++;}return res;
}
int main()
{int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];b[i]=check(a[i],2);c[i]=check(a[i],5);}for(int i=1;i<=n;i++){b[i]+=b[i-1];c[i]+=c[i-1];}LL ans=0;for(int l=0;l<=n;l++){for(int r=l+1;r<=n;r++){int t2=b[r]-b[l];int t5=c[r]-c[l];int temp=min(t2,t5);if(temp>=k){ans+=n-r+1;break;}}}cout<<ans<<endl;return 0;
}

这篇关于信息工程大学第五届超越杯程序设计竞赛（同步赛）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---