题目链接:http://codeforces.com/contest/1047
A Little C Loves 3 I
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int main()
{
cin>>n;
if(n%3==0){
cout<<"1 1 "<<n-2<<endl;
}
else if(n%3==1){
cout<<"1 2 "<<n-3<<endl;
}
else if(n%3==2){
cout<<"1 2 "<<n-3<<endl;
} return 0;
}
B Cover Points
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+9;
int n;
struct node{
int x,y;
friend bool operator <(node a,node b){
return a.x+a.y>b.x+b.y;
}
}a[maxn];
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1);
cout<<a[1].x+a[1].y<<endl;
return 0;
}
AB简单不表
C Enlarge GCD
题意:删一些数让原序列的gcd变大,不能变大则输出-1
解题思路:看到1e7其实已经想到标记数组的埃式筛法,也想到了除以他们的最大公约数,但是忽略了计算机思维中的通过筛法更新出最多的拥有共同公因数的最大值,感觉很不得劲,怅然若失,就是那种自己能写出来,却无从下手。还是那个教训,将总问题分解成一个个子问题,仔细思考一一解决。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+9;
const int N=1e7+5e6+9;
int n;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int a[maxn];
int f[N],vis[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int ans=gcd(a[1],a[2]);
for(int i=3;i<=n;i++){
ans=gcd(ans,a[i]);
}
for(int i=1;i<=n;i++){
f[a[i]/ans]++;
}
int maxx=0;
for(int i=2;i<=N;i++){
if(vis[i])continue;
int cnt=0;
for(int j=i;j<=N;j+=i){
vis[j]=1;
cnt+=f[j];
}
maxx=max(cnt,maxx);
}
printf("%d\n",maxx?n-maxx:-1);
return 0;
}
D Little C Loves 3 II
题意:两个相对格可以走日或者中间 隔两个格子。给你n,m,问最多有多少相对格子。
解题思路:好像就是手推,没啥其他的了,之前好像做过类似题目,不表了。