8.8

比赛

80%瓜分率

A

写了个dfs荣获40pts

bfs

然后同时开一个数组 \(dis\), \(dis[i][j]\) 表示目前到 \(i, j\) 所需的最小步数

若bfs时发现枚举到的状态的dis值已经小于当前位置dis值，则无需加入队列

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
bool mp[1005][1005];
int dis[1005][1005];
int sx, sy, tx, ty, n, m, k;
int res;
struct node
{
	int x, y;
};
inline void dfs()
{
	memset(dis, 0x3f, sizeof dis);
	dis[sx][sy] = 0;
	res = dis[0][0];
	queue<node> Q;
	Q.push({sx, sy});
	while(Q.size())
	{
		node now = Q.front();Q.pop();
		int x = now.x, y = now.y;
		for(int i = 1; i <= k; ++ i)
		{
			int tx = x + i, ty = y;
			if (tx < 1 || tx > n || ty < 1 || ty > m) break;
			if (dis[tx][ty] <= dis[x][y]) break;
			if (mp[tx][ty] == 0) break;
			if (dis[tx][ty] == res) {
				dis[tx][ty] = dis[x][y] + 1;
				Q.push({tx, ty});					
			}
		}
		for(int i = 1; i <= k; ++ i)
		{
			int tx = x, ty = y + i;
			if (tx < 1 || tx > n || ty < 1 || ty > m) break;
			if (dis[tx][ty] <= dis[x][y]) break;
			if (mp[tx][ty] == 0) break;
			if (dis[tx][ty] == res) {
				dis[tx][ty] = dis[x][y] + 1;
				Q.push({tx, ty});					
			}
		}
		for(int i = 1; i <= k; ++ i)
		{
			int tx = x - i, ty = y;
			if (tx < 1 || tx > n || ty < 1 || ty > m) break;
			if (dis[tx][ty] <= dis[x][y]) break;
			if (mp[tx][ty] == 0) break;
			if (dis[tx][ty] == res) {
				dis[tx][ty] = dis[x][y] + 1;
				Q.push({tx, ty});					
			}
		}
		for(int i = 1; i <= k; ++ i)
		{
			int tx = x, ty = y - i;
			if (tx < 1 || tx > n || ty < 1 || ty > m) break;
			if (dis[tx][ty] <= dis[x][y]) break;
			if (mp[tx][ty] == 0) break;
			if (dis[tx][ty] == res) {
				dis[tx][ty] = dis[x][y] + 1;
				Q.push({tx, ty});					
			}
		}
	}
	return ;
}

int main()
{
	//freopen("expedition.in", "r", stdin);
	//freopen("expedition.out", "w", stdout);
	n = read(), m = read(), k = read();
	bool bj = 1;
	for(int i = 1; i <= n; ++ i)
		for(int j = 1; j <= m; ++ j)
		{
			char c;
			cin >> c;
			if(c == '.')mp[i][j] = 1;
			if(c == '#')bj = 0;
		}
	sx = read(), sy = read(), tx = read(), ty = read();
	dfs();
	if(dis[tx][ty] == res)return cout << -1, 0;
	cout << dis[tx][ty];
	return 0;
}

B

赛时大体思路出来了，但是没想到优先队列

开优先队列，然后不断找最小的两个判断是否合并

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
ll a[150005];
struct node
{
	ll v;
	int id;
    friend bool operator < (node x, node y){
        if(x.v != y.v) return x.v > y.v;
        return x.id > y.id;
    }
};
priority_queue<node> Q;
int main()
{
	int n = read();
	for(int i = 1; i <= n; ++ i)a[i] = read(), Q.push({a[i], i});
	node x, y;
	while(!Q.empty())
	{
		x = Q.top();Q.pop();
        if(Q.empty())break;
		y = Q.top();Q.pop();
        //cout<<x.v<<' '<<y.v<<endl;
		if(x.v == y.v)
		{
			Q.push({x.v + y.v, y.id});
			a[x.id] = -1, a[y.id] = a[y.id] + a[y.id];
			
		}
		else Q.push(y);
	}
	int k = 0;
	for(int i = 1; i <= n; ++ i)if(a[i] != -1)++ k;
	cout << k << '\n';
	for(int i = 1; i <= n; ++ i)if(a[i] != -1)cout << a[i] << ' ';
	return 0;
}

C

赛时乱搞了一个贪心，寄了

结果是状压

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
int a[25][25];
int f[1 << 20];
int main()
{
	int n = read();
	for(int i = 1; i <= n; ++ i)
		for(int j = 1; j <= n; ++ j)
			a[i][j] = read();
	for(int i = 0; i < (1 << n); ++ i)
	{
		for(int j = 1; j <= n; ++ j)
		{
			if((i >> (j - 1)) & 1 == 1){
				int sum = 0;
				for(int k = 1;k <= n; ++ k)
				{
					if((i >> (k - 1)) & 1)sum += a[k][j];
				}
				f[i] = max(f[i], f[i ^ (1 << (j - 1))] + sum);
			}
		}
	}
	cout << f[(1 << n) - 1];
	return 0;
}
/*

*/

D

倍增lca，然后利用lca做一个类似的数组，只不过存的是前k小，然后暴力合并

代码等补

E

还没会