开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 2022—SWJTU-寒假ACM校队选拔赛第一场-题解 -> 正文阅读

[数据结构与算法]2022—SWJTU-寒假ACM校队选拔赛第一场-题解

A - 惠老板观星https://vjudge.net/problem/Gym-103401H

算法分析

暴力枚举正方形的四个顶点即可,由于正方形的长宽相等,时间复杂度为 $O(n^3)$

AC code

#include<bits/stdc++.h>
using namespace std;
const int N = 300 + 10;

int a[N][N];
int b[5];

void solve()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++)
     for(int j = 1;j <= n;j ++)
      cin >> a[i][j];
    int cnt = 0,res = -1;
    for(int i = 1;i <= n;i ++)
     for(int j = 1;j <= n;j ++)
      for(int k = 1;k <= min(n - i,n - j);k ++)
       {
           b[++ cnt] = a[i][j];
           b[++ cnt] = a[i + k][j];
           b[++ cnt] = a[i][j + k];
           b[++ cnt] = a[i + k][j + k];
           sort(b + 1,b + 1 + cnt);
           if(b[1] == b[3] && b[3] < b[4]) res = max(res,b[3]);
           cnt = 0;
       }
    cout << res << endl;
}
int main()
{
    int T = 1;
    //cin >> T;
    while(T --) solve();
    return 0;
}

B - Asuka大战兔子https://vjudge.net/problem/Gym-103401L

算法分析

由于Asuka有非常多的栅栏，你可以不输出使用最少栅栏的方案。由此条件可知,为了尽可能地隔开兔子和胡萝卜,直接将所有的空地都设为栅栏,然后在这个新的图上遍历兔子能走到的位置,若兔子在这种条件下仍能吃到胡萝卜,那么必然是不可能隔开的。吃不到胡萝卜的话,说明方案成立。

时间复杂度 $O(n^2)$

AC code

#include<bits/stdc++.h>
using namespace std;
const int N = 500 + 10;

char a[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool f = true;

void solve()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)
     for(int j = 1;j <= m;j ++)
     {
         cin >> a[i][j];
         if(a[i][j] == '.') a[i][j] = '#';
     }
      
    for(int i = 1;i <= n;i ++)
     for(int j = 1;j <= m;j ++)
     {
        if(a[i][j] == 'R')
        {
            for(int k = 0;k < 4;k ++)
            if(a[i + dx[k]][j + dy[k]] == 'C') 
            {
                f = false;
                puts("No");
                return ; 
            }
        }
     }
    if(f)
    {
        puts("Yes");
        for(int i = 1;i <= n;i ++)
        {
            for(int j = 1;j <= m;j ++)
            cout << a[i][j];
            cout << endl;
        }
    }
}
int main()
{
    int T = 1;
    //cin >> T;
    while(T --) solve();
    return 0;
}

C - 我不会debughttps://vjudge.net/problem/Gym-103401M

算法分析

一道非常典型的线性dp,没有想到整场只有两个人过了这题。

线性dp,顾名思义就是在线性结构上进行状态转移。

删除字符串有三种方式,删左侧第一个,删右侧第一个,删中间的一个

那么我们不妨将左右两侧分开考虑,将一个字母作为分界线,将删左侧的最优解和删右侧的最优解合并一定就是最优答案了。

最优子结构:

保证左侧前?? $i$ ?个字母合法的代价,一定是在保证前? $i-1$ ?个字母合法基础上的。假设保证前? $i-1$ ?个字母合法的代价为? $k$ ?,若第? $i$ ?个字母是? $P$ ?,那么可知前? $i$ ?个字母都是合法的因此保证前? $i$ ?个字母合法的代价也是? $k$ ?,若?第? $i$ ?个字母是? $F$ ,那么现在有两种删除方式,一种是将前? $i$ ?个字母全都删去这种代价是?? $i$ ?,另外一种就是不动?前? $i-1$ ?个字母,用? $2$ ?的代价删去中间字母,这种删除的总代价就是 $k + 2$ ?,因此对这两种方式取 $min(i,k + 2)$ ?即可。

通过上面的分析我们可以得到考虑左侧删除的动态转移方程

for(int i = 1;i <= n;i ++)
    {
        if(s[i] == 'P') f1[i] = f1[i - 1];
        else f1[i] = min(i,f1[i - 1] + 2);
    }

?那么右侧同理,在这里就不做分析了

