ICPC2023 南京站 个人简要题解
南京,俺仅谋过一次面的第四精神故乡!
单挑 5-688 好想找个队友一起打……单开 too 坐牢。
A
大众变态搜索题。
首先我们考虑,对于一只袋鼠来说如何判断是否可以存活?场上想了很多种方法,然后没看到
具体而言,我们把
记得使用 unordered_map
,用 map
喜提 +1 难绷。
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
vector <vector<int> > ma;
vector <vector<int> > vis;
const int dx[4] = {0,0,-1,1};
const int dy[4] = {1,-1,0,0};
int n,m,col;
vector <pii> ps;
unordered_map <int,int> sta,viss,rt;
bool valid(int x,int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
void dfs1(int x,int y) {
ps.push_back(mp(x,y));
vis[x][y] = col;
for (int i = 0;i < 4;++i) {
int nx = x + dx[i],ny = y + dy[i];
if (valid(nx,ny) && !ma[nx][ny]) {
if (!vis[nx][ny]) {
dfs1(nx,ny);
}
}
}
}
int zip(pii x,pii y) {
int a,b,c,d;a = x.first,b = x.second;c = y.first,d = y.second;
return d + c * m + b * n * m + a * m * n * m;
}
pair<pii,pii> unzip(int x) {
pii a,b;
b.second = x % m;
x /= m;
b.first = x % n;
x /= n;
a.second = x % m;
x /= m;
a.first = x;
return mp(a,b);
}
void bfs(int stt) {
queue <int> q;
q.push(stt);
rt[stt] = stt;
while (!q.empty()) {
int nowsta = q.front();q.pop();
pii s = unzip(nowsta).first,t = unzip(nowsta).second;
int xx = s.first,yy = s.second;
int xxx = t.first,yyy = t.second;
//printf("xx(%d,%d)-(%d,%d)\n",xx,yy,xxx,yyy);
bool flag = 0;
for (int i = 0;i < 4;++i){
int nx = xx + dx[i],ny = yy + dy[i];
int nxx = xxx + dx[i],nyy = yyy + dy[i];
//printf("nx(%d,%d)-(%d,%d)\n",nx,ny,nxx,nyy);
if (!valid(nx,ny) || ma[nx][ny]) continue;
if (!valid(nxx,nyy) || ma[nxx][nyy]) {
sta[stt] = sta[nowsta] = 1;
continue ;
}
if (!rt[zip(mp(nx,ny),mp(nxx,nyy))])q.push(zip(mp(nx,ny),mp(nxx,nyy))),rt[zip(mp(nx,ny),mp(nxx,nyy))] = stt;
}
//if (!flag) sta[nowsta] = -1;
}
}
void solve() {
cin >> n >> m;
ma.clear();vis.clear();col = 0;
sta.clear();
ma.resize(n);
vis.resize(n);
rt.clear();
int siz= 0;
for (int i = 0;i < n;++i) {
ma[i].resize(m);
vis[i].resize(m);
for (int j = 0;j < m;++j) {
char c;cin >> c;
if (c == 79) ma[i][j] = 1;
else ma[i][j] = 0,++siz;
}
}
int ans = 0;
//bfs(zip(mp(1,4),mp(1,0)));
//cout << sta[zip(mp(1,4),mp(1,0))] << "\n";
for (int i = 0;i < n;++i) {
for (int j = 0;j < m;++j) {
if (!ma[i][j] && !vis[i][j]) {
ps.clear();
++col;
dfs1(i,j);
for (auto p1 : ps) {
int cnt = 0;
for (int xx = 0;xx < n;++xx) {
for (int yy = 0;yy < m;++yy) {
pii p2 = mp(xx,yy);
if (p2 == p1 || ma[xx][yy]) continue;
if (!rt[zip(p1,p2)]) bfs(zip(p1,p2));
if (sta[rt[zip(p1,p2)]]== 1) {
++cnt;
}
}
}
//cout << p1.first << " " << p1.second << "!" << cnt << "\n";
if (cnt == siz - 1) {
++ans;
//cout << p1.first << " " << p1.second << "!\n";
}
}
}
}
}
cout << ans << "\n";
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(0);//cout.tie(0);
int T;cin >> T;
while (T--) solve();
return 0;
}
/*
1
2 5
.OO..
.O.O.
*/
C
本来以为是数学题丢了没开,但是发现同校队伍过了一卡车感觉不对劲,顶真了一下就做完了
我们考虑把柿子转化一下:
然后接下来我们不妨考虑一下
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
void solve() {
ll p,m;cin >> p >> m;
ll ans = m/p;
//cout << "l :" << m/p << " r:" <<(m+(p-1))/p -1<<"\n";
for (ll k = m/p;k <= (m+(p-1))/p;++k) {
//cout << "now:" << ((k*p+1) ^ (p-1)) << "\n";
if (((k*p+1LL) ^ (p-1LL)) <= m)++ans;
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);//cout.tie(0);
int T;cin >> T;
while (T--) solve();
return 0;
}
F
神秘建图题。
首先我们发现,对于每一个位置
所以我们不妨记录一个位置最后是哪一次修改,记作
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
const int N = 1e5 + 10;
vector <int> G[N],rk[N];
int n,m,lst[N],deg[N];
bool cmp(int x,int y) {
return x > y;
}
void solve() {
cin >> n >> m;
for (int i = 1;i <= m;++i) lst[i] = 0,rk[i].clear();
for (int i = 0;i <= n;++i) G[i].clear(),deg[i] = 0;
int cnt = 0;
for (int i = 1;i <= n;++i) {
cin >> cnt;
for (int j = 1;j <= cnt;++j) {
int x;cin >> x;
rk[x].push_back(i);
lst[x] = i;
}
}
for (int i = 1;i <= m;++i) {
if (!lst[i]) continue;
for (auto x : rk[i]) {
if (x != lst[i]) {
G[x].push_back(lst[i]);
++deg[lst[i]];
//cout << "e:" << x << " " << lst[i] <<"\n";
}
}
}
int tot = 0;
queue <int> q;
for (int i = 1;i <= n;++i) {
if (!deg[i]) {
++tot;
G[0].push_back(i);
++deg[i];
}
}
q.push(0);
vector <int> ans;
while (!q.empty()) {
int x = q.front();q.pop();
//cout << x << " ";
if (G[x].size()) sort(G[x].begin(),G[x].end(),cmp);
if (x) ans.push_back(x);
for (auto y : G[x]) {
//cout << "(" << x << "," << y << ")\n";
if (!--deg[y]) {
q.push(y);
}
}
}
bool flag = 0;
for (int i = 0;i < n;++i) {
//printf("ans%d:%d i+1 = %d\n",i,ans[i],i+1);
if (ans[i] != i+1) {
flag = 1;
}
}
if (!flag) {
cout << "No\n";
} else {
cout << "Yes\n";
for (auto x : ans)
cout << x << " ";
cout << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
//cin.tie(0);//cout.tie(0);
int T;cin >> T;
while (T--) solve();
return 0;
}
/*
1
1 3
2 2 1
*/
G
巧妙的贪心题!
首先我们考虑,我们对于
但是很快你就会发现这个贪心有点问题,所以我们改进一下,考虑
还是挺好玩的题
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
const int N = 1e4 + 10;
int n,W,k;
ll f[10010],t[N];
pll c[10010];
multiset <ll> st;
signed main() {
ios::sync_with_stdio(false);
//cin.tie(0);//cout.tie(0);
cin >> n >> W >> k;
for (int i = 1;i <= n;++i) {
cin >> c[i].first >> c[i].second;
}
sort(c+1,c+1+n);
ll ans = 0;
ll sum = 0;
if (k) {
for (int i = n;i >= n - k + 1;--i) {
sum += c[i].second;
st.insert(c[i].second);
t[i] = sum;
}
for (int i = n - k;i >= 1;--i) {
ll now = *st.begin();
if (c[i].second > now) {
sum = sum - now + c[i].second;
st.erase(now);
st.insert(c[i].second);
}
t[i] = sum;
}
}
for (int i = 1;i <= n;++i) {
for (int j = W;j>= 0;--j) {
if (j >= c[i].first) {
f[j] = max(f[j],f[j-c[i].first] + c[i].second);
}
}
ans = max(ans,t[i+1] + f[W]);
}
cout << ans << "\n";
return 0;
}
I
签到题,直接等价于区间覆盖就可以了。
/*
Undo the destiny.
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cassert>
#include <limits>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
const int N = 1e5 + 10;
pii p[N];
int n,m;
void solve() {
cin >> n >> m;
for (int i = 1;i <= m;++i) cin >> p[i].first >> p[i].second;
sort(p+1,p+1+m);
int lsta = 0,lstb = 0;
bool flag = 0;
for (int i = 1;i <= m;++i) {
int cnt = p[i].first - p[i].second;
if (cnt > lsta || cnt == lstb) {
lsta = p[i].first;lstb = cnt;
} else {
flag = 1;
break;
}
}
if (flag) puts("No");
else puts("Yes");
}
signed main() {
ios::sync_with_stdio(false);
int T;cin >> T;
while (T--) solve();
return 0;
}cin >> T;
while (T--) solve();
return 0;
}
L
很巧妙的贪心转化……吃个饭回来写
M
小清新 DS,吃个饭回来写
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
《拜见岳父大人合集(剧场版)》喜剧片高清在线免费观看:https://www.jgz518.com/xingkong/148038.html
你的文章内容非常用心,让人感动。 https://www.4006400989.com/qyvideo/77444.html
《私人订制》喜剧片高清在线免费观看:https://www.jgz518.com/xingkong/49118.html
《吞噬星空合集篇》国产动漫高清在线免费观看:https://www.jgz518.com/xingkong/36259.html
你的才华让人惊叹,请继续保持。 https://www.4006400989.com/qyvideo/38689.html
你的文章内容非常用心,让人感动。 http://www.55baobei.com/W3mPDTitQY.html
《刀不留人》动作片高清在线免费观看:https://www.jgz518.com/xingkong/67936.html
你的文章让我感受到了艺术的魅力,谢谢! https://www.yonboz.com/video/99406.html
你的文章让我心情愉悦,真是太棒了! http://www.55baobei.com/or2UTjlEy0.html
你的文章让我感受到了不一样的风景,谢谢分享。 http://www.55baobei.com/3inI0GQLJ9.html
你的才华让人瞩目,期待你的更多文章。 http://www.55baobei.com/qkOvPyQXEn.html
fbw095