Codeforces Round #432 (Div. 2)

A Arpa and a research in Mexican wave

题意:告诉你某些人人站起来和坐下来的时间,输出某时刻还站着的有多少人

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int n,k,t;
int main()
{
scanf("%d%d%d",&n,&k,&t);
if(t<=k){
printf("%d\n",t);
}else if(t>k && t<=n){
printf("%d\n",k);
}else{
printf("%d\n",k-(t-n));
}
return 0;
}

B Arpa and an exam about geometry

题意:给三个点,问能不能旋转一个角度使得三个点的位置顺移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<ll ,ll > a,b,c;
ll myabs(ll x){
return x<0?-x:x;
}
ll mysqrt(ll x){return x*x;}
ll dis(pair<ll ,ll > A,pair<ll ,ll > B)
{
return mysqrt(A.first-B.first)+mysqrt(A.second-B.second);
}
int main()
{
scanf("%lld%lld%lld%lld%lld%lld",&a.first,&a.second,&b.first,&b.second,&c.first,&c.second);
if(dis(a,b)!=dis(b,c)){
printf("No\n");
}else{
if((a.second-c.second)*(a.first-b.first)==(a.second-b.second)*(a.first-c.first)) printf("No\n");
else printf("Yes\n");
}
return 0;
}

C Five Dimensional Points

题意:五维空间里给出一些点,称一个点$V$存在两点$X,Y$使得$\overrightarrow {VX}$和$\overrightarrow{VY}$成锐角时是坏的,否则是好的。输出好的点是哪些

p.s.其实$n>11$的时候是直接可以输出0的。因为对于二维平面上,能够达到和一个点互成$90^{\circ}$的最多有4个点,然后扩展到五维空间最多有$10$个点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-6;
const int maxn=1000+5;
const double pi=3.1415926535898;
struct point{
int a,b,c,d,e;
point(int a=0,int b=0,int c=0,int d=0,int e=0): a(a),b(b),c(c),d(d),e(e) {}
};
point p[maxn];
int n;
double myabs(double x){
return x<0?-x:x;
}
point Del(point A,point B){
point C=point(A.a-B.a,A.b-B.b,A.c-B.c,A.d-B.d,A.e-B.e);
return C;
}
int vecmul(point A,point B){
int Res=A.a*B.a+A.b*B.b+A.c*B.c+A.d*B.d+A.e*B.e;
return Res;
}
double lenth(point A){
return sqrt(myabs((double)vecmul(A,A)));
}
double ang(point A,point B){
return acos((double)vecmul(A,B)/(lenth(A)*lenth(B)));
}
vector<int > good;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d%d%d",&p[i].a,&p[i].b,&p[i].c,&p[i].d,&p[i].e);
}
for(int i=1;i<=n;i++){
bool gd=true;
for(int j=1;j<=n;j++){
if(j==i) continue;
for(int k=j+1;k<=n;k++){
if(pi/2-ang(Del(p[i],p[j]),Del(p[i],p[k]))>eps)
{gd=false;break;}
}if(!gd) break;
}
if(gd) good.push_back(i);
}
printf("%d\n",good.size());
for(int i=0;i<(int)good.size();i++) printf("%d ",good[i]);
puts("");
return 0;
}

D Arpa and a list of numbers

题意:给你一个序列,你可以选择花费$x$将它删除,或者花费$y$将它$+1$,要求你花费最小的代价使得整个数列的最大公约数大于$1$。

考虑枚举一个最大的公因子,使得整个序列都更改为这个数的倍数,这样需要枚举的质因子最多只有$\frac{n}{ln_n}$个。然后考虑统计答案,对于一个因子$G$,区间$((i-1)\times G,i\times G]$而言,我们发现对于较接近且比它小的数我们可以不断$+1$到$i\times G$,其余删除。于是在一个区间内产生了一个分界点。若能在$O(1)$这样的时间内确定分界点的话自然是能保证复杂度的。

假定这个分界点为$D$,有

$x \leq ((i\times G)-D)\times y$

移项有

$\frac{x}{y} \leq (i\times G)-D$

即有

$D \leq (i\times G)-\frac{x}{y}$下取整即可。

