3.28 | Arn01d's planet

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

D

题意：给定 $n$ ，构造长为 $2n$ 的数列 $a$ ，使得
$$
(a_1 × a_2)+(a_3 × a_4)+ . . . +(a_{2n−1} × a_{2n}) = a_1 ×(a_2 + a_3)×(a_4 + a_5)× . . . ×(a_{2n−2} + a_{2n−1})× a_{2n}\neq 0
$$
且 $1\leq |a_i|\leq10^{10}$ 。

分奇偶讨论，令 $a_1 $ 与 $a_{2n}$ 为1，然后其余的数交替为-1和2，使得乘法的每一项和为1，然后留下最中间的两个数，解方程得出。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a[n*2+1];
        if(n==2)
        {
            cout<<"1 -3 -3 1\n";
            continue;
        }
        if(n==3)
        {
            cout<<"1 -10 6 6 -10 1\n";
            continue;
        }
        if(n==4)
        {
            cout<<"1 -15 10 -1 -1 10 -15 1\n";
            continue;
        }
        a[1]=1,a[n*2]=1;
        for(int i=1;i<n/2;i++)
        {
            a[i*2]=-1;
            a[i*2+1]=2;
            a[2*n-i*2+1]=-1;
            a[2*n-i*2]=2;
        }
        if(n%2==0)
        {
            a[n]=1;
            a[n+1]=2*(n-3)-1;
        }
        if(n%2==1)
        {
            a[n-1]=1;
            a[n+2]=1;
            if(n==5)a[n]=3,a[n+1]=-2;
            else
            {
                a[n]=1;
                a[n+1]=-2*(n-6)-2;
            }
            
        }

        int ans1=0,ans2=1;
        for(int i=1;i<=n;i++)ans1+=a[i*2]*a[i*2-1];
        for(int i=1;i<n;i++)ans2*=a[i*2]+a[i*2+1];
        for(int i=1;i<=n*2;i++)cout<<a[i]<<" ";cout<<endl;
    }

    return 0;
}

G

题意：给出一条蛇身上每个点的位置，蛇在网格内移动，每次可以选择上下左右移动一步或者将尾巴缩短一节。蛇不能到边界之外、不能与障碍相碰、不能和自身相碰。设 $f(i,j)$ 表示蛇头从开始位置到 $(i,j)$ 经历的最小步数。求 $\sum\sum f(i,j)^2$ 。

一开始想用bfs扩展，但是发现可能会导致重复更新。于是考虑最短路算法。

将所有点与相邻点之间连边，若不为蛇身的位置，直接由蛇头dij得到答案；

若为蛇身，假设蛇长 $k$ ，此时为蛇身上的第 $i$ 节，考虑当前步数 $d$ 与 $k-i$ 的关系，若 $d\leq k-i$ ，那么说明此时会和蛇相碰，那么答案就为 $d+(k-i-d+1)=k-i+1$ ，否则答案就为 $d$ ，将其加入优先队列等待更新。

但是这样做复杂度为 $O(nmlog(nm))$ ，刚好超时，可以优化一下：

