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;
}
完结。
![2021牛客暑期多校训练营2.I Penguins BFS广搜 简单2021牛客暑期多校训练营2.I Penguins BFS广搜 简单[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)