抱着可能杭电的多校1比牛客的多校1更恐怖的想法 看到三道签到题 幸福的都快哭出来了好吗
1001 Maximum Multiple（hdoj 6298）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6298
签到题 但是有考了一定的思维 清北大佬两分钟写出来真的让人望尘莫及啊……
题意是给定一个n 可以由三个正整数相加得到 同时这三个正整数又是要被n可以整除 求这三个整数相乘的最大值 如果没有 则输出-1
既然题目没有要求三个正整数不能相等 则可以按照比例分成 3 3 3和2 2 4两堆
代码如下 一开始爆了int 在乘法前强制转换了long long
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
ll ans=;
if(n%==) ans=(ll)(n/)*(n/)*(n/);
else if(n%==) ans=(ll)(n/)*(n/)*(n/);
else ans=-;
printf("%lld\n",ans);
}
return ;
}
1003 Triangle Partition （hdoj 6300）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6300
签到题+1；
题意为要求有n个三角形 并且给3n个点 任意两个三角形不能相交 问应该如何组合这3n个点
因为在坐标中 任意三个点围起来都是三角形 而且题目中也有说明 给出的点任意三个点不在一条直线上 所以排序就好了
代码如下
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{
int x,y;
int id;
}kk[];
int cmp(node a,node b){
if(a.x==b.x) return a.y<b.y;
else return a.x<b.x;
}
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=;i<=*n;i++){
scanf("%d%d",&kk[i].x,&kk[i].y);
kk[i].id=i;
}
sort(kk+,kk+*n+,cmp);
for(int i=;i<=*n;i++){
printf("%d",kk[i].id);
if(i%==) printf("\n");
else printf(" ");
}
}
return ;
}
1004 Distinct Values （hdoj 6301）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6301
卡了三个半小时 还是没有做出来orz 一直t了九发 最后让一队帮忙查错 就是全局定义局部定义 清空方面的优化 我都已经想到了却没有上手写 这题没出来我背锅
题意为有一个长度为n的数列 其中有m个区间操作 在每个l到r中间 都严格满足数字不相等 并且满足字典序 最后输出这个数列
队友上手写的 大概讲一下做法 用的是小根堆+莫队思想 开一个空数组赋值 在操作区间外的位置 全部都赋值为1
想到一个优化的点 在对各个区间先按l从小到大再按r从小到大排序后 如果有一个区间是包含在别的区间中 可以直接continue 不需要再赋值
先记录所有边界的最大值为maxn 即可以放入的数字最大不超过maxn 把1到maxn都放入到一个队列中 对第一个区间进行查询 先赋值一遍 并把相应的数字从队列中弹出 再加入一个指针弹来弹去 把没有重叠可以使用的数字都重新放回到队列中 下一个区间可以使用的数字就从队列中按字典序取用
一个小的点 也是这回我的锅：memset的清空范围是数组定义的范围 如果数组非常大 哪怕输入数据很小 但还是会兢兢业业从头到尾清空一遍 遇到数据比较多的情况 可以手写一个for循环进行清空 可以节省不少时间
（队友）代码如下
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int T,n,m,a[],topt,maxn;
struct data
{
int l,r;
}q[];
bool cmp(data aa,data bb){if (aa.l==bb.l) return aa.r<bb.r; return aa.l<bb.l;}
priority_queue<int,vector<int>,greater<int> >qq;
int main()
{ scanf("%d",&T);
while (T--)
{
topt=; maxn=;
while (!qq.empty()) qq.pop();
for(int i=;i<=n;i++) a[i]=;
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),maxn=max(maxn,q[i].r);
for (int i=;i<=maxn;i++) qq.push(i);
sort(q+,q+m+,cmp);
for (int i=q[].l;i<=q[].r;i++) a[i]=qq.top(),qq.pop();;
int pl=q[].l,pr=q[].r;
for (int i=;i<=m;i++)
{
if (q[i].r<=pr) continue;
while (pl<q[i].l) {qq.push(a[pl]); pl++;}
while (pr<q[i].r) {pr++; a[pr]=qq.top(); qq.pop();}
}
for (int i=;i<=n;i++) if (a[i]==) a[i]=;
for (int i=;i<n;i++) printf("%d ",a[i]);
printf("%d\n",a[n]);
}
return ;
}
1011 Time Zone （hdoj 6308）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6308
签到题+1；
题意为给出当前的北京时间 根据UTC来判断当前时区的时间 如果出现-X.Y的情况 Y=1就是6分钟
模拟题 感觉写起来还是有点麻烦的 稍不留意就写劈叉了 因为是时间类的题目 在边界上面还要有判断
PS：这个UTC是真的无比熟悉啊 打cf的时候天天见
代码如下
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int main(){
int t;
scanf("%d",&t);
while(t--){
int a,b;
char s[];
scanf("%d%d UTC%s",&a,&b,s);
int len=strlen(s);
int tmp=;
if(s[]=='-'){
if(len==){
tmp=s[]-'';
a-=(tmp+);
if(a>=) a-=;
if(a<) a+=;
}
if(len==){
tmp=(s[]-'')*+(s[]-'');
a-=(tmp+);
if(a>=) a-=;
if(a<) a+=;
}
if(len==){
tmp=s[]-'';
a-=(tmp+);
b-=*(s[]-'');
if(b<) b+=,a--;
if(a>=) a-=;
if(a<) a+=;
}
if(len==){
tmp=(s[]-'')*+(s[]-'');
a-=(tmp+);
b-=*(s[]-'');
if(b<) b+=,a--;
if(a>=) a-=;
if(a<) a+=;
}
}
else if(s[]!='-'){
if(len==){
tmp=s[]-'';
a+=(tmp-);
if(a>=) a-=;
if(a<) a+=;
}
if(len==){
tmp=(s[]-'')*+(s[]-'');
a+=(tmp-);
if(a>=) a-=;
if(a<) a+=;
}
if(len==){
tmp=s[]-'';
a+=(tmp-);
b+=*(s[]-'');
if(b>=) b-=,a++;
if(a>=) a-=;
if(a<) a+=;
}
if(len==){
tmp=(s[]-'')*+(s[]-'');
a+=(tmp-);
b+=*(s[]-'');
if(b>=) b-=,a++;
if(a>=) a-=;
if(a<) a+=;
}
}
printf("%02d:%02d\n",a,b);
}
return ;
}