首页 > 代码库 > Codeforces Round #369 (Div. 2)
Codeforces Round #369 (Div. 2)
A题，水题，暴力找即可。
B题，水题，但是需要注意n=1的情况。
C题，dp。虽然是个水dp，但是我还是没能够自己独立的写出来。= =太菜了！代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <iostream> 5 using namespace std; 6 const int N = 100 + 5; 7 typedef long long ll; 8 const int inf = 0x3f3f3f3f; 9 10 int p[N][N]; 11 int n,m,k; 12 int a[N]; 13 ll dp[N][N][N]; 14 void update(ll &x,ll y) {if(x>y) x=y;} 15 16 int main() 17 { 18 cin >> n >> m >> k; 19 for(int i=1;i<=n;i++) scanf("%d",a+i); 20 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&p[i][j]); 21 memset(dp,inf,sizeof(dp)); 22 ll INF = dp[0][0][0]; 23 dp[0][0][0] = 0; 24 //for(int i=1;i<=m;i++) dp[0][i][0] = 0; 25 for(int i=1;i<=n;i++) 26 { 27 if(a[i]) 28 { 29 for(int num=1;num<=k;num++) 30 { 31 for(int j=(i!=1);j<=m;j++) 32 { 33 if(j == a[i]) update(dp[i][a[i]][num], dp[i-1][j][num]); 34 else update(dp[i][a[i]][num], dp[i-1][j][num-1]); 35 } 36 } 37 } 38 else 39 { 40 for(int num=1;num<=k;num++) 41 { 42 for(int now=1;now<=m;now++) 43 { 44 for(int pre=(i!=1);pre<=m;pre++) 45 { 46 if(pre == now) update(dp[i][now][num], dp[i-1][pre][num]+p[i][now]); 47 else update(dp[i][now][num], dp[i-1][pre][num-1]+p[i][now]); 48 } 49 } 50 } 51 } 52 } 53 ll ans = INF; 54 for(int i=1;i<=m;i++) ans = min(ans, dp[n][i][k]); 55 if(ans == INF) puts("-1"); 56 else printf("%I64d\n",ans); 57 return 0; 58 }
D题，环的贡献是乘以（2^边数-2），去掉全选和全部选的情况。其他的贡献直接乘以（2^边数）即可。dfs中，vising数组书用来判断在dfs过程中，某点是否正在访问，作用是判环；vis数组是为了记忆化搜索。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <vector> 5 #include <iostream> 6 using namespace std; 7 const int N = 200000 + 5; 8 typedef long long ll; 9 const int mod = 1e9 + 7; 10 11 int n; 12 int to[N]; 13 bool vis[N],vising[N]; 14 int d[N]; 15 int pw[N]; 16 int ans,cnt; 17 void dfs(int u,int deep) 18 { 19 if(vising[u]) 20 { 21 ans = 1LL * ans * (pw[deep-d[u]]-2) % mod; 22 cnt += deep - d[u]; 23 return ; 24 } 25 if(vis[u]) return ; 26 vis[u] = 1; 27 d[u] = deep; 28 vising[u] = 1; 29 dfs(to[u], deep+1); 30 vising[u] = 0; 31 } 32 33 int main() 34 { 35 cin >> n; 36 pw[0] = 1; 37 for(int i=1;i<=n;i++) pw[i] = 1LL* pw[i-1] * 2 % mod; 38 for(int i=1;i<=n;i++) scanf("%d",to+i); 39 ans = 1; 40 for(int i=1;i<=n;i++) 41 { 42 if(!vis[i]) 43 { 44 dfs(i,0); 45 } 46 } 47 cnt = n - cnt; 48 ans = 1LL* ans * pw[cnt] % mod; 49 cout << ans << endl; 50 return 0; 51 }
E题，思路参见：http://blog.csdn.net/miracle_ma/article/details/52383461。好题！顺便说下，该博客中的求逆元时的那个公式是对（a^temp）的（mod-2）次，因此用了仓鼠的超欧拉进化取模公式。当然直接快速幂也是可以的= =。-->直接先对a的temp次做快速幂，再做mod-2次的快速幂即可。顺便注意下，代码中的比较2的n次是不是比k小的方法。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <vector> 5 #include <iostream> 6 #include <math.h> 7 using namespace std; 8 const int N = 200000 + 5; 9 typedef long long ll; 10 const int mod = 1e6 + 3; 11 12 ll n,k; 13 ll qpow(ll a,ll b) 14 { 15 ll ans = 1; 16 while(b) 17 { 18 if(b & 1) ans = ans * a % mod; 19 a = a * a % mod; 20 b >>= 1; 21 } 22 return ans; 23 } 24 25 int main() 26 { 27 cin >> n >> k; 28 int x = 0; 29 while((1LL<<x) < k) x++; 30 if(n < x) return 0*puts("1 1"); 31 //if(1.0*n+1e-8 < log(k)/log(2)) return 0*puts("1 1"); 32 ll temp = 0; 33 for(ll i=2;i<=k-1;i<<=1LL) temp += (k-1) / i; 34 ll fenmu = qpow(qpow(2,n),k-1) * qpow(2,mod-1-temp%(mod-1)) % mod; 35 if(k-1 >= mod) 36 { 37 cout << fenmu << " " << fenmu << endl; 38 } 39 else 40 { 41 ll fenzi = 1; 42 for(int i=1;i<=k-1;i++) 43 { 44 fenzi = fenzi * (qpow(2,n) - i); 45 fenzi = (fenzi % mod + mod) % mod; 46 } 47 fenzi = fenzi * qpow(2,mod-1-temp%(mod-1)) % mod; 48 cout << ((fenmu - fenzi) % mod + mod) % mod << " " << fenmu << endl; 49 } 50 return 0; 51 }
Codeforces Round #369 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。