9.6——模拟赛

T1 洛谷 P3014 [USACO11FEB]牛线Cow Line

题目背景

征求翻译。如果你能提供翻译或者题意简述，请直接发讨论，感谢你的贡献。

题目描述

The N (1 <= N <= 20) cows conveniently numbered 1...N are playing yet another one of their crazy games with Farmer John. The cows will arrange themselves in a line and ask Farmer John what their line number is. In return, Farmer John can give them a line number and the cows must rearrange themselves into that line.

A line number is assigned by numbering all the permutations of the line in lexicographic order.

Consider this example:

Farmer John has 5 cows and gives them the line number of 3.

The permutations of the line in ascending lexicographic order: 1st: 1 2 3 4 5

2nd: 1 2 3 5 4

3rd: 1 2 4 3 5

Therefore, the cows will line themselves in the cow line 1 2 4 3 5.

The cows, in return, line themselves in the configuration '1 2 5 3 4' and ask Farmer John what their line number is.

Continuing with the list:

4th : 1 2 4 5 3

5th : 1 2 5 3 4

Farmer John can see the answer here is 5

Farmer John and the cows would like your help to play their game. They have K (1 <= K <= 10,000) queries that they need help with. Query i has two parts: C_i will be the command, which is either 'P' or 'Q'.

If C_i is 'P', then the second part of the query will be one integer A_i (1 <= A_i <= N!), which is a line number. This is Farmer John challenging the cows to line up in the correct cow line.

If C_i is 'Q', then the second part of the query will be N distinct integers B_ij (1 <= B_ij <= N). This will denote a cow line. These are the cows challenging Farmer John to find their line number.

输入输出格式

输入格式：

  • Line 1: Two space-separated integers: N and K

  • Lines 2..2*K+1: Line 2*i and 2*i+1 will contain a single query.

Line 2*i will contain just one character: 'Q' if the cows are lining up and asking Farmer John for their line number or 'P' if Farmer John gives the cows a line number.

If the line 2*i is 'Q', then line 2*i+1 will contain N space-separated integers B_ij which represent the cow line. If the line 2*i is 'P', then line 2*i+1 will contain a single integer A_i which is the line number to solve for.

输出格式：

  • Lines 1..K: Line i will contain the answer to query i.

If line 2*i of the input was 'Q', then this line will contain a single integer, which is the line number of the cow line in line 2*i+1.

If line 2*i of the input was 'P', then this line will contain N space separated integers giving the cow line of the number in line 2*i+1.

输入输出样例

输入样例#1：
5 2 
P 
3 
Q 
1 2 5 3 4
输出样例#1：
1 2 4 3 5 
5 


