- 1mujoco环境安装问题_mujoco安装
- 2大一学生数据结构与算法的先后取舍_acm先学数据结构还是算法
- 3深度学习论文阅读路线图
- 4# hadoop入门第六篇-Hive实例_describle table语句
- 5Flink（四） 状态管理 1_flink 状态管理
- 6从零开始开发微信小程序：全面指南_微信小程序开发指南
- 7一篇文章玩转GDB/LLDB调试Redis源码_lldb 调试 redis
- 8(四)快速图像风格迁移训练模型载入及处理图像_快速风格迁移模型训练
- 9【2024版】超详细Python+Pycharm安装保姆级教程，Python+Pycharm环境配置和使用指南，看完这一篇就够了_安装python和pycharm
- 10大模型越狱攻击框架：集成11种方法，揭示大模型参数量和安全性的新规律
2023牛客暑期多校简单题解 3_2023暑假牛客多校3
赞
踩
A.World Fragments
题意：没看懂，硬猜，特判瞎搞一下
#include<bits/stdc++.h> #include<string> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #define fi first #define se second #define ll long long #define ull unsigned long long using namespace std; const int N=0; const ll md=1e9+7; const ll inf=1e18; const ll eps=1e-9; const double E=2.718281828; string sx,sy; ll x=0,y=0; void solve(){ //fucking and strange cin>>sx>>sy; // cout<<sx<<" "<<sy<<endl; reverse(sx.begin(),sx.end()); reverse(sy.begin(),sy.end()); for(int i=0;i<sx.length();i++){ if(sx[i]=='1'){ x+=(1ll<<i); } } for(int i=0;i<sy.length();i++){ if(sy[i]=='1'){ y+=(1ll<<i); } } cout<<abs(x-y)<<endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--){ solve(); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
B.Auspiciousness
题意：一共有
2
n
2n
2n张牌，每张牌有一个值，这些牌的值形成一个排列。按照如下步骤抽牌，
1.抽一张牌
2.如果牌堆空了，那么结束抽牌。否则，则猜测最上面的牌是否大于或小于最后抽到的牌，并抽最上面的牌，如果猜测正确继续步骤2，否则结束。
现有一策略，如果抽到的最后一张牌小于或等于
n
n
n,那么则猜测最上面的牌大于最后抽到的牌。如果抽到的最后一张牌大于
n
n
n,那么则猜测最上面的牌小于最后抽到的牌。问在这个策略下，对于不同的牌组，可以抽到多少数量的牌。（数值会很大对固定值取模）
思路：设
f
(
i
,
x
,
y
,
k
)
f(i,x,y,k)
f(i,x,y,k) 为 第
x
+
y
+
1
x+y+1
x+y+1次抽牌后往大猜或者往小猜
(
i
=
0
/
1
)
(i=0/1)
(i=0/1),取
x
/
y
x/y
x/y的前
k
k
k小的值的方案数，
x
x
x为
[
1
,
n
]
[1,n]
[1,n]之间数的数量，
y
y
y为
[
n
+
1
,
2
n
]
[n+1,2n]
[n+1,2n]之间的数量。题目要求的是抽出牌的数量，那么每个方案在当前位置对抽牌的贡献是
(
x
+
y
−
1
)
!
(x+y-1)!
(x+y−1)!。（当前已经确定的乘上没有确定的数量阶乘）
然后考虑转移：
如果当前抽的牌是
[
1
,
n
]
[1,n]
[1,n]区间内我们取枚举当前值的次序
k
∈
[
1
,
x
]
k \in[1,x]
k∈[1,x]，
如果上一次的抽的牌在
[
1
,
n
]
[1,n]
[1,n]之间，那么可以转移的次序为
[
k
+
1
,
x
+
1
]
[k+1,x+1]
[k+1,x+1]
f
(
0
,
x
,
y
,
k
)
+
=
f
(
0
,
x
+
1
,
y
,
x
+
1
)
−
f
(
0
,
x
+
1
,
y
,
k
)
f(0,x,y,k)+=f(0,x+1,y,x+1)-f(0,x+1,y,k)
f(0,x,y,k)+=f(0,x+1,y,x+1)−f(0,x+1,y,k)
如果上一次抽的牌在
[
n
+
1
,
2
n
]
[n+1,2n]
[n+1,2n],那么可以转移的次序为
[
1
,
y
+
1
]
[1,y+1]
[1,y+1]
f
(
0
,
x
,
y
,
k
)
+
=
f
(
1
,
x
,
y
+
1
,
y
+
1
)
f(0,x,y,k)+=f(1,x,y+1,y+1)
f(0,x,y,k)+=f(1,x,y+1,y+1)
如果当前抽的牌是 [ n + 1 , 2 n ] [n+1,2n] [n+1,2n]区间内我们取枚举当前值的次序 k ∈ [ 1 , y ] k \in[1,y] k∈[1,y]，
如果上一次的抽的牌在
[
1
,
n
]
[1,n]
[1,n]之间，那么可以转移的次序为
[
1
,
x
+
1
]
[1,x+1]
[1,x+1]
f
(
1
,
x
,
y
,
k
)
+
=
f
(
0
,
x
+
1
,
y
,
x
+
1
)
f(1,x,y,k)+=f(0,x+1,y,x+1)
f(1,x,y,k)+=f(0,x+1,y,x+1)
如果上一次抽的牌在
[
n
+
1
,
2
n
]
[n+1,2n]
[n+1,2n],那么可以转移的次序为
[
k
+
1
,
y
+
1
]
[k+1,y+1]
[k+1,y+1]
f
(
0
,
x
,
y
,
k
)
+
=
f
(
1
,
x
,
y
+
1
,
y
+
1
)
−
f
(
1
,
x
,
y
+
1
,
k
)
f(0,x,y,k)+=f(1,x,y+1,y+1)-f(1,x,y+1,k)
f(0,x,y,k)+=f(1,x,y+1,y+1)−f(1,x,y+1,k)
每次找到一类去就去维护答案，维护前缀和用于下次转移，用滚动数组优化空间。（没想出来，看的题解觉得很妙，但是上面自己写的一坨…答辩）。
唯一可以清楚知道的是，在最后因为我们计算的只是合法转移下的抽出的牌的数量，对于无法全部抽完的牌型来说，是可以在抽出一张不合法的牌加入答案，所以对于无法抽完的牌组累加答案。
//It's better to have sex than to do questions #include<bits/stdc++.h> #include<string> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #define fi first #define se second #define ll long long #define ull unsigned long long using namespace std; const int N=605; //const ll md=1e9+7; const ll inf=1e18; const ll eps=1e-9; const double E=2.718281828; ll f[2][2][N][N],n,md,inc[N],C[N][N]; void solve(){ cin>>n>>md; inc[0]=1; for(int i=1;i<=2*n;i++){ inc[i]=inc[i-1]*i%md; } C[0][0]=1; for(int i=1;i<=n*2;i++){ C[i][0]=1; for(int j=1;j<=i;j++){ C[i][j]=(C[i-1][j-1]+C[i-1][j])%md; } } // 0 1 代替 for(int i=0;i<2;i++){ for(int j=0;j<=n;j++){ for(int k=0;k<=n;k++){ f[0][i][j][k]=f[1][i][j][k]=0; } } } ll ans=inc[2*n]; for(int i=1;i<=n;i++){ f[0][n%2][n][i]=i%md; f[1][n%2][n][i]=i%md; } for(int x=n;x>=0;x--){ for(int y=n;y>=0;y--){ if(x+y==2*n){ continue; } for(int k=1;k<=max(y,x);k++){ f[0][x%2][y][k]=f[1][x%2][y][k]=0; } for(int k=1;k<=x;k++){//当前取[1,n] if(x!=n){ f[0][x%2][y][k]+=(f[0][(x+1)%2][y][x+1]-f[0][(x+1)%2][y][k]+md)%md; f[0][x%2][y][k]%=md; } if(y!=n){ f[0][x%2][y][k]+=f[1][x%2][y+1][y+1]; f[0][x%2][y][k]%=md; } ans+=f[0][x%2][y][k]*inc[x+y-1]%md; ans%=md; } for(int k=1;k<=x;k++){ f[0][x%2][y][k]+=f[0][x%2][y][k-1]; f[0][x%2][y][k]%=md; } for(int k=1;k<=y;k++){// [n+1,2*n] if(x!=n){ f[1][x%2][y][k]+=f[0][(x+1)%2][y][x+1]; f[1][x%2][y][k]%=md; } if(y!=n){ f[1][x%2][y][k]+=(f[1][x%2][y+1][y+1]-f[1][x%2][y+1][k]+md)%md; f[1][x%2][y][x]%=md; } ans+=f[1][x%2][y][k]*inc[x+y-1]%md; ans%=md; } for(int k=1;k<=y;k++){ f[1][x%2][y][k]+=f[1][x%2][y][k-1]; f[1][x%2][y][k]%=md; } } } ans+=(inc[2*n]-(f[1][0][1][1]+f[0][1][0][1])%md+md)%md;//除了可以全部去完的牌型 ，所有牌形的贡献都可以+1 ans%=md; cout<<ans<<endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
J.Fine Logic
题意：给定n个实体和m个关系，构造数量最少的排名，每个关系都要被满足。
思路：直接抽象成有向图，然后再图上疯狂找环，花了两个小时发现无法找到所有的环。
换个思路可以发现，两个排名，一个升序，一个降序，就可以包括所有关系。那么什么样的图可以只用一个排名表示所有的关系，通过上面有小丑再疯狂找环可以知道如果图内包含环必然无法由一个排名包含所有关系。所以只要去判环就可以了。通过拓扑排序可以判断是否有环，顺带处理出拓扑序。就是要求的答案。
#include<bits/stdc++.h> #include<string> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #define fi first #define se second #define ll long long #define ull unsigned long long using namespace std; const int N=1e6+5; const ll md=1e9+7; const ll inf=1e18; const ll eps=1e-9; const double E=2.718281828; int hd[N],cnte=0,n,m,vis[N],in[N],out[N]; int a[N]; struct aa{ int v,nt; }e[N]; void add(int v,int u){ e[++cnte].v=u; e[cnte].nt=hd[v]; hd[v]=cnte; } int fa[N],dfn[N],ts=0; bool toposort(int n){ int cnt=0; queue<int>q; for(int i=1;i<=n;i++){ if(in[i]==0){ q.push(i); } } while(!q.empty()){ int now=q.front(); q.pop(); a[++cnt]=now; for(int i=hd[now];i;i=e[i].nt){ int v=e[i].v; in[v]--; if(in[v]==0){ q.push(v); } } } return cnt==n; } void solve(){ //fucking and strange cin>>n>>m; for(int u,v,i=1;i<=m;i++){ cin>>u>>v; add(u,v); out[u]++; in[v]++; } if(toposort(n)){ cout<<1<<endl; for(int i=1;i<=n;i++){ cout<<a[i]<<" "; } cout<<endl; }else{ cout<<2<<endl; for(int i=1;i<=n;i++){ cout<<i<<" "; } cout<<endl; for(int i=n;i>=1;i--){ cout<<i<<" "; } cout<<endl; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--){ solve(); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
E.Until the Blue Moon Rises
题意：给定一张图，问用题中的随机DFS代码处理出的每个点到顶点的最短距离是否正确。
思路：BFS再图中建出树，枚举每一个顶点
u
u
u及其链接的点
v
v
v,
如果
u
u
u与
v
v
v属于同一层那么不会是正确的，因为当走到
u
u
u时有可能直接到
v
v
v使得
v
v
v错误。
如果
v
v
v再
u
u
u的上层且最近公共祖先不是
v
v
v，那么也是错的。
兴奋的交一发，喜提 wong answer。
仔细想想，给的图形成一颗树，那么无论怎样答案都是对的。一个点
v
v
v指向的在BFS树中深度小于它的点
u
u
u,如果走到
v
v
v一定经过了
u
u
u，无影响。如果没有则不正确。
原来这叫支配关系，去网上拉下板子瞎改改。
//It's better to have sex than to do questions #include<bits/stdc++.h> #include<string> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #define fi first #define se second #define ll long long #define ull unsigned long long using namespace std; const int N=5e5+5; const ll md=1e9+7; const ll inf=1e18; const ll eps=1e-9; const double E=2.718281828; struct graph{ int cnte,hd[N],in[N]; struct edge{ int v,nt; }e[N<<1]; void addedge(int v,int u){ e[++cnte].v=u; e[cnte].nt=hd[v]; hd[v]=cnte; in[u]++; } }; graph g,gf,dfstree,dfstreef; int n,m,dfn[N],id[N],tim,fa[N]; void dfs(int x){ id[++tim]=x; dfn[x]=tim; for(int i=g.hd[x];i;i=g.e[i].nt){ int v=g.e[i].v; if(!dfn[v]){ fa[v]=x; dfstree.addedge(x,v); dfs(v); } } } int sdom[N]; //半支配点 int mn[N]; // 在dfs树上sdom 最小的祖先 int anc[N]; //祖先 int find(int x){//带权并查集 if(x!=anc[x]){ int t=anc[x]; anc[x]=find(anc[x]); if(dfn[sdom[mn[x]]]>dfn[sdom[mn[t]]]){ mn[x]=mn[t]; } } return anc[x]; } void lengauertarjan(){ for(int i=1;i<=n;i++){ anc[i]=i; sdom[i]=i; mn[i]=i; } for(int j=n;j>=2;j--){ int x=id[j]; if(!x){ continue; } int pos=j; for(int i=gf.hd[x];i;i=gf.e[i].nt){ int y=gf.e[i].v; if(!dfn[y]){ continue; } if(dfn[y]<dfn[x]){ pos=min(pos,dfn[y]); }else{ find(y); pos=min(pos,dfn[sdom[mn[y]]]); } } sdom[x]=id[pos]; anc[x]=fa[x]; dfstree.addedge(sdom[x],x); } } int f[N][25],dep[N];//维护的是支配树 int getlca(int x, int y) { //获取LCA if (dep[x] < dep[y]) swap(x, y); for(int i=20;i>=0;i--){ if(dep[f[x][i]]>=dep[y]){ x=f[x][i]; } } if (x == y) return x; for (int i = 20; i >= 0; i--) { if (f[x][i] != f[y][i]) { x = f[x][i]; y = f[y][i]; } } return f[x][0]; } void builddominate(int x){ int to=dfstreef.e[dfstreef.hd[x]].v; for(int i=dfstreef.hd[x];i;i=dfstreef.e[i].nt){ int y=dfstreef.e[i].v; to=getlca(to,y); } dep[x]=dep[to]+1; f[x][0]=to; // dominate.addedge(to,x); for(int i=1;i<=20;i++){ f[x][i]=f[f[x][i-1]][i-1]; } } void topsort(){ for(int i=1;i<=n;i++){ for(int j=dfstree.hd[i];j;j=dfstree.e[j].nt){ int v=dfstree.e[j].v; dfstreef.addedge(v,i); } } for(int i=1;i<=n;i++){ if(!dfstree.in[i]){ dfstree.addedge(0,i); dfstree.in[i]--; dfstreef.addedge(i,0); } } queue<int>q; q.push(0); while(!q.empty()){ int x=q.front(); q.pop(); // cout<<"topo "<<x<<endl; for(int i=dfstree.hd[x];i;i=dfstree.e[i].nt){ int y=dfstree.e[i].v; if((--dfstree.in[y])<=0){ q.push(y); builddominate(y); } } } } int dis[N]; void init(){ g.cnte=gf.cnte=dfstree.cnte=dfstreef.cnte=0; for(int i=0;i<=n;i++){ fa[i]=g.hd[i]=gf.hd[i]=dfstree.hd[i]=dfstreef.hd[i]=0; dfn[i]=0; dis[i]=md; dfstree.in[i]=g.in[i]=gf.in[i]=dfstreef.in[i]=0; for(int j=0;j<=20;j++){ f[i][j]=0; } } tim=0; } void solve(){ cin>>n>>m; init(); for(int u,v,i=1;i<=m;i++){ cin>>v>>u; g.addedge(v,u); gf.addedge(u,v); } dfs(1); lengauertarjan(); topsort(); bool flag=1; dis[1]=0; queue<int>q; q.push(1); while(!q.empty()){ int x=q.front(); q.pop(); for(int j=g.hd[x];j;j=g.e[j].nt){ int v=g.e[j].v; if(dis[v]==md){ q.push(v); dis[v]=dis[x]+1; }else if(dis[v]!=dis[x]+1){ if(getlca(v,x)!=v){ flag=0; } } } } if(flag){ cout<<"YES"<<"\n"; }else{ cout<<"NO"<<"\n"; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
D.Ama no Jaku
题意：给定个01矩阵，每个可以将一列或者一行取反，求能否使矩阵全部变成一样。如果能输出最小步数，不能输出-1。
思路：取反的操作就很明显了，某一行或者某一列要么操作要么不操作。那么无论是全部变成0，还是全部变成1，如果可以变成一样那么其步数是定的，取min即可。对于所有行，那些列被操作过是一样的，也就是所有行要么一样那么每一个相反，相反的行对于行进行一次取反。
//It's better to have sex than to do questions #include<bits/stdc++.h> #include<string> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #define fi first #define se second #define ll long long #define ull unsigned long long using namespace std; const int N=2005; const ll md=1e9+7; const ll inf=1e18; const double eps=1e-9; const double E=2.718281828; int n; string a[N]; void solve(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } int all1=0,all0=0; for(int i=0;i<n;i++){ if(a[0][i]=='1'){ all0++; }else{ all1++; } } int same=0,oppo=0; bool f=1; for(int i=0;i<n;i++){ bool f1=1,f2=1; for(int j=0;j<n;j++){ if(a[i][j]!=a[0][j]){ f1=0; } } for(int j=0;j<n;j++){ if(a[i][j]==a[0][j]){ f2=0; } } if(!f1&&!f2){ f=0; }else if(f1){ same++; }else if(f2){ oppo++; } } if(!f){ cout<<-1<<endl; return ; } int ans=min(all1,all0)+min(oppo,same); cout<<ans<<endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--){ solve(); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