我们来看看最后答案该怎么取,枚举所有分界点,保证左侧? $i$ ?个字母合法的代价,保证最右端至第 $i + 1$ 个字母合法的代价合并取? $min$ ?即为答案

int ans = 1 << 30;
    for(int i = 1;i <= n;i ++) ans = min(ans,f1[i] + f2[i + 1]); 
    cout << ans << endl;

AC code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

char s[N];
int f1[N],f2[N];

void solve()
{
    int n;
    cin >> n;
    scanf("%s",s + 1);
    for(int i = 1;i <= n;i ++)
    {
        if(s[i] == 'P') f1[i] = f1[i - 1];
        else f1[i] = min(i,f1[i - 1] + 2);
    }
    for(int i = n;i >= 1;i --)
    {
        if(s[i] == 'P') f2[i] = f2[i + 1];
        else f2[i] = min(n - i + 1,f2[i + 1] + 2);
    }
    int ans = 1 << 30;
    for(int i = 1;i <= n;i ++) ans = min(ans,f1[i] + f2[i + 1]); 
    cout << ans << endl;
}
int main()
{
    int T = 1;
    //cin >> T;
    while(T --) solve();
    return 0;
}

D - 我要吃饭https://vjudge.net/problem/Gym-103145I

算法分析

简单模拟

AC code

#include<iostream>
using namespace std;
int a[] = {7,27,41,49,63,78,108};
int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        int sum = 0;
        int n;scanf("%d",&n);
        for(int i = 1;i <= n;i ++)
        {
            int x;scanf("%d",&x);
            sum += a[x - 1];
        }
        if(sum >= 120) sum -= 50;
        else if(sum >= 89) sum -= 30;
        else if(sum >= 69) sum -= 15;
        printf("%d\n",sum);
    }
    return 0;
}

E - 删删删https://vjudge.net/problem/Gym-103145C

算法分析

树形dp,树形dp的常用思路就是考虑父结点和儿子结点的关系,在树的结构下进行状态转移。

按照闫氏dp分析法,我们将集合划分成三个部分

集合划分

1. 把自己删掉,那么子结点可以一起删,若子节点不删的话需要保证子节点至少有一个儿子相连
2. 不删去自己,且自己非叶子结点,那么自己一定会有一个父亲结点与自己相连,因此儿子无论如何都能成立
3. 不删除自己,且自己是叶子结点 => 自己是叶子结点,因此不能有儿子,因此自己的儿子必须删去自己

Tips: 上述的自己,指的是父亲结点,因为是考虑父亲结点所在子树的情况。

状态表示:
f[u][0]: 第一类情况
f[u][1]: 第二类情况
f[u][2]: 第三类情况

状态转移:
? ? f[u][0] = f[u][0] * f[j][0] + f[j][1]
? ? f[u][1] = f[u][1] * (f[j][0] + f[j][1] + f[j][2])
? ? f[u][2] = f[u][2] * f[j][0] % mod;

由此我们就可以愉快的开始写代码了(本题需要注意取模的问题)。

AC code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
const int M = N * 2; 
const int mod = 998244353; 
int h[N],ne[M],e[M],idx;
LL f[N][3];

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

void dfs(int u,int fa)
{
	f[u][0] = f[u][1] = f[u][2] = 1;
	for(int i = h[u];~ i;i = ne[i])
	{
		int j = e[i];
		if(j == fa) continue;
		dfs(j,u);
		f[u][0] = (f[u][0] % mod) * (f[j][0] + f[j][1]) % mod;
		f[u][1] = (f[u][1] % mod) * (f[j][0] + f[j][1] + f[j][2]) % mod;
		f[u][2] = f[u][2] * f[j][0] % mod;
	}
	f[u][1] = (f[u][1] - f[u][2] + mod) % mod;
}

int main() 
{	
	int T;
	cin >> T;
	while(T --)
	{
	    memset(h, -1, sizeof h);idx = 0;
		int n;
		cin >> n;
		for(int i = 1;i < n;i ++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			add(a,b),add(b,a);
		}
		dfs(1,0);
		cout << (f[1][0] + f[1][1] + mod) % mod << endl;
	}
	return 0;
}

F - 大水题https://vjudge.net/problem/Gym-103145E

算法分析

简单构造,

想求一个整数? $k$ ，它是正整数? $x$ ?的倍数，使得? $k$ ?是一个半完美数。反向构造,任意取一个半完美数,将其因子的最小单位赋为? $x$ ?即可。

