首页 / 更多教程 / 浙大城市学院第十八届程序设计竞赛
浙大城市学院第十八届程序设计竞赛
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了浙大城市学院第十八届程序设计竞赛，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5223字，纯文字阅读大概需要8分钟。
内容图文
D-LCA On N-ary Tree
题意：
给出一棵 n 叉树，求某两点的最近公共祖先
题解:
如果你知道怎么求一个n叉树的中某个节点它的父节点，就很好做了(fa(x)=(x+n-2)/n)。n=1的情况直接min(x,y)。考虑n=2的情况，最大节点编号是1e9。那么该节点树的高度肯定不会超过30层。至于n>2的更小于30层。所以暴力即可
#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=1e5+5;
vector<int> fun(int x,int n)
{
vector<int>res;
while(x!=1){
int fa=(x+n-1)/n;
if(fa*n>x&&fa!=1)fa--;
res.pb(fa);
x=fa;
}
return res;
}
void print_(vector<int >v)
{
for(auto it:v)cout<<it<<' ';
cout<<'\n';
}
void solve()
{
int t;
cin>>t;
while(t--){
int n,x,y;
cin>>n>>x>>y;
if(n==1){
cout<<min(x,y)<<'\n';
continue;
}
while(x!=y){
if(x<y)swap(x,y);
x=(x+n-2)/n;
}
cout<<x<<'\n';
}
}
int main() {
solve();
return 0;
}
F-Palindrome
题意：
给出一个只包含小写字母的字符串，问能否删去两个字符后使其转化为 回文串
思路：
我们可以算出来该串的最大回文子序列长度，然后和原串长度相减，只要<=2，即可满足条件（差=0，max(len)不管是奇或者偶他都可以删去两个满足条件，同理1也满足）
#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=2e3+5;
int f[N][N];
char a[N];
void solve()
{
int t;
cin>>t;
while(t--){
int n;
scanf("%d",&n);
getchar();
for(int i=1;i<=n;i++)scanf("%c",&a[i]);
for(int i=n;i>=1;i--){
f[i][i]=1;
for(int j=i+1;j<=n;j++){
if(a[i]==a[j])f[i][j]=f[i+1][j-1]+2;
else f[i][j]=max(f[i+1][j],f[i][j-1]);
}
}
if(n-f[1][n]<=2)puts("Yes");
else puts("No");
// printf("%d\n",f[1][n]);
// int ans=n-res;
// if(ans<=2)puts("Yes");
// else puts("No");
// puts("\n");
}
}
int main() {
solve();
return 0;
}
G-Permutation
题意：
给出两个排列 a 和 b 操作一：删去 a 的 1 个头部整数并在尾部添加 1 个任意整数 操作二：修改 1 个 ai 为任意整数 问最少多少次操作能使 a， b 相同
思路：（来自官方）
易知操作一二的先后顺序没有影响，所以我们不妨假设先进行操作 一，再进行操作二 假设我们操作一进行了 k 次，那么问题就变成：在 a 的后缀 a[1 + k, n] 和 b 的前缀 b[1, n ? k] 中，有多少个位置（相对位置，即 a1+k 对应 b1）上的数不同，即接下来操作二需要进行的次数。枚 举 k，问题就变成：我们需要求出所有等长的 a 后缀与 b 前缀相对 位置上不同的个数。
注意到 a，b 均为排列，我们假设 ai = bj = x，当且仅当两者的相 对位置相同，即 i ? (1 + k) = j ? 1 时，才能让我们少进行一次操 作二。因此对于排列中每个数均计算一次即可
#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=1e6+5;
int a[N],b[N],cot[N],pos[N];
void solve()
{
int t;
cin>>t;
while(t--){
}
}
int main() {
// solve();
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];pos[a[i]]=i;
}
for(int i=1;i<=n;i++){
cin>>b[i];
if(pos[b[i]]>=i)cot[pos[b[i]]-i]++;
}
int res=0x3f3f3f3f;
for(int i=0;i<=n;i++){
res=min(res,n-cot[i]);
}
cout<<res<<'\n';
return 0;
}
J-K-clearing
题意：
给出一个数组长度为 n 的数组，要求当数组中存在等于 k 的整数时，所 有数字减一，直到不存在 k 时输出该数组
题解：
如果数组中有从k开始连续的一段，那么整个数组所减去的就是该连续一段的长度（去掉重复的）。所以做法就是求该连续数组的长度。排序之后求一下即可。
#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=1e6+5;
struct node{
int id,val;
}a[N];
bool cmp(node a,node b)
{
if(a.val==b.val){
return a.id<b.id;
}else return a.val<b.val;
}
bool cmp2(node a,node b)
{
return a.id<b.id;
}
void solve()
{
int t;
cin>>t;
while(t--){
}
}
int main() {
// solve();
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].val);a[i].id=i;
}
sort(a+1,a+n+1,cmp);
int sum=0;
for(int i=1;i<=n;i++){
if(a[i].val-sum==k){
sum++;
}
}
for(int i=1;i<=n;i++)a[i].val=max(0,a[i].val-sum);
sort(a+1,a+n+1,cmp2);
for(int i=1;i<=n;i++)cout<<a[i].val<<' ';
cout<<"\n";
return 0;
}
/*
6 2
2 3 5 1 6 2
*/
另一种就是看题解思路来写的。（严格求连续长度）
#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=1e6+5;
struct node{
int id,val;
}a[N];
bool cmp(node a,node b)
{
if(a.val==b.val){
return a.id<b.id;
}else return a.val<b.val;
}
bool cmp2(node a,node b)
{
return a.id<b.id;
}
void solve()
{
int t;
cin>>t;
while(t--){
}
}
int main() {
// solve();
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].val);a[i].id=i;
}
sort(a+1,a+n+1,cmp);
int sum=0,flag=0;
for(int i=1;i<=n;i++){
if(a[i].val==k+sum){
sum++;flag=1;
}
else if(a[i].val==a[i-1].val)continue;
else if(flag)break ;
}
for(int i=1;i<=n;i++)a[i].val=max(0,a[i].val-sum);
sort(a+1,a+n+1,cmp2);
for(int i=1;i<=n;i++)cout<<a[i].val<<' ';
cout<<"\n";
return 0;
}
/*
6 2
2 3 5 1 6 2
*/
L-Polygon
题意：
判断 n 条边能否构成一个非退化（面积为正）的 n 边形。
思路：
只需要判断第 2 ? n 大的之和边是否大于最大边长即可
百度了一波才知道…
#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[105],sum[105];
void solve()
{
int t;
// cin>>t;
// while(t--){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
bool flag=true;
for(int i=1;i<=n;i++){
sum[i]=a[i-1]+sum[i-1];
if(i>=2){
if(sum[i]<=a[i]){
flag=false;break;
}
}
}
if(flag)cout<<"Yes";
else cout<<"No";
cout<<'\n';
// }
}
int main() {
solve();
return 0;
}
内容总结
以上是互联网集市为您收集整理的浙大城市学院第十八届程序设计竞赛全部内容，希望文章能够帮你解决浙大城市学院第十八届程序设计竞赛所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。