天天看点

牛客小白月赛28水题

Powered by:AB_IN 局外人

A 牛牛和牛可乐的赌约

快速幂+逆元。

//C++17
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

using namespace std;

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define rint register int
#define ld long double
#define db double
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define rep1(i,a,n) for (rint i=a;i<n;i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define per1(i,a,n) for (rint i=a;i>n;i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define sd(x) scanf("%d",&(x))
#define slld(x) scanf("%lld",&(x))
#define sdd(x,y) scanf("%d%d",&(x),&(y))
#define sc(s) scanf("%s",(s))
#define pd(x) printf("%d\n",(x))
#define plld(x) printf("%lld\n",(x))
#define pdk(x) printf("%d ",(x))
const int inf=0x3f3f3f3f;

namespace IO{
    char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;
    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);
    inline char gc(){
        if(ip!=ip_)return *ip++;
        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);
        return ip==ip_?EOF:*ip++;
    }
    inline void pc(char c){
        if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;
        *op++=c;
    }
    inline ll read(){
        register ll x=0,ch=gc(),w=1;
        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;
        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;
        return w*x;
    }
    template<class I>
    inline void write(I x){
        if(x<0)pc('-'),x=-x;
        if(x>9)write(x/10);pc(x%10+'0');
    }
    class flusher_{
    public:
        ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}
    }IO_flusher;
}
using namespace IO;
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;
}
const int mod=1e9+7;
int t,n,m;
int main()
{
	t=read();
    while(t--){
        n=read();m=read();
        ll a=qm(n , m ,mod);
        write( (ll) (a-1) * qm(a, mod-2, mod)%mod);
        pc('\n');
    }
	return 0;
}
           

B 牛牛和牛可乐的赌约2

s g sg sg博弈,第一行/列 能除尽 3 3 3的都是牛牛的必败点。其它的点,如果你能从当前点转移到一个必败,那这个点就是必胜。

打表出来总结规律即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll t,x,y;
int main()
{
    cin>>t;
    while(t--){
        int f1=1,f2=1;
        cin>>x>>y;
        if((x%3)^(y%3)) printf("yyds\n");
        else printf("awsl\n");
    }
}
           

或者用大佬的方法,打出 3 × 3 3×3 3×3的表,用这个表解决。

int ans[3][3] = {{1,0,0},{0,1,0},{0,0,1}};
int main() {
    int T = read();
    while(T--) {
        int n = read(),m = read();
        if(ans[n%3][m%3]) printf("awsl\n");
        else printf("yyds\n"); 
    }
}
           

D 位运算之谜

对于二进制的某一位来说, a   x o r   b a \ xor\ b a xor b表示不进位的加法, a   &   b < < 1 a \ \& \ b<<1 a & b<<1可以表示加法的进位。

所以就有了公式 a + b = a   x o r   b + 2 ∗ ( a & b ) a+b=a~xor~b+2*(a\&b) a+b=a xor b+2∗(a&b)

但有两种情况不存在:

  • a   x o r   b < 0 a \ xor\ b \lt 0 a xor b<0
  • ( a   x o r   b ) & ( a & b )   ! = 0 (a \ xor\ b ) \& (a \& b) ~!=0 (a xor b)&(a&b) !=0

    因为异或 是不同得1,所以那一位必然是一个 0 0 0一个 1 1 1, 与 是相同得1,所以那一位必然两个全是 1 1 1。如果有一位这俩都有值,那么是相悖的。

//C++17
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

using namespace std;

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define rint register int
#define ld long double
#define db double
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define rep1(i,a,n) for (rint i=a;i<n;i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define per1(i,a,n) for (rint i=a;i>n;i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define sd(x) scanf("%d",&(x))
#define slld(x) scanf("%lld",&(x))
#define sdd(x,y) scanf("%d%d",&(x),&(y))
#define sc(s) scanf("%s",(s))
#define pd(x) printf("%d\n",(x))
#define plld(x) printf("%lld\n",(x))
#define pdk(x) printf("%d ",(x))
const int inf=0x3f3f3f3f;

namespace IO{
    char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;
    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);
    inline char gc(){
        if(ip!=ip_)return *ip++;
        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);
        return ip==ip_?EOF:*ip++;
    }
    inline void pc(char c){
        if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;
        *op++=c;
    }
    inline ll read(){
        register ll x=0,ch=gc(),w=1;
        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;
        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;
        return w*x;
    }
    template<class I>
    inline void write(I x){
        if(x<0)pc('-'),x=-x;
        if(x>9)write(x/10);pc(x%10+'0');
    }
    class flusher_{
    public:
        ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}
    }IO_flusher;
}
using namespace IO;
ll t,x,y;
int main()
{
	t=read();
    while(t--){
        x=read();y=read();
        ll c=x-2*y;
        if(c<0 || c&y) puts("-1");
        else printf("%lld\n",c);
    }
	return 0;
}
           