蛇身点用优先队列 $q1$ 维护。
非蛇身点直接用普通队列 $q2$ 维护，类似于bfs，一定是递增的。
每次在 $q1$ 和 $q2$ 中选择最小的点取出来进行更新。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
int n,m,k;
char g[3001][3001];
bool vis[3001][3001];
ll d[3001][3001];
int body[3001][3001];
int hx,hy;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void dij()
{
    d[hx][hy]=0;
    priority_queue<pair<int,pair<int,int> >, vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > >q1;//body
    queue<pair<ll,pair<int,int> > >q2;//notbody

    q1.push({0,{hx,hy}});
    while(q1.size() || q2.size())
    {
        int ans,x,y;
        if(q1.size() && q2.size())
        {
            if(q1.top().first<q2.front().first)
            {
                ans=q1.top().first;
                x=q1.top().second.first;
                y=q1.top().second.second;
                q1.pop();
            }
            else
            {
                ans=q2.front().first;
                x=q2.front().second.first;
                y=q2.front().second.second;
                q2.pop();
            }
        }
        
        else if(q1.size())
        {
            ans=q1.top().first;
            x=q1.top().second.first;
            y=q1.top().second.second;
            q1.pop();
        }

        else
        {
            ans=q2.front().first;
            x=q2.front().second.first;
            y=q2.front().second.second;
            q2.pop();
        }

        if(vis[x][y])continue;
        vis[x][y]=1;

        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m || g[nx][ny]=='#')continue;
            if(body[nx][ny]==0)
            {
                ll tmp=d[x][y]+1;
                if(tmp<d[nx][ny])
                {
                    d[nx][ny]=tmp;
                    q2.push({tmp,{nx,ny}});
                }
                
            }
            else
            {
                ll tmp=max(d[x][y]+1,(ll)k-body[nx][ny]+1);
                if(tmp<d[nx][ny])
                {
                    d[nx][ny]=tmp;
                    q1.push({tmp,{nx,ny}});
                }
            }
            
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;

    for(int i=1;i<=k;i++)
    {
        int x,y;
        cin>>x>>y;
        body[x][y]=i;
        if(i==1)hx=x,hy=y;
    }
    for(int i=1;i<=n;i++)cin>>g[i]+1;
    memset(d,0x3f,sizeof(d));
    dij();

    ull sum=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(d[i][j]<0x3f3f3f3f && g[i][j]!='#')sum+=(ull)d[i][j]*d[i][j];
        }
    }
    cout<<sum;
    return 0;
}

最短路

H

题意：有 $n$ 个人，每个人最初有 $a_i$ 颗糖，现在有 $n$ 个事件按随机顺序发生：第 $i$ 个事件表示若 $i$ 的糖比 $b_i$ 的糖少，那么 $i$ 获得 $w_i$ 颗糖。求最后每个人获得的糖的期望。

只有当 $a[b_i]\leq a[i]<a[b_i]+w[b_i]$ 时 $i$ 才会得到奖励，否则 $i$ 的值是固定的。那么可以遍历所有有效限制关系，使具有如上关系的 $b_i$ 成为 $i$ 的父亲，然后若遇到确定的 $i$ ，那么打上标记，使其成为根节点。这棵树代表了先后顺序，只有父节点获得了糖，子节点才会获得糖。

最后会构成很多棵树，从根节点往下遍历：若根节点的值是确定的且不会获得糖，那么这棵子树的所有子节点都不会获得糖；若根节点能获得糖，那么往下遍历，假设从根到某个点经历了 $x$ 个点，那么该点获得糖的概率就是 $\frac{1}{x!}$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10,mod=1e9+7;
int n;
int a[N],b[N],w[N];
int inv[N],jcinv[N];
int cnt,head[N],nxt[N],to[N];
bool h[N],rt[N],vis[N];
int ans[N];
inline void add(int u,int v){
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
}

void dfs(int u,int tot){
    ans[u]=(ans[u]+jcinv[tot]*w[u]%mod)%mod;
    for(int i=head[u];i;i=nxt[i]){
        dfs(to[i],tot+1);
    }
}

signed main(){
    int T;
    scanf("%lld",&T);
    inv[1]=1;
    jcinv[1]=1;
    for(int i=2;i<=5e5;++i){
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        jcinv[i]=jcinv[i-1]*inv[i]%mod;
    }
    // cout<<"asdf"<<endl;
    while(T--){
        scanf("%lld",&n);
        cnt=0;
        for(int i=1;i<=n;++i)   head[i]=0;
        for(int i=1;i<=n;++i)   scanf("%lld",&a[i]);
        for(int i=1;i<=n;++i)   scanf("%lld",&b[i]);
        for(int i=1;i<=n;++i)   scanf("%lld",&w[i]);
        for(int i=1;i<=n;++i){
            ans[i]=a[i];
            if(a[b[i]]<=a[i]&&a[i]<a[b[i]]+w[b[i]])    add(b[i],i),rt[i]=0;
            else rt[i]=1;
        }
        for(int i=1;i<=n;++i){
            if(!rt[i])  continue;
            if(a[i]>=a[b[i]]+w[b[i]])   continue;
            // cout<<"asdf"<<endl;
            dfs(i,1);
        }
        for(int i=1;i<=n;++i)   printf("%lld ",ans[i]);
        puts("");
    }
    // system("pause");
}

