比赛链接：Dashboard - The 2023 ICPC Asia Nanjing Regional Contest (The 2nd Universal Cup. Stage 11: Nanjing) - Codeforces

SUA牛逼

A

题意：在一个 $n\times m$ 的网格中有很多洞，没有洞的位置上都有一只袋鼠，现在控制所有袋鼠上下左右移动，移出网格或到洞里就会淘汰，问对每一只袋鼠，能否存在一种操作序列使其成为最后一只袋鼠，求这样的袋鼠的数量。$n\times m\leq1000$

一个比较难写的bfs。

对每个袋鼠，考虑它是否能将其他所有袋鼠都带进坑里，可用 $(i,j,i’,j’)$ 表示，在存储状态时将其哈希处理为 $S=n\times m\times n\times i+n\times m\times j+m\times i’+j’$ 。在bfs时，将某一初始状态能到达的所有位置都记录下初始位置进行剪枝，若以后的初始状态遍历过，那么就直接跳过。复杂度 $O(n^2\times m^2)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
#define MAXP 1000
using namespace std;

int n, m, ans;
vector<string> MAP;

char s[MAXP + 10];
int vis[MAXP * MAXP + 10];
bool flag[MAXP * MAXP + 10];

int gao(int i, int j, int r, int c) {
    return
        i * m * n * m +
        j * n * m +
        r * m +
        c;
}

void ungao(int msk, int &i, int &j, int &r, int &c) {
    i = msk / (m * n * m);
    j = msk / (n * m) % m;
    r = msk / m % n;
    c = msk % m;
}

bool fall(int i, int j) {
    return i < 0 || j < 0 || i >= n || j >= m || MAP[i][j] == 'O';
}

short dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};

void bfs(int S) {
    queue<int> q;
    q.push(S); vis[S] = S;
    flag[S] = false;

    while (!q.empty()) {
        int i, j, r, c; ungao(q.front(), i, j, r, c); q.pop();
        for (int k = 0; k < 4; k++) {
            int ii = i + dir[k][0], jj = j + dir[k][1];
            int rr = r + dir[k][0], cc = c + dir[k][1];
            
            if (fall(ii, jj)) continue;
            
            if (fall(rr, cc)) { flag[S] = true; continue; }
            int nxt = gao(ii, jj, rr, cc);
            if (vis[nxt] >= 0) continue;
            q.push(nxt); vis[nxt] = S;
        }
    }
}


int check(int i, int j) {
    for (int r = 0; r < n; r++) for (int c = 0; c < m; c++) if (MAP[r][c] == '.') {
        if (i == r && j == c) continue;
        int msk = gao(i, j, r, c);
        if (vis[msk] == -1) bfs(msk);
        if (!flag[vis[msk]]) return 0;
    }
    return 1;
}

void solve() {
    scanf("%d%d", &n, &m);
    MAP.clear();
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        MAP.push_back(string(s));
    }

    memset(vis, -1, sizeof(int) * (n * m * n * m + 3));
    ans = 0;
    
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (MAP[i][j] == '.') ans += check(i, j);
    printf("%d\n", ans);
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}

bfs/dfs

C

求不超过 $m$ 的 $g$ 的数量，其中 $g\bigoplus(P-1)\equiv1(mod P)$。

化简后可得到 $g=(P-1)\bigoplus(kP+1)$ 。注意到：
$$
a-b\leq a\bigoplus b\leq a+b
$$
故：
$$
(k-1)P+2\leq g\leq(k+1)P
$$
因有 $m$ 的限制，得到当 $k$ 满足 $k\leq \lfloor\frac{m}{P}\rfloor-1$ 时一定满足，当 $k\geq \lceil\frac{m-2}{p}\rceil+1$ 时一定不满足。接下来只需要枚举这两个之间有无满足的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# include <bits/stdc++.h>

using namespace std;
typedef long long LL;
LL p,m;

void solve()
{
	cin >> p >> m;
	if((m - 2) / p + 1 < 0 )
		if( 1 ^ (p - 1) <= m) cout << 1 << '\n';
		else cout << 0 << '\n';
	else
	{
	 	LL cnt1 = m / p;  
		for(LL i = max(0ll, m / p) ; i <= (m - 2) / p + 1; i ++)
		{
			//cout << ((i * p + 1) ^ (p - 1)) << ' ' << i << endl;
			if(((LL)(i * p + 1) ^ (p - 1)) <= m) cnt1  ++;
		}
		cout << cnt1 << '\n'; 
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	while(T --) solve();
	return 0;
}

位运算

F

题意：有一个长度为 $m$ 的序列初始为空，第 $i$ 次操作可以把一些数变成 $i$ ，问能否打乱操作顺序但是使最后的序列相同。

对于每一个位置，所涉及的操作有先后顺序，最后该位的数字所涉及的操作需最后执行，用拓扑排序解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
# include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 1e6 + 10;
int din[N],dout[N];
int h[N],e[M],ne[M],idx;
int n,m;
int color[N];
bool st[N];
vector<int>ver[N + 1];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void solve()
{
    unordered_set<LL>S;
    idx = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)  h[i] = -1, color[i] = din[i] = dout[i] = st[i] = 0;
    for(int i = 1; i <= m; i ++) ver[i].clear();


    for(int i = 1; i <= n; i ++)
    {
        int cnt;
        cin >> cnt;
        while(cnt --)
        {
            int a;
            cin >> a;
            color[a] = i;
            ver[a].push_back(i);
        }
    }

    for(int i = 1; i <= m; i ++)
    {
        int t = color[i];
        if(!color[i]) continue;
        for(auto c : ver[i]) 
        {
            if(c >= t) continue;
            LL hash = (LL)c * N + t;
            if(!S.count(hash)) 
            {
                add(c, t);
                S.insert(hash);
                din[t] ++;
                dout[c] ++;
            }
        }
    }
    vector<int>path;
    queue<int>q;

    for(int i = 1; i <= n; i ++)
        if(!din[i])
            q.push(i);
    bool flag = false;

    while(q.size())
    {
        int t = q.front();
        if(q.size() >= 2)
        {
            q.pop();
            int tt = q.front();
            st[t] = st[tt] = true;
            if(t > tt) path.push_back(t),path.push_back(tt);
            else path.push_back(tt), path.push_back(t);
            flag = true;
            break;
        }
        path.push_back(t);
        st[t] = true;
        q.pop();
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(!(--din[j])) q.push(j);
        }
    }

    if(!flag) cout << "No" << '\n';
    else
    {
        cout << "Yes" << '\n';
        for(int c : path) cout << c << ' ';
        for(int i = 1; i <= n; i ++)
            if(!st[i]) cout << i << ' ';
        cout << '\n';
    }
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    int T = 1;
    cin >> T;
    while(T --) solve();
    //system("pause");
    return 0;
}

