A - Two Screens
大意：
给两个字符串，每次在两个空子符串进行两种操作
1、字符串末尾加一个任意字母
2、一个字符串全部复制给另一个字符串
求得到给定的两个字符串的最小操作数
思路：
看最前面有多少相等即可
当时想多了。。。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int, int>>
#define ff first
#define ss second
#define rep(i, l, r) for(int i = l; i <= r; i ++)
#define rrep(i, r, l) for(int i = r; i >= l; i --)
void solve()
{
string s1, s2;
cin >> s1 >> s2;
int ans = s1.size() + s2.size();
int num = min(s1.size(), s2.size());
if (s1[0] == s2[0])ans++;
for (int i = 0; i < num; i++)
{
if (s1[i] == s2[i])ans--;
else break;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
/* /\_/\
* (= ._.)
* / > \>
*/B - Binomial Coefficients, Kind Of
大意：
利用错误的公式求组合数
思路：
首先这个错误的公式没有什么实际意义，找不到简化的公式
从开始列举发现了规律，只看上边的数即可，相当于2的i 次方
当时组合数还翻了y总算法基础课的四种，发现没有针对这种公式的
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int, int>>
#define ff first
#define ss second
#define rep(i, l, r) for(int i = l; i <= r; i ++)
#define rrep(i, r, l) for(int i = r; i >= l; i --)
int qmi(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)res = (res * a) % mod;
a = a * a % mod;
b /= 2;
}
return res;
}
void solve()
{
int n;
cin >> n;
vi v1(n), v2(n);
for (int i = 0; i < n; i++)cin >> v1[i];
for (int i = 0; i < n; i++)cin >> v2[i];
for (int i = 0; i < n; i++)
{
cout << qmi(2, v2[i]) << endl;
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
return 0;
}
/* /\_/\
* (= ._.)
* / > \>
*/C - New Game
大意：
还是给一堆数，按照相等或加一的拿法，求的是限制拿k种数的情况下，拿的数的最大数量
思路：
当时就先把这堆不同的数用map记录了一下，然后用vector来存连续的数，然后依次求vector内k段长度的最大值，当时能想到的就这了，化繁为简
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int, int>>
#define ff first
#define ss second
#define rep(i, l, r) for(int i = l; i <= r; i ++)
#define rrep(i, r, l) for(int i = r; i >= l; i --)
void solve()
{
int n, k;cin >> n >> k;
map<int, int>mp;
for (int i = 0; i < n; i++)
{
int x;cin >> x;
mp[x] ++;
}
int last = -1;
vector<vi> v(n + 1);
int idx = -1;
for (auto i : mp)
{
if (last + 1 != i.first)
{
v[++idx].push_back(0);
v[idx].push_back(i.second);
}
else v[idx].push_back(i.second);
last = i.first;
}
int ans = 0;
for (auto vv : v)
{
if (vv.size() == 0)break;
int si = vv.size() - 1;
for (int i = 1; i <= si; i++)
{
vv[i] += vv[i - 1];
}
if (k >= si)
{
ans = max(ans, vv[si]);
continue;
}
for (int i = k; i <= si; i++)
{
ans = max(ans, vv[i] - vv[i - k]);
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
/* /\_/\
* (= ._.)
* / > \>
*/D. Attribute Checks
没做出来，看了jiangly大佬的提交代码https://codeforces.com/contest/2025/submission/285854273
大意：
给一堆数，如果遇到0，就给正数或负数 +1，如果遇到正数或负数，就比较相应的绝对值，已加的数大于等于该绝对值，ans++，求最大ans
思路：
这个DP的算法当时一直想不明白，之后推演了好几遍才跟上jiangly的思路，
用了两个vector， DP[j]来存1-n 遍历到第i个数时用掉了j个经验来升级正数的最大通过测试数，f[j]是个中间变量，来记录两个相邻零之间的数对DP的更新值，f[j]表示第j个数结果加了多少
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int, int>>
#define ff first
#define ss second
#define rep(i, l, r) for(int i = l; i <= r; i ++)
#define rrep(i, r, l) for(int i = r; i >= l; i --)
void solve()
{
int n, m;
cin >> n >> m;
int num = 0; // 记录当已经分配的经验
vi dp = { 0 }; // dp[i]记录当前已分配经验下，共i种分配给正数的方案最优解
vi f = { 0 }; // 记录测试点
rep(i, 0, n - 1) {
int r; cin >> r;
if (r > 0) { // 正数测试
if (r < f.size())f[r] ++; // 默认经验点都给正数
}
else if (r < 0) { //负数测试
r = - r;
r = num - r;
if (r >= 0) { // 如果这个负数测试点有可能通过
f[0] ++, f[r + 1] --;
}
}
else {
rep(j, 1, num) f[j] += f[j - 1]; //累加，表示前j种选择的更新量
rep(j, 0, num) dp[j] += f[j];
dp.push_back(0);
num++;
// cout << "--DP1" << endl;
// for (auto it : dp)cout << it << " ";cout << endl;
rrep(j, num, 1) dp[j] = max(dp[j], dp[j - 1]);
/*这一步当时想了好久，其实是还是流程没掌握好，
这一步的DP更新是从大到小更新的，
因为现在是加了一点经验的时候，所以多加的这一点经验对应的DP直接先取上一个的
而对于j，DP[j]现在是之前的num + 1个经验点里面选j个，现在比较灵活了
多出来的经验点给正数，那么DP[j] = DP[j - 1];
多出来的经验点给负数，那么DP[j] = DP[j];
而我们只需要取最大值即可
*/
// cout << "--DP2" << endl;
// for (auto it : dp)cout << it << " ";cout << endl;
f.assign(num + 1, 0);
}
}
rep(j, 1, num) f[j] += f[j - 1];
rep(j, 0, num) dp[j] += f[j];
int ans = *max_element(dp.begin(), dp.end());
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
return 0;
}
/* /\_/\
* (= ._.)
* / > \>
*/