社区讨论
错误提示答案太短,哪位大佬可以帮忙指教下
P10246 Exciting Days参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @ltp96k2b
- 此快照首次捕获于
- 2024/03/13 11:40 2 年前
- 此快照最后确认于
- 2024/03/13 15:45 2 年前
CPP
#include <bits/stdc++.h>
using namespace std;
/*枚举月份-日期后面10多个点超时
反向思考:枚举出合适的特殊字,分析是否可以拆分为范围内的
结合上一个程序验证:范围内最多408个特征值,给个500的结构体存放ans
**/
const int N=3e5+5;
int T,n,tt;
long long k,m[N],ans[N],maxn;//分析可知,最多408个特殊值
struct node{ int m,d; }nd[500];//存放合理的月份和日期
bool cmp(node a,node b){//比较函数
if(a.m!=b.m) return a.m<b.m;//月份小的在前
return a.d<b.d;//日期小的在前
}
int len(long long x){//分析x位数
int ret=0;
while(x>0){ ret+=1; x/=10;}
return ret;
}
long long pj(int a,long long b){//将月份和日期拼接起来
long long ret=a;//初始化
int k=len(b);//加0次数
while(k--) ret*=10;
return ret+b;
}
void csh(){//初始化范围内k的x次方
//memset(ans,0,sizeof(ans));
ans[tt=0]=1;
long long end=pj(n,maxn);//printf("%lld %d\n",end,k);
while(ans[tt]<=end){
tt++;
ans[tt]=ans[tt-1]*k;//printf("%lld ",ans[tt]);
}//printf("\n");//printf("最多个数=%d\n");
sort(ans,ans+tt);//记得排序啊!!!
}
void deal(){
maxn=0;//memset(m,0,sizeof(m));
scanf("%d%lld",&n,&k);//月份个数和k
for(int i=1;i<=n;i++) {scanf("%lld",&m[i]);maxn=max(maxn,m[i]);}//输入
if(k==1){ printf("0\n"); return ;}//特殊情况判断
csh();//初始化
int cnt=0;
for(int i=1;i<tt;i++){//枚举特殊值分析结果个数
if(ans[i]<11) continue;//跳过1位数
long long tmp=ans[i];//取出当前数字
long long power=10,left,right;;//位权初始化
do{
left=tmp/power,right=tmp%power;
if(left<=n&&right<=m[left]&&right!=tmp%(power/10)){//日期在范围内 注意天数前面不能有前导0
nd[cnt].m=left,nd[cnt].d=right;//printf("%d %d\n",left,right);
cnt++;
}
power*=10;//更新权重
}while(left>0);
}
if(cnt==0){ printf("0\n"); return ;}
sort(nd,nd+cnt,cmp);//排序
//输出
printf("%d\n",cnt);
for(int i=0;i<cnt;i++) printf("%d %d\n",nd[i].m,nd[i].d);
printf("\n");
}
int main(){
scanf("%d",&T);
while(T--){
deal();
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...