2023牛客暑期多校训练营7
C.Beautiful Sequence
题意：有长为\(n\)的数组\(a\)，通过操作\(a_i \oplus a_{i+1}\)得到\(b_i\)，现在给出数组\(b\)，求出字典序第\(k\)小的数组\(a\)
Solution
不难发现，如果确定了\(a_1\)的某一二进制位上的数，就可以确定整个数组\(a\)的这一位上的数，我们首先把所有的二进制位数都变为-1，表示这一位还未确定
对于两个相邻的数，如果它们以0经过异或处理后的某一位是\(x,y\)
若\(x=y\)，对答案没有影响
若\(x>y\)，则\(a_1\)的这一位必须是1
若\(x<y\)，则\(a_1\)的这一位必须是0
于是我们每次看一下前面是否有冲突即可
然后就是统计答案了，对于\(k\)，我们也可以拆成二进制，来对\(a\)上的-1的位置进行修改即可
void solve()
{
memset(a, -1, sizeof(a));
int n, k;
cin >> n >> k;
for (int i = 2; i <= n; i++)
cin >> b[i];
for (int i = 2; i <= n; i++)
c[i] = c[i - 1] ^ b[i];
for (int i = 1; i < n; i++)
{
for (int j = 29; j >= 0; j--)
{
int k1 = (c[i] >> j)&1, k2 = (c[i + 1] >> j)&1;
if (k1 == k2)
continue;
if (a[j] == -1)
a[j] = k1;
else if (a[j] != k1)
{
cout << "-1\n";
return;
}
break;
}
}
int temp = k - 1;
for (int i = 0; i < 30; i++)
{
if (a[i] == -1)
{
a[i] = (temp & 1);
//cout<<(temp&1)<<"\n";
temp >>= 1;
}
}
/*for(int i=29;i>=0;i--)cout<<a[i];
cout<<"\n";*/
if (temp)
{
cout << "-1\n";
return;
}
int res = 0;
for (int j = 29; j >= 0; j--)
{
res <<= 1;
res += a[j];
}
for (int i = 1; i <= n; i++)
{
cout << (res ^ c[i]) << " \n"[i == n];
}
}
G.Cyperation
题意：给出一个数组，把它看成一个环，每次可以选择环上最短距离为k的两个数，让它们都-1，问能否使得其变为全0
Solution
原数组可以看成若干个小环，令这个环为\(a_1,a_2,...,a_n\)
假设现在对\(a_1,a_2\)进行\(x\)次操作
后面要使得\(a_2\)归零，则还需对\(a_2,a_3\)进行\(a_2-x\)次操作
同理对\(a_3,a_4\)进行\(a3-(a2-x)\)次操作
...
依次类推，最后对\(a_n,a_1\)进行\(a_n-(a_{n-1}-...-(a_2-x))\)次操作
令\(p_2=a_2,p_i=a_i-p_{i-1},p_1=a_1-p_n\)，则有
对于\(n\)为偶数情况，可以发现\(a_1-p_n=p_1=0\)
对于\(n\)为奇数情况，有\(2x=a_1-p_n=p_1\)
所以对于对应的情况判断一下，然后看\(x\)范围是否合法即可
bool check(vector<int> v)
{
b[0] = 0;
int n=v.size();
for (int i = 1; i < n; i++)
{
b[i] = v[i] - b[i - 1];
}
b[0] = v[0] - b[n - 1];
int l = 0, r = v[0];
for (int i = 0; i < n; i++)
{
if (i & 1)
r = min(r, b[i]);
else
l = max(l, -b[i]);
if (l > r)
return false;
}
if (n % 2 == 0)
return b[0] == 0;
else
{
int x=b[0]/2;
return ((2*x==b[0])&&(l<=x&&x<=r));
}
}
int n, k;
void solve()
{
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> a[i];
vis[i] = 0;
}
int flag = 1;
for (int i = 0; i < n; i++)
{
if (a[i] != 0)
{
flag = 0;
break;
}
}
if (flag)
{
cout << "YES\n";
return;
}
if (k > n / 2)
{
cout << "NO\n";
return;
}
for (int i = 0; i < n; i++)
{
if (vis[i])
continue;
vector<int> r;
r.push_back(a[i]);
int pos = (i + k) % n;
while (pos != i)
{
r.push_back(a[pos]);
vis[pos] = 1;
pos += k;
pos%=n;
}
//for(auto it:r)cout<<it<<" ";
// cout<<"\n";
if (!check(r))
{
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
I.We Love Strings
题意：给出一些由0,1,?组成的字符串，'?'既可以是1也可以是0，问有多少字符串能与之匹配
Solution
考虑到字符串总长不会超过400，如果字符串个数>20，则长度<20，反之亦然
对于长度<20的，我们可以暴力法求出个数，对于长度>20的，我们可以通过容斥原理来算出个数
int brute_get(vector<string> &v)
{
if (v.size() == 0)
return 0;
int res = 0;
int len = v[0].size();
for (int j = 0; j < (1 << len); j++)
{
for (auto it : v)
{
int flag = 1;
for (int i = 0; i < len; i++)
{
if (it[i] == '?' || it[i] - '0' == ((j >> i) & 1))
{
continue;
}
else
{
flag = 0;
break;
}
}
if (flag)
{
res = (res + 1) % mod;
break;
}
}
}
return res;
}
int inc_get(vector<string> &v)
{
if (v.size() == 0)
return 0;
int res = 0;
int len = v[0].size();
int op;
for (int i = 1; i < (1 << v.size()); i++)
{
int flag = 1;
op = 0;
string check(len, '?');
for (int j = 0; j < v.size(); j++)
{
for (int k = 0; k < len; k++)
{
if (((i >> j) & 1) == 0)
continue;
if (check[k] == '?')
{
check[k] = v[j][k];
}
else if (check[k] != v[j][k] && v[j][k] != '?')
{
flag = 0;
break;
}
}
}
if (!flag)
continue;
int cnt = 1;
for (int k = 0; k < len; k++)
{
if (check[k] == '?')
cnt = (cnt * 2) % mod;
}
int temp = i;
while (temp > 0)
{
if (temp & 1)
op ^= 1;
temp >>= 1;
}
res = ((res + (2 * op - 1) * cnt % mod) % mod + mod) % mod;
}
return res;
}
void solve()
{
int n;
cin >> n;
int ans = 0;
for (int i = 1; i <= n; i++)
{
string t;
cin >> t;
e[t.size()].push_back(t);
}
for (int i = 1; i <= 400; i++)
{
if (i <= 20)
ans = (ans + brute_get(e[i])) % mod;
else
ans = (ans + inc_get(e[i])) % mod;
}
cout << ans << "\n";
}