康托展开：
  1 #include <algorithm>
  2 #include <string>
  3 #include <cstdio>
  4 #include <map>
  5 
  6 using namespace std;
  7 
  8 #define LL long long
  9 LL jc[21]={1,1,2,6,24,120,720,5040,40320,362880,328800,
 10             39916800,479001600,6227020800LL,87178291200LL,
 11             1307674368000LL,20922789888000LL,355687428096000LL,
 12             6402373705728000LL,121645100408832000LL,2432902008176640000LL};
 13 map<LL,string>m1;
 14 map<string,LL>m2;
 15 LL n,m,x,cnt,tmp[26];
 16 char num[26],sta[26];
 17 string a;
 18 
 19 inline void read(LL &x)
 20 {
 21     x=0; register char ch=getchar();
 22     for(;ch>'9'||ch<'0';) ch=getchar();
 23     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
 24 }
 25 
 26 void work1()
 27 {
 28     for(int i=1; i<=n; ++i) num[i-1]=i+'0';
 29     for(;1;next_permutation(num,num+n))
 30     {
 31         if(m2[num]) break;
 32         m1[++cnt]=num;
 33         m2[num]=cnt;
 34     }
 35     for(char s[2];m--;)
 36     {
 37         scanf("%s",s);
 38         if(s[0]=='P')
 39         {
 40             read(x); a=m1[x];
 41             for(int i=0;i<n-1;i++)
 42                 printf("%d ",a[i]-'0');
 43             printf("%d
",a[n-1]-'0');
 44         }
 45         else
 46         {
 47             for(int i=0; i<n; ++i)
 48                 read(x),a[i]=x+'0';
 49             printf("%lld
",m2[a]);
 50         }
 51     }
 52 }
 53 
 54 int AC()
 55 {
 56 //    freopen("permutation.in","r",stdin);
 57 //    freopen("permutation.out","w",stdout);
 58 
 59     read(n),read(m);
 60     /*jc[0]=1;
 61     for(LL i=1; i<=n; ++i) jc[i]=jc[i-1]*i;*/
 62     if(n<=5) work1();
 63     else
 64     {
 65         for(char s[2];m--;)
 66         {
 67             scanf("%s",s);
 68             if(s[0]=='P')
 69             {
 70                 read(x); x--;
 71                 bool use[26]={0};
 72                 for(LL j,i=1; i<=n; ++i)
 73                 {
 74                     LL tmp=x/jc[n-i];
 75                     for(j=1; j<=n; ++j)
 76                     if(!use[j])
 77                     {
 78                         if(!tmp) break;
 79                         tmp--;
 80                     }
 81                     use[j]=1;
 82                     x%=jc[n-i];
 83                     printf("%d ",j);
 84                 }
 85                 puts("");
 86             }
 87             else
 88             {
 89                 for(LL i=1; i<=n; ++i) read(tmp[i]);
 90                 LL ans=0;
 91                 for(LL t=0,i=1;i<=n;i++)
 92                 {
 93                     t=0;
 94                     for(LL j=i+1; j<=n; ++j)
 95                         if(tmp[i]>tmp[j]) t++;
 96                     ans+=t*jc[n-i];
 97                 }
 98                 printf("%I64d
",ans+1);
 99             }
100         }
101     }
102     return 0;
103 }
104 
105 int Hope=AC();
106 int main(){;}
考试60分
阶乘没打表就能过了、、

 1 #include <cstdio>
 2 
 3 using namespace std;
 4 
 5 #define LL long long
 6 LL jc[21];
 7 LL n,m,x,cnt,tmp[26];
 8 
 9 inline void read(LL &x)
10 {
11     x=0; register char ch=getchar();
12     for(;ch>'9'||ch<'0';) ch=getchar();
13     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
14 }
15 
16 int AC()
17 {
18 //    freopen("permutation.in","r",stdin);
19 //    freopen("permutation.out","w",stdout);
20 
21     read(n),read(m);
22     jc[0]=1; for(LL i=1; i<=n; ++i) jc[i]=jc[i-1]*i;
23     for(char s[2];m--;)
24     {
25         scanf("%s",s);
26         if(s[0]=='P')
27         {
28             read(x); x--;
29             bool use[26]={0};
30             for(LL j,i=0; i<n; ++i)
31             {
32                 LL tmp=x/jc[n-i-1];
33                 for(j=1; j<=n; ++j)
34                 if(!use[j])
35                 {
36                     if(!tmp) break;
37                     tmp--;
38                 }
39                 use[j]=1;
40                 x%=jc[n-i-1];
41                 printf("%d ",j);
42             }
43             puts("");
44         }
45         else
46         {
47             for(LL i=0; i<n; ++i) read(tmp[i]);
48             LL ans=0;
49             for(LL t=0,i=0;i<n;i++)
50             {
51                 t=0;
52                 for(LL j=i+1; j<n; ++j)
53                     if(tmp[i]>tmp[j]) t++;
54                 ans+=t*jc[n-i-1];
55             }
56             printf("%lld
",ans+1);
57         }
58     }
59     return 0;
60 }
61 
62 int Hope=AC();
63 int main(){;}
AC


T2 洛谷 U3357 C2-走楼梯

题目背景

在你成功地解决了上一个问题之后，方方方不禁有些气恼，于是他在楼梯上跳来跳去，想要你求出他跳的方案数。..

题目描述

方方方站在一个n阶楼梯下面，他每次可以往上跳一步或两步，往下跳一步到四步（由于地心引力跳得比较远），而且在往下跳的时候你只能踩在你往上跳时踩过的格子。

现在方方方在楼梯上乱跳，想问他跳到楼梯顶上最后又跳回楼梯下面的方案数mod 2333333。

请注意：针对题目有歧义的情况，这里再说明一下。方方方只能一直向上跳，跳到楼梯最上面，然后再往下跳，跳回楼梯最底下。

输入输出格式

输入格式：

输入一行一个数n。

输出格式：

输出方方方跳回楼梯下面的方案数mod 2333333。

输入输出样例

输入样例#1：
5
输出样例#1：
52
输入样例#2：
7654321
输出样例#2：
451197
输入样例#3：
3
输出样例#3：
8

说明

对于30%的数据，n<=10。

对于100%的数据，1<=n<=10^7。

（其实也可以做到10^18，可是出题人懒）

 1 #include <cstdio>
 2 
 3 const int mod(2333333);
 4 const int N(1e7+5);
 5 int n;
 6 
 7 inline void read(int &x)
 8 {
 9     x=0; register char ch=getchar();
10     for(;ch>'9'||ch<'0';) ch=getchar();
11     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
12 }
13 
14 int ans;
15 bool vis[N],vis_[N];
16 void DFS_(int now)
17 {
18     if(now==0)
19     {
20         ans++;
21         ans%=mod;
22         return ;
23     }
24     for(int i=1; i<=4; ++i)
25     {
26         if(vis_[now-i]||(now-i<0)) continue;
27         if(!vis[now-i]) continue;
28         vis_[now-i]=1;
29         DFS_(now-i);
30         vis_[now-i]=0;
31     }
32 }
33 void DFS(int now)
34 {
35     if(now==n)
36     {
37         DFS_(now);
38         return ;
39     }
40     for(int i=1; i<=2; ++i)
41     {
42         if(vis[now+i]||(now+i>n)) continue;
43         vis[now+i]=1;
44         DFS(now+i);
45         vis[now+i]=0;
46     }
47 }
48 
49 int AC()
50 {
51 //    freopen("stair.in","r",stdin);
52 //    freopen("stair.out","w",stdout);
53     
54     read(n); vis[0]=1; DFS(0);
55     printf("%d
",ans);
56     return 0;
57 }
58 
59 int Hope=AC();
60 int main(){;}
考试，爆搜30分

正解DP：

向下走可以看成向上走

f[i]表示第一次向上走到i，第二次向上也走到i的方案数

如果第二次向上走1步到i，这1步第一次有1种走法

如果第二次向上走2步到i，这2步第一次有2种走法

如果第二次向上走3步到i，这3步第一次有3种走法

如果第二次向上走4步到i，这4步第一次有5种走法

所以状态转移方程：f[i]=f[i-1]+f[i-2]*2+f[i-3]*3+f[i-4]*5

 1 #include <cstdio>
 2 
 3 const int mod(2333333);
 4 const int N(1e7+5);
 5 int n,f[N];
 6 
 7 inline void read(int &x)
 8 {
 9     x=0; register char ch=getchar();
10     for(;ch>'9'||ch<'0';) ch=getchar();
11     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
12 }
13 
14 int AC()
15 {
16     read(n);
17     f[0]=1; f[1]=1; f[2]=3; f[3]=8;
18     for(int i=4;i<=n;i++)
19         f[i]=(f[i-1]+f[i-2]*2+f[i-3]*3+f[i-4]*5)%mod;
20     printf("%d
",f[n]);
21     return 0;
22 }
23 
24 int Hope=AC();
25 int main(){;}
AC

T3 BZOJ——1821: [JSOI2010]Group 部落划分 Group

Description

聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。 不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了N个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了K个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法： 对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。 例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。 

Input

第一行包含两个整数N和K(1< = N < = 1000,1< K < = N)，分别代表了野人居住点的数量和部落的数量。
接下来N行，每行包含两个正整数x,y，描述了一个居住点的坐标(0 < =x, y < =10000)

Output

输出一行，为最优划分时，最近的两个部落的距离，精确到小数点后两位。

Sample Input

4 2
0 0
0 1
1 1
1 0


Sample Output

1.00

HINT

 

Source

JSOI2010第二轮Contest1

最小生成树+乱搞活似一个大zz

 1 #include <algorithm>
 2 #include <cstdio>
 3 #include <cmath>
 4 
 5 const int N(1026);
 6 int n,k,sumedge;
 7 struct Node {
 8     int x,y;
 9 }peo[N];
10 struct Edge {
11     double dis;
12     int u,v;
13     bool operator < (const Edge x)const
14     {
15         return dis>x.dis;
16     }
17     Edge(int u=0,int v=0,double dis=0.0):u(u),v(v),dis(dis){}
18 }e[N*N];
19 
20 inline void read(int &x)
21 {
22     x=0; register char ch=getchar();
23     for(;ch>'9'||ch<'0';) ch=getchar();
24     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
25 }
26 
27 double Get_dis(int u,int v)
28 {
29     return sqrt((double)(peo[u].x-peo[v].x)*(peo[u].x-peo[v].x)+(double)(peo[u].y-peo[v].y)*(peo[u].y-peo[v].y));
30 }
31 
32 int fa[N];
33 int find(int x)
34 {
35     return fa[x]==x?x:fa[x]=find(fa[x]);
36 }
37 
38 #define max(a,b) (a>b?a:b)
39 #define min(a,b) (a<b?a:b)
40 
41 int AC()
42 {
43     freopen("people.in","r",stdin);
44     freopen("people.out","w",stdout);
45     
46     read(n),read(k);
47     for(int i=1; i<=n; ++i)
48         read(peo[i].x),read(peo[i].y);
49     for(int i=1; i<=n; ++i)
50         for(int j=1; j<=n; ++j)
51         if(i!=j) e[++sumedge]=Edge(i,j,Get_dis(i,j));
52     int cnt=0;
53     double ans=0;
54     std::sort(e+1,e+sumedge+1);
55     for(int i=1; i<=n; ++i) fa[i]=i;
56     for(int fx,fy,i=1; i<=sumedge; ++i)
57     {
58         fx=find(e[i].u), fy=find(e[i].v);
59         if(fa[fx]==fy) continue;
60         fa[fx]=fy;
61         if(++cnt<=k) ans=max(ans,e[i].dis);
62         else ans=min(ans,e[i].dis);
63         if(cnt==n-1) break;
64     }
65     printf("%.2lf",ans);
66     return 0;
67 }
68 
69 int Hope=AC();
70 int main(){;}
考试的zz写法。。10分

最小生成树：

首先按照边权排序，要让最小的距离最大，那么就让那些很小的距离放在部落内部；

原来有n个部落，而每加入一条边就会减少一个，ans=最小生成树的第n-k+1条边。

 1 #include <algorithm>
 2 #include <cstdio>
 3 #include <cmath>
 4 
 5 const int N(1026);
 6 int n,k,sumedge;
 7 double dist[N];
 8 struct Node {
 9     int x,y;
10 }peo[N];
11 struct Edge {
12     double dis;
13     int u,v;
14     bool operator < (const Edge &x)const
15     {
16         return dis<x.dis;
17     }
18     Edge(int u=0,int v=0,double dis=0.0):u(u),v(v),dis(dis){}
19 }e[N*N];
20 
21 inline void read(int &x)
22 {
23     x=0; register char ch=getchar();
24     for(;ch>'9'||ch<'0';) ch=getchar();
25     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
26 }
27 
28 double Get_dis(int u,int v)
29 {
30     return sqrt((double)(peo[u].x-peo[v].x)*(peo[u].x-peo[v].x)+(double)(peo[u].y-peo[v].y)*(peo[u].y-peo[v].y));
31 }
32 
33 int fa[N];
34 int find(int x)
35 {
36     return fa[x]==x?x:fa[x]=find(fa[x]);
37 }
38 
39 #define max(a,b) (a>b?a:b)
40 #define min(a,b) (a<b?a:b)
41 
42 int AC()
43 {
44 //    freopen("people.in","r",stdin);
45 //    freopen("people.out","w",stdout);
46     
47     read(n),read(k);
48     for(int i=1; i<=n; ++i)
49         read(peo[i].x),read(peo[i].y);
50     for(int i=1; i<=n; ++i)
51         for(int j=1; j<=n; ++j)
52         if(i!=j) e[++sumedge]=Edge(i,j,Get_dis(i,j));
53     int cnt=0;
54     double ans=0;
55     std::sort(e+1,e+sumedge+1);
56     for(int i=1; i<=n; ++i) fa[i]=i;
57     for(int fx,fy,i=1; i<=sumedge; ++i)
58     {
59         fx=find(e[i].u), fy=find(e[i].v);
60         if(fa[fx]==fy) continue;
61         fa[fx]=fy;
62         if(++cnt>n-k)
63         {
64             printf("%.2lf",e[i].dis);
65             return 0;
66         }
67     }
68     return 0;
69 }
70 
71 int Hope=AC();
72 int main(){;}
AC
——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Shy-key/p/7484966.html