2018.9.21 Codeforces Round #511(Div.2)

只写了AB，甚至还WA了一次A题，暴露了蒟蒻的本质=。=

感觉考的时候有好多正确或和正解有关的思路，但是就想不出具体的解法或者想的不够深(长)(怕不是过于鶸)

话说CF的E题怎么都这么清奇=。=

A.Little C Loves 3 I

随便拆一下就好了，大概全场就我一个心太急写挂了一次TAT

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int main ()
 6 {
 7     long long n; scanf("%lld",&n);
 8     if(n%3==2) printf("%lld 1 2",n-3);
 9     else printf("%lld 1 1",n-2);
10     return 0;
11 }

View Code

B.Cover Points

初中数学知识(?)或者随手推一推，水水(我**就会这俩水题)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int main ()
 6 {
 7     long long n,m,p,ans=0;
 8     scanf("%lld",&n);
 9     for(int i=1;i<=n;i++)
10         scanf("%lld%lld",&m,&p),ans=max(m+p,ans);
11     printf("%lld",ans);
12     return 0;
13 }

View Code

C.Enlarge GCD

题目并不难......

然而被这题确实没做出来，调的时候也调了半天，我好菜啊=。=

首先我们求一个全序列的gcd，然后从每个数中除掉它，剩下的数肯定是互质的，也就是说现在我们要从这些剩下的数中删掉最少的数使得他们不互质。我们将每个数分解质因数，统计出现次数最多的质因数(出现在一个数里算是一次)，保留下它肯定就是最优的，于是用总数减去出现次数更新答案即可

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=300005,M=15000005;
 6 int mpr[M],pri[M],cnt[M],num[N];
 7 int n,g,maxx,ans=2e9;
 8 int gcd(int a,int b)
 9 {
10     return b?gcd(b,a%b):a; 
11 }
12 inline int maxi(int a,int b)
13 {
14     return a>b?a:b;
15 }
16 inline int mini(int a,int b)
17 {
18     return a<b?a:b;
19 }
20 int main ()
21 {
22     scanf("%d",&n);
23     for(register int i=1;i<=n;i++)
24     {
25         scanf("%d",&num[i]);
26         g=gcd(g,num[i]),maxx=maxi(maxx,num[i]);
27     }
28     mpr[1]=1; 
29     for(register int i=2,sz=0;i<=maxx+1;i++)
30     {
31         if(!mpr[i]) pri[++sz]=mpr[i]=i;
32         for(register int j=1;j<=sz&&i*pri[j]<=maxx+1;j++)
33         {
34             mpr[i*pri[j]]=i;
35             if(!(i%pri[j])) break;
36         }
37     }
38     for(register int i=1;i<=n;i++)
39     {
40         int t=num[i]/g;
41         for(register int j=1;pri[j]*pri[j]<=t;j++)
42             if(!(t%pri[j]))
43             {
44                 ans=mini(ans,n-(++cnt[pri[j]]));
45                 while(!(t%pri[j])) t/=pri[j];
46             }
47         if(t>1) ans=mini(ans,n-(++cnt[t]));
48     }
49     if(ans>=n) ans=-1;
50     printf("%d",ans);
51     return 0;
52 }

View Code

D.Little C Loves 3 II

这题毒瘤啊，各种分类海星

比赛的时候怎么就没玩玩小数据呢，明明能A的TAT

首先的首先，要考虑$n*m$的奇偶性，不解释

然后我们可以发现，有些$n*m$是可以填满且无法被其他的$n*m$表示出来的，它们分别是

$1*6$,$2*4$,$2*5$

所以说我们可以考虑用这些块填满棋盘，最后小块单独处理

那么没什么可说的，我们开始讨论吧=。=

1.$n,m$都为偶数

这种情况只有$(2,2)$填不满，别的都可以填满

2.$n,m$都为奇数

有一种特殊情况是有一边的长度为$1$，这种情况要以$1*6$这种填满的填法特殊考虑(代码中的$line$数组就是干这个用的)，易证其余情况都是正好剩一个

3.$n,m$一偶一奇

同理于上，根据那三种填满情况特殊考虑，发现我们不能用$4,5,6$凑出来的数只有$1,2,3,7$，$1,2$的情况我们讨论过了，$3,7$特殊讨论一下，然后剩下的肯定都能填满

然后终于做完辣=。=

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 long long line[6]={0,1,2,3,2,1};
 6 long long n,m;
 7 int main ()
 8 {
 9     scanf("%lld%lld",&n,&m);
10     if(n>m) swap(n,m);
11     if(n==1) printf("%lld",m-line[m%6]);
12     else if(!(n&1)&&!(m&1)) (n==2&&m==2)?printf("0"):printf("%lld",n*m);
13     else if((n&1)&&(m&1)) printf("%lld",n*m-1);
14     else
15     {
16         if(n&1) swap(n,m);
17         if(n==2&&m==3) printf("4");
18         else if(n==2&&m==7) printf("12");
19         else printf("%lld",n*m);
20     }
21     return 0;
22 }

View Code

E.Region Separation

至今没看懂题意，咕咕咕