^ & ^(位运算+思维)
比赛链接：https://acm.dingbacode.com/showproblem.php?pid=6702
题目大意
给定整数A，B，请求出C的最小值使得(A xor C)&(B xor C)的值最小。
若当C==0时(A xor C)&(B xor C)==0，请输出1。
思路
(A xor C)&(B xor C)=(A & B) xor C，再根据异或的特点可以知道 当C=A&B时(A xor C)&(B xor C)=0，即得到最小值。
别忘了特判输出 1 1 1的情况。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
int main()
{
int t;
cin>>t;
while(t--)
{
ll a,b;
cin>>a>>b;
ll c=a&b;
if(c==0) cout<<"1"<<endl;
else cout<<c<<endl;
}
return 0;
}
Shuffle Card(思维)
比赛链接：https://acm.dingbacode.com/showproblem.php?pid=6707
题目大意
给定
n
n
n张卡片，每张卡片上都有一个数字
a
i
a_i
ai?，
1
<
=
a
i
<
=
n
1<=a_i<=n
1<=ai?<=n，并且每一张卡片上的数字互不相同。一开始所有的卡片按照数字大小的顺序由小到大排列在桌上。
接下来会进行
m
m
m次操作，每次操作会把卡片
x
x
x(值为
x
x
x的卡片)移至序列的首位。
请输出 m m m次操作之后卡片的顺序。
思路
每一次都需要把卡片
x
x
x移动到首位，那就意味着在卡片
x
x
x前面的所有卡片都要向后退一位。
硬模拟的话太麻烦，有超时的风险，代码量还大，懒狗表示十分不情愿。
反向一想，为什么我们要让在卡片
x
x
x前面的所有卡片后退呢？为什么来到首位的卡片
x
x
x一定要是原本的那张卡片
x
x
x呢？
不当谜语人了，其实每次操作的时候我们并不需要把卡片
x
x
x移动到首位，而是做一件等价的事取代这个操作：把一张新的值为x的卡片x'放在首位。
最后输出答案的时候，由于每张卡片只会出现一次，所以每一张卡片最后的位置就应该是它在这个序列中第一次出现的位置。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
bool vis[maxn];
int main()
{
deque<int> q;
int n,m,x;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>x;
q.push_back(x);
vis[i]=false;
}
for(int i=1;i<=m;i++)
{
cin>>x;
q.push_front(x);
}
while(n--){
while(vis[q.front()]){
q.pop_front();
}
cout<<q.front();
vis[q.front()]=true;
q.pop_front();
cout<<" ";
}
}
Windows Of CCPC(规律+思维)
比赛链接：https://acm.dingbacode.com/showproblem.php?pid=6708
题目大意
已知
n
=
=
k
n==k
n==k时，
A
A
A是一个由C与P拼凑而成的大小为
2
k
?
2
k
2^k*2^k
2k?2k的矩阵。
n
=
=
1
n==1
n==1时，矩阵
A
A
A为：
n
=
=
2
n==2
n==2时，矩阵
A
A
A为：
请求出
n
=
=
k
n==k
n==k时矩阵
A
A
A的样子。
思路
这种题就属于那种只要看对眼了就可以牵回AC区防止爆0的题目。
样例中给出了 n = = 3 n==3 n==3时矩阵A的值：
CCCCCCCC
PCPCPCPC
PPCCPPCC
CPPCCPPC
PPPPCCCC
CPCPPCPC
CCPPPPCC
PCCPCPPC
一开始博主并没有注意到有什么规律，疯狂薅头发。
紧接着，我顺着CCPC的顺序看了一下
n
=
=
1
n==1
n==1时的矩阵A，然后用同样的方法看了一下
n
=
=
2
n==2
n==2时的矩阵
A
A
A，然后发现了一个东西：
我们把
n
=
=
2
n==2
n==2时的矩阵
A
A
A拆成四个模块之后，我们发现三个C对应的模块的内容是相同的，而P所对应的模块和C对应的模块内容上是相反的。这样的话只要知道了矩阵
A
k
A_k
Ak?红色模块的内容就可以推出其他模块的内容。
而根据题目中给出的所有矩阵
A
A
A我们可以发现，矩阵
A
k
A_k
Ak?的红色模块的内容就是矩阵
A
k
?
1
A_{k-1}
Ak?1?。
k k k的值最大为 10 10 10，所以我们直接预处理出矩阵 A 10 A_{10} A10?的值，矩阵 A k A_k Ak?一定是矩阵 A 10 A_{10} A10?的子矩阵(见红色字体)。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
char s[2500][2500];
void init()
{
s[1][1]=s[1][2]=s[2][2]='C';
s[2][1]='P';
for(int i=2; i<=10; i++)
{
for(int j=1; j<=(1<<(i-1)); j++)
for(int k=1+(1<<(i-1)); k<=(1<<i); k++)
{
s[j][k]=s[j][k-(1<<(i-1))];
s[j+(1<<(i-1))][k]=s[j][k-(1<<(i-1))];
}
for(int j=1+(1<<(i-1)); j<=(1<<i); j++)
for(int k=1; k<=(1<<(i-1)); k++)
{
if(s[j-(1<<(i-1))][k]=='C')
s[j][k]='P';
else
s[j][k]='C';
}
}
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
init();
while(t--)
{
int n;
cin>>n;
for(int i=1; i<=(1<<n); i++)
{
for(int j=1; j<=(1<<n); j++)
cout<<s[i][j];
cout<<'\n';
}
}
}
Fishing Master(贪心+优先队列)
比赛链接：https://acm.dingbacode.com/showproblem.php?pid=6709
题目大意
卖鱼强正在钓鱼，他要把鱼塘里的鱼全部钓出来煮熟带回家当晚餐。
鱼塘里现在有
n
n
n条鱼，煮熟第
i
i
i条鱼的时间为
a
i
a_i
ai?分钟。
卖鱼强抛出鱼钩之后等待
k
k
k分钟就会钓上一条鱼(
n
n
n条鱼中的任意一条，一定会上钩，除非鱼塘没有鱼了)。
卖鱼强在钓鱼的时候无法煮鱼，但在煮鱼的时候可以钓鱼。
请问：卖鱼强最少需要多少时间才能把鱼塘里所有的鱼煮熟带回家呢？
思路
有点像小学的时候老师讲过的煮茶问题：给出煮茶过程中每一步的内容与所需要的时间，煮茶的部分过程是可以同时进行的，求出喝到茶的最短时间。
同理，对于这道题而言，我们肯定希望在煮鱼的时候钓尽可能多的鱼，让钓鱼所需要花费的额外时间全部融入在煮鱼的时间内。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
ll a[maxn];
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
ll m;
int n;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n,greater<int>());
priority_queue<ll> q;
ll num=1;
ll ans=m;
for(int i=1;i<=n;i++)
{
ans+=a[i];
num+=a[i]/m;
q.push(a[i]%m);
if(num<i){
ans+=m-q.top();
q.pop();
}
}
cout<<ans<<'\n';
}
}
后话
感谢阅读，希望能对你产生一点用处。
以下台词取自《银魂：完结篇·永远的万事屋》：
(MADAO才是人生赢家)
