SDKD 2024 Summer Training Contest E2
A - Paper Watering
题意
对x进行至多k次操作（平方或开方后向下取整），求可以得到多少不同的数。
思路
平方完一定不同，且平方完后一定能开方出整数，所以只用额外考虑开方后平方的情况。若开方再平方与原来不同，则答案加上当前变化数的次数，直到变化到1为止。
代码
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int x, k;
scanf("%d%d", &x, &k);
if (x == 1)
{
printf("1");
return;
}
int ans = 0;
while (k--)
{
int cur = sqrt(x);
ans++; // 当前个数
if (cur == 1)
{
break;
}
if (cur * cur != x) // 是否与原来相等
{
ans += k;
}
x = cur;
}
printf("%d", ans + 1); // 本身还有1
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//scanf("%d", &T);
while (T--)
{
solve();
}
return 0;
}
D - nIM gAME
题意
n个石头，每次抓1或2或3个，抓完那个人的赢，现在你(brz)是先手，问你能不能赢。
思路
nim game的变体，先手必胜的条件是 a[1]a[2] ~ ^a[k] = 0。但是这题每次抓的石子数不同，每当brz石头数量接近偶数时，另一个人总可以改变她拿到石头的个数导致数量不为偶数，所以无论怎么操作brz必输。(什么叫博弈啊(战术后仰))
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
scanf("%d", &n);
printf("lose\n");
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
scanf("%d", &T);
while (T--)
{
solve();
}
return 0;
}
E - Checksum
题意
给定长为n的01串a，构造01串b，使得长为k的01串(a+b)中1的个数的二进制数d的前k位与b相同。
思路
考虑到k很小，就直接枚举所有1的个数，加上a中1的个数计算出d，再检查d中和当前枚举的1的个数是否相同，相同则计入答案。
代码
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n, k, cnt = 0;
cin >> n >> k;
string a, b = "22222222222222222222";
cin >> a;
for (int i = 0; i < n; i++)
{
if (a[i] == '1')
{
cnt++;
}
}
//int cur = 1LL << (k - 1); // k位最小二进制数
for (int i = 0; i <= k; i++) // 最多(k+cnt)个1
{
int cur = cnt + i, num = 0;
string d;
while (cur)//转二进制
{
if (cur & 1)
{
d.push_back('1');
num++;
}
else
{
d.push_back('0');
}
cur >>= 1;
if (d.size() >= k)//只要k位
{
break;
}
}
while (d.size() < k)//补0不然会比错
{
d.push_back('0');
}
reverse(d.begin(), d.end());
if (num == i)
{
b = min(d, b);
}
}
if (b == "22222222222222222222")
{
cout << "None" << endl;
}
else
{
cout << b << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
//scanf("%d", &T);
while (T--)
{
solve();
}
return 0;
}
L - Bracket Generation
题意
给定括号序列，两种操作：在最右端加括号()，以及选定合法区间加上括号，如()() -> (()())。问有多少种不同的生成方式，答案对998244353取模
思路
先从左到右标记1，2出现的顺序，然后将该顺序进行颠倒，接着遍历该序列，当出现2时乘以它当前的下标+1（即它出现的顺序），最后对答案取模.操作二的顺序越靠前，可操作次数就越多，其可操作的次数就是当前位置的（）加上后面（）的个数
代码
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
void solve()
{
string s;
cin >> s;
stack<int> st; // 用栈匹配括号
vector<int> v; // 操作序列
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '(')
{
st.push(i);
}
else
{
if (st.top() == i - 1) // i连续，即括号相邻，如 ((
{
v.push_back(1);
}
else
{
v.push_back(2);
}
st.pop();
}
}
reverse(v.begin(), v.end());
int ans = 1;
for (int i = 0; i < v.size(); i++)
{
if (v[i] == 2)
{
ans *= (i + 1); // ans乘以当前可操作的括号数量（即为下标i+1）
ans %= mod;
}
}
cout << ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//scanf("%d", &T);
while (T--)
{
solve();
}
return 0;
}