链接：https://www.nowcoder.com/acm/contest/70/D
题目：
定义一个数字为幸运数字当且仅当它的所有数位都是4或者7。
比如说，47、744、4都是幸运数字而5、17、467都不是。
现在想知道在1...n的第k小的排列中，有多少个幸运数字所在的位置的序号也是幸运数字。
比如说，47、744、4都是幸运数字而5、17、467都不是。
现在想知道在1...n的第k小的排列中，有多少个幸运数字所在的位置的序号也是幸运数字。
输入描述:
第一行两个整数n，k。
1 <= n，k <= 1000,000,000
输出描述:
一个数字表示答案。
如果n没有k个排列，输出-1。
示例1
输入
7 4
输出
1
说明
1 2 3 4 6 7 5
示例2
输入
4 7
输出
1
说明
2 1 3 4
思路：13以内暴力，13以后的可以保证前面N-13为的排列是1，2....N-13，然后暴力后面13位。
（应该可以统一起来）。
当时由于一些细节问题，wa了很多次。导致最后面那个水题没有搞定。
#include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; #define ll long long const int inf=1000000000; ll p[200];int num[200],ans; int vis[200],t1,t2,cnt,tot=0,N,K; ll a[200000],cnt2; void dfs(ll sum) { a[++cnt2]=sum; if(sum>inf) return ; dfs(sum*10+4); dfs(sum*10+7); } void Work(int n,int m) { t2=m-1;t1=0; memset(vis,0,sizeof(vis)); int k=1; for(int i=1;i<=n;i++){ t1=t2/p[n-i]; t2=t2%p[n-i]; cnt=0; for(int j=k;j<=n;j++) if(!vis[j]){ cnt++; if(cnt==t1+1){ vis[j]=1; num[++tot]=j; break; } } } for(int i=1;i<=n;i++){ bool Flag1=false,Flag2=false;int pos; pos=lower_bound(a+1,a+cnt2+1,num[i])-a; if(num[i]==a[pos]) Flag1=true; pos=lower_bound(a+1,a+cnt2+1,i)-a; if(i==a[pos]) Flag2=true; if(Flag1&&Flag2) ans++; } } void Work2(int n,int m) { t2=m-1;t1=0; memset(vis,0,sizeof(vis)); int k=1; for(int i=1;i<=n;i++){ t1=t2/p[n-i]; t2=t2%p[n-i]; cnt=0; for(int j=k;j<=n;j++) if(!vis[j]){ cnt++; if(cnt==t1+1){ vis[j]=1; num[++tot]=j; break; } } } //for(int i=1;i<=13;i++) num[i]+=N-13; //for(int i=1;i<=n;i++) cout<<N-13+i<<" "<<num[i]+N-13<<endl; for(int i=1;i<=13;i++){ bool Flag1=false,Flag2=false;int pos; pos=lower_bound(a+1,a+cnt2+1,num[i]+N-13)-a; if(num[i]+N-13==a[pos]) Flag1=true; pos=lower_bound(a+1,a+cnt2+1,i+N-13)-a; if(i+N-13==a[pos]) Flag2=true; if(Flag1&&Flag2) ans++; } } int main() { dfs(0); sort(a+1,a+cnt2+1); p[0]=1; p[1]=1; for(int i=2;i<=14;i++) p[i]=p[i-1]*i; scanf("%d%d",&N,&K); if(N<=13){ if(K>p[N]) printf("-1 "); else{ Work(N,K); printf("%d ",ans); } } else { for(int i=2;i<=cnt2;i++) if(a[i]<=N-13) ans++; Work2(13,K); printf("%d ",ans); } return 0; }
F题：8个方向分别排序即可，一共10种情况，比赛的时候写到8就没时间了，可能也就两三分钟的事情，GG。
#include<cstdio> #include<vector> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; const int maxn=400000; int ans[maxn+10],num[10],cnt,M,N; struct in { int x; int y; int op; int id; in(){} in(int xx,int yy,int oo,int ii):x(xx),y(yy),op(oo),id(ii){} }; in xx[maxn+10]; vector<in>s[maxn+10]; bool cmp1(in a,in b){ return a.op>b.op; } bool cmp2(in a,in b){ return a.op<b.op; } void solve1() { for(int i=0;i<=M;i++) s[i].clear(); for(int i=1;i<=N;i++) { s[xx[i].x].push_back(in(xx[i].x,xx[i].y,xx[i].y,xx[i].id)); } for(int i=0;i<=M;i++) { sort(s[i].begin(),s[i].end(),cmp1); for(int j=1;j<s[i].size();j++){ ans[s[i][j].id]++; } } } void solve2() { for(int i=0;i<=M;i++) s[i].clear(); for(int i=1;i<=N;i++) { s[xx[i].x].push_back(in(xx[i].x,xx[i].y,xx[i].y,xx[i].id)); } for(int i=0;i<=M;i++) { sort(s[i].begin(),s[i].end(),cmp2); for(int j=1;j<s[i].size();j++){ ans[s[i][j].id]++; } } } void solve3() { for(int i=0;i<=M;i++) s[i].clear(); for(int i=1;i<=N;i++) { s[xx[i].y].push_back(in(xx[i].x,xx[i].y,xx[i].x,xx[i].id)); } for(int i=0;i<=M;i++) { sort(s[i].begin(),s[i].end(),cmp1); for(int j=1;j<s[i].size();j++){ ans[s[i][j].id]++; } } } void solve4() { for(int i=0;i<=M;i++) s[i].clear(); for(int i=1;i<=N;i++) { s[xx[i].y].push_back(in(xx[i].x,xx[i].y,xx[i].x,xx[i].id)); } for(int i=0;i<=M;i++) { sort(s[i].begin(),s[i].end(),cmp2); for(int j=1;j<s[i].size();j++){ ans[s[i][j].id]++; } } } void solve5() { for(int i=0;i<=M;i++) s[i].clear(); for(int i=1;i<=N;i++) { s[xx[i].y+xx[i].x].push_back(in(xx[i].x,xx[i].y,xx[i].x,xx[i].id)); } for(int i=0;i<=M;i++) { sort(s[i].begin(),s[i].end(),cmp1); for(int j=1;j<s[i].size();j++){ ans[s[i][j].id]++; } } } void solve6() { for(int i=0;i<=M;i++) s[i].clear(); for(int i=1;i<=N;i++) { s[xx[i].y+xx[i].x].push_back(in(xx[i].x,xx[i].y,xx[i].x,xx[i].id)); } for(int i=0;i<=M;i++) { sort(s[i].begin(),s[i].end(),cmp2); for(int j=1;j<s[i].size();j++){ ans[s[i][j].id]++; } } } void solve7() { for(int i=0;i<=M;i++) s[i].clear(); for(int i=1;i<=N;i++) { if(xx[i].y>=xx[i].x) s[xx[i].y-xx[i].x].push_back(in(xx[i].x,xx[i].y,xx[i].x,xx[i].id)); } for(int i=0;i<=M;i++) { sort(s[i].begin(),s[i].end(),cmp1); for(int j=1;j<s[i].size();j++){ ans[s[i][j].id]++; } } } void solve8() { for(int i=0;i<=M;i++) s[i].clear(); for(int i=1;i<=N;i++) { if(xx[i].y>=xx[i].x) s[xx[i].y-xx[i].x].push_back(in(xx[i].x,xx[i].y,xx[i].x,xx[i].id)); } for(int i=0;i<=M;i++) { sort(s[i].begin(),s[i].end(),cmp2); for(int j=1;j<s[i].size();j++){ ans[s[i][j].id]++; } } } void solve9() { for(int i=0;i<=M;i++) s[i].clear(); for(int i=1;i<=N;i++) { if(xx[i].y<xx[i].x) s[xx[i].x-xx[i].y].push_back(in(xx[i].x,xx[i].y,xx[i].x,xx[i].id)); } for(int i=0;i<=M;i++) { sort(s[i].begin(),s[i].end(),cmp1); for(int j=1;j<s[i].size();j++){ ans[s[i][j].id]++; } } } void solve10() { for(int i=0;i<=M;i++) s[i].clear(); for(int i=1;i<=N;i++) { if(xx[i].y<xx[i].x) s[xx[i].x-xx[i].y].push_back(in(xx[i].x,xx[i].y,xx[i].x,xx[i].id)); } for(int i=0;i<=M;i++) { sort(s[i].begin(),s[i].end(),cmp2); for(int j=1;j<s[i].size();j++){ ans[s[i][j].id]++; } } } int main() { scanf("%d%d",&M,&N); M=M*2+1; for(int i=1;i<=N;i++){ xx[i].id=i; scanf("%d%d",&xx[i].x,&xx[i].y); } solve1(); solve2(); solve3(); solve4(); solve5(); solve6(); solve7(); solve8(); solve9(); solve10(); for(int i=1;i<=N;i++) num[ans[i]]++; for(int i=0;i<8;i++) cout<<num[i]<<" "; cout<<num[8]<<endl; return 0; }