「樓下一個男人病得要死，那間隔壁的一家唱著留聲機，對面是弄孩子。樓上有兩人狂笑；還有打牌聲。河中的船上有女人哭著她死去的母親。人類的悲歡並不相通，我只覺得他們吵鬧。」
把a和b看成二進位制數處理，不難發現只要a，b某位都是1我們就有辦法把它消掉，否則答案該位一定是a+b（0，1）該位的值
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
int a,b;
cin>>a>>b;
int res=0;
for(int i=30;i>=0;i--)
if(!(a>>i&1)&&(b>>i&1)||(a>>i&1)&&!(b>>i&1))
res+=1<<i;
cout<<res<<'\n';
}
return 0;
}
我們只要讓g[1][2]和g[2][1]的值相等並且不等於g[n][n-1]和g[n-1][n]的值即可，最多操作3步。
懶得想了，直接列舉( 2 4 = 16 2^4=16 24=16)，應該有更好寫的寫法。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=210;
char g[N][N];
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>g[i]+1;
if(g[1][2]=='0'&&g[2][1]=='0'&&g[n][n-1]=='0'&&g[n-1][n]=='0')
cout<<2<<'\n'<<1<<' '<<2<<'\n'<<2<<' '<<1<<'\n';
else if(g[1][2]=='1'&&g[2][1]=='0'&&g[n][n-1]=='0'&&g[n-1][n]=='0')
cout<<1<<'\n'<<2<<' '<<1<<'\n';
else if(g[1][2]=='0'&&g[2][1]=='1'&&g[n][n-1]=='0'&&g[n-1][n]=='0')
cout<<1<<'\n'<<1<<' '<<2<<'\n';
else if(g[1][2]=='1'&&g[2][1]=='1'&&g[n][n-1]=='0'&&g[n-1][n]=='0')
cout<<0<<'\n';
else if(g[1][2]=='0'&&g[2][1]=='0'&&g[n][n-1]=='1'&&g[n-1][n]=='0')
cout<<1<<'\n'<<n-1<<' '<<n<<'\n';
else if(g[1][2]=='1'&&g[2][1]=='0'&&g[n][n-1]=='1'&&g[n-1][n]=='0')
cout<<2<<'\n'<<2<<' '<<1<<'\n'<<n<<' '<<n-1<<'\n';
else if(g[1][2]=='0'&&g[2][1]=='1'&&g[n][n-1]=='1'&&g[n-1][n]=='0')
cout<<2<<'\n'<<2<<' '<<1<<'\n'<<n<<' '<<n-1<<'\n';
else if(g[1][2]=='1'&&g[2][1]=='1'&&g[n][n-1]=='1'&&g[n-1][n]=='0')
cout<<1<<'\n'<<n<<' '<<n-1<<'\n';
else if(g[1][2]=='0'&&g[2][1]=='0'&&g[n][n-1]=='0'&&g[n-1][n]=='1')
cout<<1<<'\n'<<n<<' '<<n-1<<'\n';
else if(g[1][2]=='1'&&g[2][1]=='0'&&g[n][n-1]=='0'&&g[n-1][n]=='1')
cout<<2<<'\n'<<1<<' '<<2<<'\n'<<n<<' '<<n-1<<'\n';
else if(g[1][2]=='0'&&g[2][1]=='1'&&g[n][n-1]=='0'&&g[n-1][n]=='1')
cout<<2<<'\n'<<1<<' '<<2<<'\n'<<n-1<<' '<<n<<'\n';
else if(g[1][2]=='1'&&g[2][1]=='1'&&g[n][n-1]=='0'&&g[n-1][n]=='1')
cout<<1<<'\n'<<n-1<<' '<<n<<'\n';
else if(g[1][2]=='0'&&g[2][1]=='0'&&g[n][n-1]=='1'&&g[n-1][n]=='1')
cout<<0<<'\n';
else if(g[1][2]=='1'&&g[2][1]=='0'&&g[n][n-1]=='1'&&g[n-1][n]=='1')
cout<<1<<'\n'<<1<<' '<<2<<'\n';
else if(g[1][2]=='0'&&g[2][1]=='1'&&g[n][n-1]=='1'&&g[n-1][n]=='1')
cout<<1<<'\n'<<2<<' '<<1<<'\n';
else
cout<<2<<'\n'<<1<<' '<<2<<'\n'<<2<<' '<<1<<'\n';
}
return 0;
a
b
c
d
e
f
→
(
e
d
c
b
)
a
b
c
d
e
f
→
e
d
c
b
a
b
c
d
e
f
(
e
d
c
b
a
)
→
e
d
c
b
a
b
c
d
e
f
e
d
c
b
a
(
b
c
d
e
)
abcdef \to (edcb)abcdef\to edcbabcdef(edcba)\to edcbabcdefedcba(bcde)
abcdef→(edcb)abcdef→edcbabcdef(edcba)→edcbabcdefedcba(bcde)
只要三步直接搞出來，可以配合程式碼和上述例子食用
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int main()
{
IO;
int T=1;
//cin>>T;
while(T--)
{
string s;
cin>>s;
int n=s.size();
cout<<3<<'\n';
cout<<"L "<<n-1<<'\n';
cout<<"R "<<n-1<<'\n';
cout<<"R "<<2*n-1<<'\n';
}
return 0;
}
六個方向分別讓座標的變化：
c
1
:
(
x
+
1
,
y
+
1
)
c_1:(x+1,y+1)
c1:(x+1,y+1)
c
2
:
(
x
,
y
+
1
)
c_2:(x,y+1)
c2:(x,y+1)
c
3
:
(
x
−
1
,
y
)
c_3:(x-1,y)
c3:(x−1,y)
c
4
:
(
x
−
1
,
y
−
1
)
c_4:(x-1,y-1)
c4:(x−1,y−1)
c
5
:
(
x
,
y
−
1
)
c_5:(x,y-1)
c5:(x,y−1)
c
6
:
(
x
+
1
,
y
)
c_6:(x+1,y)
c6:(x+1,y)
不難發現操作
c
2
+
c
6
=
c
1
c_2+c_6=c_1
c2+c6=c1、
c
3
+
c
5
=
c
4
c_3+c_5=c_4
c3+c5=c4
因此從兩方面考慮是否使用
c
1
c_1
c1和
c
4
c_4
c4操作
如果不使用那麼只通過單獨進行橫座標±1和縱座標±1到達目的地直接算即可。
如果使用那麼首先使得最終向x座標和向y座標移動的步數（dx=dy）相等，於是考慮先通過橫座標±1或者縱座標±1操作使最終dx=dy，然後再通過
c
1
c_1
c1或者
c
4
c_4
c4操作使之到達目的地。
不過注意等效操作
c
2
+
c
6
=
c
1
c_2+c_6=c_1
c2+c6=c1、
c
3
+
c
5
=
c
4
c_3+c_5=c_4
c3+c5=c4取代價更小的。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll c[10];
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
ll x,y;
cin>>x>>y;
for(int i=1;i<=6;i++) cin>>c[i];
ll res=8e18;ll now=0;
// +x 6
// -x 3
// +y 2
// -y 5
// 不用c1和c4
if(x>=0&&y>=0)
now=c[6]*x+c[2]*y;
else if(x>=0&&y<0)
now=c[6]*x+c[5]*(-y);
else if(x<0&&y>=0)
now=c[3]*(-x)+c[2]*y;
else
now=c[3]*(-x)+c[5]*(-y);
res=min(res,now);
// 使用c1和c4
if(x>y)
{
now=0;
now+=c[5]*(x-y);
if(x>=0) now+=min(c[1],c[2]+c[6])*x;
else now+=min(c[4],c[3]+c[5])*(-x);
res=min(res,now);
now=0;
now+=c[6]*(x-y);
if(y>=0) now+=min(c[1],c[2]+c[6])*y;
else now+=min(c[4],c[3]+c[5])*(-y);
res=min(res,now);
}
else
{
now=0;
now+=c[3]*(y-x);
if(y>=0) now+=min(c[1],c[2]+c[6])*y;
else now+=min(c[4],c[3]+c[5])*(-y);
res=min(res,now);
now=0;
now+=c[2]*(y-x);
if(x>=0) now+=min(c[1],c[2]+c[6])*x;
else now+=min(c[4],c[3]+c[5])*(-x);
res=min(res,now);
}
cout<<res<<'\n';
}
return 0;
}
吐槽一波，這題debug了半天竟然是上限搞小了，自己一般開
1
0
18
10^{18}
1018結果有資料的答案比該值還大，最終把最大值開到
8
×
1
0
18
8×10^{18}
8×1018才過的。。。
剛剛看了一波別人的題解，發現D題只需要把所有等效操作的代價取個最小值即可，沒必要這樣討論，嗨自己還是太菜了
這題好像是dp，以後回補的！
最近學業壓力有點重，而且快期中考試了。。。這週六還有校賽，希望能打出好成績。