### 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多分钟，觉得自己没有什么时间写接下来的几题了，虽然至少有一题还是有清晰的思路，还是没有写了，然后后就这样结束了。
总之，感觉还是实力有很多不足吧，希望自己能不断努力学习，还有就是觉得有时自己有点钻牛角尖，导致浪费很多时间。
校赛结束了，准备省赛了，舞台很大，我还是很渺小，加油吧！
