### Contest1068 - 2017“久源软件杯”安徽科技学院第八届程序设计大赛
关于举办“久源软件杯”
安徽科技学院第八届程序设计大赛通知
ACM 国际大学生程序设计竞赛 (International Collegiate Programming Contest)是由美国计算机协会(ACM)主办的一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的著名竞赛。2010年以来,我校参与了历届安徽省 ACM 程序设计竞赛,并取得了优异的成绩。为选拔省ACM 参赛队员,特举办“久源软件杯” 安徽科技学院第八届计算机程序设计大赛,热忱欢迎广大程序设计爱好者踊跃参加。
主办方:安徽科技学院教务处、信息与网络工程学院
承办方:信息与网络工程学院计算机系
赞助方:无锡久源软件股份有限公司(独家赞助)
一、 比赛时间:2017 年 4 月 22(周六)上午 8:00~12:00
二、比赛地点:计算机与网络实验中心(力行楼六楼)
三、参赛对象:14~16 级计算机、网络、信息、电子等专业
四、 报名方式(免费报名参赛):
(1)报名网站: https://oj.ahstu.cc/JudgeOnline/contest_join.php?cid=1068
(2)请加入比赛 QQ 群:391668336(安科ACM官方群)
(3) 报名时间:2017 年 4 月 10日至 4月 21 日
五、比赛设奖:设一等奖8%、二等奖12%、三等奖15%、优秀奖若干
(1)一二三等奖都有丰厚的物质奖励
(2)一二等奖同学直接进入省ACM赛集训
六、竞赛相关:
1. 竞赛语言:C/C++/JAVA环境:DevCpp /CodeBlock /Eclipse
2. 比赛试题:采用 ICPC 样式——赛题 8~10 道
3. 练习与比赛网站(AOJ):https://oj.ahstu.cc/
相关竞赛辅导将随后展开,请关注群通知。
教务处、信息与网络工程学院
2017 年 4月 11 日
Start Time: 2017-04-22 08:00:00 End Time: 2017-04-22 12:00:00
Current Time: 2017-4-22 22:28:34 Status:Ended Public
<div style=”font-family:”Helvetica Neue”,Helvetica,Arial,sans-serif; font-size:14px”>
[Status] [Standing]
[Statistics]
<table id=”problemset” width=”90%” style=”text-align:center; border-collapse:collapse; width:1158px; margin-left:83.7969px; font-family:”Helvetica Neue”,Helvetica,Arial,sans-serif”>
Problem ID
Title
Source
AC
Submit
N
1847 Problem A
A -bits
icpc08th
2
48
Y
1848 Problem B
B-黄金矿工
icpc08th
4
16
1849 Problem C
C-皇后的争斗
icpc08th
3
5
1850 Problem D
D-纸盘游戏
icpc08th
4
48
N
1851 Problem E
E-平均数
icpc08th
2
117
Y
1852 Problem F
F-刹车
icpc08th
99
156
1853 Problem G
G-圆组
icpc08th
2
35
Y
1854 Problem H
H-曲线长度
icpc08th
34
56
Y
1855 Problem I
I-相交点
icpc08th
63
70
Y
1856 Problem J
J-老赵的挑逗
icpc08th
45
159
## 1847: A -bits
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 48 Solved: 2
上一题SubmitStatus标签打分编辑题目信息编辑测试数据下一题
## Description
定义F(n)为n的二进制表示中,“连续两个1出现的次数”例如 F(27)=2(27的二进制位11011)输入整数n(0<=n<=263 -2)求S = F(0)+F(1)+…+F(n)的值
Input
多组输入,每行输入n,当n=-1时结束输入
Output
输出每行输入对应的S值
Sample Input
0615202122-1
Sample Output
Case 1: 0
Case 2: 2
Case 3: 12
Case 4: 13
Case 5: 13
Case 6: 14
这道题一开始感觉挺简单,可是不是这么简单,首先需要用到长整型long long,然后需要考虑时间问题
#include
#include
#include
#include
using namespace std;
long long aa,bb;
void cal(long long n) {
bb += n;
if (bb >= (1000000000000ll)) {
aa += bb / (1000000000000ll);
bb %= (1000000000000ll);
}
}
int main() {
freopen(“a.in”,”r”,stdin);
freopen(“a.out”,”w”,stdout);
int cas = 1;
long long n;
long long a,b,c,m;
while (cin >> n && n >= 0) {
aa = bb = 0;
m = 1, a = n;
for (int i = 0; i < 62; i++) {
cal((n>>2)*m);
if ((n & 3) == 3)
cal((a&((1ll<<i)-1))+1);
m <<= 1;
n >>= 1;
}
printf(“Case %d: “, cas++);
if(aa) {
cout << aa;
printf(“%012lld\n”,bb);
}
else cout<<bb<<endl;
}
return 0;
}
## 1848: B-黄金矿工
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 16 Solved: 4
上一题SubmitStatus标签打分编辑题目信息编辑测试数据下一题
## Description
在上个世纪前,安科的后山曾经是一个黄金矿山(现在无力吐槽)。在山上住着是n个矿工,他们辛苦一年终于到了发年终奖励的时候了,公司的CEO vyoung先生决定将一块黄金发给最有价值矿工,不过这就很让他头痛了,这些矿工每个人都是非常卖力的工作的。无奈,vyoung决定让上帝来决定。他让n课矿工围坐在一起成一个圈,第一次淘汰第m个,以后每数k个数淘汰一个,最后一个留下的将获得这块金块。
Input
输入包含多组数据。每组数据包含三个整数 n,k,m(<=2n<=10000,1<=k<=10000,1<=m<=n)
输入结束标志为n=k=m=0
Output
对于每组数据输出最后被留下来的人
##
##
Sample Input
8 5 3
100 9999 98
10000 10000 10000
0 0 0
Sample Output
1
93
2019
模板题,较为简单
#include
int main()
{
freopen(“a.in”,”r”,stdin);
freopen(“a.out”,”w”,stdout);
int n,m,k,f;
while(scanf(“%d%d%d”,&n,&k,&m)==3&&n)
{
f=0;
for(int i=2;i<=n;i++)f=(f+k)%i;
f=(m-k+1+f)%n;
if(f<=0)f+=n;
printf(“%d\n”,f);
}
}
## 1849: C-皇后的争斗
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 5 Solved: 3
上一题SubmitStatus标签打分编辑题目信息编辑测试数据下一题
## Description
在国际象棋中,两个皇后相互攻击只会是在同一行,同一列,或者同一对角线上。现在给出一个nxm的棋盘,问有多少种方法放置两个相互攻击的皇后
Input
多组输入,每组输入包含两个整数n,m(0<=n,m<=106)输入结束的标志为n=m=0
Output
对于每组输入,输出对应的方案数
Sample Input
100 223
Sample Output
10907100
这道题还是不是很理解,不过下面一个代码就一个公式就解决了,挺郁闷的
#include
#include
#include
using namespace std;
int main()
{ freopen(“a.in”,”r”,stdin);
freopen(“a.out”,”w”,stdout);
unsigned long long n,m;
while(cin>>n>>m){
if(!n&&!m)break;
if(n>m)swap(n,m);
cout<<nm(m+n-2)+2n(n-1)(3m-n-1)/3<<endl;
}
return 0;
}
1850: D-纸盘游戏
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 48 Solved: 4
## Description
大学英语四级考试就要来临了,你是不是在紧张的复习?也许紧张得连短学期的ACM都没工夫练习了,反正我知道的Kiki和Cici都是如此。当然,作为在考场浸润了十几载的当代大学生,Kiki和Cici更懂得考前的放松,所谓“张弛有道”就是这个意思。这不,Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
“升级”?“双扣”?“红五”?还是“斗地主”?
当然都不是!那多俗啊~
作为计算机学院的学生,Kiki和Cici打牌的时候可没忘记专业,她们打牌的规则是这样的:
1、 总共n张牌;
2、 双方轮流抓牌;
3、 每人每次抓牌的个数只能是2的幂次(即:1,2,4,8,16…)
4、 抓完牌,胜负结果也出来了:最后抓完牌的人为胜者;
假设Kiki和Cici都是足够聪明(其实不用假设,哪有不聪明的学生~),并且每次都是Kiki先抓牌,请问谁能赢呢?
当然,打牌无论谁赢都问题不大,重要的是马上到来的CET-4能有好的状态。
Good luck in CET-4 everybody!
Input
输入数据包含多个测试用例,每个测试用例占一行,包含一个整数n(1<=n<=1000)。
Output
如果Kiki能赢的话,请输出“Kiki”,否则请输出“Cici”,每个实例的输出占一行。
这道题也是,看了代码少的简直难以置信,考察的博弈论。
<span style=”font-family:”Times New Roman””>容易找到规律,最佳策略是通过取1或2张牌,使留给对手的牌数总是3的倍数,这时对手不可能一次取光,而你就可以将除以3的余数部分取光。
<span style=”font-family:”Times New Roman””>这样一来就必然胜利。
<span style=”font-family:”Times New Roman””>
<span style=”font-family:”Times New Roman””>容易找到规律,最佳策略是通过取1或2张牌,使留给对手的牌数总是3的倍数,这时对手不可能一次取光,而你就可以将除以3的余数部分取光。
<span style=”font-family:”Times New Roman””>这样一来就必然胜利。
<span style=”font-family:”Times New Roman””>
#include
#include
using namespace std;
int main(void)
{
freopen(“a.in”,”r”,stdin);
freopen(“a.out”,”w”,stdout);
int n;
while(scanf(“%d”,&n)==1)
{
if(n%3==0)
cout<<”Cici”<<endl;
else
cout<<”Kiki”<<endl;
}
return 0;
}
## 1851: E-平均数
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 117 Solved: 2
上一题SubmitStatus标签打分编辑题目信息编辑测试数据下一题
## Description
给出n个数,每相邻两个数求一次平均数得到n-1个数,在经过n-1次操作后,剩下1个数,求这个数是多少。
Input
多组输入,先输入T,表示有T组测试数据 每行输入一个n(0<=n<=50000),接下来一行输入n个数a[i],(-1000<=a[i]<=1000)
Output
对每组输入输出最后得到的一个数(保留小数点后三位)
Sample Input
4110.421.0 2.231 2 351 2 3 4 5
<span style=”font-family:”Helvetica Neue”,Arial,”Hiragino Sans GB”,STHeiti,SimSun,”WenQuanYi Micro Hei”,”Microsoft YaHei”,sans-serif; font-size:14px; white-space:pre-wrap”>解题思路:类似与杨辉三角,第i个数起始被加了<span class=”mathjax” style=”font-family:”Helvetica Neue”,Arial,”Hiragino Sans GB”,STHeiti,SimSun,”WenQuanYi Micro Hei”,”Microsoft YaHei”,sans-serif; font-size:14px; white-space:pre-wrap; display:inline-block; margin:0px”>C(n−1i−1)<span style=”font-family:”Helvetica Neue”,Arial,”Hiragino Sans GB”,STHeiti,SimSun,”WenQuanYi Micro Hei”,”Microsoft YaHei”,sans-serif; font-size:14px; white-space:pre-wrap”>次。总共有<span class=”mathjax” style=”font-family:”Helvetica Neue”,Arial,”Hiragino Sans GB”,STHeiti,SimSun,”WenQuanYi Micro Hei”,”Microsoft YaHei”,sans-serif; font-size:14px; white-space:pre-wrap; display:inline-block; margin:0px”>2n−1<span style=”font-family:”Helvetica Neue”,Arial,”Hiragino Sans GB”,STHeiti,SimSun,”WenQuanYi Micro Hei”,”Microsoft YaHei”,sans-serif; font-size:14px; white-space:pre-wrap”>个数相加。但是因为n有50000,<span class=”mathjax” style=”font-family:”Helvetica Neue”,Arial,”Hiragino Sans GB”,STHeiti,SimSun,”WenQuanYi Micro Hei”,”Microsoft YaHei”,sans-serif; font-size:14px; white-space:pre-wrap; display:inline-block; margin:0px”>250000<span style=”font-family:”Helvetica Neue”,Arial,”Hiragino Sans GB”,STHeiti,SimSun,”WenQuanYi Micro Hei”,”Microsoft YaHei”,sans-serif; font-size:14px; white-space:pre-wrap”>根本存不下,所以借助log函数。
#include
#include
#include
#include
#include
#include
#include
#include
## 1852: F-刹车
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 156 Solved: 99
上一题SubmitStatus标签打分编辑题目信息编辑测试数据下一题
## Description
汽车一每小时n km的速度行驶,到某处需要减速停车。设汽车以等加速度 a m/s2 刹车。问从开始刹车,到停车,汽车驶过多少距离。
Input
多组输入,每行输入n (0<=n<=400),a(-10<=a<=10)
Output
对于每组输入,输出汽车到停下驶过的距离(单位:米)(小数点后保留三位)
Sample Input
36 -5
简单题
#include
#include
using namespace std;
int main(){
// freopen(“a.in”,”r”,stdin);
// freopen(“a.out”,”w”,stdout);
int a,n;
while(cin>>n>>a){
double v0 = n10001.0/3600;
double t = v01.0/(a-1);
double s = v0t + 0.5att;
printf(“%.3f\n”,s);
}
return 0;
}
## 1853: G-圆组
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 35 Solved: 2
上一题SubmitStatus标签打分编辑题目信息编辑测试数据下一题
## Description
给出n个圆的圆心和半径,相交的圆算在同一组中,如圆1和圆2和圆3相交,则圆1,2,3在同一组中。求总共有几组圆。
Input
多组输入,第一行输入n,表示有n(0<=n<=1000)个圆,接下来n行,每行输入 圆心坐标 x,y,半径r (都是int型)
Output
对每组输入输出总共圆的组数
Sample Input
42 0 10 2 1-2 0 10 -2 1
Sample Output
4
题目较为简单,遍历判断任意两个圆,并查集进行操作即可
#include
#include
#include
#include
#include
#include
using namespace std;
typedef struct round {
int x;
int y;
int r;
};
int n;
const int maxn = 1000+10;
//int mp[maxn][maxn];
int f[maxn];
vectorV;
int findset(int x){
return x==f[x]?x:f[x] = findset(f[x]);
}
void init(){
V.clear();
for(int i=0;i<maxn;i++)
f[i]=i;
for(int i=0;i<n;i++){
int x0,y0,R;
scanf(“%d%d%d”,&x0,&y0,&R);
struct round s;
s.x = x0;
s.y = y0;
s.r = R;
V.push_back(s);
}
}
void Union(int a,int b){
int x = findset(a);
int y = findset(b);
if(x!=y)
f[y]=x;
}
double dis(struct round a,struct round b){
double s = sqrt(1.0(a.x-b.x)(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
return s;
}
bool charge(struct round a,struct round b){
return dis(a,b)<(a.r+b.r);
}
void solve(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(charge(V[i],V[j])&&i!=j){
// cout<<dis(V[i],V[j])<<endl;
Union(i,j);
}
}
}
int s = 0;
for(int i=0;i<n;i++)
if(f[i]==i)s++;
printf(“%d\n”,s);
}
int main(){
freopen(“a.in”,”r”,stdin);
freopen(“a.out”,”w”,stdout);
while(~scanf(“%d”,&n)){
init();
solve();
}
return 0;
}
## 1854: H-曲线长度
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 56 Solved: 34
上一题SubmitStatus标签打分编辑题目信息编辑测试数据下一题
## Description
计算曲线y = x3/2 上相应于ab的一段弧长(-100<a,b<100,a,b均为int)
Input
多组输入,每组包含两个数,a,b
Output
对于每组输入,输出对应区间的弧长,结果小数点后保留三位
Sample Input
1 2
Sample Output
1.578
#include
#include
#include
using namespace std;
int main(){
//freopen(“a.in”,”r”,stdin);
// freopen(“a.out”,”w”,stdout);
int a,b;
while(cin>>a>>b){
// double d = 3.0/2;
double s = 2.0/3(pow((1+b)1.0,1.5)-pow((1+a)*1.0,1.5));
printf(“%.3f\n”,s);
}
return 0;
}
## 1855: I-相交点
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 70 Solved: 63
上一题SubmitStatus标签打分编辑题目信息编辑测试数据下一题
## Description
圆1 圆心坐标(-1,0)半径为1.5,圆2圆心坐标为(2,0)半径为2,求这两个圆的交点坐标,结果保留小数点后三位
Input
Output
顺序输出两个点坐标,输出格式如下
x1 y1
x2 y2
#include
#include
#include
using namespace std;
int main()
{
freopen(“a.out”,”w”,stdout);
int x1 = -1,y1 = 0,r1 = 1.5;
int x2 = 2,y2 = 0, r2 = 2;
double mid = 1.0(x2+x1)/2;
double x = 2 - mid;
double y = sqrt(4-xx1.0);
printf(“%.3f %.3f\n%.3f %.3f\n”,x,y,x,y-1);
return 0;
}
## 1856: J-老赵的挑逗
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 159 Solved: 45
上一题SubmitStatus标签打分编辑题目信息编辑测试数据下一题
## Description
精通数学的老赵现在想难为一下喜爱编程的童鞋们,现在给出一个三角形的三条边a,b,c求出这个三角形的内切圆和外接圆的面积
Input
多组输入,每行包括三个整数数a,b,c
Output
没有每组输入输出对应三角形的内切圆和外界圆面积(结果保留小数点后三位)
Sample Input
3 4 5
Sample Output
3.142 19.635
#include
#include
#include
using namespace std;
double cacu(double r){
double pi = atan(1)4;
return pirr;
}
int main(){
// freopen(“a.in”,”r”,stdin);
// freopen(“a.out”,”w”,stdout);
int a,b,c;
while(cin>>a>>b>>c){
double p = 1.0(a+b+c)/2;
double temp = p(p-a)(p-b)(p-c);
double s = sqrt(temp);
double R = 1.0abc/(4s);
double r = 2s/(a+b+c);
double S1 = cacu(r);
double S2 = cacu(R);
printf(“%.3f %.3f\n”,S1,S2);
}
return 0;
}
附上终榜
属于我参加的最后一届校赛了,简单总结下这次校赛吧,这次校赛考的大部分都是数学题,比赛刚开始时,不知道题目是pdf文档,有点意思,一开始做A题,考的二进制,感觉有思路,于是写,结果老是通不过样例,写的挺着急的,当时好多同学都AC好几题了,有点慌了,再换下一题,一看就是约瑟夫环问题,挺好的,准备的有模板,然后写上去就AC了,C题D题跳过,感觉没什么好的思路,E题平均数,随便写了一下也AC了,接着写F题,写了写也AC了,感觉时间比较充足,不是很慌了,又返回去写A题,终于也AC了。。结果临时说题目全部重判了,重判了,结果全都WA了,全部WA,名次一下掉到了最后。我当时有什么办法呢,我也很绝望啊。算了吧,感觉这次成绩会很差,已经这样了,那慢慢写吧,接着看A题,感觉数据量有点大,似乎有点麻烦,还是看B题吧,于是再写了一遍约瑟夫环问题,因为材料准备充足,找了个纯数学方法写了一遍,然后就AC了,然后F题,真是不知道是什么问题,过了很久,用c++再提交了一遍然后就过了,很是无语啊,不过还好F题最后还是重判了,不过真的也花了点时间找问题。再看I题相交点,因为很多都AC了这题,乍一看感觉很是麻烦啊,没有样例,又过了很久才知道这题就一组数据,输出结果就好了,我却还在找什么输入输出格式。。。然后AC了I题,接着写J,什么内切圆和外接圆面积的问题,怎么这么多数学啊,公式什么的早已经忘了,慢慢推吧,感觉一时半会又推不出。。。内切圆是找材料写好的,最后还是通过余弦定理求出外接圆的半径,于是AC了,然后H题,H题求弧长,是考定积分的,一开始没有怎么写,算了很久然后却积分不出来,最后发现积分里有地方写错了,挺简单的积分被我弄得很复杂,修改了一下,可是还是通不过样例,输出了一串奇怪的串,我相信这次写的不会有问题,可是还是不对,时间就快要结束了,不会我这道题也写不出来吧,,最后发现程序中一个变量用了两次,似乎值已经改变了,其实很早就发现了,可是我就是觉得那样也是不会有问题的,最后还是AC了,这道题。还剩10多分钟,觉得自己没有什么时间写接下来的几题了,虽然至少有一题还是有清晰的思路,还是没有写了,然后后就这样结束了。
总之,感觉还是实力有很多不足吧,希望自己能不断努力学习,还有就是觉得有时自己有点钻牛角尖,导致浪费很多时间。
校赛结束了,准备省赛了,舞台很大,我还是很渺小,加油吧!