HNUCM省赛训练赛第14场题解
这边是这次训练赛的地址，都是中文题了这次。
目录
- A——Ticket
- B——GCD
- C——Function
- G——Circle
- H——Clock
- I——Tangram
- J——Tetris
A——Ticket
水题一道，没什么好讲的，但是我们wa了一发，题目没给清楚，实际上我们需要的是多组输入。。。这道签到题让队友做了，代码如下
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
typedef long long ll;
int main()
{
int n;
while(cin >> n){
double ans = 0;
for (int i = 0; i < n; i++){
double price;
cin >> price;
if (ans < 100)ans += price;
else if (ans >= 100 && ans < 150)ans = ans + price * 0.8;
else if (ans >= 150 && ans < 400)
ans = ans + price * 0.5;
else ans += price;
}
printf("%.2lf\n", ans);
}
return 0;
}
B——GCD
一道结论题，容易发现，当我们的和sum为偶数的时候，一定可以把1-n个数分成两堆和都为sum/2的数列。接着试着多打印一些n和sum进行比对，容易发现这题的结论：
当sum%素数=0时，答案就是sum/这个素数
因此这道题可以先打个大概的素数表，然后直接循环找到最小的素数满足sum%这个素数=0即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int prime[100005],cnt;
bool isprime[1000005];
inline void solve(int n){
memset(isprime,true,sizeof(isprime));isprime[1]=false;
for(int i=2;i<=n;++i){
if(isprime[i])prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=n;++j){
isprime[i*prime[j]]=false;
if(i%prime[j]==0)break;
}
}
}
int main(){
solve(1000000);
ll n;cin>>n;
ll sum=n*(n+1)/2;
for(int i=1;i<=100000;++i){
int num=prime[i];
if(sum%num==0){printf("%d\n",sum/num);break;}
}
}
C——Function
其实这种类型的题目印象里面已经不是第一次见到了，当时没有做出来，也没有补题，这次居然做出来了，状态比较好吧。
这题一开始以为是个数学题，需要推导结论，但是由于对于不同的Fi(x)，其中的系数ai,bi,ci都是不一样的，不太可能通过函数的联合来推导出斜率等结论，这些都是开口向上的函数，对称轴可能小于0，情况会复杂很多，不太可能归结为数学题。
这是这样考虑的，因为题目要求每个x都是正整数，也就是说题目中的m一定会大于等于n，因此我们可以尝试先给每个函数的x分配1，接下来剩余m-n个数，我们的分配规则就需要查看对于每个函数来说的变化率，因此设置结构体变量，存储当前分配的x和当前值以及当x+1的时候函数的变化率，利用优先队列即可。
#include<bitsdc++.h>
#define ll long long
using namespace std;
struct Node{
int a,b,c;
ll sum,dx,x;
bool operator<(const Node &s)const{
return dx>s.dx;
}
};
priority_queue<Node>q;
int main(){
int n,m;cin>>n>>m;
ll sum=0;
for(int i=1;i<=n;++i){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
q.push({a,b,c,a+b+c,3*a+b,1});
sum+=a+b+c;
}
for(int i=1;i<=m-n;++i){
Node u=q.top();q.pop();
int a=u.a,b=u.b,c=u.c;
ll ans=u.sum,dx=u.dx,x=u.x+1;
q.push({a,b,c,ans+dx,a*(2*x+1)+b,x});
sum+=dx;
}
printf("%lld\n",sum);
}
G——Circle
一道比较简单的题目，对于正n边形，再加上一个点使得其面积最大的方式一定是在n个分割点的中间取一个点，最后得到的面积是正n边形的面积加上多出来的三角形的面积，得到角度容易推出公式，简单题，不详细阐述，直接上代码。
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
typedef long long ll;
#define PI acos(-1)
int main()
{
int n;
while (cin >> n)
{
double j = PI / (double)n;
double ans = sin(j) * cos(j) * (double)n + sin(j) * (1 - cos(j));
printf("%.6lf", ans);
}
return 0;
}
H——Clock
Input：
1
0 1 0
0 1 1
Output：
6.00
这道题有毒。。。main中不能使用sort函数，不然就不让交。。。
排了半天才知道原来是不让这样做，最后把sort在之前宏定义一下，不在main中用sort这四个字符就能交上去了。。。离谱
其实这道题一开始就想太复杂了，其实可以暴力一点的，直接就记录每一个点到出发点的顺时针角度差和逆时针角度差（当然这里有一点细节要是没处理好，就容易wa），然后进行排序，排序规则可以是顺时针的距离差从小到大排，那么这个题目的最小转动的度数一定在这四种情况之间：
（1）直接逆时针转完
（2）直接顺时针转完
（3）除了第一个点，对于每个点来说，都顺时针先到这个点以后再逆时针转回来（顺时针到i点，再逆时针到i+1点），对于这个点来说，转到以后不可能再继续顺时针转下去了，因为如果继续转下去到某个点后再逆时针转过来，代价很大，要是想继续转下去不如直接转到底，那就是（2）的情况了
（4）除了最后一个点，对于每个点，都是先逆时针转到这里以后再顺时针转回来（逆时针到i点，再逆时针到i-1点）
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int SUM=12*60*60*6;
#define my_sor sort
struct Node{
int a,b;
}node[100000];
inline bool cmp(Node a,Node b){
return a.a<b.a;
}
int main(){
int n;cin>>n;
int h,m,s;cin>>h>>m>>s;
if(h>=12)h-=12;
int now=(h*3600+m*60+s)*6;
for(int i=1;i<=n;++i){
int hi,mi,si;scanf("%d%d%d",&hi,&mi,&si);
if(hi>=12)hi-=12;
node[i].a=(hi*3600+mi*60+si)*6+SUM-now;
if(node[i].a>=SUM)node[i].a-=SUM;
node[i].b=SUM-node[i].a;
}
my_sor(node+1,node+1+n,cmp);
int ans=min(node[n].a,node[1].b);
for(int i=2;i<=n-1;++i){
int x=2*node[i].a+node[i+1].b;
ans=min(ans,x);
}
for(int i=n-1;i>=1;--i){
int x=2*node[i].b+node[i-1].a;
ans=min(ans,x);
}
printf("%.2lf\n",1.0*ans);
}
I——Tangram
题目描述
一块七巧板有 7 块，现在 wls 想再在七巧板上加 n条直线将七巧板切分并且使得切出来的块最多，请问最多能有多少块？
首先大家肯定都知道一个定理：一条直线割平面，所增加的平面数量将会是割点的数量+1，那么我们自然是尽可能多的割点。
容易发现，这个图上面能被一条直线造成最多割点的数量是5，因此增加的平面数量是6；如果再加一条直线，只需要继续割上次的五条线再加上之前割的所有线，所以增加的平面数量是7 8 9…依次类推，结论就出来了，挺容易看出来的
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ll n;
while(~scanf("%lld",&n)){
ll sum=7;
ll a=6,b=a+n-1;
sum+=(a+b)*n/2;
printf("%lld\n",sum);
}
}
J——Tetris
自己多画一下图，容易验证n和m任意一个不是4的倍数的，都无法构成答案，如果是4的倍数，题目就很简单了。。。直接把样例的输出拿来做一些复制的处理操作即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s1="1113",s2="2133",s3="2243",s4="2444";
int main(){
int n,m;
while(cin>>n>>m){
if(n%4!=0||m%4!=0)puts("no response");
else{
n>>=2,m>>=2;
string a="",b="",c="",d="";
for(int i=1;i<=m;++i)a+=s1,b+=s2,c+=s3,d+=s4;
while(n--){
cout<<a<<endl;cout<<b<<endl;
cout<<c<<endl;cout<<d<<endl;
}
}
}
}