ex.? $6$ ?是个半完美数,其因子 $1,2,3$ 符合条件,那么假设? $x$ ?为? $10$ ?,那么就可以构造成 $10 + 20 +30 = 60$ 。同理? $24$ ?也是个半完美数,其因子 $2,4,6,12$ 符合条件,那么就可以构造成 $20,40,60,120 = 240$

AC code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve()
{
    LL x;
    cin >> x;
    printf("%lld %lld\n",6 * x, 3);
    printf("%lld %lld %lld\n",x,2 * x,3 * x);
}
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        solve();
    }
    return 0;
}

G - 你一定会种树吧https://vjudge.net/problem/Gym-103145D

算法分析

线段树

Cold 太菜了,自己没做出来,待补....................

先放个宋老板的AC代码(狗头保命)

AC code

#include <bits/stdc++.h>

#define il inline
#define fi first
#define se second
#define ll long long
#define pii pair<int, int>
#define pll pair<long, long>
#define pb(x) push_back(x)
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
#define mem(num) memset(num,0,sizeof num)
#define lowbit(x) ((x)&-(x))

using namespace std;

const int mod = 998244353;
const int maxn = 1e5 + 100;

int n, m;
int a[maxn];
struct node{
	int l, r;
	ll sum;
	bool flag;
	int lazy;
} sgt[maxn<<2];

int judge(int x){
	return bitset<32>(x).count() == 1;
}

void push_up(int x){
	sgt[x].sum = (1LL*sgt[x<<1].sum + sgt[x<<1|1].sum)%mod;
	sgt[x].flag = (1LL*sgt[x<<1].flag && sgt[x<<1|1].flag);
}

void push_down(int x, int t){
	sgt[x].lazy = (1LL*sgt[x].lazy*t)%mod;
	sgt[x].sum = (1LL*sgt[x].sum*t)%mod;
}



void push_down(int x){
	if(sgt[x].lazy == 1) return;
	push_down(x<<1,sgt[x].lazy); push_down(x<<1|1,sgt[x].lazy);
	sgt[x].lazy = 1;
}

void build(int x, int l, int r){
	sgt[x] = {l, r, a[l], 0, 1};
	if(l == r) {
		//sgt[x].sum = a[l];
		if(judge(a[l])) sgt[x].flag = 1;
		return;
	}
	int mid = l + r >> 1;
	build(x<<1, l, mid); build(x<<1|1, mid + 1, r);
	push_up(x);
}

void update(int x, int l, int r){
	if(sgt[x].l>=l && sgt[x].r<=r){
		if(sgt[x].flag) {
			push_down(x, 2);
			return;
		}
		if(sgt[x].l == sgt[x].r){
			sgt[x].sum += lowbit(sgt[x].sum);
			sgt[x].flag = judge(sgt[x].sum);
			return;
		}
	}
	push_down(x);
	int mid = sgt[x].l + sgt[x].r >> 1;
	if(l<=mid) update(x<<1,l,r); 
	if(r>mid) update(x<<1|1,l,r);
	push_up(x);
}


inline ll query(int x, int l ,int r){
	if(sgt[x].l>=l&&sgt[x].r<=r) return sgt[x].sum;
	push_down(x);
	int mid = sgt[x].l + sgt[x].r >> 1;
	ll res = 0;
	if(l<=mid) res = (query(x<<1,l,r))%mod;
	if(r>mid) res = (res+query(x<<1|1,l,r))%mod;
	return res;
}

inline void solve(){
	cin >> n;
	for (int i = 1; i <= n; ++ i) {
		cin>>a[i];
	}
	build(1,1,n);
	int op, l, r;
	cin >> m;
	for (int i = 1; i <= m; ++ i) {
		cin>>op>>l>>r;
		if(op == 1) {
			update(1,l,r);
		} else {
			cout<<query(1,l,r)<<"\n";
		}
	}
	
}

signed main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);std::cout.tie(NULL);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
}

H - 货车https://vjudge.net/problem/Gym-103145K

算法分析

经典题型: 并查集求连通块中的联通点对数量。

本题的数据范围,限制了在线的做法。于是我们转向了离线查询,那么我们只需要询问从大到小排序即可。还有可以注意到的一点就是,如果货车总重量? $p$ ?大于? $k$ ?，则货车不能通过该条路,相当于图上没有这条边。因此我们也对边排序,按照询问要求,将满足承重量的边依次加入建图即可。(因为前边加入的边一定是能够承受住后面的重量的因此保证了正确性)

