- ConneR and the A.R.C. Markland-N
- JOE is on TV!
- NEKO's Maze Game
- Aroma's Search
- Xenon's Attack on the Gangs
ConneR and the A.R.C. Markland-N
[Time Limit: 1 squad Memory Limit: 256 MB
]
直接把所有的时间记录下来，然后暴力跑一遍答案判断是否合法即可。
view
/***************************************************************
> File Name : a.cpp
> Author : Jiaaaaaaaqi
> Created Time : 2020/1/19 21:35:08
***************************************************************/
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define dbg(x) cout << #x << " = " << (x) << endl
#define mes(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
int n, m, k;
int T, cas, tol = 0;
map<int, bool> mp;
int main() {
// freopen("in", "r", stdin);
scanf("%d", &T);
while(T--) {
mp.clear();
scanf("%d%d%d", &n, &m, &k);
for(int i=1, x; i<=k; i++) {
scanf("%d", &x);
mp[x] = true;
}
for(int ans=0; ; ans++) {
int x = m + ans;
int y = m - ans;
if(x <= n && !mp.count(x)) {
printf("%d
", ans);
break;
}
if(y>=1 && !mp.count(y)) {
printf("%d
", ans);
break;
}
}
}
return 0;
}
JOE is on TV!
[Time Limit: 1 squad Memory Limit: 256 MB
]
答案就是 (sum_{i=1}^{n} frac{1}{i})
view
/***************************************************************
> File Name : b.cpp
> Author : Jiaaaaaaaqi
> Created Time : 2020/1/19 21:42:50
***************************************************************/
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define dbg(x) cout << #x << " = " << (x) << endl
#define mes(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
int n, m;
int T, cas, tol = 0;
int main() {
// freopen("in", "r", stdin);
scanf("%d", &n);
double ans = 0;
for(int i=1; i<=n; i++) {
ans += 1.0/i;
}
printf("%.10f
", ans);
return 0;
}
NEKO's Maze Game
[Time Limit: 1.5 squad Memory Limit: 256 MB
]
首先 ((1, 1)) 和 ((2, n)) 肯定不能为岩浆地板，肯定不能存在这三种情况:
- 存在 ((1, x)) 和 ((2, x-1)) 都为 (1)
- 存在 ((1, x)) 和 ((2, x+1)) 都为 (1)
- 存在 ((1, x)) 和 ((2, x)) 都为 (1)
只要记录存在多少对这样的对数，当不存在这样的对数，并且((1, 1)) 和 ((2, n)) 不为岩浆时，则可以通过。
view
/***************************************************************
> File Name : c.cpp
> Author : Jiaaaaaaaqi
> Created Time : 2020/1/19 21:48:23
***************************************************************/
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define dbg(x) cout << #x << " = " << (x) << endl
#define mes(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
int n, m, x, y;
int T, cas, tol = 0;
int a[2][maxn];
int main() {
// freopen("in", "r", stdin);
scanf("%d%d", &n, &m);
int f1 = 1, f2 = 1, cnt = 0;
while(m--) {
scanf("%d%d", &x, &y);
x--;
if(x==0 && y==1) f1 = !f1;
if(x==1 && y==n) f2 = !f2;
if(a[x][y] == 0) {
a[x][y] = 1;
if(y-1 >= 1 && a[!x][y-1] == 1) cnt++;
if(a[!x][y] == 1) cnt++;
if(y+1 <= n && a[!x][y+1] == 1) cnt++;
} else {
a[x][y] = 0;
if(y-1 >= 1 && a[!x][y-1] == 1) cnt--;
if(a[!x][y] == 1) cnt--;
if(y+1 <= n && a[!x][y+1] == 1) cnt--;
}
puts(f1 && f2 && cnt==0 ? "Yes":"No");
}
return 0;
}
Aroma's Search
[Time Limit: 1 squad Memory Limit: 256 MB
]
可以先把和 ((x_s, y_s)) 曼哈顿距离在 (t) 以内的点都找出来，这个数量不会很多。
然后可以枚举从 ((x_s, y_s)) 直接到第 (i) 个节点，因为 (a_x, a_y) 都是大于 (2) 的，那么说明越往后面，曼哈顿距离越大，所以我肯定是先走 (j -> (j-1)) 方向，一直到第一个点以后，如果还有多余的步数可以走的话，那么就从到第 (i+1) 节点，然后在走 (j -> (j+1)) 方向。
view
/***************************************************************
> File Name : d.cpp
> Author : Jiaaaaaaaqi
> Created Time : 2020/1/19 22:08:43
***************************************************************/
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define dbg(x) cout << #x << " = " << (x) << endl
#define mes(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int maxn = 1e3 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
int n, m, sz;
int T, cas, tol = 0;
ll ans = 0;
ll maps[maxn][maxn];
vector<pair<ll, ll>> g;
int main() {
// freopen("in", "r", stdin);
ll x, y, ax, ay, bx, by, xs, ys, t;
scanf("%lld%lld%lld%lld%lld%lld", &x, &y, &ax, &ay, &bx, &by);
scanf("%lld%lld%lld", &xs, &ys, &t);
g.pb({0, 0});
g.pb({xs, ys});
for(int i=0; ; i++) {
if(abs(x-xs) + abs(y-ys) <= t) g.pb({x, y});
x = ax*x+bx;
y = ay*y+by;
if(x-xs>t || y-ys>t) break;
}
sz = g.size()-1;
for(int i=0; i<=sz+1; i++) for(int j=0; j<=sz+1; j++) maps[i][j] = INF;
for(int i=1; i<=sz; i++) for(int j=1; j<=sz; j++)
maps[i][j] = abs(g[i].fi-g[j].fi) + abs(g[i].se-g[j].se);
ll ans = 0;
for(int i=2; i<=sz; i++) {
ll res = maps[1][i], cnt = 1;
if(res > t) break;
for(int j=i; j>=3; j--) {
if(res + maps[j][j-1] > t) break;
res += maps[j][j-1], cnt++;
}
ans = max(ans, cnt);
res += maps[2][i+1], cnt++;
if(res > t) continue;
for(int j=i+1; j<sz; j++) {
if(res+maps[j][j+1] > t) break;
res += maps[j][j+1], cnt++;
}
ans = max(ans, cnt);
}
printf("%lld
", ans);
return 0;
}
Xenon's Attack on the Gangs
[Time Limit: 3 squad Memory Limit: 256 MB
]
首先我们假设某一条边为 (0)，那么这条边一侧到另一侧的节点的 (mex) 至少为 (1)，接下来考虑加入一个条为 (1) 的边，我们发现只有当 (1) 与 (0) 相连时，这个 (1) 才会使 (0-1) 这条链两侧的节点的 (mex) 至少为 (2)，同理，接下来的 (2) 应该和 (0-1) 这条链相连，也就是说只有 (x) 和 (0-(x-1)) 相连并且形成一条链时， (x) 才能造成新的贡献。
那么可以枚举每一条链，在这条链上填满 (0-x)，令 (dp[i][j]) 为从 (i) 到 (j) 这条简单路径的链上的最大 (S) 值。因为最大的 (x) 必须和 (0-(x-1)) 相连，所以 (x) 肯定是在链的最外的两条边的其中一条。那么我们可以预处理出 (fa[root][i]) 表示以 (root) 为根时 (i) 的父亲节点，那么就可以知道 (i、j) 是如何往中间缩减的，(dp) 也就可以推出来了。
view
/***************************************************************
> File Name : e.cpp
> Author : Jiaaaaaaaqi
> Created Time : 2020/1/21 18:52:51
***************************************************************/
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define dbg(x) cout << #x << " = " << (x) << endl
#define mes(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int maxn = 3e3 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
int n, m;
int T, cas, tol = 0;
vector<int> g[maxn];
ll dp[maxn][maxn];
int fa[maxn][maxn], cnt[maxn][maxn];
void dfs(int u, int f, int root) {
fa[root][u] = f, cnt[root][u] = 1;
for(auto v : g[u]) if(v != f) {
dfs(v, u, root);
cnt[root][u] += cnt[root][v];
}
}
ll dfs(int u, int v) {
if(u == v) return dp[u][v] = 0;
if(~dp[u][v]) return dp[u][v];
return dp[u][v] = max(dfs(u, fa[u][v]), dfs(fa[v][u], v)) + cnt[u][v]*cnt[v][u];
}
int main() {
// freopen("in", "r", stdin);
scanf("%d", &n);
for(int i=2, u, v; i<=n; i++) {
scanf("%d%d", &u, &v);
g[u].pb(v), g[v].pb(u);
}
for(int i=1; i<=n; i++) dfs(i, 0, i);
mes(dp, -1);
ll ans = 0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
ans = max(ans, dfs(i, j));
}
}
printf("%lld
", ans);
return 0;
}