Educational Codeforces Round 89 (Rated for Div. 2)重点：D. Two Divisors
虽然因为菜造成了这么慢的写完，但至少策略上没有什么问题，既然卡题那就做下一题，再卡就再换，虽然最后的时间都不够做这道D题了
A、Shovels and Swords
题意简单不表
菜是原罪，比赛的时候尝试了各种手段，各种方法
首先要求出x+y的最大值
可以列出等式
x + 2y <= a;
2x + y <= b;
由此可知3x+3y <= (a+b)
因此x+y <= (a+b)/3
到了这步我就不会了，感觉不是充要条件，当然事后题解是和a,b再取个最小值，但我当时真懵了，感觉搞不出充要证明
就换方法
于是乎我就通过推样例发现，本题的难点在于贪心一方是不一定能够得到最后答案的，那么如果能够将两个值变为相等的话，那么就有固定套路，如果不能变为相等，直接取最小，如果可以，就判断一下%3的情况，于是过了。
int n ;
int a,b;
int main(){
int _;
for(scanf("%d" , &_) ; _ ; _ --){
scanf("%d %d", &a , &b);
if(a > b )swap(a,b);
int x = b - a;
int y = min(x ,min(a,b/2));
b -= 2*y, a -= y;
if(b == a){
int q ;
if(a % 3 >= 2)q = 1;
else q = 0;
printf("%d\n",a / 3 * 2 + y + q);
}
else{
printf("%d\n" , y);
}
}
return 0;
}
int main(){
int _;
for(scanf("%d" ,&_); _ ;_ --){
int a,b;
scanf("%d %d" ,&a, &b);
int mini = min((a + b) / 3 , min(a,b));
cout << mini <<endl;
}
return 0;
}
B. Shuffle
题意：给你一个n,m,x。x代表初始位置，有n个数，m个区间，如果x在区间里，你可以将x替换成区间内的任意一个值，问你最后可能的最大范围是多少
思路：大致就是x在某个区间里，就将x扩大为这个区间，然后利用这个区间再更新
int main(){
int _;
for(scanf("%d" , &_) ; _ ; _ --){
int n , m , x , l ,r;
scanf("%d %d %d" ,&n , &x, &m);
int maxx = -1 , mini = 0x3f3f3f3f , flag = 0;
for(int i = 1; i <= m ; i ++){
scanf("%d %d",&l , &r);
if(flag){
if((l >= mini && l <= maxx)||(r >=mini && l <= maxx)){
maxx = max(r, maxx);
mini = min(l, mini);
}
}
if(l <= x && r >= x){
maxx = max(r, maxx);
mini = min(l, mini);
flag = 1;
}
}
if(!flag)puts("1");
else{
cout << maxx - mini + 1 << "\n";
}
}
}
C. Palindromic Paths
题意：你从1，1点到n，m点的所有路径必须是回文路径
思路：类似于一个bfs的思想，第一步和最后一步的数字必须相同，第二步和倒数第二步…以此类推，再将里面的值肯定是取数量最大的值，改变数量最小的值。
int a[33][33];
int dx[2] = {1,0},
dy[2] = {0,1};
int v[100][3];
int main(){
int _;
for(scanf("%d" , &_) ; _ ; _ --){
int n , m;
memset(v,0,sizeof v);
scanf("%d %d" ,&n ,&m );
for(int i = 1; i <= n ; i++){
for(int j = 1; j <= m ; j ++){
scanf("%d",&a[i][j]);
v[abs(i-1) + abs(j-1)][a[i][j]] ++;
}
}
int ans = 0;
for(int i = 0 ,j = n+m-2 ; i < j ; i ++ , j --){
// int maxx = max(v[i][0]+v[j][0],v[i][1] + v[j][1]);
ans += min(v[i][0]+v[j][0],v[i][1] + v[j][1]);
}
printf("%d\n",ans);
}
}
D. Two Divisors
来到重点题，题意好像还是很轻松明白的
重要的是这题的思路证明。
首先对于这一题的求解，想要寻找问题的突破口，于是就必须看给出的条件，他d1，d2的限制是在每一个a[i]的所有因子里，再加上 他的每一个a[i] 是在1e7里的，我们很容易想到一个n*sqrt(A)的做法，将每一个数的因子找出来，然后找两个符合的，我们这时候会发现n是5e5而sqrt(A)大约在5e3左右综合复杂度大约在1e9左右，是不能跑过cf的样例的。到了这里我们会继续看，其实对于d1+d2想要和a[i]取到一个gcd为1，我们可以这样，感性认知一下，对于每一个数分解成一个数乘以另一个数，这俩个数相加一定会符合gcd为1
下面给出证明
- 假设A分解成p1c1 p2c2 p3c3…
将他分成
x = p1c1p2c2…pkck ,
y = pk+1ck+1pk+2ck+2…
因为xy = n
那么
gcd(x+y,n) = gcd(x+y,xy) = gcd(x+y,x)*gcd(x+y,y) = gcd(x,y)*gcd(y,x) = 1
命题得证
(这个格式用法好迷啊=-=不会用）
那么现在我们只需要维护1e7以内所有数的最小公因数，并且只要为两个就可以输出，否则就是-1，两种方法（实际上还有很多种随你用，线性筛蛮快的）
int n;
int a[N];
int v[10000007];
int main(){
for(int i = 2 ; i <= M ; i ++){
if(v[i] == 0){
v[i] = i;
for(int j = i + i ; j <= M ; j +=i){
v[j] = i;
}
}
}
while(~scanf("%d" , &n)){
for(int i = 1; i <= n ; i ++){
scanf("%d" , &a[i]);
}
VI G[2];
for(int i = 1; i <= n ; i ++){
int res = a[i] , lin = v[res];
while(res % lin == 0 )res /= lin;
if(res > 1){
G[0].pb(res);
G[1].pb(a[i]/res);
continue;
}
G[0].pb(-1);
G[1].pb(-1);
}
for(auto x : G[0])printf("%d ",x);puts("");
for(auto x : G[1])printf("%d ",x);puts("");
}
return 0;
}
int n;
int a[N];
int v[10000007],prime[10000007];
int main(){
int m = 0;
for(int i = 2 ; i <= M ; i ++){
if(v[i] == 0){
v[i] = i;
prime[++m] = i;
}
for(int j = 1 ; j <= m ;j ++){
if(prime[j]>v[i]||prime[j]>M/i)break;
v[i*prime[j]] = prime[j];
}
}
// for(int i = 1; i <= 100; i ++)cout << prime[i] <<" ";puts("");
while(~scanf("%d" , &n)){
for(int i = 1; i <= n ; i ++){
scanf("%d" , &a[i]);
}
VI G[2];
for(int i = 1; i <= n ; i ++){
int res = a[i] , lin = v[res];
while(res % lin == 0 )res /= lin;
if(res > 1){
G[0].pb(res);
G[1].pb(a[i]/res);
continue;
}
G[0].pb(-1);
G[1].pb(-1);
}
for(auto x : G[0])printf("%d ",x);puts("");
for(auto x : G[1])printf("%d ",x);puts("");
}
return 0;
}
投递芯原股份等公司10个岗位 >
