提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

2020-10-2 大二2020下训练三

训练 10 2020
2023-09-27 14:27:32 时间

Powered by:AB_IN 局外人

A 宋哥爬树

一开始wa了4发，就是因为好多有个地方没想到。

分三种情况

  • 当 z ≤ x z \le x z≤x时，一步就可以到达目的地。
  • 当 x ≤ y x \le y x≤y时，不管怎样也到不了终点。（终点最小是 1 1 1）
  • 其次，就是算 t m p = z − x x − y tmp=\frac {z-x} {x-y} tmp=x−yz−x​。 t m p tmp tmp要先变成不小于它的最大整数（因为小数可能是没走全的）。此时 t m p tmp tmp变成了在终点前小于 x x x的点，故最后加1即可。
    在这里插入图片描述
#include <bits/stdc++.h>
using namespace std;
int t,x,y,z,ans;
double tmp;
int main()
{
    ios::sync_with_stdio(0);
    cin>>t;
    for(int k=1;k<=t;k++){
        cin>>x>>y>>z;
        if(z<=x) printf("Case #%d: 1\n",k);
        else if(x<=y) printf("Case #%d: QAQ\n",k);
        else{
            tmp=(z-x)*pow((x-y),-1);
            ans=ceil(tmp)+1;
            printf("Case #%d: %d\n",k,ans);
        }
    }
    return 0;
}

B 宋哥看星星

生成 k k k个最小生成树。
（没想到一开始 n = k n=k n=k的情况）
这样写更方便，不用开始和结尾都判断一下 n n n与 k k k的关系。每有一条边生成， k k k就自增， k k k最后要是和 n n n相等了，说明成了。

#include <bits/stdc++.h>
#define ll long long
#define rep(i,x,y) for (ll i=(x);i<=(y);i++)
using namespace std;
const ll maxn=1e6+10;
ll n,m,u,v,w,ans,k;

ll fa[maxn];

struct sa{
    ll u,v,w;
}e[maxn];

bool cmp(struct sa x,struct sa y){
    return x.w<y.w;
}

ll find(ll x) {
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
int t;
int main()
{
    cin>>t;
    for(int j=1;j<=t;j++){
        ans=0;
        memset(e,0,sizeof(e));
        cin>>n>>m>>k;
        rep(i,1,m) cin>>e[i].u>>e[i].v>>e[i].w;
        sort(e+1,e+1+m,cmp);
        rep(i,1,n) fa[i]=i;
        for(int i=1;i<=m&&k!=n;i++){
            w=e[i].w; u=find(e[i].u);v=find(e[i].v);
            if(u!=v){
                fa[u]=v;
                ans+=w;
                k++;
            }
        }
        if(k==n)  printf("Case #%d: %lld\n",j,ans);
        else printf("Case #%d: QAQ\n",j);
    }
    return 0;
}

C 破解棋局

博弈论。
当 n ≠ m ≠ 1 n\neq m\neq1 n​=m​=1时， A l i c e Alice Alice先手拿(2,2),那么就只会剩下两个边界了，分别是（1,1）到（1，n) 和(1,1)到（n，1）。之后不管 B o b Bob Bob怎么拿， A l i c e Alice Alice只要拿和他拿的对称的点即可，这样 B o b Bob Bob必输。

#include <bits/stdc++.h>

using namespace std;
int x,y,c;
int main()
{
    while(~scanf("%d%d",&x,&y)){
       if(x==1&&y==1){
            printf("Bob\n");
       }
       else printf("Alice\n");
    }
}

D 军哥排队

奇偶分情况模拟即可。

#include <bits/stdc++.h>
#define ll long long
const ll mod=1e9+7;
using namespace std;
ll a[10010];
ll t,n,x;
ll qm (ll a, ll b ,ll c){
    ll ret=1%c;
    while(b){
        if(b&1)
            ret=ret*a%c;
        a=a*a%c;
        b=b>>1;
    }
    return ret;
}
int main()
{
    cin>>t;
    for(int j=1;j<=t;j++){
        int f=0;
        cin>>n;
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++){
            cin>>x;
            a[x]++;
        }
        if(n&1){
            if(a[0]!=1){
                f=1;
            }
            for(int i=2;i<=n-1;i+=2){
                if(a[i]!=2){
                    f=1;
                    break;
                }
            }
            if(f) cout<<"0"<<endl;
            else cout<<qm(2,(n-1)/2,mod)<<endl;
        }
        else{
            for(int i=1;i<=n-1;i+=2){
                if(a[i]!=2){
                    f=1;
                    break;
                }
            }
            if(f) cout<<"0"<<endl;
            else cout<<qm(2,(n)/2,mod)<<endl;
        }
    }
    return 0;
}

完结。

相关文章