还有一个需要注意的两个子树合并时的贡献要怎么计算呢,假设合并前的两个 size 分别为? $a$ ?和? $b$ ?那么贡献就是

? ? ? ? ? ? ? ???????????????????????????????????????????????????????????????? $C\binom{a}{2} + C\binom{b}{2}$

合并后就是 $C\binom{a + b}{2}$ ?

那么贡献就是 $C\binom{a + b}{2} - C\binom{a}{2} - C\binom{b}{2} = a * b$

然后最后要注意的是long long?

经典名言 : 不开long long 见祖宗

AC code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
int p[N];
LL sz[N];
LL res[N];

struct Edge
{
    int a,b,c;
}edge[N];

struct Query
{
    int v;
    int id;
}query[N];

bool cmp1(Edge a,Edge b)
{
    return a.c > b.c;
}

bool cmp2(Query a,Query b)
{
    return a.v > b.v;
}

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void solve()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i = 1;i <= n;i ++) p[i] = i,sz[i] = 1;//并查集初始化
    for(int i = 1;i <= m;i ++)  scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);
    sort(edge + 1,edge + 1 + m,cmp1);//边从大到小排序
    for(int i = 1;i <= q;i ++) 
    {
        int x; scanf("%d",&x);
        query[i].v = x; query[i].id = i;
    }
    sort(query + 1,query + q + 1,cmp2);//从大到小询问,方便离线查询
    
    int pos = 1;
    LL sum = 0;
    for(int i = 1;i <= q;i ++)
    {
        for(;pos <= m;pos ++)
        {
            if(edge[pos].c >= query[i].v)//按询问顺序,从大到小建图
            {
                int fa = find(edge[pos].a);
                int fb = find(edge[pos].b);
                if(fa != fb)
                {
                    sum += sz[fa] * sz[fb];
                    p[fa] = fb;
                    sz[fb] += sz[fa];
                }
            }
            else break;
        }
        res[query[i].id] = sum;
    }
    for(int i = 1;i <= q;i ++) printf("%lld\n",res[i]);
}
int main()
{
    int T;
    cin >> T;
    while(T --) solve();
    return 0;
}

I - 超级打字大师https://vjudge.net/problem/Gym-103145M

算法分析

easy 大模拟

比赛过程中遭遇了题面上的质疑,但明明我在 "您只需按两次键即可输入任何中文单词" 加了着重符号。希望选手们以后可以认真读题,毕竟英文题面可比这个中文题面阴间多了,像"rang"这个例子在原题中是没有提醒的,但是只要盯着按两次键这句话就可以推断出 "rang" 一定是输出 "rh" 而不是"rah"的

好啦,本题的核心就是这句话,只需要对一个输入匹配两次就可以了。那么我们很自然就可以想到先用map打个表,然后substr分割一下,做个匹配就完事了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
char s[N];
int n;

map<string, char> mp = 
{
	{ "iu", 'q' }, { "ei", 'w' }, { "uan", 'r' }, { "ue", 't' },{ "un", 'y' }, { "sh", 'u' }, { "ch", 'i' }, { "uo", 'o' },
	{ "ie", 'p' }, { "ong", 's' }, { "iong", 's' }, { "ai", 'd' },{ "en", 'f' }, { "eng", 'g' }, { "ang", 'h' }, { "an", 'j' },
	{ "uai", 'k' }, { "ing", 'k' }, { "uang", 'l' }, { "iang", 'l' },{ "ou", 'z' }, { "ia", 'x' }, { "ua", 'x' }, { "ao", 'c' },
    { "zh", 'v' }, { "ui", 'v' }, { "in", 'b' }, { "iao", 'n' },{ "ian", 'm' }
};


