2020-2021 ACM-ICPC, Asia Nanjing Regional Contest (XXI Open Cup, Grand Prix of Nanjing)
给队友贡献了 5 发罚时
目录
K - K Co-prime Permutation
将数字shift k 个即可，注意特判
#include<bits/stdc++.h>
using namespace std;
int n, k;
int res[1000010];
void solve()
{
cin>>n>>k;
if(k == 0)
{
cout<<-1;
return;
}
res[1] = k;
for(int i = 2; i <= k; i++)
res[i] = i - 1;
for(int i = k + 1; i <= n; i++)
res[i] = i;
for(int i = 1; i <= n; i++)
{
cout<<res[i];
if(i != n)
cout<<" ";
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
solve();
}
L - Let's Play Curling
问蓝球中间的红球最多能有多少个
双指针弄一下
演了队友3发罚时，晕
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n, m;
int a[N], b[N], d[N];
bool vis[N];
vector<int> vx;
void solve()
{
cin>>n>>m;
vx.clear();
for(int i = 0; i <= n + m; i++)
a[i] = b[i] = d[i] = 0, vis[i] = false;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
vx.push_back(a[i]);
}
for(int i = 1; i <= m; i++)
{
cin>>b[i];
vx.push_back(b[i]);
}
// sort(a + 1, a + 1 + n);
sort(vx.begin(), vx.end());
vx.erase(unique(vx.begin(), vx.end()), vx.end());
for(int i = 1; i <= n; i++)
{
int p = lower_bound(vx.begin(), vx.end(), a[i])
- vx.begin();
d[p]++;
}
for(int i = 1; i <= m; i++)
{
int p = lower_bound(vx.begin(), vx.end(), b[i])
- vx.begin();
vis[p] = true;
}
int k = vx.size();
int res = 0;
for(int i = 0; i < k; i++)
{
int ans = 0;
if(vis[i] == false && d[i] >= 1)
{
int j = i;
ans = d[j];
while(j + 1 < k && vis[j + 1] == false && d[j + 1] >= 1)
{
j++;
ans = ans + d[j];
}
res = max(ans, res);
i = j;
}
}
if(res != 0)
{
cout<<res<<'\n';
}
else
cout<<"Impossible\n";
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int tc; cin>>tc;
for(int i = 1; i <= tc; i++)
solve();
}
M - Monster Hunter
树上背包典题
定义状态\(f_{u,i,0/1}\) 定义状态为以 \(u\) 为根的子树，已经删掉了 \(i\) 个结点,\(0/1\) 分别代表没删自己和删了自己
因为可以子节点也可以被删掉，转移的时候要减去子节点的权值，具体看代码吧
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3 + 10;
const ll inf = 1ll << 60;
int n;
ll f[N][N][2], sz[N], w[N], h[N], tmp[N][2];
vector<int> e[N];
void dfs(int u)
{
h[u] = w[u];
sz[u] = 0;
for(auto v : e[u])
{
dfs(v);
h[u] += w[v];
}
for(int i = 0; i <= N - 10; i++)
f[u][i][0] = f[u][i][1] = inf;
f[u][1][0] = h[u];
f[u][0][1] = 0;
sz[u] = 1;
for(auto v : e[u])
{
for(int i = 0; i <= sz[u] + sz[v]; i++)
tmp[i][0] = inf, tmp[i][1] = inf;
for(int i = 0; i <= sz[u]; i++)
for(int j = 0; j <= sz[v]; j++)
{
tmp[i + j][0] = min(tmp[i + j][0], f[u][i][0] + f[v][j][1] - w[v]);
tmp[i + j][0] = min(tmp[i + j][0], f[u][i][0] + f[v][j][0]);
tmp[i + j][1] = min(tmp[i + j][1], f[u][i][1] + f[v][j][1]);
tmp[i + j][1] = min(tmp[i + j][1], f[u][i][1] + f[v][j][0]);
}
sz[u] += sz[v];
for(int i = sz[u]; i >= 0; i--)
f[u][i][0] = tmp[i][0], f[u][i][1] = tmp[i][1];
}
}
void solve()
{
cin>>n;
for(int i = 1; i <= n; i++)
{
e[i].clear();
w[i] = h[i] = 0;
}
for(int i = 2; i <= n; i++)
{
int p; cin>>p;
e[p].push_back(i);
}
for(int i = 1; i <= n; i++)
cin>>w[i];
dfs(1);
// for(int i = 1; i <= n; i++)
// {
// cout<<"i: "<<i<<" " ;
// for(int j = 0; j <= n; j++)
// {
// cout<<f[i][j]<<" ";
// }
// cout<<'\n';
// }
for(int i = n; i >= 0; i--)
{
cout<<min(f[1][i][0], f[1][i][1]);
if(i != 0)
cout<<" ";
}
cout<<'\n';
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int tc; cin>>tc;
for(int i = 1; i <= tc; i++)
solve();
}
E - Evil Coordinate
check 一下16种RLUD的排列是否有一种符合即可
我懒得预处理出全排列，写了一个更暴力求排列的了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll mx,my;
string s;
void solve()
{
cin>>mx>>my;
cin>>s;
int cnt[5]; memset(cnt, 0, sizeof cnt);
for(auto it : s)
{
if(it=='R') cnt[1]++;
if(it=='L') cnt[2]--;
if(it=='U') cnt[3]++;
if(it=='D') cnt[4]--;
}
// for(int i = 1; i <= 4; i++)
// cout<<cnt[i]<<" ";
// cout<<'\n';
for(int i = 1; i <= 4; i++)
{
for(int j = 1; j <= 4; j++)
{
for(int k = 1; k <= 4; k++)
{
for(int l = 1; l <= 4; l++)
{
if(i != j && i != k && i != l
&& j != k && j != l
&& k != l)
{
int x = 0, y = 0;
int tx = 0, ty = 0;
bool ok = true;
if(i == 1 || i == 2)
{
x = x + cnt[i];
if(y == my && ((tx <= mx && mx <= x) || (tx >= mx && mx >= x)))
ok = false;
tx = x;
}
else
{
y = y + cnt[i];
if(x == mx && ((ty <= my && my <= y) || (ty >= my && my >= y)))
ok = false;
ty = y;
}
if(j == 1 || j == 2)
{
x = x + cnt[j];
if(y == my && ((tx <= mx && mx <= x) || (tx >= mx && mx >= x)))
ok = false;
tx = x;
}
else
{
y = y + cnt[j];
if(x == mx && ((ty <= my && my <= y) || (ty >= my && my >= y)))
ok = false;
ty = y;
}
if(k == 1 || k == 2)
{
x = x + cnt[k];
if(y == my && ((tx <= mx && mx <= x) || (tx >= mx && mx >= x)))
ok = false;
tx = x;
}
else
{
y = y + cnt[k];
if(x == mx && ((ty <= my && my <= y) || (ty >= my && my >= y)))
ok = false;
ty = y;
}
if(l == 1 || l == 2)
{
x = x + cnt[l];
if(y == my && ((tx <= mx && mx <= x) || (tx >= mx && mx >= x)))
ok = false;
tx = x;
}
else
{
y = y + cnt[l];
if(x == mx && ((ty <= my && my <= y) || (ty >= my && my >= y)))
ok = false;
ty = y;
}
if(ok)
{
// cout<<i<<" "<<j<<" "<<k<<" "<<l<<'\n';
// cout<<cnt[i]<<" "<<cnt[j]<<" "<<cnt[k]<<" "<<cnt[l]<<'\n';
cnt[2] = abs(cnt[2]);
cnt[4] = abs(cnt[4]);
while(cnt[i] >= 1)
{
cnt[i]--;
if(i == 1) cout<<'R';
else if(i == 2) cout<<'L';
else if(i == 3) cout<<"U";
else if(i == 4) cout<<"D";
}
while(cnt[j] >= 1)
{
cnt[j]--;
if(j == 1) cout<<'R';
else if(j == 2) cout<<'L';
else if(j == 3) cout<<"U";
else if(j == 4) cout<<"D";
}
while(cnt[k] >= 1)
{
cnt[k]--;
if(k == 1) cout<<'R';
else if(k == 2) cout<<'L';
else if(k == 3) cout<<"U";
else if(k == 4) cout<<"D";
}
while(cnt[l] >= 1)
{
cnt[l]--;
if(l == 1) cout<<'R';
else if(l == 2) cout<<'L';
else if(l == 3) cout<<"U";
else if(l == 4) cout<<"D";
}
cout<<'\n';
return;
}
}
}
}
}
}
cout<<"Impossible\n";
// if(my == 0 && (0 <= mx && mx <= x) || )
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int tc; cin>>tc;
for(int i = 1; i <= tc; i++)
solve();
}
F - Fireworks
发现是一个可以三分函数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n, m, v;
double p, q;
double qmi(double a, int b)
{
double res = 1.0;
while(b)
{
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
double calc(int x)
{
return (1.0 * n * x + m) / (1.0 - qmi(q, x));
}
void solve()
{
cin>>n>>m>>v;
p = 1.0 * v / 10000;
q = 1.0 - p;
int l = 1, r = 1e9;
while(r - l > 2)
{
int lmid = l + (r - l) / 3;
int rmid = r - (r - l) / 3;
if(calc(lmid) <= calc(rmid))
r = rmid;
else l = lmid;
}
double res = 1e18;
for(int i = l; i <= r; i++)
res = min(res, calc(i));
//double res = min(calc(l), calc(r));
printf("%.7lf\n", res);
}
int main()
{
// ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int tc; cin>>tc;
for(int i = 1; i <= tc; i++)
solve();
}
A - Ah, It's Yesterday Once More
尽可能地构造出分叉可以多走的迷宫，使得指令无效，而不是构造步数尽可能多的迷宫
// AC one more times
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//const int mod = 1e9 + 7;
const int N = 2e5 + 10;
// AC one more times
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[30][30] = {{0 ,1 ,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
{1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1},
{2, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1},
{3, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1},
{4, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1},
{5, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0},
{6, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0},
{7, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0},
{8, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1},
{9, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1},
{10, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1},
{11, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0},
{12, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0},
{13, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0},
{14, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1},
{15, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1},
{16, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1},
{17, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0},
{18, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0},
{19, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0},
{20, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0}};
void solve()
{
cout<<"20 20\n";
for(int i = 1; i <= 20; i++)
{
for(int j = 1; j <=20; j++)
cout<<a[i][j];
cout<<'\n';
}
return;
}
int main()
{
std::ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int TC = 1;
//cin >> TC;
for(int tc = 1; tc <= TC; tc++)
{
//cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
- ACM-ICPC Regional Contest Nanjing KLMEFAacm-icpc regional contest nanjing regional contest nanjing 2022 regional contest nanjing 2023 yesterday regional contest nanjing acm-icpc regional contest seoul inscryption regional contest nanjing nanjing regional contest grand programming acm-icpc american regional the universal acm-icpc regional subregional programming acm-icpc contest