时间复杂度,$\mathcal O(\frac{n}{ln_n}\times log_{n\times ln_n})$,就是说一共有$\frac{n}{ln_n}$个质因数要枚举,然后你枚举他们小于$n$的倍数,简化来看就是枚举$x\leq n$的小于$n$的$x$的倍数,因为每个数都会被它的约数给算一次所以是$\mathcal O(nlog_n)$的,带回原式$x=\frac{n}{ln_n}$,即为$O(\frac{n}{ln_n} \times log_{n \times ln_n})$,看作$O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=5*100000+5;
const ll UP=2000000+5;
typedef long long ll;
ll n;
ll x,y;
bool vis[UP];
vector<ll > prim;
ll sum[UP];
ll cnt[UP],a[maxn];
ll gcd(ll A,ll B)
{
return B==0?A:gcd(B,A%B);
}
void seive()
{
for(ll i=2;i<UP;i++){
if(!vis[i])
prim.push_back(i);
for(ll j=0;j<(ll)prim.size();j++){
if(i*prim[j]>=UP) break;
vis[i*prim[j]]=1;
if(i%prim[j]==0) break;
}
}
}
int main()
{
scanf("%lld%lld%lld",&n,&x,&y);
ll ones=0,mx=0;
for(ll i=1;i<=n;i++) {
scanf("%lld",&a[i]);mx=max(mx,a[i]);ones+=(a[i]==1);
cnt[a[i]]++;
}
for(ll i=0;i<UP;i++) sum[i]=sum[i-1]+cnt[i]*i,cnt[i]+=cnt[i-1];
seive();
ll gd=a[1];
for(ll i=2;i<=n;i++) gd=gcd(gd,a[i]);
if(gd>1) printf("0\n");
else{
if(ones==n){
printf("%lld\n",min(x*n,y*n));
}else{
ll Ans=LLONG_MAX;
for(ll i=0;i<(ll)prim.size();i++){
if(prim[i]>mx) break;
ll p=prim[i];
ll now=0;
for(ll j=1;j<=(mx/p)+1;j++){
ll lef=(j-1)*p,rgh=j*p;
ll mid=max(lef,(ll)(rgh-(x/y)-1));
assert(mid>=lef);
now+=x*(cnt[mid]-cnt[lef])+
((cnt[rgh]-cnt[mid])*rgh-(sum[rgh]-sum[mid]))*y;
}
Ans=min(Ans,now);
}
printf("%lld\n",Ans);
}
}
return 0;
}

E Arpa and a game with Mojtaba

题意:给你一个序列,要求每次操作是选择一个质数$p$和一个正整数$k$,将序列里每个数除以$p^k$,然后不能操作的人输。

考虑对当前序列定义一些状态,然后求这些状态的$Nim$和,然后判断先手是否胜利。由于每个质因子它被除都是互相独立的,因而可以将序列看成很多质因子(每个质因子对应一堆石子),然后对于一个质因子它的状态我们只需要表示出这个质因子它在序列当中的整除的状态即可。

考虑$p$的一个状态$mask$,然后第$i$位为1表示这个序列中有数能被$p^i$整除且这个数不整除$p^{i+1}$(就是说恰好能达到$p^i$)。

然后考虑后继状态,当我们除掉一个$p^i$时,状态变为(mask>>i)|(mask&((1<<(i-1))-1)),右移$i$位是表示能整除$p^i$的全部除掉,或上是表示前面的位没有动再还原回去。对于这些后继状态求所有状态的$mex$值即为这个状态的$grundy$值了。对于所有序列中的质因子的$grundy$值求$nim$和,判断是否为必胜态即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
const int maxn=100+5;
int a[maxn],n;
map<int ,int > frc;
map<int ,int > divisor(int x)
{
map<int ,int > ret;ret.clear();
for(int i=2;i*i<=x;i++){
while(x%i==0){
ret[i]++;
x/=i;
}
}
if(x!=1) ret[x]++;
return ret;
}
map<int ,int > sts;
map<int ,int > grd;
int grundy(int mask)
{
if(mask==0) return grd[mask]=0;
if(grd.find(mask)!=grd.end()) return grd[mask];
int maxbit=0,tmp=mask;
while(tmp>0){
tmp>>=1;
maxbit++;
}
set<int > vis;vis.clear();
for(int i=1;i<=maxbit;++i){
vis.insert(grundy((mask>>i)|(mask&((1<<(i-1))-1))));
}
int mex=0;
while(vis.find(mex)!=vis.end()) mex++;
return grd[mask]=mex;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
frc=divisor(a[i]);
for(map<int ,int >::iterator ite=frc.begin();ite!=frc.end();++ite)
{
int k=ite->second;
sts[ite->first]|=(1<<(k-1));
}
}
int Ans=0;
for(map<int ,int >::iterator ite=sts.begin();ite!=sts.end();++ite)
{
Ans^=grundy(ite->second);
}
if(Ans==0) printf("Arpa\n");
else printf("Mojtaba\n");
return 0;
}