void solve()
{
	for (char c = 'a'; c <= 'z'; ++ c)//单个字母映射为本身 写在这里 比打表打出来方便点 
	{
		string ch (1, c);//生成一个长度为 1 的字符 c 的 string
		mp[ch] = c;
	}
	while(~scanf("%s",s))
	{
	    int len = strlen(s);
	    if(len == 1) printf("%c%c",s[0],s[0]);//单字母
	    else if(len == 2) printf("%s",s);//双
	    else 
	    {
	        string yun_mu = s;
	        if(mp.count(yun_mu)) 
	        {
	            printf("%c%c",yun_mu[0],mp[yun_mu]);
	        }
	        else 
	        {
	            string a;
	            for(int i = 0;i < yun_mu.size();i ++)
	            {
	                a += yun_mu[i];
	                string b = yun_mu.substr(i + 1);
	                if(mp.count(a) && mp.count(b))
	                {
	                    printf("%c%c",mp[a],mp[b]);
	                    break;
	                }
	            }
	        }
	    }
	    putchar(getchar());
	}
}

int main()
{
    int T = 1;
    //cin >> T;
    while(T --) solve();
    return 0;
}

J - 简单数学https://vjudge.net/problem/Gym-103107F

算法分析

线性筛质数 + 数学推导

1. 当 $n$ ?为? $1$ ?或者质数时, $f(n) = 1$

2. 当? $n = p^{k}$ ?时,? $f(p^{k}) = pf(p^{k-2}) = p^2 f(p^{k - 4}) .......$

因此当 $k = 2x$ 时, $f(p^{k}) = p^xf(1) = p^x = p^{\frac{k} {2}}$

当? $k = 2x + 1$ ?时, $f(p^{k}) = p^xf(p) = p^x = p^{\frac{k} {2}}$ ?(对其向下取整)

3. 翻译成人话就是当? $n = {p_{1}} ^ {k1} {p_{2}} ^ {k2} {p_{3}} ^ {k3}...... {p_{i}} ^ {ki}$ ?, $f(n) = f({p1}^{k1}) {p_{2}} ^ {k2} {p_{3}} ^ {k3}...... {p_{i}} ^ {ki}$

而由第二种情况已知, $f(p^{k}) = p^xf(1) = p^x = p^{\frac{k} {2}}$ ?那么?

$f(n) = p_{1}^{\frac{k1} {2}} {p_{2}} ^ {k2} {p_{3}} ^ {k3}...... {p_{i}} ^ {ki}$ ? ,而? ${p_{2}} ^ {k2} {p_{3}} ^ {k3}...... {p_{i}} ^ {ki} = (n / {p1}^{k1})$

因此 $f(n) = p_{1}^{\frac{k1} {2}}* (n / {p1}^{k1})$ ?

而其实第二问中? $n = p^{k}$ ?时? $(n / {p1}^{k1}) = 1$ ?因此第二种情况和第三种情况是可以合并的

分析到这里我们就可以知道,,用线性筛把质数给筛出来然后保留第一个质因子就可以了。

AC code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10;

int primes[N],a[N];
bool st[N];
int cnt;

void get_primes(int n)  // 线性筛质数
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i,a[i] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            a[primes[j] * i] = primes[j];
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) 
            {
                a[i] = primes[j];
                break;
            }
        }
    }
}
LL quick_power(LL a, LL k)  // 龟速幂
{
    LL res = 1;
    while (k)
    {
        if (k & 1) res = res * a;
        a = (LL)a * a;
        k >>= 1;
    }
    return res;
}

LL f(int n)
{
    if(n == 1 || st[n] == false) return 1;//1 || 质数为 1
    LL k1 = 0, p1 = a[n];
    LL tmp = n;
    while(tmp % a[n] == 0)//计算 n 在 p1 这个底数上的次幂有多少 即求 k1
    {
        tmp /= a[n];
        ++ k1;
    }
    //printf("k = %d \n",k);
    return quick_power(p1, floor(k1 / 2)) * (n / pow(p1, k1));
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);//先将质数全都筛出
    LL res = 0;
    for(int i = 1;i <= n;i ++) res += f(i);//求和
    cout << res << endl;
    return 0;
}

K - 小游戏https://vjudge.net/problem/Gym-103107D

算法分析

区间 dp 模板题,学过区间dp以后这题应该是随便切的在这里就不过多赘述了。

关于区间dp 强烈推荐wls写的文章。wls yyds

AC code

#include<bits/stdc++.h>
using namespace std;
const int mod = 1000003;
const int N = 300 + 10;
typedef long long LL;

int res = -1;
LL f[N][N];
LL a[N],s[N];
LL Ni[N];

