社区讨论

错误提示答案太短,哪位大佬可以帮忙指教下

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 条回复,欢迎继续交流。

正在加载回复...