namomo camp day1
目录B - Brexiting and Brentering
字符串替换
void solve()
{
string s; cin>>s;
int n = s.size();
for(int i = n - 1; i >= 0; i--)
{
if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' ||
s[i] == 'o' || s[i] == 'u')
{
for(int j = 0; j <= i; j++)
cout<<s[j];
cout<<"ntry\n";
return;
}
}
cout<<s<<'\n';
return;
}
A - Amusement Arcade
对于一段区间将其分成两段去做，只考虑其中一段区间即可，不难发现当区间大小为 \(2 ^ a + 1\) 时可以满足条件，判断是否满足 \(n = 2 ^ a + 2 ^ b + 1\) 即可
void solve()
{
ll n;
cin>>n;
ll b1 = 1;
if(n == 1 || n == 3)
{
cout<<1<<'\n';
return;
}
for(int p = 0; p <= 60; p++)
{
if(p) b1 *= 2;
ll b2 = 1;
for(int q = 0; q <= 60; q++)
{
if(q) b2 *= 2;
//cout<<b1 + b2 +<<" "<<b1<<" "<<b2<<'\n';
if(n == b1 + b2 + 1)
{
if(n == 1)
cout<<1<<'\n';
else
cout<<b1 + 1<<'\n';
return;
}
}
}
cout<<"impossible\n";
return;
}
I - Monty's Hall
第一次没选中: \(\dfrac{d - s}{d}\) ，换 \(l\) 个选中了 \(\dfrac{l}{d - s - e}\)
第一次选中: \(\dfrac{s}{d}\) ，换 \(l\) 个还是选中了 \(\dfrac{s - l}{s}\)
答案： $\dfrac{d - s}{d} \times $$\dfrac{l}{d - s - e}$$+\dfrac{s}{d}$$\times \dfrac{s - l}{s}$ ，\(l = \min(s, d - s - e)\)
void solve()
{
int d, s, e; cin>>d>>s>>e;
int l = min(s, d - s - e);
double res = 1.0 * (d - s) / d * l / (d - s - e) + 1.0 * s / d * (s - l) / s;
//cout<<res<<'\n';
printf("%.7lf\n", res);
return;
}
D - Excursion to Porvoo
离线操作，维护区间最小值，再依次加边
我用线段树作，用 set 也可以，显得我很蠢
const int N = 1e5 + 10;
int n, m, q, cnt[N];
vector<array<int, 2>> event;
vector<array<ll, 2>> e[N];
ll res[N];
struct segtree
{
ll s, w, p;
}seg[N * 4];
void update(int id)
{
seg[id].s = seg[id * 2].s + seg[id * 2 + 1].s;
seg[id].w = min(seg[id * 2].w, seg[id * 2 + 1].w);
if(seg[id * 2].w <= seg[id * 2 + 1].w)
seg[id].p = seg[id * 2].p;
else
seg[id].p = seg[id * 2 + 1].p;
}
void build(int id, int l, int r)
{
if(l == r)
{
seg[id].s = 0, seg[id].w = -1, seg[id].p = l;
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
void change(int id, int l, int r, int pos, ll s, ll w)
{
if(l == r)
{
seg[id].s = s;
seg[id].w = w;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid)
change(id * 2, l, mid, pos, s, w);
else
change(id * 2 + 1, mid + 1, r, pos, s, w);
update(id);
}
void solve()
{
cin>>n>>m;
int r = n - 1;
for(int i = 1; i <= m; i++)
{
ll u, s, w; cin>>u>>s>>w;
e[u].push_back({w, s});
}
for(int i = 1; i < n; i++)
sort(e[i].begin(), e[i].end());
cin>>q;
for(int i = 1; i <= q; i++)
{
int w; cin>>w;
event.push_back({w, i});
}
sort(event.begin(), event.end());
build(1, 1, r);
//return;
for(auto [w, id] : event)
{
while(seg[1].w < w)
{
ll cost = 1e18;
int pos = seg[1].p;
for(int i = cnt[pos]; i < e[pos].size(); i++)
if(e[pos][i][0] >= w && e[pos][i][1] <= cost)
{
cost = e[pos][i][1];
cnt[pos] = i + 1;
}
// cout<<pos<<" "<<cost<<'\n';
if(cost == 1e18)
{
break;
}
else
{
// cout<<pos<<" "<<cnt[pos]<<" "<<e[pos][cnt[pos] - 1][1]<<" "<<e[pos][cnt[pos] - 1][0]<<'\n';
change(1, 1, r, pos, e[pos][cnt[pos] - 1][1], e[pos][cnt[pos] - 1][0]);
//break;
}
}
// cout<<"calc: "<<w<<" "<<id<<" "<<seg[1].w<<" "<<seg[1].s<<'\n';
if(seg[1].w >= w)
res[id] = seg[1].s;
else
res[id] = -1;
//break;
}
for(int i = 1; i <= q; i++)
{
if(res[i] == -1) cout<<"impossible\n";
else
cout<<res[i]<<'\n';
}
return;
}
H - Looking for Waldo
枚举每个位置和一条边的长度，再二分另一条边的长度，时间复杂度\(O(h^2w\log w)\) 或 \(O(hw^2\log h)\)
好像有更快的做法
int n, m;
void solve()
{
cin>>n>>m;
int s[n + 10][m + 10][6];
memset(s, 0, sizeof s);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
char x; cin>>x;
if(x == 'W') s[i][j][1] = 1;
else if(x == 'A') s[i][j][2] = 1;
else if(x == 'L') s[i][j][3] = 1;
else if(x == 'D') s[i][j][4] = 1;
else if(x == 'O') s[i][j][5] = 1;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
for(int k = 1; k <= 5; k++)
s[i][j][k] = s[i][j][k] + s[i - 1][j][k] + s[i][j - 1][k] - s[i - 1][j - 1][k];
// for(int k = 1; k <= 5; k++)
// cout<<s[n][m][k]<<'\n';
int res = n * m + 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
for(int x2 = i; x2 <= n; x2++)
{
int x = i, y = j;
int l = 1, r = m - j + 1;
bool st = true;
while(l < r)
{
int mid = (l + r) >> 1;
int y2 = y + mid - 1;
bool ok = true;
for(int k = 1; k <= 5; k++)
{
int t = s[x2][y2][k] - s[x2][y - 1][k]
- s[x - 1][y2][k] + s[x - 1][y - 1][k];
//cout<<i<<" "<<j<<" "<<k<<" " <<t<<" "<<mid<<'\n';
if(t == 0)
ok = false;
}
if(ok) r = mid;
else l = mid + 1;
}
for(int k = 1; k <= 5; k++)
{
int y2 = y + l - 1;
int t = s[x2][y2][k] - s[x2][y - 1][k]
- s[x - 1][y2][k] + s[x - 1][y - 1][k];
//cout<<i<<" "<<j<<" "<<k<<" " <<t<<" "<<'\n';
if(t == 0)
st = false;
}
if(st)
res = min((x2 - x + 1) * l, res);
}
//cout<<i<<" "<<j<<" "<<l<<'\n';
if(res == n * m + 1)
cout<<"impossible\n";
else
cout<<res<<'\n';
return;
}
G - Killjoys' Conference
对于每个连通块（哪怕只有一个点），都可以分成两堆，去放进房间，那么设连通块的个数为 \(c\) ，答案即为 \(2 ^ {c - 1} + 1\)， 这里 \(c\) 为什么要 -1 手玩一下就懂了
无解情况看样例三分析，存在长度为 \(3\) 的环就无解
typedef long long ll;
//const int mod = 1e9 + 7;
const int N = 1e6 + 10;
ll qmi(ll a, ll b, ll mod)
{
ll ans = 1 % mod;
while(b)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int n, m, p, f[N];
vector<int> e[N];
bool ok = true;
void dfs(int u, int from)
{
for(auto v : e[u])
{
if(v == from) continue;
if(f[v])
{
if(f[u] - f[v] == 2)
ok = false;
}
else
{
f[v] = f[u] + 1;
dfs(v, u);
}
}
}
void solve()
{
cin>>n>>m>>p;
for(int j = 1; j <= m; j++)
{
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
ll res = 1;
int c = 0;
for(int i = 1; i <= n; i++)
{
if(f[i] == 0)
{
f[i] = 1;
dfs(i, 0);
c++;
}
}
res = res * qmi(2, c - 1, p) % p;
res = res + 1;
res %= p;
if(ok)
cout<<res<<'\n';
else
cout<<"impossible\n";
return;
}