D . Magic Multiplication
题意：给出A,B可以计算出C，计算方式是：A的第一位与B位上的数相乘得到一个数，加入字符串，接着A第二位数，，举个例子就是：23 $\otimes$45=8101215。8=24,10=25,12=34,15=35.
然后给出C，然我们求出，A,B,如果有多组符合条件，我们直接输出最小的A即可。
分析：首先我们知道这个运算，那么我们就能够得到，如果我们确定了A的第一位，那么就可以通过C前几位确定B的全部位上的数字：
因为A[1]确定了那么C[1]要是大于等于A[1]只能是A[1]B[1]构成的C[1],因为B[1]是一位数。然后如果小于A[1]，那么只能是A[1]B[1]=C[1]*10+C[2].因为B[1]是一位数，当然对于C[1]等于0的话B[1]一定是0(这样是不行的。之后就可行)，因为A[1]一定不是能，当然如果我们判断完几位之后看是否整除，如果无法整除那么肯定无解换一个数即可。一直把B整出来，然后用B挨着计算A[2],A[3]...反过来计算。当然里面有坑点，具体看代码吧，整体思路意思就是这样。
还有一点就是，如果我们A[1]是从小到大枚举的那么如果我们找到答案那么他一定是最小的！直接输出退出即可、
这样按着思路写来下代码也不是特别长，去掉头文件哪些没大用的东西，主代码也就30，40行，所以好好分析就好的。
/// 欲戴皇冠，必承其重。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
#define x first
#define y second
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define debug(x) cout << #x << ": " << x << endl;
const int MOD = 998244353;
const int mod = 998244353;
const int N = 1e6 + 10;
const int dx[] = {0, 1, -1, 0, 0, 0, 0};
const int dy[] = {0, 0, 0, 1, -1, 0, 0};
const int dz[] = {0, 0, 0, 0, 0, 1, -1};
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
ll n, m;
char str[N],s[N];
void solve()
{
scanf("%lld",&n);
scanf("%s",str+1);
scanf("%s",s+1);
ll flag=1;
ll sum=0,ans=0;
for(int i=1;i<=n;i++){
if(str[i]==s[i]){
if(flag==1) continue;
else {
flag=1;
}
}else {
ans++;
if(flag==0) continue;
else {
flag=0;
sum++;
}
}
}
if(sum>2) puts("0");
else if(sum==2){
puts("6");
return ;
}else if(sum==1) {
printf("%lld\n",(n-ans)*2+(ans-1)*2);
}
else if(sum==0){
printf("%lld\n",n*(n+1)/2);
}
}
int main()
{
ll t = 1;
scanf("%lld", &t);
while(t--)
{
solve();
}
return 0;
}
E . Plants vs. Zombies
题意：长度为N的序列，初始为0，然后每次经过第i个点时，第i个数会增加a[i]价值,我们只能向左，或向右一格。一共可以m步，问这个序列最小价值最大是多少？
分析：首先我们看问题是最小价值最大化，再结合题意那么我们想到他一定有单调性。然后我们就可以二分答案，重要是如果check了。
check的话我们这样想，首先，我们发现他只能往左或这往右走，那么我们判断答案x是否符合条件，就得n个数都要≥x，那么我们要向一个位置多走几次我们就需要在(i,i+1)之间来回走，直到i位置符合题意(也就是≥x)然后就可以继续往后判断，最后只需要判断所需步数是否合法即可。需要注意如果i位置符合条件也要走一步因为，我们要一直走到最后(当然除了最后一个，最后一个如果也合法了，就没必要走了！！！这个很重要。)
/// 欲戴皇冠，必承其重。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
#define x first
#define y second
#define sf scanf
#define pf printf
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
#define debug(x) cout << #x << ": " << x << endl;
const int MOD = 998244353;
const int mod = 998244353;
const int N = 2e5 + 10;
const int dx[] = {0, 1, -1, 0, 0};
const int dy[] = {0, 0, 0, 1, -1};
const int dz[] = {1, -1, 0, 0, 0, 0 };
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
ll n, m;
ll a[N],b[N];
string str;
bool check(ll x){
for(int i=1;i<=n+1;i++){
b[i]=0;
}
ll num=0;
for(int i=1;i<n;i++){
ll cnt=1;
if(b[i]<x){
cnt=(x-b[i]+a[i]-1)/a[i];///次数
}
num+=cnt*2-1;
b[i]+=a[i]*cnt;
b[i+1]+=a[i+1]*(cnt-1);
if(num>m) return 0;
}
if(b[n]<x){
ll cnt=(x-b[n]+a[n]-1)/a[n];
num+=cnt*2-1;
}
if(num>m) return 0;
return 1;
}
void solve()
{
scanf("%lld%lld",&n,&m);
bool flag=0;
for(int i = 1;i<=n;i++){
scanf("%lld",&a[i]);
if(a[i]==0) flag=1;
}
if(flag) {
puts("0");
return ;
}
ll l = 0,r = 1e18;
ll ans=0;
while(l<=r){
ll mid=(l+r)/2;
if(check(mid)){
ans=mid;
l=mid+1;
}else {
r=mid-1;
}
}
printf("%lld\n",ans);
}
int main()
{
ll t = 1;
scanf("%lld", &t);
while(t--)
{
solve();
}
return 0;
}
F . Tournament
题意:
给出n个骑士，进行k次对战，每个骑士只能与另一个骑士对战一次，如果第i回合A对战B，C对战D，那么如果第j回合A对战C(D),那么B一定对战D(C)。问是否可能构成k场对局。字典序从小到大。
分析：
我们看最小的字典序，也就是我们想到的最优的不过就是
1 2 3 4 5 6 7 8 (然而这个不能用，本人不能跟本人对战)
2 1 4 3 6 5 8 7 (那么我们只好选优，肯定12互换，34互换)
3 4 1 2 7 8 5 6 (2用过了，我们看是以三打头就是介样子。)
.....
最终就是这样子
通过观察，我们就能发现其中的规律，先是长度为2交换然后长度为4 ，然后长度2然后8然后2，然后4然后2像不像树状数组！
然后我们我们只需要判断出是否可行，一共可以进行lowbit(n)-1轮超过这个就不可能实现。
然后我们只需要构造出每轮谁与谁对战即可。
大佬)
/// 欲戴皇冠，必承其重。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<string, string> pii;
typedef unsigned long long ull;
#define x first
#define y second
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define debug(x) cout << #x << ": " << x << endl;
const int MOD = 998244353;
const int mod = 998244353;
const int N = 5e5 + 10;
const int dx[] = {
0, 1, -1, 0, 0, 0, 0};
const int dy[] = {
0, 0, 0, 1, -1, 0, 0};
const int dz[] = {
0, 0, 0, 0, 0, 1, -1};
int day[] = {
0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
ll n, m;
ll a[N];
void solve()
{
scanf("%lld%lld",&n,&m);
if(m>lowbit(n)-1){
puts("Impossible");
}else {
for(int i=1;i<=n;i++){
a[i]=i;
}
for(ll i =1;i<=m;i++){
ll len=lowbit(i);
for(ll j=1;j<=n;j+=(len<<1)){
for(ll k=0;k<len;k++){
swap(a[j+k],a[j+len*2-1-k]);
}
}
for(int j=1;j<n;j++){
cout<<a[j]<<" ";
}
cout<<a[n]<<endl;
}
}
}
int main()
{
ll t = 1;
scanf("%lld", &t);
while(t--)
{
solve();
}
return 0;
}