bfs/dfs

J

题意：给出有 $n$ 个节点的树，这棵树有两种形态，要么是一条链，要么是有一个根节点，其有 $n-1$ 个儿子。现在可以询问 $\lceil\frac{n}{2}\rceil+3$ 次，每次询问可以问两个点，judge会告诉这两个点是否有边直接相连。确定这棵树是什么形态。

首先两两询问直到找到两个点 $u,v$ 有边相连，花费 $\lceil\frac{n}{2}\rceil$ 次。
对于 $u$ ，任找一个点 $x$ 询问，若 $u,x$ 有边，那么再随机询问 $u,y$ ，若有边则是状态2，若无边则一定是状态1。若 $u,x$ 无边，那么依次询问 $v,y$ 与 $v,z$ 得到答案。

# include <bits/stdc++.h>

using namespace std;
int n;
int main()
{
    int m;
    scanf("%d",&m);
    while(m --)
    {
        cin >> n;
        int i;  

        for(i = 1; i <= n; i += 2)
        {
            int t;
            if(i != n)
            {
                cout << "? " << i << " " <<  i + 1 << '\n';
                cin >> t;
            }
            else 
            {
                cout << "? " << i << " " <<  i - 1 << '\n';
                cin >> t;
            }
            if(!t) continue;
            else
            {
                int j,k;
                if(i == 1) j = n, k = n - 1;
                else if(i == n - 1) j = 1, k = 2;
                else if(i == n) j = 1, k = 2, --i;
                else j = i - 1, k = i + 2;

                cout << "? " << i << " " << j << '\n';
                cin >> t;
                if(t)
                {
                    cout << "? " << i << " " << k << '\n';
                    cin >> t;
                    if(t) 
                    {
                        cout << "! 2\n";
                        break;
                    }
                    else 
                    {
                        cout << "! 1\n";
                        break;
                    }
                }
                else
                {
                    cout << "? " << i + 1 << " " << j << '\n';
                    cin >> t;
                    if(t)
                    {
                        cout << "? " << i + 1 << " " << k << '\n';
                        cin >> t;
                        if(t) 
                        {
                            cout << "! 2\n";
                            break;
                        }
                        else 
                        {
                            cout << "! 1\n";
                            break;
                        }
                    }
                    else
                    {
                        cout << "! 1\n";
                        break;
                    }
                }
            }
        }

        if(i > n) cout << "! 1\n"; 
    }
    return 0;
}

M

题意：给出一组长度为 $n,n\geq3$ 的数，使其在数字大小上形成 $V$ 型，求一个 $V$ 型连续子序列，使得其平均值最大。

$V$ 的一边全选，另一边一个一个枚举。

#include<bits/stdc++.h>
using namespace std; 
#define LL long long
int n;
LL a[300010],mn,pm;

double sum,avr;
double ans;
signed main(){
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int T;
    scanf("%d",&T);
    while(T--){
        ans=sum=0;
        mn=1e9+10;
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%lld",a+i);
            if(a[i]<mn) mn=a[i],pm=i;
        }
        for(int i=1;i<=pm+1;++i)
            sum+=a[i];
        ans=avr=sum/(pm+1);
        for(int i=pm+2;i<=n;++i){
            sum+=a[i];
            avr=sum/i;
            ans=max(ans,avr);
        }
        sum=0;
        for(int i=n;i>=pm-1;--i){
            sum+=a[i];
        }
        avr=sum/(n-pm+2);
        ans=max(ans,avr);
        for(int i=pm-2;i;--i){
            sum+=a[i];
            avr=sum/(n-i+1);
            ans=max(ans,avr);
        }
        // cout<<fixed<<setprecision(15)<<ans<<'\n';
        printf("%.15lf\n",ans);
    }
    // system("pause");
    return 0;
}