JSOI2019 神經網路

2022-09-23 08:07:05 字數 2104 閱讀 5364

考慮一個合法的哈密頓路可以表示為什麼樣子:

按照不同樹的編號,分割為一段段,相鄰兩段屬於不同樹

同時,如果最後一段和第一段同編號,將最後一段移動到第一段前面

由此,一個哈密頓路可以由唯一表示:

1號點在第一個段中,此後每一段和上一個屬於不同樹,且最後一段不屬於1樹

由此,問題分解為兩部分:

考慮樹形\(dp\)求解,每個點記錄\(dp_\)表示當前\(i\)子樹內已經產生\(j\)條路徑,\(i\)自己是否可以向父親連邊

容易用類似樹形揹包的方式合併,每次決策兒子是否連線到自己上面

注意:一個長度\(>1\)的段,需要考慮正反方向的排放

複雜度為\(o(\sum k_i^2)\)

\[\

\]相鄰兩段不同色,考慮容斥求解

列舉這棵樹中的\(i\)個段自己生成了\(j\)個不合法的相鄰,\(i\)個段合併生成\(i-j\)個段,且乘上容斥係數\((-1)^j\)

\(i\)個並掉\(j\)個,方案數計算如下:

先把\(i\)個排好,乘上\(i!\),然後選擇\(j\)個間隔合併掉\(\binom\),然後對於剩下的\(i-j\)個元素無序,需要除掉\((i-j)!\)

揹包合併容斥之後的結果,對於當前的\(i\)個元素,任意排列即可

然而上面是理想情況,還需要考慮\(1\)號元素不能被排列,要強制最後一個段不是1樹的段

這一部分,在樹1的容斥以及最終揹包合併時特殊處理即可,即少排列一個元素,且最後合併時先選一個放在最後面

#includeusing namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef double db;

typedef pair pii;

#define reg register

#define mp make_pair

#define pb push_back

#define mod1(x) ((x>=p)&&(x-=p))

#define mod2(x) ((x<0)&&(x+=p))

#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)

#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

template inline void cmin(t &a,t b)

template inline void cmax(t &a,t b)

const int n=5e3+10,p=998244353;

int n,m;

int i[n],j[n],c[n][n];

ll qpow(ll x,ll k=p-2)

struct edge e[n<<1];

int head[n],ecnt;

void addedge(int u,int v);

head[u]=ecnt;

}int dp[n][n][2]; // 0,1 是否向上連

int g[n][3],h[n][3],sz[n];

void dfs(int u,int f)

g[0][0]=1,g[0][1]=g[0][2]=0;

for(int i=head[u];i;i=e[i].nxt)

rep(i,0,sz[u]+1) dp[u][i][0]=dp[u][i][1]=0;

rep(i,0,sz[u])

sz[u]++;

}int f[n],t[n];

void get()

dfs(1,0);

rep(i,1,n) }}

int s[n],c;

int main()

c+=n;

} get();

rep(i,1,n)

int ans=0;

// 不允許改變第一段的位置

// 且強制最後一段不能屬於第一棵樹

rep(i,1,c) if(s[i]) rep(j,1,n) if(t[j])

printf("%d\n",ans);

}

JSOI2019遊記

十二省聯考命題組溫馨提醒您 資料千萬條,清空第一條。多測不清空,爆零兩行淚。 第一次參加省選差點十二響了。。。 突然接到通知說我可以報名省選...

JSOI2019 Round2 遊記

感覺現在江蘇省選有向浙江省選靠攏的趨勢啊,題目不僅題型和以前不太一樣 比方說今年既沒有網路流也沒有計算幾何 ,然後分數出來也是兩位數一堆,三位數沒幾個,一些強的選手就這樣被莫名其妙地刷下去了。。。感覺不是很好。。。 然而我這個菜雞又有什麼資格評價題目的好壞什麼事也不想做,晚上看yy打遊戲,後來又和y...

Luogu5334 JSOI2019 節日慶典

luogu5334 jsoi2019 節日慶典 exkmp 本題的突破口在於,對於一個位置 i ,從 i 以後可能成為最優解的字尾數量極少。 容易發現,當我們處理到位置 k 時,對於此時的兩個字尾 i j i,如果 t i t j 均有可能在 ge k 的位置成為最優解,那麼一定滿足 operato...