题意:给出两个正整数 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; }
|
题意:有一叠纸牌,每张牌有一个单独的序号。最开始的时候纸牌的序号是 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; }
|
题意:最开始第一个图形的 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++) 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++){ 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);
for(int i=1;i<=len;i++){ for(int j=1;j<=len;j++)cout<<ans[i][j]; cout<<endl; } } return 0; }
|
题意:有 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; }
|