UPC 2020年夏混合个人训练第五十一场【D&E&F&G】
问题 D: 狼堡的密码
时间限制: 1 Sec 内存限制: 128 MB
题目描述
很不幸，虽然大家很努力，可羊羊们还是被灰太狼抓进了狼堡。不过，由于灰太狼太累了，准备第二天再吃羊。夜深了，灰太狼夫妇正呼呼大睡。羊羊们偷偷解开了绳子，准备逃跑。可灰太狼早有准备，把窗子封得严严实实，唯一的门上装有密码锁。不甘被吃的羊羊们决定试一试密码。
狼堡的密码是这样的：显示屏上有 n 个数，有的数出现了奇数次，有的数出现了偶数次，逃出的密码就是分别输入出现了奇数次的数的所有正因数的个数。
输入
第 1 行，一个正整数 n，表示有ｎ个数。
第 2~n+1 行，每行一个正整数 x（x≤100000）。
输出
若干行，每行两个整数，用一个空格隔开。第一个是出现了奇数次的数，第二个数是它正因数的个数。按第一个数从小到大输出。
样例输入
10
1
2
2
3
3
3
4
4
4
4
样例输出
1 1
3 2
提示
30%的数据满足：n≤500；
50%的数据满足：n≤1000；
100%的数据满足：n≤10000。
// D.模拟
#include
using namespace std;
int total(int i)
{
int tmp=1;
int j=2;
while(j<=i) {
int t=0;
while (!(i%j)) {
i/=j;
t++;
}
tmp*=(t+1);
++j;
}
return tmp;
}int main()
{
int n;
scanf("%d", &n);
int a[100100];
memset(a,0,sizeof(a));
int x;
for(int i=0;
i 【UPC 2020年夏混合个人训练第五十一场【D&E&F&G】】问题 E: 买礼物的艰辛
时间限制: 1 Sec 内存限制: 128 MB
题目描述
小 X 同学给小 C 同学选了 N 件礼物，决定顺序购买并赠送，但作为一个没有工资没有零花钱的可怜小朋友，有 M 位好心的同学伸出了援助之手，然而为了减少最高的借款量，小 X 同学希望 OI 竞赛的你为他合理规划，使得他能轻松快乐地送出礼物。
输入
第一行输入两个用空格隔开的正整数 N 和 M。
以下 N 行，每行一个不超过 10000 正整数，依次表示礼物的价格。
输出
一行一个整数，最高借款量。
样例输入
7 5
100
400
300
100
500
101
400
样例输出
500
提示
样例解释：
借第一个 500，够 1,2 个人，
然后借第二个 500，够 3,4 个人，下来不够第五个人，余下的钱全丢失。
借第三个 500，够第 5 个人。
借第四个 500，够第 6 个人，余下的钱全丢失。
借第五个 500，够第 7 个人，全都发到礼物，任务完成。
数据规模：
30%的数据满足：n≤10；
60%的数据满足：n≤1000；
100%的数据满足：n≤100000。
// E.二分
#include
#define N 100010
using namespace std;
int n,m,l,r,ans,mid,te;
int a[N];
templateinline void read(T &x)
{
x=0;
int f=1;
static char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}inline int check(int x)
{
int i=1,rem=m,now;
while(i<=n)
{
now=0;
while(now+a[i]<=x)now+=a[i],i++;
if(rem==0)return 0;
rem--;
//i++;
}
return 1;
}int main()
{
read(n),read(m);
for(int i=1;
i<=n;
i++)read(a[i]),l=max(l,a[i]);
r=1000000000;
while(l<=r){
mid=l+r>>1;
if(check(mid)) {
r=mid-1;
ans=mid;
}
else l=mid+1;
}
printf("%d",ans);
return 0;
}
问题 F: 景点拍照
时间限制: 1 Sec 内存限制: 128 MB
题目描述
中国式旅游的特点就是，上车睡觉，下车拍照。关键是还抢着拍照。
我们学生也是如此吧，先假设是这样的吧。
在一个美丽的景点，有 N 个同学想每人拍一张照片作为留念，于是他们就排好队一个一个来拍。但是呢，每个人拍照需要的时间是不同的，有些同学是在创作艺术，可能花费时间比较多，有些同学比较随意，只想证明自己到此一游而已。
考虑到排队排在后面的同学可能会等比较长的时间，为了让这个现象有所缓解，现在需要你来帮助他们找到一个排队的方案，使得所有人等待的时间总和最少。
输入
输入第一行包含一个整数 N（N<=50000），表示有 N 个同学想拍照；
第二行包含 N 个用一个空格隔开的整数，表示每个人拍照所需的时间T1,T2,…Tn（0<=Ti<=100000）。
输出
输出一行一个整数，表示所有人等待时间总和的最小值。
样例输入
5
2 3 1 5 4
样例输出
20
提示
样例解释：
排队顺序(用每个人的编号表示)应该是3,1,2,5,4，每个人拍照所需的时间分别是1,2,3,4,5，这样的话每个人等待的时间分别是0,1,3,6,10，所以总的等待时间就是0+1+3+6+10=20，不可能找到比这个等待时间更少的方案了。
数据范围
对于15%的数据满足：N<=30；
对于30%的数据满足：N<=100；
对于50%的数据满足：N<=1000；
对于100%的数据满足：1<=N<=50000。
// F.模拟 (找规律)
#include
using namespace std;
const int N = 50010;
int n,a[N];
int main()
{
cin>>n;
for (int i=1;
i<=n;
i++ ) cin>>a[i];
sort(a+1,a+1+n);
long long sum=0;
for(int i=1;
i<=n;
i ++)
sum += a[i]*(n-i);
cout<< 问题 G: 寺庙遗址
时间限制: 1 Sec 内存限制: 128 MB
题目描述
很久很久以前有一座寺庙，从上往下看寺庙的形状正好是一个正方形，在4个角上竖立着圆柱搭建而成。现在圆柱都倒塌了，只在地上留下圆形的痕迹，可是现在地上有很多这样的痕迹，专家说一定是最大的那个。
写一个程序，给出圆柱的坐标，找出由4个圆柱构成的最大的正方形，因为这就是寺庙的位置，要求计算出最大的面积。注意正方形的边不一定平行于坐标轴。
例如下图有10根柱子，其中(4,2),(5,2),(5,3),(4,3)可以形成一个正方形，(1,1),(4,0),(5,3),(2,4)也可以，后者是其中最大的，面积为10。
文章图片
输入
第一行包含一个N(1<=N<=3000)，表示柱子的数量。
接下来N行，每行有两个空格隔开的整数表示柱子的坐标(坐标值在0.到5000之间)，柱子的位置互不相同。
输出
如果存在正方形，输出最大的面积，否则输出0。
样例输入
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
样例输出
10
提示
对于30%的数据满足：1<=n<=100；
对于60%的数据满足：1<=n<=500；
对于100%的数据满足：1<=n<=3000。
// G.
#include
#define N 5010
using namespace std;
int exist[N][N];
struct email{
int x,y;
}a[N];
int n,ans,maxx;
inline int read(int &ret)
{
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';
ch=getchar();
}
return ret*f;
}inline int dis(email a,email b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}inline int check(int x,int y)
{
if(x<0||x>5000||y<0||y>5000||exist[x][y]==false)
return 0;
elsereturn 1;
}int main()
{
read(n);
for(int i=1;
i<=n;
i++)
{
read(a[i].x);
read(a[i].y);
exist[a[i].x][a[i].y]=1;
}
for(int i=1;
i<=n;
i++)
for(int j=i+1;
j<=n;
j++)
{
int x1=a[i].x,x2=a[j].x,y1=a[i].y,y2=a[j].y;
int dx=abs(x1-x2),dy=abs(y1-y2);
int x3=x2+dy,y3=y2+dx,x4=x1+dy,y4=y1+dx;
if(check(x3,y3)&&check(x4,y4))
ans=max(ans,dis(a[i],a[j]));
x3=x2+dy,y3=y2-dx,x4=x1+dy,y4=y1-dx;
if(check(x3,y3)&&check(x4,y4))
ans=max(ans,dis(a[i],a[j]));
}
printf("%d\n",ans);
return 0;
}
推荐阅读
- 清闲
- 我的2020年年度规划
- 2020-3-17
- 2020年，财富逻辑的大变迁
- 2020年，告别焦虑的自己，2021年，期待满意的自己。
- 我的剩女日记1
- 慌慌张张的2020年，再见啦！
- 如何做2020年年度复盘，写出100件成就事件
- 静待春暖花开
- 积极探索|积极探索 绽放生命 ???——心心相印计划:青少年心理工作研讨小组全国大型公益行动第二次活动包头市青山区分校圆满成功