2023年10月8日
群里发的题 四月是你的谎言
题目描述
嘤嘤最近正在看《四月是你的谎言》，看完后她觉得——呜~，太好哭了吧！。
嘤嘤PTSD了，现在她一看到某些单词就会嘤嘤嘤，现在有一个字符串里面包含了很多会让嘤嘤嘤嘤嘤的单词，而魔法少女qcjj为了让嘤嘤看到这个字符串时不会嘤嘤嘤，她决定使用魔法将字符串中的某些字符变成′∗′。
为了尽可能使字符串保持原来的特征，魔法少女qcjj希望字符串改变的次数尽可能少，即′∗′的数量尽可能少，她想让你帮他找到一个这样的方案。如果有多种方案，输出任意方案均有效。
输入格式
第一行输入一个整数T 表示测试用例数。
对每一个测试用例，第一行输入一个整数n表示嘤嘤看到会嘤嘤嘤的单词的数量。
接下来n 行，每行输入一个字符串s 表示嘤嘤看到会嘤嘤嘤的单词。
接下来1 行，输入牛牛的字符串str 。
输出格式
输出一个字符串，使得字符串不包含嘤嘤看到后会嘤嘤嘤的单词，并且需要保证字符串中 ′∗′的数量最少，如果存在多种方案，输出任意一个均有效。
数据范围
\(1≤T≤10^5\)
\(1≤n≤10\)
每个单词长度不超过\(10\)
str总长度不超过\(5*10^5\)。
题目理解
只需要用n个字符串记录一下连续的，符合条件的串，每当我们匹配到了以后我们就需要清空所有的长度。如果长度相等，就意味着，匹配到了。把字符换成星号即可。
代码实现
const int N = 2e5 + 10;
int cnt[N];
string a[N], s;
void solve()
{
memset(cnt, 0, sizeof cnt);
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
cin >> s;
for(int i = 0; i < (int)s.size(); i++)
{
char c = s[i];
for(int j = 0; j < n; j++)
{
if(c == a[j][cnt[j]])
{
cnt[j]++;
if(cnt[j] == (int)a[j].size())
{
cnt[j] = 0;
s[i] = '*';
memset(cnt, 0, sizeof cnt);
break;
}
}else
cnt[j] = 0;
}
}
cout << s << endl << endl;
return;
}
Div.2 Round902 A Goals of Victory
题目大意
n个足球队打比赛，给了n-1个足球对的效率，效率计算是自己的总进球减去，每一场对手的进球。
题目理解
那么其实可以发现，如果把所有的数字求和，然后取负号，就是最后一个球队的效率了。因为按道理说，所有球队效率求和为0
代码实现
void solve()
{
int n;
cin >> n;
int sum = 0;
for(int i = 1; i <= n - 1; i++)
{
int t;
cin >> t;
sum += t;
}
cout << -sum << endl;
return;
}
Div.2 Round902 B Helmets in Night Light
题目大意
这个题问的是我，可以给很多人发帽子，每发一个帽子的代价是p。而被发到帽子的人最多可以给\(a_i\)个人发帽子，每发一个帽子的代价是\(b_i\)。问最少的代价是多少可以把帽子发给所有人。
题目理解
- 发给代价最小的人
- 代价比我大，我就自己发
- 最小的人可以发给第二小的人
那么我们只需要，代价排序后，从左往右一直发即可。如果遇到发完的就需要我再发一顶（按道理说不会遇到的）。
代码实现
bool cmp(const PLL& a, const PLL& b) {
if (a.x != b.x) {
return a.x < b.x;
} else {
return a.y > b.y;
}
}
void solve() {
ll n, p;
scanf("%lld%lld", &n, &p);
vector<PLL> q(n);
for(int i = 0; i < n; i++)
scanf("%lld", &q[i].y);
for(int i = 0; i < n; i++)
scanf("%lld", &q[i].x);
sort(q.begin(), q.end(), cmp);
ll cnt = 1;
ll res = p;
ll i = 0;
while(cnt < n)
{
while(i < cnt)
{
if(q[i].x < p)
{
if(n - cnt >= q[i].y)
{
res += q[i].x * q[i].y;
cnt += q[i].y;
}else{
res += (n - cnt) * q[i].x;
cnt = n;
}
}else{
res += (n - cnt) * p;
cnt = n;
}
if(cnt >= n) break;
i++;
}
if(cnt >= n) break;
else{
cnt += 1;
res += p;
}
}
printf("%lld\n", res);
return;
}
Div.2 Round899 A Increasing Sequence
题目大意
构造严格上升序列满足：
\(b_i != a_i\)
\(b_i < b_{i+1}\)
题目理解
从1开始往上加，如果发现和\(a_i\)相等就再加一个。
代码实现
void solve()
{
int n;
cin >> n;
ll k = 0, t;
for(int i = 1; i <= n; i++)
{
cin >> t;
k++;
if(k == t)
k++;
}
cout << k << endl;
return;
}
Div.4 Round859 C. Find and Replace
题目大意
把相同的字母替换成0或1，看看最后是否可以构成不相邻01串
题目理解
这个串只会有两种可能，开头不是0就是1，那么就拟开头是0和1，模拟就行。
代码实现
const int N = 2010;
int a[30], b[N];
void solve()
{
memset(a, INF, sizeof a);
string s;
int n;
cin >> n;
cin >> s;
bool flag = true;
a[s[0] - 'a' + 1] = 1;
for(int i = 0; i < n; i++)
{
if(a[s[i] - 'a' + 1] == INF)
a[s[i] - 'a' + 1] = b[i - 1] == 0 ? 1 : 0;
b[i] = a[s[i] - 'a' + 1];
if(b[i - 1] == b[i])
{
flag = false;
break;
}
}
if(flag)
{
cout << "YES" << endl;
}else{
memset(a, INF, sizeof a);
flag = true;
a[s[0] - 'a' + 1] = 1;
for(int i = 0; i < n; i++)
{
if(a[s[i] - 'a' + 1] == INF)
a[s[i] - 'a' + 1] = b[i - 1] == 0 ? 1 : 0;
b[i] = a[s[i] - 'a' + 1];
if(b[i - 1] == b[i])
{
flag = false;
break;
}
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return;
}
Div.4 Round859 D. Odd Queries
题目大意
给多个查询，每次查询是把l到r的数替换成k，问最后的和是不是奇数。每个查询的替换不保留。
题目理解
直接前缀和存一下，然后前一段 + (r - l + 1) * k + 后一段
代码实现
ll a[N], n, m;
void solve()
{
scanf("%lld%lld", &n, &m);
for(int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
a[i] += a[i - 1];
}
ll l, r, k;
for(int i = 1; i <= m; i++)
{
scanf("%lld%lld%lld", &l, &r, &k);
ll v = (r - l + 1) * k + a[l - 1] + a[n] - a[r];
if(v % 2 != 0)
printf("YES\n");
else
printf("NO\n");
}
return;
}