补题链接:https://codeforces.com/gym/104337
M. Different Billing
签到题,写几个柿子然后枚举B或C即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int x, y;cin >> x >> y;
for(int c = 0;c <= x; ++ c)
{
int b = (y - 2500 * c) / 1000;
if(b < 0 || 1000 * b + 2500 * c != y)continue;
int a = x - b - c;
if(a >= 0)
{
cout << a << ' ' << b << ' ' << c << '\n';
return 0;
}
}
cout << -1 << '\n';
return 0;
}
C. Darkness I
这题是对Minecraft中无限水的拓展过程为背景的一道思维题。
先考虑一下n, m均为奇数的情况:
然后从这种情况开始,增加一列,或者增加一行,都需要多加一个黑棋子,如果同时增加一行一列,那也是只需要增加一个棋子,增加到右下角的位置即可。
所以我们按照这种构造方法输出答案即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;cin >> n >> m;
int res = (n + 1) / 2 + (m + 1) / 2 - 1;
if(n % 2 == 0 || m % 2 == 0)res ++;
cout << res << '\n';
return 0;
}
J.Expansion
这题可以转化为以下题意:
一开始身上资源为0,从1号点走到n号点,每个点上有一些资源(可能为负数),每秒钟可以选择走或者不走,且每秒会得到当前点上的资源(此时的资源已经做了前缀和),为了保证每时每刻身上的资源都不为负数,请问从1走到n所需的最小时间。
我们模拟一下这个过程,如果到了某个点发现如果在当前点停留1秒会使得资源变为负数,就说明“我应该在左边的某个正数点多停留一会儿”,而为了使得停留时间最少,我会选择最大的点进行停留。
注意一些特判,题意需要保证最后在n一直停留都不会使得资源为负数,所以prefix[n]
需要大于等于零,还有为了使得可以走到n
,需要保证第一个非0的数为正数。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9, p = 998244353;
int a[N], prefix[N];
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;cin >> n;
for(int i = 1;i <= n; ++ i)cin >> a[i];
for(int i = 1;i <= n; ++ i)prefix[i] = prefix[i - 1] + a[i];
if(prefix[n] < 0)
{
cout << -1 << '\n';
return 0;
}
//遇到的第一个是负数
for(int i = 1;i <= n; ++ i)
{
if(prefix[i] != 0)
{
if(prefix[i] < 0)
{
cout << -1 << '\n';
return 0;
}
break;
}
}
int ans = 0, res = 0, mx = 0;
//前面一步步推进
for(int i = 1;i <= n; ++ i)
{
mx = max(mx, prefix[i]);
res += prefix[i];
ans ++;//走一秒
if(res < 0)//说明走快了,应该在前面多停留一段时间的
{
//补几秒钟
int ti = (-res + mx - 1) / mx;
ans += ti;
res += ti * mx;
}
}
cout << ans << '\n';
return 0;
}
H.Binary Craziness
赛时卡这道题了,一直在想拆位的做法(形成惯性思维了......糟糕)。
其实这题我们可以这样想,最多m条边,也就是所有点的出度之和一定是2m,然后我们最多n个点,也就是说出度的种类数不会超过 \(\sqrt{2m}\) 种。因为如果要使得种类数最多,那么就是每一种都只有一个,且从小到大,出度数组排序后(长度为t
)将会是1, 2, 3, 4, 5, ...
其和为\(\frac{t(t + 1)}{2} \le 2m\),所以长度t
不会很大。
我们就可以根据这个原理做一个桶记录一下某个数字出现的次数,然后直接双重循环暴力写!
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9, p = 998244353;
int cnt[2 * N], a[N];
int f(int x, int y)
{
return (x ^ y) * (x | y) * (x & y);
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;cin >> n >> m;
for(int i = 1;i <= m; ++ i)
{
int x, y;cin >> x >> y;
a[x] ++, a[y] ++;
}
for(int i = 1;i <= n; ++ i)cnt[a[i]] ++;
vector<int> v;
for(int i = 1;i <= 2 * m; ++ i)if(cnt[i])v.push_back(i);
int res = 0;
for(int i = 0;i < v.size(); ++ i)
{
for(int j = i + 1;j < v.size(); ++ j)
{
res = (res + cnt[v[i]] * cnt[v[j]] % p * f(v[i], v[j]) % p) % p;
}
}
cout << res << '\n';
return 0;
}
F.Inverse Manacher
这题甚至不需要会马拉车。
题目给定一个“回文半径”的数组,要你还原还原出一种可能的字符串(仅包含ab)。数据保证至少存在一种解。
只需要理解回文半径的含义即可。
当我们走到i
时,如果a[i] > 1
,说明我们要把i左边的一部分堆成到右边去,为了优化复杂度,我们可以用双指针,r
表示此时b
数组(也就是答案数组)的大小,也就是我们更新到的右端,当r < i + a[i] - 1
时,我们就拓展得到b[r]
,如果此时i > r
,再根据一些情况来确定b[i]
即可(交替的取a, b)。
注意数组开大一点,马拉车一般是两倍空间。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e6 + 9;
int a[N];
char b[N];
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;cin >> n;
for(int i = 0;i <= 2 * n + 1; ++ i)cin >> a[i];
char ch = 'a';
for(int i = 0, r = 0;i <= 2 * n + 1; ++ i)
{
while(i + a[i] - 1 > r)++ r, b[r] = b[2 * i - r];
if(i == 0)b[i] = '&';
else if(i & 1)b[i] = '|';
else if(b[i] == 0)b[i] = ch, ch = (ch == 'a' ? 'b' : 'a');
}
for(int i = 2;i <= 2 * n + 1;i += 2)cout << b[i];
return 0;
}
K.Dice Game
这题主要难在分析出n
个事件相互独立。
当x
确定时,对于n
个人当中的某一个人,他胜利的概率是\(p = \frac{m-x}{m-1}\),这个有两种理解,第一个感性的理解就是,当投出y = x
是没有意义的,所以有效的y
一共是m
个,其中m - x
个是可以赢的。
数学的理解是,这个人可能在第一次赢,也可能第二次赢,也可能第三次赢...,设平局概率为t
,胜利概率为q
。
其中\(t=\frac{1}{m}\), \(q = \frac{m-x}{m}\)。
根据等比数列求和我们可以知道:
然后对于某个x,一共有n个人,那么答案就是\(p^n = (\frac{m-x}{m-1}) ^ n\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9, p = 998244353;
int qmi(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1)res = res * a % p;
a = a * a % p, b >>= 1;
}
return res;
}
int inv(int x){return qmi(x, p - 2);}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;cin >> n >> m;
int res = 1;
for(int i = 1;i <= m; ++ i)
{
cout << qmi((m - i) * inv(m - 1) % p, n) << ' ';
}
return 0;
}
I.Step
已知\(2t | k(k+1)\),求最小的\(k\),其中\(t=lcm(p_1,p_2...,p_n)\)。
不妨设\(2t=a*b\),且\(a|k,b|(k+1)\),且\(ax=k,by=(k+1)\),那么我们可以得到:
转换一下得到:
枚举a
,可以算出b
,然后exgcd
搞出最小的x
,即得到了k=ax
答案。
现在问题是如何枚举a
,我们看这个exgcd
式子可以发现我们需要保证gcd(a, b) = 1
,且有2t = a * b
,所以我们可以对2t
进行唯一分解,然后选取不同质因子种类分配给a
和b
。
分配方案可以通过二进制直接做。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9, inf = 8e18;
int p[N];
int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
map<int, int> mp;
vector<int> v;
void func(int x)
{
for(int i = 2;i <= x / i; ++ i)
{
if(x % i)continue;
v.push_back(i);
mp[i] = 1;
while(x % i == 0)mp[i] *= i, x /= i;
}
if(x > 1)v.push_back(x), mp[x] = x;
}
int exgcd(int a, int b, int &x, int &y)
{
if(!b)return x = 1, y = 0, a;
int d = exgcd(b, a % b, y , x);
y -= a / b * x;
return d;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;cin >> n;
for(int i = 1;i <= n; ++ i)cin >> p[i];
int lc = p[1];
for(int i = 2;i <= n; ++ i)lc = lcm(lc, p[i]);
//对2 * lc进行质因数分解
func(2 * lc);
int res = inf;
for(int i = 0;i < (1ll << v.size()); ++ i)
{
//根据i得到a
int a = 1;
for(int j = 0;j < v.size(); ++ j)
if(i >> j & 1)a = a * mp[v[j]];
int b = 2 * lc / a;
int x, y, d = exgcd(a, b, x, y);
x = -x;
x = (x % (b / d) + (b / d)) % (b / d);
if(a * x)res = min(res, x * a);
//cout << "a = " << a << ' ' << "ax = " << a * x << '\n';
}
cout << res << '\n';
return 0;
}
- 题解 Programming Collegiate Provincial Contestprogramming collegiate provincial contest 题解programming collegiate provincial programming collegiate provincial shandong programming provincial collegiate sichuan programming collegiate provincial guangdong programming provincial collegiate shandong programming collegiate provincial counting programming provincial collegiate sponsored 2023 programming collegiate provincial heilongjiang programming collegiate provincial