A.^&^—思维

题意:给出两个正整数 A 和 B,找到一个正整数 C,使得 (A^C)&(B^C) 的结果最小,若是有多个符合的 C 找到最小的那个

思路:先读懂题:先满足结果值最小,其次满足 C 最小。关键是按位分析找规律,^ 是异或运算,&是位与运算。若是想让结果小,那两个括号里的数的相同的位上的数尽可能不相同(即一个 1 和一个 0,或者一个 0 和一个 1),另一方面还要让 C 尽可能的小,所以只有在万不得已的情况让 C 的上取 1,否则就取 0。下面讨论不同的情况:

  • 如果 A 和 B 相同位上的数都是 1,那么直接取 & 会导致结果值在该位上的数是 1,我们借助让 C 在该位上的数为 1,这样结果值在该位为 0
  • 如果 A 和 B 相同位上的数都是 0,那么直接取 & 还是会导致结果值在该位上的数是1,但是可以发现保持 C 在该位上的数为 0就可以保证结果值在该位为 0
  • 如果 A 和 B 相同位上的数不同,那么直接取 & 就可以让结果值在该位上的数是0,所以保持 C 在该位上的数为 0

综上:只有第一种情况时将 C 在相同位上的数为1,其他情况都为 0

还需要注意的一点是 C 为 0 的时候输出 1,所以特判 A&B==0 情况,因为这时候 C 按上述赋值为 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(){
ll a,b;cin>>a>>b;
if((a&b)==0){//&的优先级好像比==小
cout<<min(a,b)<<endl;
return ;
}
cout<<(a&b)<<endl;
}

signed main()
{
ios::sync_with_stdio(false),cin.tie(0);
int t;cin>>t;
while(t--){
solve();
}
return 0;
}

F.Shuffle Card—思维+栈

题意:有一叠纸牌,每张牌有一个单独的序号。最开始的时候纸牌的序号是 1~n。接下来开始进行 m 次洗牌,每次洗牌将指定的序号的纸牌放在最上方,让你输出最后这叠纸牌的序号

思维:无疑要将每次放在牌堆顶的纸牌序号记录下来,先放的卡牌序号会被后放的卡牌序号压住(符合栈先进后出的特点)。我们可以用堆纪录被放到过牌堆顶的牌的序号,输出的时候先输出栈内的序号再输出其他的序号。但是还要考虑的是可能会重复将某个序号的卡牌多次放在牌堆顶,所以在遍历栈的时候重复的序号只用输出靠上的那个,所以另开一个标记数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

bool vis[100005];

signed main()
{
ios::sync_with_stdio(false),cin.tie(0);
int n,m;
while(cin>>n>>m){
stack<int> sta;
for(int i=1;i<=n;i++){
int x;cin>>x;
}

for(int i=1;i<=m;i++){
int x;cin>>x;
sta.push(x);
}

while(!sta.empty()){
int x=sta.top();
sta.pop();
if(vis[x]==0){
cout<<x<<" ";
vis[x]=1;
}
}

for(int i=1;i<=n;i++)
if(vis[i]==0)cout<<i<<" ";
}
return 0;
}

G.Windows Of CCPC—图形构造

题意:最开始第一个图形的 4 个字符左下角的那个和其余的 3 个字符不同。第二个图形由第一个图形转换过来,把第二个图形分为 4 部分,左下角的和第一个图形相反,其余的三个部分和第一个图形相同。依次类推,第三个图形、第四个图形。题目给出 k(1<=k<=10),输出第 k 个图形

思路:一个一个推所以就是递推构造,找好规律就可以由第一个图形推出所有的图形。但是多样例重复构造会 TLE ,一看数据 k 那么小直接打表用个二维数组将第 10 个图形存起来,然后要哪个就输出数组内对应位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000;

char ans[N][N];//记录答案

void paint(){
ans[1][1]=ans[1][2]=ans[2][2]='C';ans[2][1]='P';

for(int i=2;i<=10;i++){//递推打表
int now=pow(2,i-1),nex=pow(2,i);//前一个图和后一个图的边长

for(int j=1;j<=now;j++)//2和4区域
for(int k=now+1;k<=nex;k++)
ans[j+now][k]=ans[j][k]=ans[j][k-now];

for(int j=now+1;j<=nex;j++){//3区域
for(int k=1;k<=now;k++){
if(ans[j-now][k]=='C')ans[j][k]='P';
else ans[j][k]='C';
}
}
}
}

signed main()
{
ios::sync_with_stdio(false),cin.tie(0);
paint();
int t;cin>>t;
while(t--){
int k;cin>>k;

int len=pow(2,k);//now为图形变长的的大小范围

for(int i=1;i<=len;i++){
for(int j=1;j<=len;j++)cout<<ans[i][j];
cout<<endl;
}
}
return 0;
}

H.Fishing Master—贪心

题意:有 N 条鱼,每条鱼都有钓鱼和烤鱼的时间,钓鱼的时间均相同,每条鱼都有自己的烤鱼时间,一次只能烤一条鱼且不能间断。现要求通过某种顺序将所有的鱼钓上来并烤完,求最小的时间是多少

思维:首先根据常识可以知道开始的时候肯定是先钓到一条鱼才能开始煮(固定时间),结束的时候肯定是钓完最后一条鱼并等到这条鱼煮完(可以尽可能小)。中间的时候可能会有煮鱼的时间相对太长,导致钓到另一条鱼但是还得等着锅里的鱼煮完,或者可能是钓鱼时间相对太长,导致煮完锅里的鱼但是还得等着你钓完鱼再煮下一条。那么对于上述两种不同的顺序情况,我们可以从全局角度进行考虑选择:钓鱼的次数和煮鱼的时间肯定是固定的,所以我们选择固定在煮鱼的时间内尽可能钓到多的鱼,不过可能会出现上述正在钓鱼但是锅的鱼煮完情况,如果这部分被浪费的时间要尽可能小那么答案就尽可能的小了。根据贪心我们算出每个煮鱼时间内可以钓到几条鱼以及浪费的时间:

  • 如果煮鱼的时间内就足以钓完所有鱼说明浪费时间也可以钓完
  • 如果煮鱼的时间内不能钓完所有鱼那么就选择浪费时间少的,这样需要额外等的时间就短了

具体看代码理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,k;
ll a[100005];
vector<ll> wait;

void solve(){
wait.clear();
scanf("%lld%lld",&n,&k);
int pos,minn=0x3f3f3f3f;//选出结尾煮鱼时间最短的
for(ll i=0;i<n;i++){
scanf("%lld",&a[i]);
if(a[i]<minn)pos=i,minn=a[i];
}

ll sum=k;//统计时间,初始需要先钓到一条鱼
for(int i=0;i<n;i++)sum+=a[i];

int cnt=0;
for(int i=0;i<n;i++){
if(i==pos)continue;//最后煮鱼的时间不会浪费时间
cnt+=a[i]/k,wait.push_back(k-a[i]%k);//每个煮鱼时间能钓的鱼和浪费的时间
}

if(cnt>=n-1){//抛去开始钓到的鱼,其他的鱼在煮的时间内都钓完了
printf("%lld\n",sum);
return ;
}

sort(wait.begin(),wait.end());//否则尽可能少浪费时间
for(int i=0;i<n-1-cnt;i++)
sum+=wait[i];
printf("%lld\n",sum);
}

signed main()
{
ll t;cin>>t;
while(t--){
solve();
}
return 0;
}