10-5训练

题目链接

2019牛客国庆集训派对day4

A

思路

这道题就是把矩阵补全之后，然后求伴随矩阵。
因为把每一列去掉，其实就是补全后的代数余子式。求伴随矩阵的话我们用高斯消元求逆矩阵然后乘上行列式的值即可

$$A^{*}=|A|A^{-1}$$

然后我们用高斯消元求出逆矩阵即可

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 250;
int a[maxn][maxn],b[maxn][maxn];
const int md = 1e9+7;
int quick_pow(int a,int b)
{
	int ans = 1;
	while(b)
	{
		if(b&1)ans=(1ll*ans*a)%md;
		b>>=1;
		a=(1ll*a*a)%md;
	}
	return ans;
}
void gs(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			b[i][j]=(i==j);
		}
	}
	int det = 1;
	for(int i=1;i<=n;i++)
	{
		int t=1;
		for(int k=1;k<=n;k++)
		{
			if(a[k][i])t=i;
		}
		if(t!=i)det*=-1;
		for(int j=1;j<=n;j++)
		{
			swap(a[i][j],a[t][j]);
			swap(b[i][j],b[t][j]);
		}
		det = 1ll*a[i][i]*det%md;
		int inv = quick_pow(a[i][i],md-2);
		for(int j=1;j<=n;j++)
		{
			a[i][j]=1ll*inv*a[i][j]%md;
			b[i][j]=1ll*inv*b[i][j]%md;
		}
		for(int k=1;k<=n;k++)
		{
			if(k==i)continue;
			int tem = a[k][i];
			for(int j=1;j<=n;j++)
			{
				a[k][j]=(a[k][j]-1ll*a[i][j]*tem%md+md)%md;
				b[k][j]=(b[k][j]-1ll*b[i][j]*tem%md+md)%md;
			}
		}
	}
	det = (det+md)%md;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			b[i][j]=1ll*det*b[i][j]%md;
		}
	}
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
		{
			if(i==1)
			{
				for(int j=1;j<=n;j++)a[i][j]=1;
			}
			else
			{
			for(int j=1;j<=n;j++)
			{
				scanf("%d",&a[i][j]);
			}
		    }
		}
		gs(n);
		for(int i=1;i<=n;i++)
		{
			if(i&1)
			{
				printf("%d ",b[i][1]%md);
		    }
		    else
		    {
		    	printf("%d ",(md-b[i][1])%md);
			}
		}
		printf("\n");
	}
}

H

思路

求出树的直径，然后找两个端点跑最短路，然后遍历每个点，选择到达两个端点的最短距离中的一个相加起来，贴一下队友的代码

代码实现

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#include<string>
#include<vector>
#include<iomanip>
#include<cstdio>
#include<stack>
using namespace std;
typedef long long ll;
const int maxn = 100005;
struct edge { int to, next; ll cost; };
typedef pair<ll, int> p;
int n, top, k1, k2;
ll ma;
ll d1[maxn], d2[maxn];
edge G[200005];
int head[maxn];
int vis[maxn];
void add(int a, int b, ll c)
{
    G[top].to = b;
    G[top].cost = c;
    G[top].next = head[a];
    head[a] = top++;
}
void dijkstra1(int s)
{
    priority_queue<p, vector<p>, greater<p> >que;
    memset(d1, 0x3f, sizeof(d1));
    d1[s] = 0;
    que.push(p(0, s));
    while (!que.empty())
    {
        p q = que.top();
        int v = q.second;
        que.pop();
        if (d1[v] < q.first) continue;
        for (int i = head[v]; i != -1; i = G[i].next)
        {
            if (d1[G[i].to] > d1[v] + G[i].cost)
            {
                d1[G[i].to] = d1[v] + G[i].cost;
                que.push(p(d1[G[i].to], G[i].to));
            }
        }
    }
}
void dijkstra2(int s)
{
    priority_queue<p, vector<p>, greater<p> >que;
    memset(d2, 0x3f, sizeof(d2));
    d2[s] = 0;
    que.push(p(0, s));
    while (!que.empty())
    {
        p q = que.top();
        int v = q.second;
        que.pop();
        if (d2[v] < q.first) continue;
        for (int i = head[v]; i != -1; i = G[i].next)
        {
            if (d2[G[i].to] > d2[v] + G[i].cost)
            {
                d2[G[i].to] = d2[v] + G[i].cost;
                que.push(p(d2[G[i].to], G[i].to));
            }
        }
    }
}
void init()
{
    top = 0;
    memset(head, -1, sizeof(head));
}
void dfs1(int x, ll ans)
{
    bool flag = true;
    for (int i = head[x]; i != -1; i = G[i].next)
    {
        if (vis[G[i].to]) continue;
        else
        {
            flag = false;
            break;
        }
    }
    if (flag)
    {
        if (ans > ma)
        {
            ma = ans;
            k1 = x;
        }
    }
    for (int i = head[x]; i != -1; i = G[i].next)
    {
        if (vis[G[i].to] == 0)
        {
            vis[G[i].to] = 1;
            dfs1(G[i].to, ans + G[i].cost);
        }
    }
}
void dfs2(int x, ll ans)
{
    bool flag = true;
    for (int i = head[x]; i != -1; i = G[i].next)
    {
        if (vis[G[i].to]) continue;
        else
        {
            flag = false;
            break;
        }
    }
    if (flag)
    {
        if (ans > ma)
        {
            ma = ans;
            k2 = x;
        }
    }
    for (int i = head[x]; i != -1; i = G[i].next)
    {
        if (vis[G[i].to] == 0)
        {
            vis[G[i].to] = 1;
            dfs2(G[i].to, ans + G[i].cost);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    while (cin >> n)
    {
        init();
        int u, v;
        ll w;
        for (int i = 0; i < n - 1; i++)
        {
            cin >> u >> v >> w;
            add(u, v, w);
            add(v, u, w);
        }
        memset(vis, 0, sizeof(vis));
        ma = 0;
        vis[1] = 1;
        dfs1(1,0);
        memset(vis, 0, sizeof(vis));
        ma = 0;
        vis[k1] = 1;
        dfs2(k1, 0);
        dijkstra1(k1);
        dijkstra2(k2);
        ll ans = d1[k2];
        for (int i = 1; i <= n; i++)
        {
            if (i == k1 || i == k2) continue;
            if (d1[i] > d2[i]) ans += d1[i];
            else ans += d2[i];
        }
        cout << ans << endl;
    }
    return 0;
}

I

思路

题目有一些误导，既然α是实数，加上1/2没啥意义，所以我们就讨论f(t)就好了

$$f(t)=|\frac{i}{n}-\frac{j}{m}+t|$$

把前两个分式通分

$$f(t)=|\frac{im-jn}{nm}+t|$$

显然，上面可以提取n,m的gcd

$$f(t)=|\frac{gcd(n,m)*k}{nm}+t|$$

这就是最后的式子，显然我们可以发现当t为$\frac{1}{2nm}$时，f(t)就是最大的，因为这个最接近$\frac{gcd(n,m)k}{nm}$且不等于0的值，所以答案就是

$$Ans = \frac{1}{2*n*m/gcd(n,m)}$$

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}
int main()
{
	ll n,m;
	while(cin>>n>>m&&n&&m)
	{
		ll up,down;
            up=1;
			down=n*m*2;
			down/=gcd(down,gcd(n,m));
		printf("%lld/%lld\n",up,down);
	}
}

你最愿意做的哪件事，才是你的天赋所在