A. Remainder
题意
给一个由0和1组成的数n，每次可以用0或1替换其中一个数，问最少要需要多少次操作才能使。
关键字
数学、模拟
思路
统计如下操作的次数：
- 第x位的0替换成1。
- 在x-1到第y-1位中，将所有1替换成0。
- 第y位的0替换成1。
- y以后的数字中，1替换成0.
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200006
#define MAXM 100006
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
int n, x, y;
SCAND(n);
SCAND(x);
SCAND(y);
int arr[MAXN];
getchar();
for (int i = 0; i < n; ++i)
{
arr[i] = getchar() - '0';
}
int ans = 0;
for (int j = n - x; j < n; ++j)
{
if (j != 0 && j < n - y - 1 && arr[j] == 1)
ans++;
else if (j == n - y - 1 && arr[j] == 0)
ans++;
else if (j > n - y - 1 && arr[j] == 1)
ans++;
}
PRINTD(ans);
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
} B. Polycarp Training
题意
有n套题目，从以第一天开始，每天可以选一套以前没选过的题目，第i天需要解决i道题目。每天做的题目中，多余i的作废。
问最多可以做多少天。
关键字
排序、模拟
思路
直接排个序，然后一天一天枚举过去即可。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200005
#define MAXM 1000006
#define MAXK 10000010
#define MOD 998244353
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
int n;
SCAND(n);
int arr[MAXN];
for (int i = 0; i < n; ++i)
{
SCAND(arr[i]);
}
sort(arr, arr + n);
int d = 0;
for (int i = 0; i < n; ++i)
{
if (arr[i] >= d + 1)
d++;
}
PRINTD(d);
puts("");
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
} C. Good String
题意
给一个字符串，如果长度为偶数，且所有奇数位的字符与下一个字符不相同，则认为这是一个“好的”字符串。
每次可以移除其中一个字符，问最少需要多少次操作，让一个字符串变为一个“好的”字符串，并输出操作后的字符串。
关键字
贪心
思路
对于每一个位置的字符，从
开始到
枚举下一个位置的字符，直到下一个位置和当前位置不同，中间相同的都移除。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200006
#define MAXM 100006
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
char str[MAXN];
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
int n;
SCAND(n);
set<char> se;
getchar();
bool tag = n % 2;
for (int i = 0; i < n; ++i)
{
str[i] = getchar();
se.insert(str[i]);
if (i % 2 == 1 && str[i - 1] == str[i])
tag = 0;
}
if (se.size() == 1)
{
printf("%d\n\n", n);
}
else
{
char s[MAXN];
int ans = 0;
int j = 0;
for (int i = 0; i < n; ++i)
{
s[j++] = str[i++];
while (s[j-1] == str[i])
{
i++;
ans++;
}
if(i<n)
{
s[j++] = str[i];
if(i == n-2)
{
// ans++;
}
}
}
if(j%2 == 1)
{
j--;
ans++;
}
s[j] = '\0';
printf("%d\n%s\n", ans, s);
}
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
} D. Almost All Divisors
题意
对于每组案例，给定n个数，问在假设这n个数为数x的除去1和x之外的所有因子，能不能唯一确定x。
关键字
数论。
思路
先对给定的个数排序，假设第
个数为
。
令:
枚举除去
和
之外的所有因子，判断是否和给定的
个数恰好完全相同。
- 如果两边不一样，显然无解。
- 若一样，则结果即为上面
的值（当
时，
则为那个唯一的数的平方）。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200005
#define MAXM 1000006
#define MAXK 10000010
#define MOD 998244353
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int main ()
{
// SYNC
int T;
SCAND(T);
while (T--)
{
int n;
SCAND(n);
vector<ll> vt;
for (int i = 0; i < n; ++i)
{
ll t;
scanf("%lld", &t);
vt.pb(t);
}
sort(vt.begin(), vt.end());
ll ans = vt.front() * vt.back();
vector<ll> vt2;
for (ll i = 2; i <= sqrt(ans); ++i)
{
if (ans % i == 0)
{
vt2.pb(i);
ll res = ans / i;
if (res != i)
vt2.pb(res);
}
}
if (vt2.size() != n)
ans = -1;
else
{
sort(vt2.begin(), vt2.end());
for (int i = 0; i < n; ++i)
{
if (vt[i] != vt2[i])
{
ans = -1;
break;
}
}
}
printf("%lld\n", ans);
}
return 0;
} E. Two Arrays and Sum of Functions
题意
给定2个数组和
，可以对两个数组任意排序，要求求出任意区间
中的
的和。
关键字
排序、贪心
思路
首先可以确定的是，对于第个数，在求区间和的过程中，一共计算了
次。
所以，最终的结果一定是：
假设数组的顺序已经确定，则可以说
都是已经知道了的，剩下需要处理的就是数组
的顺序。
要使最终结果最小，则对于最大的，用最小的
去乘即可。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200005
#define MAXM 1000006
#define MAXK 10000010
#define MOD 998244353
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int n;
ll a[MAXN], b[MAXN];
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
SCAND(n);
for (int i = 0; i < n; ++i)
{
scanf("%lld", &a[i]);
a[i] = (a[i] * (i + 1) * (n - i));
}
for (int i = 0; i < n; ++i)
{
scanf("%lld", &b[i]);
}
sort(b, b + n);
sort(a, a + n, greater<ll>());
ll ans = 0;
for (int i = 0; i < n; ++i)
{
ans = (ans + (a[i]%MOD * b[i]%MOD) % MOD) % MOD;
}
printf("%lld\n", ans);
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
} F. Microtransactions (hard version)
题意
给定n种商品需要购买的数量，和m种折扣（折扣<a,b>表示第天第
种商品打折）。
每种商品正常价格为2，折扣价格为1，且每天余额会加1。
问买齐所有商品最少需要多少天。
关键字
二分、贪心
思路
二分枚举最少需要的天数，对于
若满足一下情况即为合法的天数：
从第天到第
天，倒过来枚举折扣。假设：
- 需要购买的商品总数为
，
- 当前的余额为
，
- 每种商品需要的数量为
，
- 对于当前的折扣
，
种商品已购买的数量为
，
- 则还需购买的数量
。
在枚举的过程中，维护余额、已购买每种商品数量
、使用优惠购买的总物品数量
：
m -= cnt; num[b] += cnt; count += cnt;
如此即可判断对于当前的天数（余额最多也为
），在尽可能使用优惠购买后，余额能否购买余下的部分：
return 2*(tot-count)<=d-count
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200005
#define MAXM 1000006
#define MAXK 10000010
#define MOD 998244353
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int n, m;
int arr[MAXN];
vector<int> sale[2 * MAXN];
int tot = 0;
int num[MAXN]; // num[i]: 已购买第i种的数量
bool ok (int mid)
{
int cnt = 0; // 当前购买的数量
int mon = mid; // 余额
MSET(num, 0);
for (int i = mid; i > 0; --i)
{
if (mon > i)
mon--;
for (int j = 0; j < sale[i].size(); ++j)
{
int x = sale[i][j]; // 在第 i 天打折出售的商品
// 对于第x种商品, 在 [当前余额能购买的数量] 和 [还需要购买的数量] 之间取最小值, 并购买这个数量
int buy = min(arr[x] - num[x], mon);
mon -= buy;
num[x] += buy;
cnt += buy;
}
}
// 判断余额是否足够购买 所有不使用折扣的商品
return 2 * (tot - cnt) <= mid - cnt;
}
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
SCAND(n);
SCAND(m);
for (int i = 1; i <= n; ++i)
{
SCAND(arr[i]);
tot += arr[i];
}
for (int i = 1; i <= m; ++i)
{
int a, b;
SCAND(a);
SCAND(b);
sale[a].pb(b);
}
int l = 1, r = 2 * MAXN;
int mid;
int ans;
while (l <= r)
{
mid = ((l + r) >> 1);
if (ok(mid))
{
r = mid - 1;
ans = mid;
} else
l = mid + 1;
}
PRINTD(l);
puts("");
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
京公网安备 11010502036488号