2018-team7-T05
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
* [wiki:Summer2018Team 返回上层]
* [wiki:2018-team7 队伍主页]
* [wiki:2018-team7-T04 上场比赛]
* [wiki:2018-team7-T06 下场比赛]
== 流水账 ==
比赛链接：https://vjudge.net/contest/261865
[[Image(submit05.png,500px)]]
[[Image(T05.png,800px)]]
A water '''A1Y5'''[[br]]
B water '''B1Y12'''[[br]]
C matrix quickpow '''C1Y49'''[[br]]
E bruteforce '''E2Y101'''[[br]]
G calculate too long '''G1Y258'''[[br]]
H ACAM+probability dp+gauss but...............[[br]]
I tree-dp+k optimized but......[[br]]
== 总结 ==
basic skill disadvantage
=== IDrandom(yrb) ===
water
=== CtrlCV(wsh) ===
nothing to tell
=== godspeedcurry(zzh) ===
damn it today !
solve the problem G for almost 2 hours wrong formula!!!
happy today
solve the problems anyway
== 题解 ==
A:water(yrb)
B:water(yrb)
C:water(yrb)
D:
E:DFS+cut(wsh)
F:
G:calc
H:ACAM+pdp+gauss
I:treedp+skew optimized
J:
K:
L:
M:
== 补题 ==
|| Contest Name || A || B || C || D || E || F || G || H || I || J || K || L || M ||
||2016 - ICPC - Asia - Shenyang - Regional || O || O || O || - || O || - || O || * || * || - || - || - || - ||
O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的 -:赛后待补 *:真-赛后待补
* [wiki:Summer2018Team 返回上层]
* [wiki:2018-team7 队伍主页]
* [wiki:2018-team7-T04 上场比赛]
* [wiki:2018-team7-T06 下场比赛]
AB比较水打印输出题
'''E'''
暴力剪枝
{{{
#!C
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 2147493647ll;
#define pb push_back
vector<int>G[111];
bool E[111][111];
void init(){
memset(E,false,sizeof E);
for(int i=1;i<=102;++i) G[i].clear();
}
ll ans;int n,m,s;
int st[12];
void dfs(int step,int x){
if(step==s){
++ans;
return;
}
if(step+n-x+1<s) return;
for(int i=0;i<G[x].size();++i){
int to = G[x][i];
bool flag=false;
for(int j=1;j<=step;++j){
if(!E[st[j]][to]){
flag=1;
break;
}
}
if(!flag){
st[step+1]=to;
dfs(step+1,to);
}
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;++i){
int u,v;
scanf("%d%d",&u,&v);
G[u].pb(v);
E[u][v]=1;
E[v][u]=1;
}
ans=0;
for(int i=1;i<=n;++i){
st[1]=i;
dfs(1,i);
}
printf("%lld\n",ans);
}
return 0;
}
}}}流水账
比赛链接：https://vjudge.net/contest/261865
A water A1Y5[[br]]
B water B1Y12[[br]]
C matrix quickpow C1Y49[[br]]
E bruteforce E2Y101[[br]]
G calculate too long G1Y258[[br]]
H ACAM+probability dp+gauss but...............[[br]]
I tree-dp+k optimized but......[[br]]
总结
basic skill disadvantage
IDrandom(yrb)
water
CtrlCV(wsh)
nothing to tell
godspeedcurry(zzh)
damn it today !
solve the problem G for almost 2 hours wrong formula!!!
happy today
solve the problems anyway
题解
A:water(yrb)
B:water(yrb)
C:water(yrb)
D:
E:DFS+cut(wsh)
F:
G:calc
H:ACAM+pdp+gauss
I:treedp+skew optimized
J:
K:
L:
M:
补题
| Contest Name | A | B | C | D | E | F | G | H | I | J | K | L | M |
| 2016 - ICPC - Asia - Shenyang - Regional | O | O | O | - | O | - | O | * | * | - | - | - | - |
O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的 -:赛后待补 *:真-赛后待补
AB比较水打印输出题
E
暴力剪枝
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 2147493647ll;
#define pb push_back
vector<int>G[111];
bool E[111][111];
void init(){
memset(E,false,sizeof E);
for(int i=1;i<=102;++i) G[i].clear();
}
ll ans;int n,m,s;
int st[12];
void dfs(int step,int x){
if(step==s){
++ans;
return;
}
if(step+n-x+1<s) return;
for(int i=0;i<G[x].size();++i){
int to = G[x][i];
bool flag=false;
for(int j=1;j<=step;++j){
if(!E[st[j]][to]){
flag=1;
break;
}
}
if(!flag){
st[step+1]=to;
dfs(step+1,to);
}
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;++i){
int u,v;
scanf("%d%d",&u,&v);
G[u].pb(v);
E[u][v]=1;
E[v][u]=1;
}
ans=0;
for(int i=1;i<=n;++i){
st[1]=i;
dfs(1,i);
}
printf("%lld\n",ans);
}
return 0;
}