输入一个长度为 的字符串 ,从头到尾每个字符输出两次。
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> s;
for (int i = 1; i <= n; i++)
cout << s[i - 1] << s[i - 1];
return 0;
}
输入一个序列 ,即一个长度为 的序列,保证 为 或 。
输出 .
#include <bits/stdc++.h>
using namespace std;
unsigned long long ans, now, p;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ans = 0;
p = 1;
for (int i = 0; i <= 63; i++)
{
cin >> now;
if (now)
ans += p;
p *= 2;
}
cout << ans << "\n";
return 0;
}
输入一个长度为 的序列 ,保证 每个元素都刚好出现 次。
定义 为 三次出现的位置里,中间那次的位置。将 按照 作为权值排序后输出。
#include <bits/stdc++.h>
using namespace std;
int n;
int cnt[112345];
int id[112345];
int a[112345];
bool cmp(int x, int y)
{
return id[x] < id[y];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n * 3; i++)
{
int x;
cin >> x;
cnt[x]++;
if (cnt[x] == 2)
id[x] = i;
}
for (int i = 1; i <= n; i++)
a[i] = i;
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << "\n";
return 0;
}
给定 道菜的属性。
分别表示第 道菜的毒性( 有毒、 解毒),与第 道菜的得分。
初始 Taka 处于健康状态。
按顺序上每道菜,每道菜都可以吃或跳过(如果跳过,以后也不能回过头去吃)。求不死的前提下的最大得分。
简单 DP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int x[312345], y[312345];
// 第 i 道菜后,中毒情况为 j 时的最大得分
int f[312345][2];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> x[i] >> y[i];
f[0][0] = f[0][1] = 0;
for (int i = 1; i <= n; i++)
{
if (x[i] == 0)
{
// 吃
f[i][0] = max(f[i - 1][0] + y[i], f[i - 1][1] + y[i]);
// 不吃
f[i][0] = max(f[i][0], f[i - 1][0]);
f[i][1] = f[i - 1][1];
}
else
{
// 吃
f[i][1] = f[i - 1][0] + y[i];
// 不吃
f[i][1] = max(f[i][1], f[i - 1][1]);
f[i][0] = f[i - 1][0];
}
}
cout << max(f[n][0], f[n][1]) << "\n";
return 0;
}
给定一个长度为 的序列 ,初始 都是 。
给定 。
接下来有 次操作,第 次操作会给定两个正整数 ,你需要进行以下操作:
数据范围:
做法很多,比如可以直接权值线段树维护“数量”及“区间和”。然后在线段树上 统计指定数量的区间和即可。
我的写法更精细,map<int,int>
统计每个数出现次数。维护一个迭代器指向分界线。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 500000;
const int MAXK = 500000;
const int MAXQ = 500000;
int n, k, q;
int a[MAXN + 5];
// m[i]:i这个数出现了几次
map<int, int> m;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k >> q;
for (int i = 1; i <= n; i++)
a[i] = 0;
m[0] = n;
// cnt(it->first ~ INF) >= K
// cnt(it->first + 1 ~ INF) < K
map<int, int>::iterator it = m.begin();
int cnt = 0; // cnt(it->first + 1 ~ INF)
int ans = 0; // sum(it->first + 1 ~ INF)
// realAns = ans + (it -> first) * (K - cnt)
while (q--)
{
int x, y;
cin >> x >> y;
int preAx = a[x];
a[x] = y;
if (preAx == y)
cout << ans + (it->first) * (k - cnt) << "\n";
else
{
m[preAx]--;
m[y]++;
// preAx->y 时,在当前分界线下,对 cnt/ans 的影响
if (preAx <= it->first &&
y > it->first)
{
cnt++;
ans += y;
}
else if (preAx > it->first &&
y <= it->first)
{
cnt--;
ans -= preAx;
}
else if (preAx > it->first &&
y > it->first)
{
ans += (y - preAx);
}
if (m[preAx] == 0)
{
if (it->first == preAx)
{
if (it != m.begin())
it--;
else
{
it++;
cnt -= it->second;
ans -= (it->first) * (it->second);
}
}
m.erase(preAx);
}
// 分界线变化
while (cnt >= k)
{
// 当前的分界线小了
it++;
ans -= (it->first) * (it->second);
cnt -= it->second;
}
while (cnt + it->second < k)
{
// 当前的分界线大了
cnt += it->second;
ans += (it->first) * (it->second);
it--;
}
// cout << "-> " << it->first << "x[" << it->second << "]\n";
cout << ans + (it->first) * (k - cnt) << "\n";
}
}
return 0;
}