[Codeforces] 855C. Helga Hufflepuff's Cup

題目連結:http://codeforces.com/contest/855/problem/C
賽中看到一堆大大們都寫出來的題目，但是自己怎麼寫都寫不出來就是了QQ，一定是因為我DP太爛的緣故
總之這題很明顯就是個樹DP題，狀態這裡是定成$$ dp[i][x][0] := 第i個節點放[1,k-1]種類且有x個k的方法數 \\ dp[i][x][1] := 第i個節點放k且有x個k的方法數 \\ dp[i][x][2] := 第i個節點放[k+1,M]且有x個k的方法數 $$轉移的話就算滿好想的了，大致就是0號可以從0,1,2轉來；2只能從0轉來；ㄉ可以從0, 2轉來，而怎麼轉就直接枚舉其中一邊有幾個就好了。 
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long lld;
const int N = 100000 + 5;
const int K = 10 + 2;
const int MOD_BASE = 1e9+7;
	
int n, m, k, x;
lld dp[N][K][3];
vector<int> G[N];
void dfs(int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<n-1;i++){
		int u, v; cin>>u>>v;
		G[u].PB(v);
		G[v].PB(u);
	}
	cin>>k>>x;
	dfs(1, 1);
	lld ans = 0;
	for(int i=0;i<=x;i++){
		ans=(ans+dp[1][i][0])%MOD_BASE;
		ans=(ans+dp[1][i][1])%MOD_BASE;
		ans=(ans+dp[1][i][2])%MOD_BASE;
	}
	cout<<ans<<'\n';
	return 0;
}

void dfs(int w, int f){
	dp[w][1][1]=1;
	dp[w][0][0]=k-1;
	dp[w][0][2]=m-k;
	for(auto i: G[w]){
		if(i==f) continue;
		dfs(i, w);
		lld ndp[K][3]={0};
		for(int kk=0;kk<=x;kk++){
			for(int j=0;j<=kk;j++){
				ndp[kk][0] = (ndp[kk][0]+(dp[w][j][0]*dp[i][kk-j][0])%MOD_BASE)%MOD_BASE;
				ndp[kk][0] = (ndp[kk][0]+(dp[w][j][0]*dp[i][kk-j][1])%MOD_BASE)%MOD_BASE;
				ndp[kk][0] = (ndp[kk][0]+(dp[w][j][0]*dp[i][kk-j][2])%MOD_BASE)%MOD_BASE;

				ndp[kk][1] = (ndp[kk][1]+(dp[w][j][1]*dp[i][kk-j][0])%MOD_BASE)%MOD_BASE;

				ndp[kk][2] = (ndp[kk][2]+(dp[w][j][2]*dp[i][kk-j][0])%MOD_BASE)%MOD_BASE;
				ndp[kk][2] = (ndp[kk][2]+(dp[w][j][2]*dp[i][kk-j][2])%MOD_BASE)%MOD_BASE;
			}
		}
		for(int ii=0;ii<=x;ii++){
			for(int j=0;j<3;j++){
				dp[w][ii][j]=ndp[ii][j];
			}
		}
	}
}

留言

張貼留言

這個網誌中的熱門文章

[TIOJ] 1094. C.幼稚國王的獎賞

題目連結: http://tioj.infor.org/problems/1094 這題有三種作法，一種是我看完馬上想到的砍半枚舉後套trie #include <bits/stdc++.h> using namespace std; const int LOG_C = 20; const int N = 30 + 5; inline int two(int x){return 1<<x;} class Trie{ private: static constexpr int MEM = 5000000; struct node{ int lc, rc; node(): lc(0), rc(0){} } nodes[MEM]; int mem_, root; inline int new_node(){ assert(mem_ < MEM); nodes[mem_] = node(); return mem_++; } void insert(int x, int& cur, int d){ if(!cur) cur = new_node(); if(d == -1) return; if(x & two(d)) insert(x, nodes[cur].rc, d-1); else insert(x, nodes[cur].lc, d-1); } int query(int x, int cur, int d){ if(d == -1) return 0; if(x & two(...
閱讀完整內容

[IOJ] 19. 啦啦啦

題目連結: http://ioj.infor.org/problems/19 因為$xor$有神奇(?的性質$a \oplus b = c \Longrightarrow a \oplus c = b$，所以就$O(n)$掃過去建好表，再$O(n)$掃一遍加起來，值得注意的是因為$a \oplus 0 = a$，所以若$x=0$，那要再減掉所有數的個數(自己不能算) #include <stdio.h> void gn(int &_){ _=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')_=_*10+c-'0',c=getchar(); } int MiccWan[100000 + 10]; int wayneTu[1000000 + 10] = {0}; int main(){ int t,x; long long edisonhello=0; gn(t);gn(x); for(int i=0;i<t;i++){ gn(MiccWan[i]); wayneTu[MiccWan[i]^x]++; } for(int i=0;i<t;i++){ edisonhello+=wayneTu[MiccWan[i]]; } if(x==0) edisonhello-=t; printf("%lld",edisonhello>>1); return 0; }
閱讀完整內容

[Codeforces] 731F. Video Cards

題目連結: http://codeforces.com/problemset/problem/731/F 惹...原來可以暴力做。直接枚舉每個人$i$當作leader時的情況，而計算時就是要算$[ik, i(k+1))$的數字數有幾個，因為在這區間的數字$a$再扣完之後一定都變成$ik$。此外枚舉倍數是$nlogn$的(某種調和級數的想法)，所以就照著做囉(? #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 200000 + 5; lld sum[N]; bool isok[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ int x; cin>>x; sum[x]++; isok[x]=1; } for(int i=1;i<N;i++) sum[i]+=sum[i-1]; lld ans = 0; for(int i=1;i<N;i++){ if(!isok[i]) continue; lld cur = 0; for(int j=i;j<N;j+=i) cur += j*(sum[min(j+i,N)-1]-sum[j-1]); ans = max(ans, cur); } cout<<ans<<'\n'; return 0; }
閱讀完整內容