M - V-Diagram
Solution
很显然，连续的子序列的一段肯定是包括最左边或最右边的其中一个点
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1ll << 60;
int main(){
int t; cin >> t;
while (t--) {
int n; cin >> n;
ll sum = 0;
double ans = 0;
vector<ll> a(n + 1),s(n + 1,0);
for (int i = 1; i <= n; i++)
cin >> a[i], s[i] = s[i - 1] + a[i];
ll minn = inf; int idx = -1;
for (int i = 1; i <= n; i++)
if (a[i] < minn) minn = a[i], idx = i;
for (int i = 1; i < idx; i++)
ans = max(ans, 1.0 * (s[n] - s[i - 1]) / (n - i + 1));
for (int i = idx + 1; i <= n; i++)
ans = max(ans, 1.0 * (s[i] - s[0]) / i);
printf("%.10f\n", ans);
}
return 0;
}
J - Mysterious Tree
Solution
交互题
首先，显然需要找到一条连着的边，我们可以用 \(\lceil \frac{n}{2}\rceil\) 个问来找到一条连着的边
方法就是 \((1,2),(3,4),\cdots\)
如果都没有连着的边肯定是链了
考虑一条连着的边，我们把两个端点定义为 \(A,B\)
如果是菊花图，考虑那个点是中心点，找到与 \(A,B\) 不同的两个点 \(X,Y\)
如果 \(A\) 和 \(X,Y\) 都有连边，说明是菊花图，且 \(A\) 是中心点
如果 \(B\) 和 \(X,Y\) 都有连边， 说明是菊花图，且 \(B\) 是中心点
不满足菊花图的性质的就认为是链
Code
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n; cin >> n;
int A = -1, B = -1;
for (int i = 1; i <= n; i += 2) {
int now_a = i, now_b = (i + 1 - 1) % n + 1;
cout << '?' << ' ' << now_a << ' ' << now_b << endl;
int ok; cin >> ok;
if (ok) {
A = now_a, B = now_b;
break;
}
}
if (A == -1) {cout << '!' << ' ' << 1 << endl; return;}
int o1 = 1, o2 = 2;
while (o1 == A || o1 == B) o1 = rand() % n + 1;
while (o2 == A || o2 == B || o2 == o1) o2 = rand() % n + 1;
cout << '?' << ' ' << A << ' ' << o1 << endl;
int ok1; cin >> ok1;
if (ok1) { // A is center
cout << '?' << ' ' << A << ' ' << o2 << endl;
int ok2; cin >> ok2;
if (ok2) {cout << '!' << ' ' << 2 << endl; return;}
else {cout << '!' << ' ' << 1 << endl; return;}
}
else { // B is center
cout << '?' << ' ' << B << ' ' << o1 << endl;
int ok3; cin >> ok3;
if (ok3) {
cout << '?' << ' ' << B << ' ' << o2 << endl;
int ok4; cin >> ok4;
if (ok4) {cout << '!' << ' ' << 2 << endl; return;}
else {cout << '!' << ' ' << 1 << endl; return;}
}
else {cout << '!' << ' ' << 1 << endl; return;}
}
}
int main() {
srand(time(0));
int t; cin >> t;
while (t--) solve();
return 0;
}
D - Operator Precedence
Solution
考虑到一个加和等于一个乘积
所以乘积中的很多项的绝对值应该为 \(1\)
不妨假定 \(a_i\) 对于所有的 \(i\) 为奇数的情况，为 \(a_i=1\)
除了 \(a_2\) 和 \(a_n\) 之外，\(i\) 为偶数的情况为 \(a_i=-2\)
那么我们就构造出了很多个 \(-1\)
然后假设 \(a_{2n}=1\) 反解 \(a_2\) ，如果解不出就定义 \(a_{2n} =2\) 反解 \(a_2\)
解得：
- \(n\) 为奇数时，\(a_{2n}=1,a_2=(n-3)\)
- \(n\) 为偶数时，\(a_{2n}=2,a_2=(n-2)\times (-2)\)
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
int n; cin >> n;
if (n == 2) {
cout << "1 -3 -3 1" << '\n';
return ;
}
if (n == 3) {
cout << "1 -10 6 6 -10 1" << '\n';
return ;
}
ll a2, an;
if (n & 1) {
a2 = (n - 2) - 1;
an = 1;
}
else { // n 为偶数
a2 = (n - 2) * (-2);
an = 2;
}
for (int i = 1; i <= 2 * n; i++) {
if (i & 1) printf ("1 ");
else if (i == 2) printf ("%lld ", a2);
else if (i == 2 * n) printf ("%lld\n", an);
else printf ("-2 ");
}
}
int main() {
int t; cin >> t;
while (t--) solve();
}
G - Snake Move
Solution
我们发现，蛇每走一步，无论是什么操作，尾都会短一截
对于一个点来说，我们可以定义头走到这个点所需要花费的最少步数 \(dis[x][y]\)
当这个点位于原来的蛇身上时，我们可以得出此时的蛇尾所在的位置，如果蛇头和蛇身碰上的话，那么需要多走几步 \(S\) 操作，\(S\) 的操作步数就是 此时 蛇尾和 蛇头的距离
我们发现蛇头走一步所需要的代价是 \(1\) 但是走到蛇身所在的格子每次的代价可能 \(>1\)
我们借用 01BFS 的想法，把蛇身的多余代价和位置放在一个优先队列里面
当枚举到与此时的步数相同的蛇身格子时，把这个格子放在队列的前端处理
Code
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const int flg[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int read() {
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int read_ch() {
char ch = getchar();
while (ch != '.' && ch != '#') ch = getchar();
return ch;
}
int main() {
freopen ("G.in", "r", stdin);
int N = read(), M = read(), K = read();
vector<pii> node(1 + K);
vector<vector<int> > mp(N + 1, vector<int>(M + 1, 0));
for (int i = 1; i <= K; i++) {
int x = read(), y = read();
node[i] = {x, y};
}
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++) {
char ch = read_ch();
if (ch == '#') mp[i][j] = -1;
}
for (int i = 1; i <= K; i++) {
auto [x, y] = node[i];
mp[x][y] = i;
}
priority_queue<pair<int, pii>, vector<pair<int, pii> >, greater<pair<int, pii> > > pq;
vector<vector<int> > dis(N + 1, vector<int>(M + 1, inf));
auto [sx, sy] = node[1];
pq.push({0, {sx, sy}}); deque<pii> q;
while (!pq.empty()) {
auto get_node = [&] () -> bool{
if (pq.empty()) return false;
auto [d, u] = pq.top(); auto [x, y] = u;
if (dis[x][y] != inf) { pq.pop(); return true;}
auto [nx, ny] = q.front();
if (q.empty() || d <= dis[nx][ny]) {
pq.pop();
dis[x][y] = d;
q.push_front(u);
return true;
}
return false;
};
while (get_node()) ;
while (!q.empty()) {
while (get_node()) ;
auto [x, y] = q.front(); q.pop_front();
for (int i = 0; i < 4; i++) {
int nx = x + flg[i][0], ny = y + flg[i][1];
if (nx < 1 || nx > N || ny < 1 || ny > M || mp[nx][ny] == -1 || dis[nx][ny] != inf) continue;
if (mp[nx][ny] == 0) {
dis[nx][ny] = dis[x][y] + 1;
q.push_back({nx, ny});
}
else {
int d = dis[x][y] + 1 + max(0, K - dis[x][y] - mp[nx][ny]);
pq.push({d, {nx, ny}});
}
}
}
}
ull e = 1, ans = 0;
for (int i = 1; i <= N; i++){
for (int j = 1; j <= M; j++) {
if (dis[i][j] == inf) dis[i][j] = 0;
// printf("%d ", dis[i][j]);
ans += e * dis[i][j] * dis[i][j];
}
// printf("\n");
}
printf("%llu\n", ans);
return 0;
}
H - Sugar Sweet II
Solution
对于一个事件：
- \(a_i<b_i\) 的话，那么这个事件时必然时间
- \(a_i>b_i+w_{b_i}\) 的话，那么这个时间不可能事件
- 否则就是可能发生或者肯可能不发生
我们需要计算的就是第三类时间发生的概率
如果我们对 \(b_i\Rightarrow i\) 连边，此时构成一个基环树
我们定义 \(L_i\) 表示 \(i\) 节点到距离最近的必然发生的时间的概率
此时 \(p(i)=\frac{1}{L_i !}\)，\(p(i)\) 表示 \(i\) 增加的概率
如果在到必然事件的路径上出现了不可能事件，那么 \(p(i)=0\)
具体实现时，可以把必然事件都丢到队列里面去进行多源 BFS
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 5e5+5;
const ll MOD = 1e9 + 7;
ll Tex, n, a[MAXN], b[MAXN], c[MAXN], inv[MAXN];
// init
bool flag[MAXN];
vector<ll> mp[MAXN];
ll p[MAXN];
ll fastPow(ll a, ll b){
ll res = 1;
while(b){
if(b & 1) res = (res * a) % MOD;
a = (a * a) % MOD;
b >>= 1;
}
return res;
}
void AC(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
mp[i].clear();
flag[i] = 0;
p[i] = 0;
}
for(int j = 1; j <= n; j ++){
cin >> b[j];
}
for(int i = 1; i <= n; i ++){
cin >> c[i];
}
queue<pair<ll,ll>> op;
for(int i = 1; i <= n; i ++){
if(a[b[i]] + c[b[i]] > a[i]){
mp[b[i]].push_back(i);
}
if(a[b[i]] > a[i]){
op.push({i, 1});
p[i] += 1;
flag[i] = 1;
}
}
while(!op.empty()){
pair<ll, ll> qwq = op.front();
op.pop();
for(int i = 0; i < mp[qwq.first].size(); i ++){
if(flag[mp[qwq.first][i]]) continue;
flag[mp[qwq.first][i]] = 1;
p[mp[qwq.first][i]] += inv[qwq.second + 1];
op.push({mp[qwq.first][i], qwq.second + 1});
}
}
for(int i = 1; i <= n; i ++){
cout << (a[i] + (c[i] * p[i]) % MOD) % MOD << " ";
}
cout << endl;
}
int main(){
ios::sync_with_stdio(false);
inv[1] = 1;
for(int i = 2; i <= 500000; i ++){
inv[i] = (inv[i - 1] * i) % MOD;
}
inv[500000] = fastPow(inv[500000], MOD - 2);
for(int i = 499999; i >= 1; i --){
inv[i] = (inv[i + 1] * (i + 1)) % MOD;
}
cin >> Tex;
while(Tex --) AC();
return 0;
}