F 看错题了,以为是求取得 \(1,2,\dots,m\) 。 后面npy告诉我是 \(1 \text{ and } m\) 。
A - Attack
\(B \times x \geq A\) ,求 \(x\)
void solve()
{
ll a, b; cin>>a>>b;
cout<<(a / b) + (a % b != 0)<<'\n';
return;
}
B - Find snuke
8 个方向找 \(\text{snuke}\)
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int n, m;
string op[110];
string s = "snuke";
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
cin>>op[i];
op[i] = "?" + op[i];
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
for(int k = 0; k < 8; k++)
{
bool ok = false;
int x = i + 4 * dx[k];
int y = j + 4 * dy[k];
if(x < 1 || x > n || y < 1 || y > m)
continue;
for(int q = 0; q <= 4; q++)
{
x = i + q * dx[k];
y = j + q * dy[k];
if(x < 1 || x > n || y < 1 || y > m)
break;
if(op[x][y] != s[q])
break;
if(q == 4)
ok = true;
}
if(ok)
{
for(int q = 0; q <= 4; q++)
cout<<i + q * dx[k]<<" "<<j + q * dy[k]<<'\n';
return;
}
}
}
}
return;
}
C - Almost Equal
全排列判断
int n, m;
string op[110];
int id[10];
bool vis[10], ok = false;
void dfs(int u)
{
if(u == n)
{
for(int i = 2; i <= n; i++)
{
int cnt = 0;
for(int j = 0; j < m; j++)
if(op[id[i]][j] != op[id[i - 1]][j])
cnt++;
if(cnt != 1)
return;
}
ok = true;
return;
}
for(int i = 1; i <= n; i++)
{
if(!vis[i])
{
vis[i] = true;
id[u + 1] = i;
dfs(u + 1);
vis[i] = false;
id[u + 1] = 0;
}
}
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
cin>>op[i];
dfs(0);
if(ok)
cout<<"Yes\n";
else
cout<<"No\n";
return;
}
D - Impartial Gift
对 B 序列排序后,分别找出 \(A_i (1 \leq i \leq N)\) 在 B 序列中分别找出 \(A_i-d \leq B_j\) 中最小的\(B_j\) 和 \(B_j \leq A_i + d\) 中最大的 \(B_j\) 。直接找会 TLE,但将 B 序列排序后,有序即可二分,时间复杂度 \(O(N \log M)\) 。
要注意二分得到的数只满足一个条件,最后要判断一下是否满足\(A_i - d \leq B_J \leq A_i + d\)
int n, m;
ll a[N], b[N], d;
void solve()
{
cin>>n>>m>>d;
for(int i = 1; i <= n; i++)
cin>>a[i];
for(int j = 1; j <= m; j++)
cin>>b[j];
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + m);
ll ans = -1;
for(int i = 1; i <= n; i++)
{
int l = 1, r = m;
while(l < r)
{
int mid = (l + r) >> 1;
if(b[mid] >= a[i] - d) r = mid;
else l = mid + 1;
}
if(b[l] >= a[i] - d && b[l] <= a[i] + d)
ans = max(ans, a[i] + b[l]);
l = 1, r = m;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(b[mid] <= a[i] + d) l = mid;
else r = mid - 1;
}
if(b[l] >= a[i] - d && b[l] <= a[i] + d)
ans = max(ans, a[i] + b[l]);
}
cout<<ans<<'\n';
return;
}
E - Isolation
对于每个点,我们要统计如下:
- 操作1,u,v 连一条边,我们分别在 \(\text{set}_u, \text{set}_v\) 中记录边,分别查看其的度数,若为 \(0\) , \(\text{答案} - 1\) 并将 u, v 的度数加 \(1\)
- 将和 u 有两边的点的度数减 \(1\) , 若为 \(0\) , \(\text{答案} + 1\) , 并删去其边,将 u 的边集清空,度数赋值为 \(0\) , \(\text{答案} +1\) 。
int n, q, d[N];
set<int> e[N];
void solve()
{
cin>>n>>q;
int res = n;
for(int i = 1; i <= q; i++)
{
int opt; cin>>opt;
if(opt == 1)
{
int u, v; cin>>u>>v;
if(d[u] == 0)
res--;
if(d[v] == 0)
res--;
d[u]++, d[v]++;
e[u].insert(v);
e[v].insert(u);
}
else
{
int u; cin>>u;
vector<int> a;
for(auto &it : e[u])
a.push_back(it);
for(auto &it : a)
{
e[it].erase(u);
d[it]--;
if(d[it] == 0)
res++;
}
e[u].clear();
if(d[u] != 0)
res++;
d[u] = 0;
}
cout<<res<<'\n';
}
return;
}
F - Merge Set
问合并集合取得 \(1 \text{ and } m\) 的最小路径, 一眼 \(\text{BFS}\)
记录这个点可以到哪些集合,记录集合可以到哪些点
\(\text{BFS}\) 里面存的是点 \(u\),遍历 \(u\) 的集合中其他的点 \(v\), 然后是常规的 \(BFS\) 操作了。
int n, m, dist[N];
vector<int> e1[N], e2[N];
bool vis[N];
void bfs()
{
for(int i = 1; i <= m; i++)
dist[i] = 1e9;
queue<int> q;
q.push(1);
dist[1] = 0;
while(!q.empty())
{
auto u = q.front(); q.pop();
for(auto &it : e1[u])
{
if(vis[it]) continue;
vis[it] = true;
for(auto &v : e2[it])
{
if(dist[v] > dist[u] + 1)
{
dist[v] = dist[u] + 1;
if(v == m)
{
cout<<dist[u]<<'\n';
return;
}
q.push(v);
}
}
}
}
cout<<-1<<'\n';
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
int len; cin>>len;
while(len--)
{
int x; cin>>x;
e1[x].push_back(i);
e2[i].push_back(x);
}
}
bfs();
return;
}
- Beginner AtCoder Contest ABCDEF 302beginner atcoder contest abcdef beginner atcoder contest 302 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334