2020牛客暑期多校训练营(第九场)题解A、I、F、K、E

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


A. Groundhog and 2-Power Representation

思路:

大数,python,直接在计算幂的地方替换python的幂次计算(**),然后用eval函数计算即可

AC Code:

print(eval(str(input()).replace('(', '**(')))

I. The Crime-solving Plan of Groundhog

思路:

显然两个数字相差越大,乘积越小,所以需要找到第一个不为0的数字成为第一个数,第二个不为0的数字为第二个数的开头,后面接上0和其他非递减的数

AC Code:

.cpp:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n;
int a[N];
void solve(){   
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    sort(a+1, a+1+n);
    int pos=0;
    while(!a[++pos]);
    swap(a[1], a[pos]), swap(a[2], a[pos+1]);
    for(int i=2; i<=n; i++) a[i]*=a[1];
    for(int i=n; i>2; i--) a[i-1]+=a[i]/10, a[i]%=10;
    for(int i=2; i<=n; i++) cout<<a[i];
    cout<<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;
}

.py:

T=int(input())
while T:
    T-=1
    n=int(input())
    a=input().split()
    a.sort()
    pos=0
    while a[pos]=='0':
        pos+=1
    x=a[pos]
    y=a[pos+1]+'0'*pos+''.join(a[pos+2:])
    print(int(x)*int(y))

F. Groundhog Looking Dowdy

题目大意:

给你n天,n天中每天都有k件衣服,衣服具有权值
你需要选择其中的m天,使得衣服的最大权值和最小权值差最小

思路:

显然的尺取,开个vector记录没件衣服的权值和来源(天数),然后按照权值排序后,再用滑动窗口维护一个天数为m的区间即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e6 +9;
int n, m, k, vis[N], x;         
vector<pair<int,int>>a;
void solve(){
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        cin>>k;
        for(int j=0; j<k; j++){
            cin>>x;
            a.emplace_back(x,i);
        }
    }
    sort(a.begin(), a.end());
    int r=0, now=0, ans=INF, len=a.size();
    for(int l=0; l<len; l++){
        while( r<len && now<m ){            //当前衣服的天数不到m
            if(!vis[a[r].second])   now++;  //该件衣服的天数没出现过就记录
            vis[a[r].second]++;             //vis-当前衣服的天数出现的次数
            r++;
        }
        if(now==m) ans=min(ans, a[r-1].first-a[l].first);   //当前维护的区间的最小值
        vis[a[l].second]--;             //l右移的状态改变
        if(!vis[a[l].second]) now--;
    }
    cout<<ans<<endl;
}

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
    solve();
    return 0;
}

K. The Flee Plan of Groundhog

题目大意:

给你n个点和n-1条边,每条边的权值为1,土拨鼠从1开始向着n走t分钟(速度为1 m / s),然后橘子从n开始追土拨鼠(速度为2 m / s ),问最多多长时间橘子才能抓到土拨鼠

思路:

可以以n为根节点,算出到每个点的距离d,并且求出每个点的fa,然后就可以模拟土拨鼠从1到t的位置s,从s开始进行dfs(追击)并且取最大值(d [ i ]/2 向上取整),最后的答案ans还要和d[s]取最小值,因为最大不会超过d[s],这是土拨鼠能跑的最远了,超过的话是在途中被抓到了。

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, t, fa[N], d[N], s, ans;
vector<int> a[N];

void dfs1(int u, int v){
    fa[u]=v;
    for(auto i:a[u])
        if(i!=v)
            d[i]=d[u]+1, dfs1(i,u);
}

void dfs2(int u){
    ans=max(ans, (d[u]+1)/2);
    for(int v:a[u])
        if(v!=fa[u])
            dfs2(v);
}

void solve(){
    cin>>n>>t;
    int u, v;
    for(int i=1; i<n; i++){
        cin>>u>>v;
        a[u].emplace_back(v), a[v].emplace_back(u);
    }
    dfs1(n,0);
    s=1;
    for(int i=1; i<=t; i++) s=fa[s];
    dfs2(s);
    cout<<min(ans,d[s])<<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
    solve();
    return 0;
}

E. Groundhog Chasing Death

思路:

image 16

总的贡献就是:

for(int i=a, j=c; i<=b&&j<=d; ){
        if(ansx<=ansy)  sum+=ansx*(d-j+1), ansx+=xi, i++;
        else            sum+=ansy*(b-i+1), ansy+=yj, j++;
    }

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int mod=998244353;
int a, b, c, d, x, y;
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;
}

inline int Calc(int xi,int yj){     //质因子的贡献计算
    __int128_t sum=0;               //会爆long long,sum为当前质因子的指数和
    int ansx=xi*a, ansy=yj*c;
    for(int i=a, j=c; i<=b&&j<=d; ){
        if(ansx<=ansy)  sum+=ansx*(d-j+1), ansx+=xi, i++;
        else            sum+=ansy*(b-i+1), ansy+=yj, j++;
    }
    return sum%(mod-1);     //费马小定律降幂
}

void solve(){
    cin>>a>>b>>c>>d>>x>>y;
    int sum=1;
    for(int i=2; i*i<=x; i++){          //质因子分解
        if(x%i==0){
            int ansx=0, ansy=0;
            while(x%i==0)    ansx++, x/=i;
            while(y%i==0)    ansy++, y/=i;
            if(ansy)   sum=sum*quick_pow(i, Calc(ansx, ansy))%mod;
        }
    }
    if(x!=1){
        int ansx=1, ansy=0;
        while(y%x==0)    ansy++, y/=x;
        if(ansy)   sum=sum*quick_pow(x,Calc(ansx, ansy))%mod;
    }
    cout<<sum<<endl;
}

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
    solve();
    return 0;
}

平平无奇的在校大学生