第九届河南理工大学算法程序设计大赛 正式赛 部分题解
A. Asia区域赛 单测试点时限: 1.0 秒
内存限制: 512 MB
2018年11月24日至25日，由我校承办的第43届ACM国际大学生程序设计竞赛亚洲区域赛（焦作站）在学校体育馆举行。来自清华大学、北京大学、香港中文大学、蒙古国立大学等国内外186所高校以及3所中学和1家企业的298支参赛队伍共计894名计算机算法设计精英及226名教练参加比赛。 24日下午，大赛在雄壮的国歌声中拉开帷幕。大赛亚洲区域主席黄金雄、河南省计算机学会理事长周清雷、校党委副书记安士伟、校教务处副处长原东方、计算机科学与技术学院院长贾宗璞、计蒜客首席布道师钦恩强出席开幕式。全体裁判员、参赛师生、学生志愿者等1400余人参加开幕式。 大赛亚洲区主席黄金雄教授对于焦作站的准备工作给予高度的赞扬，周清雷对此次大赛在我校的举办表示热烈祝贺。安士伟在致辞中简要介绍了学校的办学情况及计算机学院的发展现状，他充分肯定了ACM国际大学生程序设计竞赛对于提高IT创新人才培养水平、促进计算机教育事业和人工智能发展的重要意义。他表示，国际大学生程序设计竞赛亚洲区域赛在我校举办，既是对我校的高度信任，也是我校学习提高的一次难得的机会。他希望参加本届大赛的老师和同学们能够深入交流、增进友谊、互相切磋、共同进步。开幕式结束后，随即开展了历时2个小时的热身赛，参赛选手们在热身赛中熟悉了比赛环境和流程。 25日上午9时，比赛正式开始，经过5个小时的激烈角逐，大赛落下帷幕。本次大赛29支队伍获得金奖、58支队伍获得银奖、87支队伍获得铜奖、11支队伍获得最快解题奖、1支队伍获得最佳女队奖、1支队伍获得顽强拼搏奖。清华大学的“随串鸡”代表队获得第一名，清华大学、中山大学和西安交通大学分别赢得冠军、亚军和季军。副校长赵同谦为获得冠军、亚军和季军的队伍颁奖。 此次大赛由我校承办是该项国际赛事首次进入河南高校，为加强我校对外交流与合作、展示我校办学水平提供了宝贵的机会和平台，对进一步探讨教育教学改革的经验和做法、推进我校计算机类学科建设、培育拔尖创新人才具有重要意义。
输入 本题没有输入要求.
输出 请输出文中表述的发放奖牌个数，并单独占一行.
提示 本题只需按照题目描述，输出一个整数即可(无需纠结比赛规则问题).
语文阅读理解
答案：187
B. Asia区域制 单测试点时限: 1.0 秒
内存限制: 512 MB
二进制数据是用 0 和 1 两个数码来表示的数.它的基数为 2 ，进位规则是“逢二进一”，借位规则是“借一当二”，由18世纪德国数理哲学大师莱布尼兹发现. 十六进制（简写为hex或下标 16 ）在数学中是一种逢 16 进 1 的进位制.一般用数字 0 到 9 和字母 A 到 F（或 a ~ f ）表示，其中: a ~ f 表示 10 ~ 15 ，这些称作十六进制数字. 请将给定的二进制数转为十六进制数，英文字母使用小写形式.
输入 第一行一个正整数 T， 代表有 T 组测试数据. (1≤T≤10). 接下来 T 行，每行输入一串只包含 0 和 1 的字符串（无前导 0），字符串长度：1≤length≤106.
输出 对于每组测试样例，输出转化后的十六进制数并单独占一行.
样例 input 2 1 10 output 1 2
2进制转16进制，先全部输进来，然后从后边4个一个16进制，转换就好
#include
using namespace std;
int n;
char c;
string a;
stack sta;
void solve()
{
int t=1,sum;
int cnt=a.size()-1;
while(cnt>=3)
{
sum=0;
t=1;
for(int i=0;i!=4;i++)
{
sum+=(a[cnt]-'0')*t;
cnt--;
t*=2;
}
if(sum<10)
{
sta.push(sum+'0');
}
else
{
sum-=10;
sta.push(sum+'a');
}
}
t=1;
sum=0;
while(cnt>=0)
{
sum+=(a[cnt]-'0')*t;
cnt--;
t*=2;
}
if(sum>0)
{
if(sum<10)
{
sta.push(sum+'0');
}
else
{
sum-=10;
sta.push(sum+'a');
}
}
}
void out()
{
while(sta.size())
{
cout<<sta.top();
sta.pop();
}
cout<<endl;
}
int main()
{
cin>>n;
cin.get();
for(int i=0;i!=n;i++)
{
cin>>a;
solve();
out();
}
return 0;
}
C. Asia区域宫 单测试点时限: 1.0 秒
内存限制: 512 MB
远古洪荒时期，女王Alice和战神Bob因爱相恋，一段催人泪下的爱情故事流传民间. 相传，女王Alice的美貌惊艳六界，作为对颜值颇有要求的上古灵兽Qaq芳心异动，可是女王早已许配给战神Bob，怎么会移情于己呢，而且单挑自己也不是战神Bob的对手。于是，灵兽Qaq便设计将战神Bob引入洪荒之地，种下十里桃花困住战神Bob。女王Alice得知后，冒着渡劫的天雷赶去营救……实在bian不下去了. 简言之，一个 n×n 的迷宫，Alice站在 (1,1) 位置，Bob被困在 (n,n) 位置，迷宫中会有障碍物，规定障碍物在迷宫中不能同行且不能同列。Alice只能在迷宫中移动且不能跨越障碍物，每次只能移动一个格子且只有上下左右四个方向。 Alice能顺利解救Bob么？若成功解救输出 Yes，并输出最少所用步数.否则输出 No. 如图所示，A 代表Alice，B 代表Bob，# 代表障碍物，箭头代表移动的四个方向：
输入 第一行一个整数 T，代表 T 组测试数据. 对于每一组数据，第一行两个整数 n 和 m，分别表示 n×n 迷宫大小和 m 个障碍物，接下来 m 行，每一行两个整数 x 和 y，表示障碍物坐标 (x,y)。 数据保证障碍物不同行且不同列，且不在位置 (1,1),(n,n)。 (1≤T≤2000，1≤m,n≤10000，1≤x,y≤n)
输出 对于每组测试样例，输出占一行。 若成功解救输出 Yes，并输出最少所用步数.否则输出 No 。
样例 input 2 2 1 1 2 2 2 1 2 2 1 output Yes 2 No
呵呵这题目也是没谁了，就让你看看是不是有一个从左下方到右上方的拦截线，因为不让在同一行同一列放置，所以只要不存在这样的拦截那么答案就是2*n-2
#include
using namespace std;
int T;
int ans,m,n,cnt,sum;
int x,y;
int main()
{
scanf("%d",&T);
for(int t=0;t!=T;t++)
{
cnt=0;
scanf("%d %d",&n,&m);
for(int j=0;j!=m;j++)
{
scanf("%d %d",&x,&y);
if(j==0)
{
sum=x+y;
cnt=1;
}
else
{
if(sum==x+y)
{
cnt++;
}
}
}
if(sum==cnt+1)
{
cout<<"No"<<endl;
}
else
{
cout<<"Yes "<<2*n-2<<endl;
}
}
return 0;
}
D. Asia区域阵 单测试点时限: 1.0 秒
内存限制: 512 MB
一个 n×m 的矩阵，由 A−Z 字符将其填充. 现在我们定义一个异矩阵：
同一行字符都不相同的矩阵。 同一列字符都不相同的矩阵。 求解异矩阵的最大面积。
输入 第一行一个正整数 T， 代表有 T 组测试数据。(1≤T≤10) 每组数据第一行输入正整数 n,m，表示 n 行 m 列的一个矩阵。(1≤n,m≤100)
输出 输出单独占一行，表示最大异矩阵面积.
样例 input 1 2 3 HPU UHP output 6
暴力扫描，没啥好办法
#include
using namespace std;
const int maxn=101;
int n,m;
int ans;
char map1[maxn][maxn];
int T;
int calc(int r,int c)
{
//以这个点为起点二维想右下角扩张，看看最多再符合要求的条件下能扩展多远
int area=1;
int i=r,j=c;
set rs[maxn];
set cs[maxn];
int maxrs[maxn];
int maxcs[maxn];
memset(maxrs,0,sizeof(maxrs));
memset(maxcs,0,sizeof(maxcs));
for(int i=r;i!=n;i++)
{
maxrs[i]=c-1;
}
for(int j=c;j!=m;j++)
{
maxcs[j]=r-1;
}
for(int i=r;i!=n;i++)
{
for(int j=c;j!=m;j++)
{
if(maxrs[i]!=j-1&&maxcs[j]!=i-1)
{
return area;
}
if(maxrs[i]==j-1&&maxcs[j]==i-1)
{
if(rs[i].find(map1[i][j])==rs[i].end()&&cs[j].find(map1[i][j])==cs[j].end())
{
area=max((i-r+1)*(j-c+1),area);
rs[i].insert(map1[i][j]);
cs[j].insert(map1[i][j]);
maxrs[i]=j;
maxcs[j]=i;
}
else
{
break;
}
}
else
{
break;
}
}
}
return area;
}
int main()
{
scanf("%d",&T);
for(int t=0;t!=T;t++)
{
ans=1;
scanf("%d %d",&n,&m);
getchar();
for(int i=0;i!=n;i++)
{
for(int j=0;j!=m;j++)
{
map1[i][j]=getchar();
}
getchar();
}
// for(int i=0;i!=n;i++)
// {
// for(int j=0;j!=m;j++)
// {
// cout<<map1[i][j];
// }
// cout<<endl;
// }
for(int i=0;i!=n;i++)
{
for(int j=0;j!=m;j++)
{
int t = calc(i,j);
ans=max(t,ans);
}
}
cout<<ans<<endl;
}
return 0;
}
E. Mo的游戏 单测试点时限: 1.0 秒
内存限制: 512 MB
Mo翻书看到一种新的连连看游戏：对于一个字符串来说，只有当两个字符相同时候才可以进行相连，得分为字符串的长度减去两个相连字符的距离（如果整个字符串中某一种字符个数为1，那么不能相连故得分为0）。Mo现在在玩这个游戏，但是Mo不知道该选择哪一种字符进行相连，所以请你列出每种字符相连可以获得的最大分数，以此来让Mo进行参考。
输入 一个字符串s （0<strlen(s)<106， s中只包含大小写字符）。
输出 针对s中出现过的字符，每行输出一个整数表示用当前字符进行相连可以获得的最大分数, 按照a−z，A−Z的顺序。具体格式参见样例。
样例 input Aabcaabcb output a:8 b:7 c:5 A:0
本来很简单的题，然而他的数据有的是以’ ’结尾的，有的就没有回车符，直接就是EOF了。。。。 然后就很难受了
#include
using namespace std;
const int maxn=260;
const int inf=0x3f3f3f3f;
int big[maxn];
int small[maxn];
int c;
int cnt=0;
int ba[maxn],sa[maxn];
int main()
{
memset(big,0,sizeof(big));
memset(small,0,sizeof(small));
memset(ba,0x3f,sizeof(ba));
memset(sa,0x3f,sizeof(sa));
c=getchar();
while(c!='
'&&c!=EOF)
{
cnt++;
if(c>='a')
{
int tt=cnt-small[c];
if(tt!=cnt&&sa[c]>tt)
{
sa[c]=tt;
}
small[c]=cnt;
}
else
{
int tt=cnt-big[c];
if(tt!=cnt&&ba[c]>tt)
{
ba[c]=tt;
}
big[c]=cnt;
}
c=getchar();
}
for(int i='a';i<='z';i++)
{
if(small[i])
{
if(sa[i]==inf)sa[i]=cnt;
//cout<<char(i+'a')<<":"<<cnt-sa[i]<<endl;
printf("%c:%d
",i,cnt-sa[i]);
}
}
for(int i='A';i<='Z';i++)
{
if(big[i])
{
if(ba[i]==inf)ba[i]=cnt;
//cout<<char(i+'A')<<":"<<cnt-ba[i]<<endl;
printf("%c:%d
",i,cnt-ba[i]);
}
}
return 0;
}
F. Mo的极限 单测试点时限: 1.0 秒
内存限制: 512 MB
Mo今天遇到了一个极限问题，他不会，故请教你。 给两个多项式 f(x) 和 F(x) , 求 limx→+∞f(x)F(x) . 保证每个多项式中每一项都表示为：kx^y，y 为整数 0≤y≤1000，k 为整数且 |k|≤1000 , F(x)≠0 。
输入 第一行表示 f(x)。 第二行表示 F(x)。
输出 输出 limx→+∞f(x)F(x) 的值。 如果是无穷大输出 oo。 如果是无穷小输出 0。 其余的输出 最简分数。
样例
分情况输出就好
#include
using namespace std;
const int maxn=1001;
int f[2][maxn];
int fzx,fzc,fmx,fmc;
int a,b;
int x,c;
int maxc=0;
int gcd(int a,int b)
{
while(a%b)
{
int t=b;
b=a%b;
a=t;
}
return b;
}
void read(int t)
{
while(cin.peek()!='
')
{
scanf("%dx^%d",&x,&c);
maxc=max(maxc,c);
f[t][c]+=x;
}
x=0;c=-1;
for(int i=0;i<=maxc;i++)
{
if(f[t][i]&&c<i)
{
x=f[t][i];
c=i;
}
}
}
void outf()
{
for(int i=0;i!=2;i++)
{
for(int j=0;j!=10;j++)
{
cout<<j<<" "<<f[i][j]<<endl;
}
}
}
int main()
{
read(0);
fzx=x;fzc=c;
cin.get();
read(1);
fmx=x;fmc=c;
//outf();
// cout<<fzx<<fzc<<endl;
// cout<<fmx<<fmc<<endl;
if(fzx!=0&&fmx==0)
{
cout<<"oo"<<endl;
}
else
if(fzx==0&&fmx!=0)
{
cout<<0<<endl;
}
else
if(fzx==0&&fmx==0)
{
cout<<1<<endl;
}
else
if(fzc>fmc)
{
cout<<"oo"<<endl;
}
else
if(fzc<fmc)
{
cout<<"0"<<endl;
}
else
{
int gc=gcd(fzx,fmx);
// cout<<fzx<<fmx<<endl;
// cout<<gc<<endl;
fzx/=gc;
fmx/=gc;
if(fmx<0)
{
fmx*=-1;
fzx*=-1;
}
if(fmx==1)
{
cout<<fzx<<endl;
}
else
{
cout<<fzx<<"/"<<fmx<<endl;
}
}
return 0;
}
G. Mo的数学 单测试点时限: 1.0 秒
内存限制: 512 MB
Mo偶然间得到一个数学问题，听说你很擅长数学，于是前来虚心请教！ 求区间 [1,n] 中 与 m 互质的数的乘积。
输入 多组输入（不超过100组） 每行两个整数 n 和 m. ( 0<n≤106, 0<m≤109)
输出 每行输出一个答案.(由于答案很大，故请输出对 109+7 取模后的结果)
样例 input 3 2 output 3
先把m的因子找出来，把他所有的因子的倍数全部打上标记，说明这些数和m有公因子 然后遍历1-n找到没被标记的数，这些数就是和m互质的数了
#include
#define ll long long
using namespace std;
const int maxn=1e7+1;
const int mod=1e9+7;
int n,m;
ll ans=1;
vector factor;
bool vis[maxn];
void init()
{
factor.clear();
if(m%2==0)factor.push_back(2);
while(m%2==0)
{
m/=2;
}
for(int i=3;i<=sqrt(m);i+=2)
{
if(m%i==0)
{
factor.push_back(i);
while(m%i==0)m/=i;
}
}
if(m>2)factor.push_back(m);
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
ans=1;
init();
memset(vis,0,sizeof(vis));
vector::iterator it;
for(it = factor.begin();it!=factor.end();it++)
{
int t=1;
int tt=*it*t;
while(tt<=n)
{
vis[tt]=1;
t++;
tt=*it*t;
}
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
ans*=i;
ans%=mod;
}
}
printf("%lld
",ans);
}
return 0;
}
H. Mo的面积 单测试点时限: 1.0 秒
内存限制: 512 MB
Mo的老师给了他两个矩形，让他求两个矩形的面积并。Mo很忙没时间解决这种小case，请你帮他解决。
输入 输入两行，每行四个整数 x,y,x1,y1 。(x,y) 是矩形左下角，(x1,y1) 是矩形的右上角. (0≤x,y,x1,y1≤1000)。
输出 输出一个整数表示二个矩形的面积并。
样例 input 0 1 2 3 1 0 3 2 output 7
一个巧妙的解法，一个菜鸡的解法，如下：
#include
using namespace std;
int a[10];
int main()
{
int l,r,u,d;
for(int i=1;i<=8;i++){
scanf("%d",&a[i]);
}
l=max( min(a[1],a[3]) , min(a[5],a[7]) );
r=min( max(a[1],a[3]) , max(a[5],a[7]) );
d=max( min(a[2],a[4]) , min(a[6],a[8]) );
u=min( max(a[2],a[4]) , max(a[6],a[8]) );
int area1 = 0;
if( r - l > 0 && u - d > 0 )
{
area1=(r-l)*(u-d);
}
area1=(a[3]-a[1])*(a[4]-a[2])+(a[7]-a[5])*(a[8]-a[6])-area1;
cout<<area1<<endl;
return 0;
}
``````
#include
using namespace std;
const int maxn=1010;
int x,y,x2,y2;
int x11,y11,x22,y22;
bool map1[maxn][maxn];
int main()
{
cin>>x>>y>>x2>>y2;
cin>>x11>>y11>>x22>>y22;
memset(map1,0,sizeof(map1));
for(int i=x;i<x2;i++)
{
for(int j=y;j<y2;j++)
{
map1[i][j]=1;
}
}
for(int i=x11;i<x22;i++)
{
for(int j=y11;j<y22;j++)
{
map1[i][j]=1;
}
}
int xxs = min(x,x11);
int xxe = max(x2,x22);
int yys = min(y,y11);
int yye = max(y2,y22);
int ans=0;
for(int i=xxs;i<=xxe;i++)
{
for(int j=yys;j<=yye;j++)
{
if(map1[i][j])
{
//cout<<map1[i][j];
ans++;
}
}
//cout<<endl;
}
cout<<ans<<endl;
return 0;
}
I. 安全距离 单测试点时限: 2.0 秒
内存限制: 512 MB
在一个三维空间中给定一个三角形薄片和一个球形安全区，现在需要求出这个三角形薄片到安全区的最短距离。若三角形薄片上的某点在安全区内，则最短距离为零。
输入 第一行一个整数 n，（ n≤103）。 之后的 n 行，每行 13 个整数 x1 y1 z1 x2 y2 z2 x3 y3 z3 xo yo zo r。 (x1,y1,z1),(x2,y2,z2),(x3,y3,z3) 表示三角形薄片的三个顶点，(xoyozo),r 表示球的球心和半径。 数据保证所有的数均不超过 103 。
输出 输出 n 行，每行一个实数为所求答案，请保留6位小数（四舍五入）。
样例 input 3 0 0 0 0 0 1 0 1 0 2 0 0 1 1 0 5 0 0 1 0 1 0 2 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 output 1.000000 1.121320 0.000000
三维的并不会做。。。
J. 简单递归 单测试点时限: 1.0 秒
内存限制: 512 MB
这是一段 C/C++ 代码，用于计算递推数列 an 的。
const int MOD = (int)1e9 + 7; int a(int n) { if(n < 3) return 1; return ((a(n - 1) > 1)) % MOD; } 现在请根据这段代码输出第 n 项数列的值 an 。
输入 第一行一个整数 T。 之后的 T 行，每行 1 个整数，表示 n 。 0<T≤105, 0<n≤106 。
输出 每一行请输出一个 an 的值。
样例 input 3 1 2 3 output 1 1 2
存一下就好
#include
using namespace std;
int ans[1000001];
const int MOD = (int)1e9 + 7;
int a(int n)
{
if(ans[n]>=0)
{
return ans[n];
}
ans[n]=((a(n - 1) > 1)) % MOD;
return ans[n];
}
int t,k;
int main()
{
memset(ans,-1,sizeof(ans));
ans[0]=ans[1]=ans[2]=1;
scanf("%d",&t);
for(int i=0;i!=t;i++)
{
scanf("%d",&k);
printf("%d
",a(k));
}
return 0;
}
K. 高度期望 单测试点时限: 1.0 秒
内存限制: 512 MB
这里是 22 世纪，有一款神奇的机器，可以使任意一棵树长到任意高度但不超过 1000 cm，但是该机器却只能使用一次。为了提升整片树林的平均树高，使得平均树高大于某个值，请设计提升方案。我们的 Boss 对方案本身不感兴趣，你只需要提供提升后需要的机器数量。
输入 第一行 2 个整数 n, m, 表示有 n 颗树和期望的最小平均树高 m cm。 之后的一行 n 个整数 a1 a2⋯an，表示 n 颗树的高度。 0<n≤105, 0<m≤103, 0<a1 a2⋯an≤103 。
输出 输出提升平均树高所需要的最少机器数量。
样例 input 5 1000 1000 1000 1000 500 1000 output 1
贪心水题
#include
using namespace std;
const int maxn=100001;
int n,m;
int a[maxn];
int sum=0;
int main()
{
scanf("%d %d",&n,&m);
sum=n*m;
for(int i=0;i!=n;i++)
{
scanf("%d",&a[i]);
sum-=a[i];
}
sort(a,a+n);
int ans=0;
int cnt=0;
while(sum>0)
{
ans++;
int d=1000-a[cnt++];
sum-=d;
}
printf("%d
",ans);
return 0;
}
L. 最优规划 单测试点时限: 1.0 秒
内存限制: 512 MB
有很多城市之间已经建立了路径，但是有些城市之间没有路径联通。为了联通所有的城市，现在需要添加一些路径，为了节约，需要满足添加总路径是最短的。
输入 第一行 3 个整数 n, m, s, 分别表示城市的数量、已经存在的路的数量、可修的路的数量。 之后的 m 行，每行 3 个整数 x, y, d，表示点 x 到点 y 有一条长度为 d 的已经存在的路径。 之后的 s 行，每行 3 个整数 x, y, d，表示点 x 到点 y 有一条长度为 d 的可修的路径。 0<n,m,s,d≤105 。
输出 输出一个整数表示需要添加的最短的路径长度。 若果无论如何也无法使得所有的城市联通，输出 Concubines can’t do it. 。
样例 input 5 3 2 1 2 1 1 3 2 1 4 3 2 3 4 2 5 5 output 5
注意答案有可能超int，要用longlong 然后并查集水一下就行
#include
#define ll long long
using namespace std;
const int maxn=100011;
class E
{
public:
int s,e;
ll len;
};
bool operator < (const E a,const E b)
{
return a.len<b.len;
}
E rode[maxn];
ll n,m,s;
ll x,y,len;
int F[maxn];
ll sum=0;
ll ans=0;
set ss;
int find(int a)
{
return a==F[a]?a:F[a]=find(F[a]);
}
void join(int a,int b)
{
int fa=find(a);
int fb=find(b);
F[fa]=fb;
}
void init()
{
for(int i=0;i<=n;i++)
{
F[i]=i;
}
}
void outf()
{
for(int i=1;i<=n;i++)
{
cout<<F[i]<<" ";
}
cout<<endl;
}
int main()
{
scanf("%d %d %d",&n,&m,&s);
init();
for(int i=0;i!=m;i++)
{
scanf("%d %d %d",&x,&y,&len);
join(x,y);
}
for(int i=0;i!=s;i++)
{
scanf("%d %d %d",&x,&y,&len);
rode[i].s=x;
rode[i].e=y;
rode[i].len=len;
}
sort(rode,rode+s);
for(int i=1;i<=n;i++)
{
ss.insert(find(i));
}
sum=ss.size();
//cout<<sum<<endl;
//outf();
for(int i=0;i!=s&&sum>1;i++)
{
int fa=find(rode[i].s);
int fb=find(rode[i].e);
if(fa!=fb)
{
join(fa,fb);
ans+=rode[i].len;
sum--;
}
}
if(sum==1)
{
printf("%lld
",ans);
}
else
{
printf("Concubines can't do it.
");
}
return 0;
}