H 上学要迟到了

最短路的板子题。

建图方法用的链式前向星,输入车站能停什么车时,用了链表的思维, p r e pre pre数组就是代表,目前最后这个车可以停在哪个站。将老的能停什么车作为下标,几站作为值,每次更新即可。最后再从 1 1 1到 n n n,建走路的双向边。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rint register int
#define ld long double
#define db double
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define rep1(i, a, n) for (rint i = a; i < n; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define per1(i ,a, n) for (rint i = a; i > n; i--)
namespace IO{
    char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;
    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);
    inline char gc(){
        if(ip!=ip_)return *ip++;
        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);
        return ip==ip_?EOF:*ip++;
    }
    inline void pc(char c){
        if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;
        *op++=c;
    }
    inline int read(){
        register int x=0,ch=gc(),w=1;
        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;
        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;
        return w*x;
    }
    template<class I>
    inline void write(I x){
        if(x<0)pc('-'),x=-x;
        if(x>9)write(x/10);pc(x%10+'0');
    }
    class flusher_{
    public:
        ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}
    }IO_flusher;
}
using namespace IO;


const int N=1e7+10;
const int inf=0x3f3f3f3f;
struct sa{
    int dis;
    int pos;
};
bool operator <(const sa &a,const sa &b) { return a.dis>b.dis; }

priority_queue<sa>q;


struct Edge
{
    int u, v, w, next;
}edge[N<<2];
int head[N];
int cnt;
void add_edge(int u, int v, int w)
{
    edge[cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}


int dis[N],a[N],b[N],pre[N];
bool vis[N];
int n,m,s,t,u,v,w,T;

void dij(int s,int v,int d[]){
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;i++) d[i] = inf;
    d[s]=v;
    q.push( (sa) {v,s});
	while(!q.empty())
	{
		sa ns=q.top();
		q.pop();
		int x=ns.pos;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x]; i!=-1 ; i=edge[i].next)
		{
			int to=edge[i].v;
			int dd=d[x]+edge[i].w;
			if(d[to]>dd)
			{
				d[to]=dd;
				q.push( (sa) {d[to],to});
			}
		}
	}
}
int main()
{
    memset(head,-1,sizeof(head));
	n=read();m=read();s=read();t=read();T=read();
    rep(i, 1, m) a[i]=read();
    rep(i, 1, n){
        b[i]=read();
        if(pre[b[i]]) add_edge(pre[b[i]],i,a[b[i]]);
        pre[b[i]]=i;
    }
    rep1(i, 1, n){
        add_edge(i,i+1,T);
        add_edge(i+1,i,T);
    }
    dij(s,0,dis);
    write(dis[t]);
	return 0;
}
           

J 树上行走

并查集,将 1   1 1~1 1 1连边的点连起来,将 0   0 0~0 0 0连边的点连起来,写一个循环让它们的根 + + ++ ++,再通过这个根的最大值,找它的子节点。

用的出题人大佬的板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;

int fa[maxn],sz[maxn],col[maxn];
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",col+i);
        fa[i]=i;
    }
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(col[u]==col[v])fa[find(u)]=find(v);
    }
    set<int> ans;
    int mx=0;
    for(int i=1;i<=n;i++){
        sz[find(i)]++;
        mx=max(mx,sz[find(i)]);
    }
    for(int i=1;i<=n;i++)
        if(sz[find(i)]==mx)ans.insert(i);
    printf("%d\n",ans.size());
    for(auto i:ans)printf("%d ",i);
    return 0;
}
           

完结。

继续阅读