第二届中国计量大学ACM程序设计竞赛个人赛（同步赛）
A - Little Gyro and Sort
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Little Gyro has just found an integer sequence a_1,a_2,…,a_na
in his right pocket. As Little Gyro is bored, he decides to sort the sequence.
Now given an integer sequence, and its size is no more than 10^6 , please sort it within the ascending order.
输入描述:
There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 10^6 ), indicating the length of the sequence.
The second line contains n integers a_1,a_2,…,a_na (1 ≤ a_i ≤ 10^4 ), indicating the given sequence.
It’s guaranteed that the sum of n of all test cases will not exceed 10^71 .
输出描述:
For each test case output the sequence after sorting.
Note: Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!
示例1
输入
2
5
1 4 8 3 7
6
10000 9999 9998 9997 9996 9995
输出
1 3 4 7 8
9995 9996 9997 9998 9999 10000
说明
This problem has huge input data, use scanf instead of cin to read data to avoid time limit exceed.
大声BB
大骗子（我之前写的桶排序怎么就没过呢我想不通！！！！！
幸好我重新又打了一遍……
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int temp[100005]={0};
void f(int n) {
}
int main ()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i = 0;i < 100005; i++) temp[i]=0;
for(int i=0;i<n;i++)
{
int ttt;
scanf("%d",&ttt);
temp[ttt]++;
}
int flag=0;
for (int i = 0; i < 100005; i++) {
if(temp[i]==0) continue;
else
{
for(int j=0;j<temp[i];j++)
{
if(flag==0)
{
flag=1;
printf("%d",i);
}
else printf(" %d",i);
}
}
}
printf("\n");
}
return 0;
}
B - Little Gyro and Sets
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Little Gyro has just found an empty integer set A in his right pocket, and an empty integer set B in his left pocket. At the same time, Little Gyro has already thought about two integers n, m in his mind. As Little Gyro is bored, he decides to play with these two sets.
Then, Little Gyro is ready to divide the integer series {1, 2, 3… m-1, m}1,2,3…m−1,m to these two empty sets. With the following rules:
- If the number is an integer multiple of n, Little Gyro will put it in set A.
- Otherwise, Little Gyro will put it in set B instead.
Now given two integers n, m, after these operations, Little Gyro wants to know the result of sum(B)-sum(A) and ask you for help, please help him to calculate.
输入描述:
There are multiple test cases. The first line of the input contains an integer T (1 ≤ T ≤ 10^5 ), indicating the number of test cases. For each test case:
Each line contains two integers n, m (1 ≤ n, m ≤ 10^9 ), indicating the length of the sequence.
输出描述:
For each test case output an integer indicating the result of sum(B)-sum(A).
示例1
复制
3
3 5
2 10
3 16
输出
9
-5
46
说明
For the first sample, after these operations, A = < 3 >, B = < 1, 2, 4, 5 >, and the answer is 9.
For the second sample, after these operations, A = < 2, 4, 6, 8, 10 >, B = < 1, 3, 5, 7, 9 >, and the answer is -5.
大声BB
我想着吧这个题我好像是忘记输入m了当时
一顿操作猛如虎，样例没过满脸懵
幸好发现挺早的（氦//心虚//
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
long long s1(long long n)
{
long long ans=(n+1)*n/2;
return ans;
}
int main()
{
int t;
scanf("%d",&t);
long long n,m;
while(t--)
{
scanf("%lld %lld",&n,&m);
long long t = m/n,sum=s1(m);
t = t*n;
long long xs=(t-n)/n+1;
long long sa=xs*(xs-1)/2*n + xs*n;
long long sb = sum-sa;
long long res = sb-sa;
// cout<<sum<<" "<<sb<<" "<<sa<<endl;
printf("%lld\n",res);
}
return 0;
}
I - Logs Stacking
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Daxinganling produces a lot of timber. Before loading onto trains, the timber jacks will place the logs to some place within no more than two logs’ height first. Looking from the sideway, the figure of a logs stack is as follows:
We have known that the number of logs in each layer is fewer than the lower layer for at least one log, and that in each layer the logs are connected in a line.
In the figure above, there are 4 logs in the bottom layer of the stack, and 3 logs in the top layer of the stack. So the picture shows one kind of figures with 7 logs accumulated together.
Now, given the total number of logs, Little Gyro wants to know how many possible figures there may be.
输入描述:
There are multiple test cases. The first line of the input contains an integer T (1 ≤ T ≤ 10^510
5
), indicating the number of test cases. For each test case:
Each line contains one integer n (1 ≤ n ≤ 2×10^910
9
), indicating the total number of logs.
输出描述:
For each test case in the input, you should output the corresponding number of possible figures.
Because the number may be very large, just output the number mod 10000.
示例1
输入
5
1
3
5
7
2000000000
输出
1
2
5
13
3125
说明
In the third sample, you can accumulate 5 logs within such following ways:
First, you can put all the 5 logs at the ground floor.
Then, you can put 4 logs at the bottom layer, and there are 3 positions for the last log to pile up.
After that, you can also put 3 logs at the bottom layer, while the other 2 logs at the top layer.
Above all, you can get 1 + 3 + 1 = 5 figures in order to accumulate 5 logs.
大声BB
（这题，放在比赛时候也是封榜才过的了/厕所回来之后的灵感
话说回来我刚坐下就想到了斐波那契数列……
好巧……
其实我之前不是没想过……
但是……
我的样例……也不是样例就是……我举例，比如输入6的话，难道不是应该有9种方法吗（气死我了这个破图在电脑上搞了 好久 ……我才想起来我可以手画的呀55555）
所以我就很纠结……
然后我想着……
反正时间也快到了……
要不试一下？？？
然后我就试了……
然后就成功了……
在线疑惑？？？
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int md = 10000;
typedef long long ll;
int a[15005]={0};
void fin()
{
a[1]=1;
a[2]=1;
for(int i=3;i<15000;i++)
a[i]=(a[i-1]+a[i-2]) %md;
}
int main()
{
int t;
long long n;
scanf("%d",&t);
fin();
while(t--)
{
scanf("%lld",&n);
long long ans=0;
printf("%d\n",a[n%15000]);
}
return 0;
}
L - Story of Eden
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Recently, Little Gyro had read a fantastic story of Eden. It’s about a meaningful dialog by Love and Others.
Two loved people created an Eden on Earth and opened the door to heaven.
Experience said: “This is impossible.”
Love replied to Experience, “Nothing is good or bad, and the interpretation is in people.”（事无好坏，诠释在人）
Proud said to Love quite proudly: “It’s ridiculous.”
Love replied to Proud, “Nothing is good or bad, and the interpretation is in people.”
Cautious whispered: “This is too risky.”
Love replied to Cautious, “Nothing is good or bad, and the interpretation is in people.”
Reason told Love very strictly: “This is not reasonable.”
Love replied to Reason, “Nothing is good or bad, and the interpretation is in people.”
Superstition said with bad fortune: “It’ll bring bad luck.”
Love replied to Superstition, “Nothing is good or bad, and the interpretation is in people.”
Vision silently said that: “It’s hopeless.”
Love replied to Vision, “Nothing is good or bad, and the interpretation is in people.”
So this story teach us the truth that:
When you speak, let your words begin with love.
When you are silent, let your silence be from love.
When you scold someone, let your scold come from love.
When you and your partner protect one another, you should protect one another from love.
Let love take root in your life, and good things will happen.
No matter what other people speak to Love, Love always replied the same sentence, “Nothing is good or bad, and the interpretation is in people”. That’s the attitude Love always insist on.
In this problem, given a series of strings by lots of different people, you should output the reply Love will speak.
输入描述:
There are multiple test cases. The first line of the input contains an integer T (1 ≤ T ≤ 20), indicating the number of test cases. For each test case:
Each line contains a string (only contains a word) S (1 ≤ |S| ≤ 20), indicating the name of the person, |S| indicating the length of the string.
输出描述:
For each test case output a sentence which Love will reply to. You should output within the following format:
Love replied to XXX, “Nothing is good or bad, and the interpretation is in people.”
示例1
输入
6
Experience
Proud
Cautious
Reason
Superstition
Vision
输出
Love replied to Experience, “Nothing is good or bad, and the interpretation is in people.”
Love replied to Proud, “Nothing is good or bad, and the interpretation is in people.”
Love replied to Cautious, “Nothing is good or bad, and the interpretation is in people.”
Love replied to Reason, “Nothing is good or bad, and the interpretation is in people.”
Love replied to Superstition, “Nothing is good or bad, and the interpretation is in people.”
Love replied to Vision, “Nothing is good or bad, and the interpretation is in people.”
小声bb 签到题
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
char si[30];
cin>>si;
printf("Love replied to %s, \"Nothing is good or bad, and the interpretation is in people.\"\n",si);
}
return 0;
}