首页 > 代码库 > HDU 4028 The time of a day STL 模拟题
HDU 4028 The time of a day STL 模拟题
暴力出奇迹。。
#include<stdio.h> #include<iostream> #include<algorithm> #include<vector> #include<cmath> #include<queue> #include<set> #include<map> using namespace std; #define ll __int64 #define N 42 ll n,m,ans; ll Gcd(ll x,ll y){ if(x>y)swap(x,y); while(x){ y%=x; swap(x,y); } return y; } ll Lcp(ll x,ll y){return x*y/Gcd(x,y);} map<ll,ll>mp[N]; map<ll,ll>::iterator p; pair<ll,ll>tmp; void work(ll x, ll cur){ p = mp[cur].end(); if(p==mp[cur].begin())return; p--; for(;;p--){ tmp = *p; ll dou = Lcp(tmp.first,x); if(dou>=m){ ans += tmp.second; } mp[cur][dou]+=tmp.second; if(p==mp[cur].begin())return; } } struct node{ ll num, ans; bool operator<(const node&a)const{ return a.num>num; } }; set<node>myset[N]; int main(){ ll i, j, Cas = 1, T;scanf("%I64d",&T); mp[0].clear(); for(i=1;i<=40;i++) { mp[i] = mp[i-1]; work(i,i); mp[i][i]++; node now = {0,0}; myset[i].clear(); for(p=mp[i].end(),p--;;p--){ tmp = *p; now.num = tmp.first; now.ans += tmp.second; myset[i].insert(now); if(p==mp[i].begin())break; } } while(T--){ scanf("%I64d %I64d",&n,&m); printf("Case #%I64d: ",Cas++); node dou = {m,-1}; if(myset[n].lower_bound(dou)==myset[n].end())puts("0"); else printf("%I64d\n",myset[n].lower_bound(dou)->ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。