2024 (ICPC) Jiangxi Provincial Contest -- Official Contest
A. Maliang Learning Painting
题意：a + b + c
void solve(){
ll a, b, c;
cin >> a >> b >> c;
ll ans = a + b + c;
cout << ans << '\n';
}
C. Liar
题意：n 个 数字总和是 s ，每个人说出自己得到的数字，有人可能撒谎，问最多有多少人说真话
思路：首先总和就是 s 的话，最多所有人说的都是真话，再或者假设 1~i 的人都不撒谎，只有第 n 个人撒谎
void solve(){
ll n, s;
cin >> n >> s;
ll sum = 0;
for(int i = 1; i <= n; i ++){
ll x;
cin >> x;
sum += x;
}
if(sum == s) cout << n << '\n';
else cout << n - 1 << '\n';
}
D. Magic LCM
题意：给定 n 个数，每次可以选定两个数，把其中一个改为 gcd(x, y)，另外一个改为 lcm(x, y)，求最大的数列和
思路：可以发现，通过操作，可以把二者共有的质因子的最大的幂交给一方，如果是非共有的质因子，会交给较大的一方，相当于共有质因子的较大幂和非共有质因子交给一方，共有质因子的较小幂交给另外一方，我们可以先处理 1e3 以内的质数，求出每个数的质因子，然后对共有质因子的幂进行排序，然后找出项数最多的质因子，对该质因子的所有幂排序，其它的质因子会全部转移当这个项数最多的质因子上，同时我们要贪心的其它质因子的每一项的幂按照大和大匹配来运算，最后不要忘了除了最多项数的质因子之外其它的全部变成了1，要把它们加上
const int N = 1000010, mod = 998244353;
const int Mod = 1e9 + 7, INF = 0x3f3f3f3f;
bool vis[1010];
vector<ll> pri;
void ola_s(ll n){
for(int i = 2; i <= n; i ++){
if(!vis[i]) pri.push_back(i);
for(auto v : pri){
if(i * v > n) break;
vis[i * v] = true;
if(i % v == 0) break;
}
}
}
vector<ll> v[N];
set<ll> st;
void get_fac(ll x){
for(auto p : pri){
if(x < p) break;
if(x % p == 0){
ll t = 1;
while(x % p == 0) {
t *= p;
x /= p;
}
v[p].push_back(t);
st.insert(p);
}
}
if(x > 1){
v[x].push_back(x);
st.insert(x);
}
}
void solve(){
ll n;
cin >> n;
vector<ll> a(n + 1);
for(int i = 1; i <= n; i ++){
cin >> a[i];
get_fac(a[i]);
}
ll len = 0, ma = 0;;
for(auto i : st){
if(v[i].size() > len) len = v[i].size(), ma = i;
sort(v[i].begin(), v[i].end());
}
for(auto i : st){
if(i == ma) continue;
for(int j = len - 1, k = v[i].size() - 1; k >= 0; j --, k --){
v[ma][j] = v[ma][j] * v[i][k] % mod;
}
}
ll ans = n - v[ma].size();
for(auto i : v[ma]) ans = (ans + i + mod) % mod;
cout << ans << '\n';
for(auto i : st) v[i].clear();
st.clear();
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ola_s(1000);
int t = 1;
cin >> t;
while(t --){
solve();
}
return 0;
}
G. Multiples of 5
题意：给定一个11进制数，求它是不是 5 的倍数
思路：首先这个11进制数非常大，肯定不能转化成十进制的数来求，我们手推一下 11 的没一项幂会发现它们的最后一个数字都是 1 ，也只有这个 1 会影响答案，我们求出 11 进制下每一位有多少个，然后加一下看是不是 5 的整数倍就行了。（又把‘A’ == 10当成'A' == 11 wa了一发）
void solve(){
ll n;
cin >> n;
ll ans = 0;
for(int i = 1; i <= n; i ++){
ll a1, a2;
char b;
cin >> a1 >> b;
if(b != 'A') a2 = (b - '0');
else a2 = 10;
ans = (ans + a1 * a2) % 5;
}
if(ans == 5 || ans == 0) cout << "Yes\n";
else cout << "No\n";
}
H. Convolution
题意：给定一个n * m的矩阵 a ，求一个k * l的矩阵 b 和 a 的乘积的最小值，b 只包含(-1, 0, 1)
思路：手画一下发现，矩阵 b 的每一项，会和矩阵 a 左上角 （i, j) ~ (n - k + i, m - l + j) 的子矩阵相乘，处理一下二维前缀和，正数取1，否则取-1
void solve(){
ll n, m, k, l;
cin >> n >> m >> k >> l;
vector<vector<ll>> I(3010, vector<ll>(3010));
vector<vector<ll>> IQ(3010, vector<ll>(3010));
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
cin >> I[i][j];
ll x = I[i][j];
IQ[i][j] = x + IQ[i - 1][j] + IQ[i][j - 1] - IQ[i - 1][j - 1];
}
}
auto query =[&](ll x1, ll y1, ll x2, ll y2) -> ll{
ll ans = IQ[x2][y2] - IQ[x1 - 1][y2] - IQ[x2][y1 - 1] + IQ[x1 - 1][y1 - 1];
return ans;
};
ll res = 0;
for(int i = 1; i <= k; i ++){
for(int j = 1; j <= l; j ++){
res += abs(query(i, j, n - k + i, m - l + j));
}
}
cout << res << '\n';
}
I. Neuvillette Circling
题意：给定 n 个点，所有点之间都有边相连接，问包含 1 ~ n * (n - 1) / 2 条边分别至少需要的半径
思路：分类讨论，两种情况，两个点确定一个圆，三个点确定一个圆（外接圆），然后分别求一下包含多少个点
using db = double;
const db eps = 1e-6;
int sign(db a) { return a < -eps ? -1 : a > eps; } //< :-1 =:0 >:1
struct Point {
db x, y;
Point() {}
Point(db x, db y) : x(x), y(y) {}
Point operator+(Point p) { return {x + p.x, y + p.y}; }
Point operator-(Point p) { return {x - p.x, y - p.y}; }
Point operator*(db d) { return {x * d, y * d}; }
Point operator/(db d) { return {x / d, y / d}; }
bool operator==(Point &p) const { return !sign(x - p.x) && !sign(y - p.y); }
int toleft(Point b) { // 点在线段的方向
ll res = x * b.y - y * b.x;
if (res == 0)
return 0; // 直线上
else if (res > 0)
return 1; // 左
return -1; // 右
}
friend istream &operator>>(istream &is, Point &p) {
return is >> p.x >> p.y;
}
friend ostream &operator<<(ostream &os, Point p) {
return os << "(" << p.x << ", " << p.y << ")";
}
};
struct Circle {
Point o;
db r;
Circle() {}
Circle(Point _o, db _r) : o(_o), r(_r) {}
};
db dot(Point a, Point b) {
return a.x * b.x + a.y * b.y;
}
db cross(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
db dis1(Point a, Point b) { // 两点距离的平方
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
// return sqrtl((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));//long double ver
}
db dis2(Point a, Point b) { // 两点距离的平方
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool ver(Point a, Point b) { // 是否垂直
return sign(dot(a, b)) == 0;
}
db pw(db x) {
return x * x;
}
db fun(db a1, db a2, db a3, db b1, db b2, db b3, db c1, db c2, db c3) {
return a1 * b2 * c3 +
b1 * c2 * a3 +
c1 * a2 * b3 -
a3 * b2 * c1 -
b3 * c2 * a1 -
c3 * a2 * b1;
}
Circle three_p_get_cir(Point a, Point b, Point c) { // 求三角形的外接圆
db A = dis1(a, b), B = dis1(b, c), C = dis1(a, c);
db L = (A + B + C) / 2; // 三角形半周长
db S = sqrt(L * (L - A) * (L - B) * (L - C)); // 由海伦公式求得三角形面积
db r = A * B * C / (4 * S); // 外接圆半径
// cout << a << " " << b << " " << c << endl;
// cout << A << " " << B << " " << C << endl;
// cout << r << endl;
// 求圆心坐标
Point res;
res.x = 0.5 * fun(1, 1, 1, pw(a.x) + pw(a.y), pw(b.x) + pw(b.y), pw(c.x) + pw(c.y), a.y, b.y, c.y) / fun(1, 1, 1, a.x, b.x, c.x, a.y, b.y, c.y);
res.y = 0.5 * fun(1, 1, 1, a.x, b.x, c.x, pw(a.x) + pw(a.y), pw(b.x) + pw(b.y), pw(c.x) + pw(c.y)) / fun(1, 1, 1, a.x, b.x, c.x, a.y, b.y, c.y);
return Circle(res, r);
}
Circle two_p_get_cir(Point a, Point b) { // 已知直径求圆
db r = dis1(a, b) / 2;
Point res;
res.x = (a.x + b.x) / 2;
res.y = (a.y + b.y) / 2;
return Circle(res, r);
}
void solve(){
ll n;
cin >> n;
vector<Point> p(n);
vector<Circle> a;
for(int i = 0; i < n; i ++) cin >> p[i];
for(int i = 0; i < n; i ++){
for(int j = i + 1; j < n; j ++){
a.push_back(two_p_get_cir(p[i], p[j]));
for(int k = j + 1; k < n; k ++){
a.push_back(three_p_get_cir(p[i], p[j], p[k]));
}
}
}
auto cal =[&](Circle c) -> int{
auto [x1, y1] = c.o;
db r2 = c.r * c.r;
ll ans = 0;
for(auto &[x2, y2] : p){
db res = pw(x2 - x1) + pw(y2 - y1);
if(sign(res - r2) == 0 || sign(res - r2) == -1) ans ++;
}
return ans * (ans - 1) / 2;
};
vector<db> ans(n * (n - 1) / 2 + 1, INF);
for(auto &t : a){
ll num = cal(t);
ans[num] = min(ans[num], t.r);
}
for(int i = n * (n - 1) / 2 - 1; i >= 1; i --) ans[i] = min(ans[i], ans[i + 1]);
for(int i = 1; i <= n * (n - 1) / 2; i ++){
cout << fixed << setprecision(8) << ans[i] << '\n';
}
}
J. Magic Mahjong
题意：给定一副麻将牌，判断手上是否有十三幺和七对（不打麻将英语还不行的有难了）
思路：模拟即可，包含七个对子或者十三种给定牌
string win[] = {"1z", "2z", "3z", "4z", "5z", "6z", "7z", "1p", "9p", "1s", "9s", "1m", "9m"};
void solve(){
string s;
cin >> s;
vector<string> pai;
vector<ll> ws(10);
for(int i = 0; i < s.size(); i += 2){
string s1;
s1 += s[i];
s1 += s[i + 1];
pai.push_back(s1);
}
map<string, ll> mp;
for(auto v : pai) mp[v] ++;
if(mp.size() == 7){
bool ok = 1;
for(auto [x, y] : mp){
if(y != 2) ok = 0;
}
if(ok == 1){
cout << "7 Pairs\n";
return;
}
}
if(mp.size() == 13){
vector<ll> se(13);
for(auto [x, y] : mp){
bool ok = 0;
for(int i = 0; i < 13; i ++){
if(x == win[i]){
ok = 1;
se[i] = 1;
break;
}
}
if(!ok){
cout << "Otherwise\n";
return;
}
}
ll sum = 0;
for(auto x : se) sum += x;
if(sum == 13) cout << "Thirteen Orphans\n";
else cout << "Otherwise\n";
}
else cout << "Otherwise\n";
}
K. Magic Tree
题意：2 * n的路有几条不同的填充方式
思路：手画一下发现 2^（n - 1) 即可
ll fastpow(ll a, ll n){
ll res = 1, base = a;
while(n){
if(n & 1) res = (res * base) % mod;
base = (base * base) % mod;
n >>= 1;
}
return res;
}
void solve(){
ll n;
cin >> n;
ll ans = fastpow(2, n - 1);
cout << ans << '\n';
}
L. Campus
题意：一个 n 个点 m 条边的无向图，每个节点上有 ai 个人。n 个节点中有 k 个 节点为出口，每个出口有一个开放时间 [li , ri ]。求第 1 ∼ T 时刻所有人到 最近的开放出口的路径长度之和。
思路：预处理出每一种出口对每个人的最短路，然后分情况枚举取min即可
struct Node{
ll y, v;
Node(ll _y, ll _v){
y = _y, v = _v;
}
};
struct gate{
ll id, l, r;
bool operator < (gate & a1)const{
return l < a1.l;
}
};
bool cmp(gate & a1, gate & a2){
return a1.l < a2.l;
}
vector<Node> edge[N];
ll a[N], res = 0;
void solve(){
ll n, m, k, T;
cin >> n >> m >> k >> T;
string s1;
for(int i = 1; i <= k; i ++) s1 += '0';
vector<gate> v(k + 1);
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= k; i ++){
ll id, l, r;
cin >> id >> l >> r;
v[i] = {id, l, r};
}
for(int i = 1; i <= m; i ++){
ll u, v, w;
cin >> u >> v >> w;
edge[u].push_back({v, w});
edge[v].push_back({u, w});
}
auto dijkstra =[&](ll s, vector<ll> & p) -> void{
vector<ll> dist(n + 1, INF);
vector<bool> b(n + 1, false);
priority_queue<PLL, vector<PLL>, greater<PLL>> q;
dist[s] = 0;
for(int i = 1; i <= n; i ++) q.push({dist[i], i});
while(!q.empty()){
ll x = q.top().second;
q.pop();
if(b[x]) continue;
b[x] = true;
for(auto i : edge[x]){
if(dist[x] + i.v < dist[i.y]){
dist[i.y] = dist[x] + i.v;
q.push({dist[i.y], i.y});
}
}
}
p = dist;
};
vector<vector<ll>> d(k + 1, vector<ll>(n + 1));
for(int i = 1; i <= k; i ++){
dijkstra(v[i].id, d[i]);
}
// for(int i = 1; i <= k; i ++){
// cout << i << '\n';
// for(int j = 1; j <= n; j ++){
// cout << d[i][j] << ' ';
// }
// cout << '\n';
// }
map<string, vector<ll>> mp;
vector<ll> ans(T + 1);
for(int i = 1; i <= T; i ++){
string s = s1;
for(int j = 1; j <= k; j ++){
if(v[j].l <= i && i <= v[j].r) s[j - 1] = '1';
}
mp[s].push_back(i);
}
for(auto [x, y] : mp){
vector<ll> q(n + 1, INF);
bool ok = 0;
for(int i = 1; i <= k; i ++){
if(x[i - 1] == '1'){
ok = 1;
for(int j = 1; j <= n; j ++){
q[j] = min(q[j], d[i][j]);
}
}
}
ll res = 0;
if(!ok){
res = -1;
}
else{
for(int i = 1; i <= n; i ++) res += q[i] * a[i];
}
for(auto v : y) ans[v] = res;
}
for(int i = 1; i <= T; i ++) cout << ans[i] << '\n';
}
标签：Provincial,return,Contest,--,auto,ll,int,vector,ans From： https://www.cnblogs.com/RosmontisL/p/18307057