还有一种简化的思路，只要比较相邻两次操作能否交换即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int col[N];
int n,m;
int ans;
vector <int> vec[N];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        ans=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)    vec[i].clear();
        for(int i=1;i<=m;++i)   col[i]=0;
        for(int i=1;i<=n;++i){
            int p,u;
            scanf("%d",&p);
            while(p--){
                scanf("%d",&u);
                vec[i].push_back(u);
                col[u]=i;
            }
        }
        for(int i=1;i<n;++i){
            int mn=n+1;
            for(auto v:vec[i]){
                if(col[v]==i)    continue;
                mn=min(mn,col[v]);
            }
            if(mn!=i+1) {
                ans=i;
                break;
            }
        }
        if(ans){
            puts("Yes");
            for(int i=1;i<=n;++i){
                if(i==ans)  printf("%d %d ",i+1,i),++i;
                else printf("%d ",i);
            }
            puts("");
        }
        else   puts("No");
    }
}

拓扑排序

G

真心没想到

题意：在普通01背包的条件下添加附加条件：可以免费任选 $k $ 件物品，求最大价值。$n\leq 5000,W\leq 100000$ 。

根据以下条件贪心：

  1. 若某物品选择免费挑而不是买，那么一定这件物品更贵；
  2. 若挑选了物品 $A$ 而没有挑选 $B$ ，那么一定 $A$ 比 $B$ 价值高。

因此贪心策略如下：

将所有物品按照价格排序，枚举分界点，在分界点前按照背包预处理答案，分界点后免费挑价值最大的 $k$ 件物品。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k;
pair<int,int> a[500005];
int tmp[500005];
int dp[500005];

signed main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1,a+n+1);

    multiset<int>s;
    for(int i=n;i>=1;i--)
    {
        tmp[i]=tmp[i+1]+a[i].second;
        s.insert(a[i].second);
        if(s.size()>k)
        {
            tmp[i]-=*s.begin();
            s.erase(s.begin());
        }
    }

    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=a[i].first;j--)
        {
            dp[j]=max(dp[j],dp[j-a[i].first]+a[i].second);
        }
        // for(int i=0;i<=m;i++)cout<<dp[i]<<" ";cout<<endl;
        // cout<<i<<' '<<dp[m]<<' '<<tmp[i+1]<<endl;
        ans=max(ans,dp[m]+tmp[i+1]);
    }
    cout<<ans;
    // system("pause");
    return 0;
}

greedy，dp

L

题意：有很多重量只为1或2的包裹，他们需要运送到不同的楼层，每次电梯的最大载重量为 $k$ ，且 $k$ 为偶数，每一次运输消耗的电能是本次运输到达的最高楼层的层数。求最小电能。

首先容易想到贪心思路：从高楼层开始运输，若电梯容量仅为1但下一个包裹为2，那么往后找第一个重量为1的包裹。

优化：将包裹都拆分成重量为1，直接从高楼层开始运输。

$proof:$ 注意到题目特殊条件 $k$ 为偶数。当容量仅为1时，若不将下一个重量为1的包裹提前，那么只可能在下一个重量为1的包裹之前会有影响：因这之间所有包裹重量均为2，故唯一的影响是所有包裹往前进1，不影响每次最大楼层，故贪心正确。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int n;
long long K, ans;
vector<pii> A;

void solve() {
    scanf("%d%lld", &n, &K);

    A.clear();
    for (int i = 1; i <= n; i++) {
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        // 把所有大小为 2 的包裹拆成两个大小为 1 的包裹
        A.push_back(pii(-z, x * y));
    }
    // 按楼层从高到低排序
    sort(A.begin(), A.end());

    ans = 0;
    // now：这一趟电梯的最高楼层
    // sm：现在电梯里已经放了多少包裹
    long long now = -A[0].first, sm = 0;
    // 依次处理每种包裹
    for (pii p : A) {
        sm += p.second;
        // 新包裹的加入导致电梯里放了超过 K 个包裹
        if (sm > K) {
            ans += now;
            now = -p.first;
            sm -= K;

            // 用除法快速处理同一种包裹
            // 这里分子是 sm - 1，是为了防止 sm % K == 0 的情况，导致 now 的值出错
            long long t = (sm - 1) / K;
            ans += now * t;
            sm -= t * K;
        }
    }
    ans += now;

    printf("%lld\n", ans);
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}

greedy