2020杭电多校第六场题解Road To The 3rd Building、Little Rabbit‘s Equation、A Very Easy Graph Problem、Divisibilit、Expectation

发布于 2020-08-11  0 次阅读


Road To The 3rd Building

题目大意:

思路:

官方题解很容易理解

在这里插入图片描述

不过有些人不喜欢看官方的题解(比如我)所以还是写一下
1、这里区间的是未知的,所以肯定需要枚举区间的长度
2、我们只需要求得每个长度下的幸福值出现的和,然后乘上区间长度的逆元即可
3、对于每个长度下的和,经过观察可得(附上大佬的找规律:规律),其中k kk和n − k + 1 n−k+1n−k+1是相同的
4、规律其实就是一种类似三角形往上面堆,就是中间的长度会依次加1,代码就是
k = ( k + s u m [ n − i + 1 ] − s u m [ i − 1 ] + m o d ) % m o d(sum是前缀和)
5、最后注意一下,当n等于奇数的时候,单独加上中间的那个数

AC Code:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
const int mod=1e9 +7;
ll n, a[N], inv[N], sum[N];
ll quick_pow(ll a, ll b)
{ 
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
void init(){    //逆元打表
    inv[1]=1;
    for(int i=2; i<N; i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    return ;
}
void solve(){
    cin>>n;
    for(int i=1; i<=n; i++){        
        cin>>a[i];
        sum[i]=(sum[i-1]+a[i])%mod; //计算前缀和
    }
    ll ans=0, k=0;
    for(int i=1; i<=n/2; i++){
        k=(k+sum[n-i+1]-sum[i-1]+mod)%mod;          //算出当前分子的总和(类似三角形,从中间往上面堆
        ans=(ans+k*(inv[i]+inv[n-i+1])%mod)%mod;    //因为i和n-i+1的分子是一样的,所以直接一起计算了
    }
    if(n&1) ans=(ans +(k+a[n/2+1])%mod *inv[n/2+1] %mod)%mod;   //因为是两个一组,n为奇数的话中间的数要单独计算
    cout<<ans*quick_pow(((n+1)*n/2)%mod, mod-2)%mod<<endl;      //别忘了除以所有方案的总和
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    init();
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

Little Rabbit’s Equation

题目大意:

给你一个运算的字符串,让你判断是否有进制可以满足该计算,可以的话输出进制数,否则输出-1

思路:

将字符串分割成三段,然后枚举进制( 2 − 16 ) ,判断枚举的进制下计算是否成立
记得用long long

AC Code:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
#define ll long long
// #define TDS_ACM_LOCAL
string s, a, b, c;
char q;
ll x, y, z;
ll Atoi(string s,ll radix)  
{
	ll ans=0;
	for(ll i=0;i<s.size();i++)
	{
		char t=s[i];
		if(t>='0'&&t<='9') 
		{
			if(t - '0' >= radix) return -1;
			ans = ans * radix + 1ll * (t-'0');
		}
		else 
		{
			if(1ll * (t - 'A' + 10) >= radix) return -1;
			ans = ans * radix + 1ll * (t - 'A' + 10);
		}
	}
	return ans;
}

void solve(){
    int flag=1;
    a=b=c="";
    for(int i=0; i<s.length(); i++){            //分割字符串s到a,b,c
        if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/')    {flag=2, q=s[i]; continue;} //转换到字符串b
        else if(s[i]=='=')  {flag=3; continue;}     //转换到字符串c

        if(flag==1)      a+=s[i];
        else if(flag==2) b+=s[i];
        else if(flag==3) c+=s[i];   
    }
    flag=0;
    for(int i=2; i<=16; i++){   
        x=Atoi(a, i), y=Atoi(b, i), z=Atoi(c, i);       //转换成十进制
        if(x==-1 || y==-1 || z==-1) continue;           //当前进制容不下a,b,c的某个数,进行下个进制
        //判断+ - * /
        if(q=='+' && x+y==z) flag=1;                    
        else if(q=='-' && x-y==z) flag=1;
        else if(q=='*' && x*y==z)   flag=1;
        else if(q=='/' && y!=0 && x==y*z && x%y==0)   flag=1;
        if(flag)    {cout<<i<<endl; return ;}
    }
    if(!flag)   cout<<"-1"<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    while(cin>>s)   solve();
    return 0;
}

A. Very Easy Graph Problem

题目大意:

思路:

首先看看官方题解:

在这里插入图片描述

简而言之就是新添加的边权肯定是大于之前的,如果之前就能到这个点了,那就按照之前的走(一句话就是能到的点就不加新边)
然后很明显的求出来个最小生成树,算出每条边的贡献然后加起来即可
每条边的贡献:有多少次1到0会经过该边(子树的1到外面的0 and 子树的0到外面的1)

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
const int mod=1e9 +7;
int n, m, a[N];
int f0[N], f1[N], val[N<<1], fa[N], cnt, ans;
int head[N],nex[N<<1],to[N<<1],tot;
int find(int u){                  
	if(fa[u]==u)	return u;
	return fa[u]=find(fa[u]);
}
void add(int x,int y,int z) {
    to[++tot] = y;
    nex[tot] = head[x];
    val[tot] = z;
    head[x] = tot;
}
void dfs(int x, int fa){
    if(a[x])    f1[x]=1;                //该结点为1就在f1中记录,反之亦然
    else        f0[x]=1;
    for(int i=head[x]; i; i=nex[i]){
        int v=to[i], w=val[i];          //找到去的点和边权
        if(v!=fa){                      
            dfs(v, x);
            f1[x]+=f1[v], f0[x]+=f0[v]; //更新f1和f0
            int sum0, sum1;             
            sum1=f1[v], sum0=(n-cnt)-f0[v];         //此处sum1为子树的1的数量,sum0为除子树外的0的数量
            ans=(ans+sum1*sum0%mod *w%mod)%mod;
            sum1=cnt-f1[v], sum0=f0[v];             //此处sum1为除子树外的1的数量,sum0为子树的0的数量
            ans=(ans+sum1*sum0%mod *w%mod)%mod;
        }
    }
}
void solve(){
    ans=tot=cnt=0;  //tot为边的数量,cnt为点1的数量,ans为答案
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        head[i]=0, f1[i]=f0[i]=0, fa[i]=i;  //初始化,其中f0为记录子树为0的数量,f1相应的为1的数量
        cnt+=a[i];  
    }   
    int u, v, w=1, x, y;
    for(int i=1; i<=m; i++){
        cin>>u>>v;
        w=w*2%mod;
        x=find(u); y=find(v);         //如果两点未连接创建边
        if(x!=y)    {add(u, v, w), add(v, u, w), fa[x]=y;}
    }
    dfs(1,-1);      //选取1根结点进行dfs
    cout<<ans<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

Divisibility

思路:

直接看官方证明吧

在这里插入图片描述

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;

void solve(){
    int b, x;
    cin>>b>>x;
    if(b%x==1)  cout<<"T"<<endl;
    else    cout<<"F"<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

Expectation

题目大意:

基尔霍夫矩阵

给你一个无向图,有n个点,m条边,每个边的边权为wi,定义树的权为树的所有边的边权的按位与。
现在我们随机选择该图的一个生成树,问其生成树的权期望是多少。

思路:

先看一下官方题解

在这里插入图片描述

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=209;
const int mod=998244353;
vector<int>mp[N][N];
int mat[N][N];
int n, m;

int quick_pow(int a, int b)
{ 
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

int gauss(int n, int K[][N]){//求矩阵K的n-1阶顺序主子式
    int res=1;
    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n-1;j++){
            while(K[j][i]){
                int t=K[i][i]/K[j][i];
                for(int k=i;k<=n-1;k++)
                    K[i][k]=(K[i][k]-t*K[j][k]+mod)%mod;
                swap(K[i],K[j]);
                res=-res;
            }
        }
        res=(res*K[i][i])%mod;
    }
    return (res+mod)%mod;
}

void solve(){
	cin>>n>>m;
	memset(mat, 0, sizeof(mat));
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			mp[i][j].clear();
	int u, v, w;
	for(int i=1; i<=m; i++){
		cin>>u>>v>>w;
		mp[u][v].push_back(w), mp[v][u].push_back(w);
		//建立总的基尔霍夫矩阵
		mat[u][v]--, mat[v][u]--;
		mat[u][u]++, mat[v][v]++;
	}
	int sum=quick_pow(gauss(n, mat), mod-2);			//求出总的生成树的个数的逆元
	int f=0;
	for(int k=0; k<=30; k++){
		memset(mat, 0, sizeof(mat));
		for(int i=1; i<=n; i++)
			for(int j=i+1; j<=n; j++)
				for(auto x:mp[i][j])
					//求得每一位的基尔霍夫矩阵
					if(x&(1<<k)){
						mat[i][j]--, mat[j][i]--;
						mat[i][i]++, mat[j][j]++;
					}
		f=(f+quick_pow(2,k)*gauss(n,mat)%mod)%mod;		//求得每一位的生成树的个数
	}
	
	cout<<sum*f%mod<<endl;
	return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

平平无奇的大学在读本科生