<span>Codeforces #676 (div 2) A - D 题解</span>
<button class="accordion">吐槽
分类讨论 + 构造大赛（雾
B分类讨论的时候不小心把 0 打成 1 FST，D初值设小不然 1h 就过了，直接把上分场整成了掉分场，枯了。
A - XORwice
题目大意
给你 \(a\) 和 \(b\)，求 \((a \oplus x) + (b \oplus x)\) 的最小值。
解题思路
考虑怎么构造 \(x\) 才能使要求的值最小。
对于每一位，如果 \(a,b\) 都是 \(0\) ，那么当 \(x\) 的这一位为 \(0\) 时，异或后的这一位一定是零，肯定最优。
如果 \(a,b\) 一个是 \(1\)，一个是 \(0\) ，那么当 \(x\) 的这一位不论是 \(0\) 还是 \(1\) ，异或后一定是一 \(0\) 一 \(1\) ，不妨就认为 \(x\) 的这一位是 \(0\)。
如果 \(a,b\) 都是 \(1\) ，那么当 \(x\) 的这一位为 \(1\) 时，异或后的这一位一定是零，肯定最优。
简单观察就能发现，上面的构造其实就是 \(a \land b\)。
所以答案就是 \((a \oplus (a \land b)) + (b \oplus (a \land b))\)
Code
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define int long long
using namespace std;
int read()
{
int ans=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
return ans*f;
}
int t,a,b;
signed main()
{
t=read();
while(t--)
{
a=read();b=read();
printf("%lld\n",(a^(a&b))+(b^(a&b)));
}
return 0;
}
B - Putting Bricks in the Wall
题目大意
给定一个 \(01\) 矩阵，一个人会从 \((1,1)\) 走到 \((n,n)\)，他途中会只走 \(0\) 或直走 \(1\)。
现在可以将做多两个格子 \(01\) 反转，使得这个人无法找到一条可行的路径
解题思路
显然如果 \((2,1),(1,2)\) 两个格子的数字与 \((n,n-1),(n-1,n)\) 的数字不同，就一定没有可行路径，因为路径必定经过这四个格子的其中两个。
所以分类讨论一下就好了，显然可以在两次反转内做到这件事。
Code
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define int long long
using namespace std;
int read()
{
int ans=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
return ans*f;
}
const int N=205;
int t,n;
char mmap[N][N];
signed main()
{
t=read();
while(t--)
{
n=read();
for(int i=1;i<=n;++i)
scanf("%s",mmap[i]+1);
if(mmap[1][2]=='0'&&mmap[2][1]=='0')
{
if(mmap[n][n-1]=='1'&&mmap[n-1][n]=='1')
printf("0\n");
else if(mmap[n][n-1]=='1')
printf("1\n%lld %lld\n",n-1,n);
else if(mmap[n-1][n]=='1')
printf("1\n%lld %lld\n",n,n-1);
else printf("2\n%lld %lld\n%lld %lld\n",n,n-1,n-1,n);
}
else if(mmap[1][2]=='0'&&mmap[2][1]=='1')
{
if(mmap[n][n-1]=='1'&&mmap[n-1][n]=='1')
printf("1\n%lld %lld\n",2,1);
else if(mmap[n][n-1]=='1')
printf("2\n%lld %lld\n%lld %lld\n",2,1,n-1,n);
else if(mmap[n-1][n]=='1')
printf("2\n%lld %lld\n%lld %lld\n",2,1,n,n-1);
else printf("1\n%lld %lld\n",1,2);
}
else if(mmap[1][2]=='1'&&mmap[2][1]=='0')
{
if(mmap[n][n-1]=='1'&&mmap[n-1][n]=='1')
printf("1\n%lld %lld\n",1,2);
else if(mmap[n][n-1]=='1')
printf("2\n%lld %lld\n%lld %lld\n",1,2,n-1,n);
else if(mmap[n-1][n]=='1')
printf("2\n%lld %lld\n%lld %lld\n",1,2,n,n-1);
else printf("1\n%lld %lld\n",2,1);
}
else
{
if(mmap[n][n-1]=='0'&&mmap[n-1][n]=='0')
printf("0\n");
else if(mmap[n][n-1]=='0')
printf("1\n%lld %lld\n",n-1,n);
else if(mmap[n-1][n]=='0')
printf("1\n%lld %lld\n",n,n-1);
else printf("2\n%lld %lld\n%lld %lld\n",n,n-1,n-1,n);
}
}
return 0;
}
C - Palindromifier
题目大意
给一个 \(n\) 个字符的字符串，每次操作可以选择将 \(2 \sim i\) 的字符反转并添加到字符串的前部或将 \(i \sim n-1\) 的字符串反转并添加到字符串的末尾。
在 \(30\) 次操作内使得这个字符串回文。
解题思路
个人觉得这个 \(30\) 挺误导人的。
因为可以 \(3\) 次操作就做到这件事。
-
把 \(2 \sim 2\) 反转并添加到字符串前部，这样假设原来字符串是 \(XOXXX...\) ，反转后就能得到 \(OXOXXX...\)
-
把 \(2 \sim n-1\) 反转并添加到字符串尾部，这样假设原来字符串是 \(OXOXXX...\)，那么反转后的字符串就是 \(OXOXXX......XXXOX\)，此时 \(2\sim n\) 已经回文。
-
把 \(n-1 \sim n-1\) 反转并添加到字符串尾部，这样假设原来字符串是 \(OXOXX......XXOX\)，那么反转后的字符串就是 \(OXOXX......XXOXO\)，显然回文。
（Ps：上述中的 \(O\) 为一固定字符，\(X\) 为任意字符，且 \(n\) 是每次操作后的字符串长度而非读入的字符串长度）
Code
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define int long long
using namespace std;
int read()
{
int ans=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
return ans*f;
}
const int N=1e5+5;
int n;
char s[N];
signed main()
{
scanf("%s",s+1);
n=strlen(s+1);
printf("3\n");
printf("L 2\n");n++;
printf("R 2\n");n+=n-2;
printf("R %lld\n",n-1);
return 0;
}
D - Hexagons
题目大意
有一个二元组 \((a,b)\) ，每次可以把这个二元组进行 \((a+1,b+1),(a,b+1),(a-1,b),(a-1,b-1),(a,b-1),(a+1,b)\) 的加减操作。
已知每种操作的代价（代价为正数），初始时的二元组为 \((0,0)\)，求把二元组变成 \((x,y)\) 需要的最小代价。
解题思路
显然分类讨论，通常可以分为三种情况：
-
\((x,y)\) 直接通过 \((a,b+1),(a-1,b),(a,b-1),(a+1,b)\) 加减到位。
-
先通过 \((a+1,b+1),(a-1,b-1)\) 把同时加减到 \((x,x)\)，再通过第一种情况加减到 \((x,y)\)。
-
先通过 \((a+1,b+1),(a-1,b-1)\) 把同时加减到 \((y,y)\)，再通过第一种情况加减到 \((x,y)\)。
这题初值要设到 \(2 \times 10^{18}\)，然后我习惯性的设成了 \(10^{18}\) 就没了qwq
Code
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define int long long
using namespace std;
int read()
{
int ans=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
return ans*f;
}
int t,x,y,C1,C2,C3,C4,C5,C6;
signed main()
{
t=read();
while(t--)
{
x=read();y=read();
C1=read();C2=read();C3=read();
C4=read();C5=read();C6=read();
int ans=1e19;
if(x==0&&y==0) ans=0;
else if(x<=0&&y<=0)
{
x=-x,y=-y;
ans=min(ans,x*C3+y*C5);
if(x>=y) ans=min(ans,y*C4+(x-y)*C3);
else ans=min(ans,x*C4+(y-x)*C5);
if(x>=y) ans=min(ans,x*C4+(x-y)*C2);
else ans=min(ans,y*C4+(y-x)*C6);
}
else if(x<=0&&y>=0)
{
x=-x;
ans=min(ans,x*C3+y*C2);
ans=min(ans,x*C4+(x+y)*C2);
ans=min(ans,y*C1+(x+y)*C3);
}
else if(x>=0&&y<=0)
{
y=-y;
ans=min(ans,x*C6+y*C5);
ans=min(ans,x*C1+(x+y)*C5);
ans=min(ans,y*C4+(x+y)*C6);
}
else
{
ans=min(ans,x*C6+y*C2);
if(x>=y) ans=min(ans,y*C1+(x-y)*C6);
else ans=min(ans,x*C1+(y-x)*C2);
if(x>=y) ans=min(ans,x*C1+(x-y)*C5);
else ans=min(ans,y*C1+(y-x)*C3);
}
printf("%lld\n",ans);
}
return 0;
}
paypal工作强度 6人发布
