2020牛客暑期多校训练营(第十场)A、E、D

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


A. Permutation

题目大意:

思路:

AC Code:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e6 +9;
int p;
int a[N], cnt, vis[N], res;
void solve(){
    cnt=0;
    cin>>p;
    memset(vis, 0, sizeof(vis));
    a[++cnt]=vis[1]=res=1;
    for(int i=2; i<p; i++){
        if(vis[(res*2)%p])  res*=3;
        else              res*=2;
        res%=p;
        if(vis[res])    {cout<<"-1"<<endl; return ;}
        a[++cnt]=res;
        vis[res]=1;
    }
    for(int i=1; i<=cnt; 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;
}

E. Game

题目大意:

思路:

因为是向左推,所以很明显的最终高度是从左边往右边递减,而右边比左边高的地方是可以推过去的,类似于液体的流动???,然后就记录前缀和,求每个位置的平均值并且取最大就行了。

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e5 +9;
int n, a[N];
int sum, ans;
void solve(){
    cin>>n;
    sum=ans=0;
    int step;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        sum+=a[i];
        step=(sum+i-1)/i;
        ans=max(ans, step);
    }
    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;
}

D Hearthstone Battlegrounds

题目大意:

鱼人有四种,分别是:
t1:剧毒,圣盾,亡语。
t2:剧毒,圣盾。
t3:剧毒,亡语。
t4:剧毒。
(玩过炉石的一眼就懂了)剧毒是能秒杀对方,圣盾无视一次攻击,亡语在死亡时触发,召唤一个1-1的藤蔓
然后给你两个阵容a和b,分别是a的四种鱼人的数量和b的四种鱼人的数量
问你a有没有可能赢

思路:

终于来到了炉石战旗
需要注意到人鱼都是1 − 10 9(鱼人的身材tql)藤蔓都是1 − 1 ,而且藤蔓不超过5 ∗ 106
,所以全部的藤蔓也打不死一个鱼人,所以藤蔓的作用肯定是破圣盾,所以说
1、a的藤蔓应该尽可能的破b的圣盾。
2、b的藤蔓应该尽可能的被a的无圣盾鱼人打掉

同时需要注意到t1攻击后变成t3,而且t2攻击后变成t4

然后就是双方每种鱼人的出战顺序了
1、对于a来说,因为想要制作能破掉对面圣盾的藤蔓,所以应该先派出t3去触发亡语
然后就是派出圣盾去打对面的鱼人,派出t1更优(可以变成t3下次拉藤蔓)
然后再派出圣盾的t2,t4都可以(直接肉搏鱼人,所以都可以)
出战顺序就是t 3 − t 1 − t 2 − t 4

2、对于b来说,优先鱼人换鱼人,圣盾留给藤蔓,也就是t3,t4,然后圣盾会尽可能的被破掉,还有剩下的话也就只能派出去了,就是t1,t2
出战顺序就是t 3 − t 4 t 1 − t 2

最后判断谁还有剩下的鱼人,都没了的话就比谁剩下的藤蔓多

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
int a[9], b[9];

void defend(){      //b的出战
    if(b[3])        b[3]--, b[5]++;
    else if(b[4])   b[4]--;
    else if(b[1])   b[1]--, b[3]++;
    else if(b[2])   b[2]--, b[4]++;
}

void attack(){      //a的出战
    if(a[3])        a[3]--, a[5]++;
    else if(a[1])   a[1]--, a[3]++;
    else if(a[2])   a[2]--, a[4]++;
    else if(a[4])   a[4]--;
    defend();
}

void solve(){
    for(int i=1; i<=4; i++) cin>>a[i];
    for(int i=1; i<=4; i++) cin>>b[i];
    a[5]=b[5]=0;
    while((a[1]+a[2]+a[3]+a[4]) && (b[1]+b[2]+b[3]+b[4])){  //有一方没鱼人了就停止
        if(a[3]+a[4])   b[5]=0;             //a有无圣盾的并且b有藤蔓,就先打掉藤蔓
        if(a[5] && b[1]+b[2]){              //a有藤蔓,b有圣盾鱼人,就破b的圣盾
            if(b[1]) b[1]--, b[3]++, a[5]--;
            else     b[2]--, b[4]++, a[5]--;
        }
        attack();  
    }
    if(b[1]+b[2]+b[3]+b[4]) cout<<"No"<<endl;
    else if(!(a[1]+a[2]+a[3]+a[4]) &&(a[5]<=b[5]))     cout<<"No"<<endl;
    else    cout<<"Yes"<<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;
}

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