AtCoder Beginner Contest 150

AB没啥好说的

C - Count Order /

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $300$ points

Problem Statement

We have two permutations $P$ and $Q$ of size $N$ (that is, $P$ and $Q$ are both rearrangements of $(1, 2, . . ., N)$ ).

There are $N!$ possible permutations of size $N$ . Among them, let $P$ and $Q$ be the $a$ -th and $b$ -th lexicographically smallest permutations, respectively. Find $| a - b |$ .

Notes

For two sequences $X$ and $Y$ , $X$ is said to be lexicographically smaller than $Y$ if and only if there exists an integer $k$ such that $X_{i} = Y_{i} (1 \leq i < k)$ and $X_{k} < Y_{k}$ .

Constraints

$2 \leq N \leq 8$
$P$ and $Q$ are permutations of size $N$ .

Input

Input is given from Standard Input in the following format:

 $N$ 
 $P_{1}$   $P_{2}$   $. . .$   $P_{N}$ 
 $Q_{1}$   $Q_{2}$   $. . .$   $Q_{N}$

Output

Print $| a - b |$ .

用康托展开，这里数据很小也可以直接STL跑next_permutation。。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 
 5 int jc[10]={1};
 6 int a[10],b[10],n;
 7 int cal(int a[],int n){
 8     int res=0;
 9     for(int i=1;i<=n;++i){
10         int c=0;
11         for(int j=i+1;j<=n;++j)c+=(a[j]<a[i]);
12         res+=c*jc[n-i];
13     }return res;
14 }
15 int main(){
16     for(int i=1;i<=9;++i)jc[i]=i*jc[i-1];
17     cin>>n;
18     for(int i=1;i<=n;++i)cin>>a[i];
19     for(int i=1;i<=n;++i)cin>>b[i];
20     cout<<abs(cal(b,n)-cal(a,n))<<endl;
21     return 0;
22 }

D - Semi Common Multiple /

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $400$ points

Problem Statement

Given are a sequence $A = a_{1}, a_{2}, . . . . . . a_{N}$ of $N$ positive even numbers, and an integer $M$ .

Let a semi-common multiple of $A$ be a positive integer $X$ that satisfies the following condition for every $k$ $(1 \leq k \leq N)$ :

There exists a non-negative integer $p$ such that $X = a_{k} \times (p + 0.5)$ .

Find the number of semi-common multiples of $A$ among the integers between $1$ and $M$ (inclusive).

Constraints

$1 \leq N \leq 10^{5}$
$1 \leq M \leq 10^{9}$
$2 \leq a_{i} \leq 10^{9}$
$a_{i}$ is an even number.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $M$ 
 $a_{1}$   $a_{2}$   $. . .$   $a_{N}$

Output

Print the number of semi-common multiples of $A$ among the integers between $1$ and $M$ (inclusive).

X=a_i*(p+0.5)可以看作是X=a_i/2*(2p+1)，令b_i=a_i/2的话，那么显然X满足X%b_i==0且X/b_i是个奇数。

令g=lcm(b₁,b₂...b_n)的话，满足条件的数只可能是k*g，假设g不满足题意那么k*g也不会满足题意（g不满足，即存在一个b使得g/b是偶数，那显然k*g/b也是偶数，也不符合）。

假设g满足题意那么只有在k为奇数得情况下k*g满足题意，这时候统计下小于等于M且满足上述条件的数即可。

还要注意求lcm得过程可能会爆LL，为此只要当前的lcm>M那么答案显然就是零了，特判下。

这种数学规律题神烦，代码很丑= =

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 
 5 LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
 6 LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
 7 LL N,M,a[100010];
 8 int main(){
 9     cin>>N>>M;
10     LL g=1,ok=1;
11     for(int i=1;i<=N;++i){
12         cin>>a[i];
13         a[i]/=2;
14         if(i==1)g=a[i];
15         g=lcm(g,a[i]);
16         if(g>M)ok=0;
17     }
18     for(int i=1;i<=N;++i){
19         if(g/a[i]%2==0){ok=0;break;}
20     }
21     if(!ok){
22         cout<<0<<endl;
23         return 0;
24     }
25     LL ans=0;
26     LL b=M/g;
27     ans=b/2;
28     if(b&1)ans++;
29     cout<<ans<<endl;
30     return 0;
31 }