LL quick_power(LL a, LL k, LL p)  // 求a^k mod p
{
    LL res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
void solve()
{
    
    int n;scanf("%d",&n);
    s[0] = Ni[0] = 1;
    for(int i = 1;i <= n;i ++)
    {
         scanf("%lld",&a[i]);
         s[i] = (s[i - 1] * a[i] )% mod;
         Ni[i] = quick_power(s[i],mod - 2,mod);
    }
    
    for(int len = 1;len <= n;len ++)
    {
        for(int i = 1;i <= n - len + 1;i ++)
        {
            int j = i + len - 1;
            for(int k = i;k <= j - 1;k ++)
            {
                LL x = s[k] * Ni[i - 1] % mod;
                LL y = s[j] * Ni[k] % mod;
                f[i][j] = max((LL)f[i][j],f[i][k] + f[k + 1][j] + (LL)(x - y) * (LL)(x - y));
            }
        }
    }
    cout << f[1][n] << endl;
}
int main()
{
    int T = 1;
    while(T --) solve();
    return 0;
}

L - cold玩真人cshttps://vjudge.net/problem/Gym-103401F

算法分析

简单模拟,没啥好讲的

AC code

#include<bits/stdc++.h>
using namespace std;
const int mod = 1000003;
const int N = 300 + 10;
typedef long long LL;

int res = -1;
LL f[N][N];
LL a[N],s[N];
LL Ni[N];

LL quick_power(LL a, LL k, LL p)  // 求a^k mod p
{
    LL res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
void solve()
{
    
    int n;scanf("%d",&n);
    s[0] = Ni[0] = 1;
    for(int i = 1;i <= n;i ++)
    {
         scanf("%lld",&a[i]);
         s[i] = (s[i - 1] * a[i] )% mod;
         Ni[i] = quick_power(s[i],mod - 2,mod);
    }
    
    for(int len = 1;len <= n;len ++)
    {
        for(int i = 1;i <= n - len + 1;i ++)
        {
            int j = i + len - 1;
            for(int k = i;k <= j - 1;k ++)
            {
                LL x = s[k] * Ni[i - 1] % mod;
                LL y = s[j] * Ni[k] % mod;
                f[i][j] = max((LL)f[i][j],f[i][k] + f[k + 1][j] + (LL)(x - y) * (LL)(x - y));
            }
        }
    }
    cout << f[1][n] << endl;
}
int main()
{
    int T = 1;
    while(T --) solve();
    return 0;
}

M - 杰哥打怪https://vjudge.net/problem/Gym-103117L

算法分析

没想到啊 ,一个小小 BFS 没人写的,大概是因为带榜的人给带歪了,我应该当时出手开这题的。

由于? $w$ ?的范围只有 $1-100$ ?那么只要对每一个对应的防御力跑 BFS, 即跑? $100$ ? 次BFS。求出距离每个点到各个防御力怪兽的最近距离,即? $dist[i][j]$ ?表示距离? $j$ ?点最近的防御力为? $i$ ?的距离。

那么对于每次询问 p , a 就是找到距离村庄 p 最近且防御力小于 a 的就是答案

即

		int res = 0x3f3f3f3f;
		for(int i = 1;i <= a;i ++)//找到最近的 且小于猎人攻击力的点
		if(dist[i][p] != -1)  res = min(res,dist[i][p]);
		if(res == 0x3f3f3f3f) res = -1;//未被更新说明没法打
		printf("%d\n",res);

AC code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int>g[N];
int w[N];
int dist[110][N];
int n,m,q;
void bfs(int x)
{
    queue<int> q;
    for(int i = 1;i <= n;i ++) if(w[i] == x) q.push(i),dist[x][i] = 0;
    while(q.size())
    {
        auto t = q.front();q.pop();
        for(auto u : g[t])
        {
            if(dist[x][u] != -1) continue;
			q.push(u); dist[x][u] = dist[x][t] + 1;
        }
    }
}
int main()
{
    memset(dist,255,sizeof dist);
    cin >> n >> m >> q;
    for(int i = 1;i <= n;i ++) cin >> w[i];
    while(m --)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 100;i >= 1;i --) bfs(i);
    while(q --)
	{
		int p,a; scanf("%d%d",&p,&a);
		int res = 0x3f3f3f3f;
		for(int i = 1;i <= a;i ++)//找到最近的 且小于猎人攻击力的点
		if(dist[i][p] != -1)  res = min(res,dist[i][p]);
		if(res == 0x3f3f3f3f) res = -1;//未被更新说明没法打
		printf("%d\n",res);
	}
    return 0;
}