并没有参加。做做里面的题目而已。
每次给定 \(a,b\)，求出 $(a \(\operatorname{xor}\) x)+(b \(\operatorname{xor}\) x)$ 的最小值。
将其拆位。假设是两个一，那么我们考虑这一位 \(xor 1\)。对于其他情况，我们是不需要 \(xor 1\) 的，因为这不会使答案更差。
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
bool bit(int s,int i) {return (1ll<<i)&s;}
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<‘0‘||c>‘9‘) {if(c==‘-‘) f=-1; c=getchar();}
while(c>=‘0‘&&c<=‘9‘) {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
signed main() {
int T=read();
rep(t,1,T) {
int a=read(), b=read(), x=0;
rep(i,0,30) {
if(bit(a,i)&&bit(b,i)) x+=(1ll<<i);
}
printf("%lld\n",(a^x)+(b^x));
}
return 0;
}
给定一个网格图，有点权 \(0,1\)。请你反转最多 \(2\) 个点的点权，使得没有任何一条从 \((1,1)\) 到 \((n,n)\) 的路径上的点权全部相同。
\(f(x,y,0/1)\) 代表若终点为 \((x,y)\)，是否有路径点权为 \(0/1\) 的路径。现在分几种情况。
第一，\(f(n,n,0)=f(n,n,1)=1\)，我们让 \((n,n-1), (n-1,n)\) 变为 \(0\), (1,2), (2,1)$ 全部变为 \(1\) 即可。（可以证明这样子只会用两次反转机会）。
第二，\(f(n,n,0)=0, f(n,n,1)=1\)，若 \((1,2), (2,1)\) 中没有 \(0\)，那么我们把 \((n,n-1), (n-1,n)\) 全部变为 \(0\) 即可；否则我们把 \((1,2), (2,1)\) 全部变为 \(0\)。
第三，\(f(n,n,0)=1, f(n,n,1)=0\)，和上面反一下即可。
第四，\(f(n,n,0)=f(n,n,1)=0\)，直接输出 \(0\)。
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=209;
int T,n,cnt[2][2];
char c[N][N];
bool f[N][N][2];
vector<pair<int,int> >ans;
void chp(int x,int y,int val) {
if(c[x][y]!=val+‘0‘) ans.push_back(make_pair(x,y));
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
rep(i,1,n) scanf("%s",c[i]+1);
f[1][1][0]=f[1][1][1]=1;
rep(i,1,n) rep(j,1,n) if(i!=1||j!=1) {
f[i][j][1]=(f[i-1][j][1]&&c[i-1][j]!=‘0‘)||(f[i][j-1][1]&&c[i][j-1]!=‘0‘);
f[i][j][0]=(f[i-1][j][0]&&c[i-1][j]!=‘1‘)||(f[i][j-1][0]&&c[i][j-1]!=‘1‘);
}
memset(cnt,0,sizeof(cnt));
cnt[0][c[1][2]-‘0‘]++, cnt[0][c[2][1]-‘0‘]++, cnt[1][c[n][n-1]-‘0‘]++, cnt[1][c[n-1][n]-‘0‘]++;
ans.clear();
if(f[n][n][0]&&f[n][n][1]||cnt[0][0]==1&&cnt[0][1]==1&&cnt[1][0]==1) chp(n,n-1,0), chp(n-1,n,0), chp(1,2,1), chp(2,1,1);
else if(f[n][n][1]&&!f[n][n][0]) {
if(c[1][2]!=‘0‘&&c[2][1]!=‘0‘) chp(n,n-1,0), chp(n-1,n,0);
else chp(1,2,0), chp(2,1,0);
} else if(f[n][n][0]&&!f[n][n][1]) {
if(c[1][2]!=‘1‘&&c[2][1]!=‘1‘) chp(n,n-1,1), chp(n-1,n,1);
else chp(1,2,1), chp(2,1,1);
}
printf("%d\n",(int)(ans.size()));
if(ans.size()) rep(i,0,ans.size()-1) printf("%d %d\n",ans[i].first,ans[i].second);
}
return 0;
}
生草结论构造题。
可以证明，输出
R n-1
L n
L 2
即可。
其实这道题并不难。首先发现我们可以通过对每一个 \(c_i\) 都松弛一下的方法，之后就可以直接贪心。于是我们直接先松弛 \(c_i=\min(c_i,c_{i-1}+c_{i+1})\)。然后我们可以直接贪心取边。尽可能地选择 \(c_4\) 和 \(c_1\) 即可。注意分类讨论。
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<‘0‘||c>‘9‘) {if(c==‘-‘) f=-1; c=getchar();}
while(c>=‘0‘&&c<=‘9‘) {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int t,x,y,c[9];
signed main() {
t=read();
while(t--) {
x=read(), y=read();
rep(i,1,6) c[i]=read();
rep(i,1,6) c[i]=min(c[i],c[i==1 ? 6 : i-1]+c[i==6 ? 1 : i+1]);
if(x>0&&y>0&&x>=y) printf("%lld\n",y*c[1]+(x-y)*c[6]);
else if(x>0&&y>0&&x<y) printf("%lld\n",x*c[1]+(y-x)*c[2]);
else if(x<0&&y<0&&x>=y) printf("%lld\n",-x*c[4]+(x-y)*c[5]);
else if(x<0&&y<0&&x<y) printf("%lld\n",-y*c[4]+(y-x)*c[3]);
else if(x<=0&&y>=0) printf("%lld\n",-x*c[3]+y*c[2]);
else if(x>=0&&y<=0) printf("%lld\n",-y*c[5]+x*c[6]);
}
return 0;
}
【Codeforces】CF Round #676 (Div. 2)
原文：https://www.cnblogs.com/TetrisCandy/p/13875435.html