首页 > 代码库 > 2012长春赛区题解（部分）
2012长春赛区题解（部分）
总结起来自己还是太逗比，DP还是太弱，而DP却恰是算法思维能力的体现，现在要开始注重加强这方面的训练，遇到这类题目总是不敢想，令人担忧。
Problem B ZOJ 3656 Bit Magic
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3656
分析：
总共N个数，每个b[i][j]会对a[i]和a[j]的对应二进制位产生一定影响，具体见题目，我们需要做的是判断每个数的每个位是0或1，根据关系建立边，然后直接2sat就可以了。
做的时候一直MLE，发现怎么改都不可能过的。原来是我把每个数所有位都放在图里判断了，其实完全可以每次判断一个位，因为位与位之间毫无影响啊。
代码：
#include <bits/stdc++.h>#define esp 1e-8#define in freopen("solve_in.txt", "r", stdin);#define out freopen("out.txt", "w", stdout);#define pf(x) ((x)*(x))#define lowbit(x) ((x)&(-(x)))#define bug(x) printf("Line %d: >>>>>>\n", (x));#define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define pb push_back#define mp make_pair#define pi acos(-1.0)#define pf(x) ((x)*(x))using namespace std;typedef long long LL;typedef unsigned short US;const int maxn = 1100;stack<US> S;vector<US> g[maxn*2];bitset<maxn*2> mark;struct TwoSAT{ int n, c; bool dfs(int x) { if(mark[x^1]) return false; if(mark[x]) return true; mark[x] = 1; S.push(x); for(int i = 0; i < (int)g[x].size(); i++) { if(!dfs(g[x][i])) return false; } return true; } void init(int n) { this->n = n; while(!S.empty()) S.pop(); for(int i = 0; i < 2*maxn; i++) g[i].clear(); mark.reset(); } void add(US x, US y) { g[x].pb(y); } bool solve(int n) { for(int i = 0; i < 2*n; i += 2) { if(!mark[i] && !mark[i+1]) { c = 0; if(!dfs(i)) { while(!S.empty()) mark[S.top()] = false, S.pop(); if(!dfs(i+1)) return false; } } } return true; }} sat;int idx(int u, int v){ return u;}const int maxm = 555;int a[maxm][maxm];int main(){ int n; while(scanf("%d", &n) == 1) { int ok = 1; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d", &a[i][j]); for(int k = 0; k < 31 && ok; k++) { sat.init(2*n); for(int i = 0; i < n && ok; i++) for(int j = 0; j < n &&ok; j++) { int &y = a[i][j]; if(i == j) { if(y) ok = 0; continue; } if(i%2 == 1 && j%2 == 1) { int u = idx(i, k); int v = idx(j, k); if(y&1) { sat.add(u<<1, v<<1|1); sat.add(v<<1, u<<1|1); } else { sat.add(u<<1|1, u<<1); sat.add(v<<1|1, v<<1);// sat.add(u<<1, v<<1);// sat.add(v<<1, u<<1); } y >>= 1; } else if(i%2 == 0 && j%2 == 0) { int u = idx(i, k); int v = idx(j, k); if(y&1) { sat.add(u<<1, u<<1|1); sat.add(v<<1, v<<1|1); } else { sat.add(u<<1|1, v<<1); sat.add(v<<1|1, u<<1); } y >>= 1; } else { int u = idx(i, k); int v = idx(j, k); if(y&1) { sat.add(u<<1, v<<1|1); sat.add(v<<1, u<<1|1); sat.add(u<<1|1, v<<1); sat.add(v<<1|1, u<<1); } else { sat.add(u<<1, v<<1); sat.add(v<<1, u<<1); sat.add(u<<1|1, v<<1|1); sat.add(v<<1|1, u<<1|1); } y >>= 1; } } if(!sat.solve(n*2)) ok = 0; } if(ok) puts("YES"); else puts("NO"); } return 0;}
Problem C ZOJ 3657 The Little Girl who Picks Mushrooms 简单题
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3657
分析：
对于n <= 3,结果显然为1024，n == 4时，需要判断能否从中取出3个数和位1024整数倍，能够的话结果为1024，或者判断任意3个数作为剩下的数，然后计算结果。
n == 5则只能看能否取出3个数为1024整数倍，能则根据剩下的值计算结果。
代码：
1 #include <bits/stdc++.h> 2 #define esp 1e-8 3 #pragma comment(linker, "/STACK:102400000,102400000") 4 #define in freopen("F:\\rootial\\data\\data.txt", "r", stdin); 5 #define IN freopen("solve_in.txt", "r", stdin); 6 #define out freopen("out.txt", "w", stdout); 7 #define pf(x) ((x)*(x)) 8 #define lowbit(x) ((x)&(-(x))) 9 #define bug(x) printf("Line %d: >>>>>>\n", (x));10 #define lson l, m, rt<<111 #define rson m+1, r, rt<<1|112 #define pb push_back13 #define mp make_pair14 #define pi acos(-1.0)15 #define pf(x) ((x)*(x))16 17 using namespace std;18 typedef long long LL;19 int a[10];20 21 int main(){22 23 int n;24 while(scanf("%d", &n) == 1){25 int sum = 0;26 for(int i = 0; i < n; i++){27 scanf("%d", a+i), sum += a[i];28 }29 if(n <= 3) cout<<1024<<endl;30 else{31 int ans = 0;32 if(n == 4){33 for(int i = 0; i < 4; i++)34 for(int j = i+1; j < 4; j++){35 int tmp = a[i]+a[j];36 if(tmp <= 1024)37 ans = max(tmp, ans);38 else ans = max(ans, tmp%1024 + 1024*(tmp%1024 == 0));39 }40 for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) for(int k = j+1; k < n; k++)41 {42 int tmp = a[i]+a[j]+a[k];43 if(tmp %1024 == 0)44 ans = 1024;45 }46 }47 else {48 for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) for(int k = j+1; k < n; k++)49 {50 int tmp = a[i]+a[j]+a[k];51 if(tmp%1024 == 0){52 int s = sum-tmp;53 if(s <= 1024)54 ans = max(ans, s);55 else ans = max(ans, s%1024 + 1024*(s%1024 == 0));56 }57 }58 }59 cout<<ans<<endl;60 61 }62 63 }64 return 0;65 }
Problem E ZOJ 3659 Conquer a New Region
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3659
分析：
题意是一棵树，每条边有一个正权值，一个点到另一点的花费是经过的路径上边的最小权值，要求一个中心，其他所有点到这个点的总花费最大。
做法是这样的，按边权值从大到小排序，构建最大生成树，并查集里记录结点个数，及此时这个并查集构成的子树里的总花费，按权值依次选择每条边，遇到两个点不在同一并查集时，由于此时中心肯定在其中一个并查集里，所以计算这两种情况下，连接起来后总花费。因为此时这条边是两个子树里最小的，计算中心在另一并查集里时totalCost = 此并查集结点数目*边cost + 另一并查集花费，取两种情况下最大值作为合并后并查集的花费，并更新结点数目。最后一个并查集的总花费即为结果。
代码：
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 #define in freopen("data.txt", "r", stdin); 5 #define bug(x) printf("Line : %u >>>>>>\n", (x)); 6 7 using namespace std; 8 typedef long long LL; 9 typedef unsigned long long ULL;10 const int maxn = 200000 + 10;11 12 struct Edge{13 int u, v, c;14 Edge(){}15 Edge(int u, int v, int c):u(u), v(v), c(c){}16 bool operator < (const Edge &o)const{17 return c > o.c;18 }19 }e[maxn];20 struct Node{21 int f, num;22 LL cost;23 Node(){}24 Node(int f, int num, LL cost):f(f), num(num), cost(cost){}25 } fa[maxn];26 LL ans = 0;27 int findset(int x){ return x == fa[x].f ? x : fa[x].f = findset(fa[x].f);}28 void makeTree(int n){29 for(int i = 1; i <= n; i++) fa[i] = Node(i, 1, 0);30 for(int i = 0; i < n-1; i++){31 int u = e[i].u;32 int v = e[i].v;33 int c = e[i].c;34 int fu = findset(u);35 int fv = findset(v);36 if(fu != fv){37 LL ans1 = (LL)fa[fu].num*c + fa[fv].cost;38 LL ans2 = (LL)fa[fv].num*c + fa[fu].cost;39 ans1 = max(ans1, ans2);40 fa[fu].f = fv;41 fa[fv].cost = ans1;42 fa[fv].num += fa[fu].num;43 ans = max(ans, ans1);44 }45 }46 }47 int main() {48 49 int n;50 while(scanf("%d", &n) == 1){51 ans = 0;52 for(int i = 0; i < n-1; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c);53 sort(e, e+n-1);54 makeTree(n);55 printf("%lld\n", ans);56 }57 return 0;58 }
Problem H ZOJ 3662 Math Magic
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3662
分析：
问选取k个正数，和为N，最小公倍数为M，有多少种方法？考虑数的顺序。
对于M首先分解质因数Div[i]，记录每个Div[i]数目cnt[i]，然后考虑k个数中每个数a[k]，包好的质因数Div[i]的个数,由于LCM为M，每个Div[i], 要保证k个数中至少有一个数 包含有cnt[i]个。这里用bitmask表示，s相应位为1，表示Div[i]已经有a[k]包含cnt[i]个了
思路是Dp的，考虑前k个数，和为sum，Div的包含状态表示为s时选取方案数目。
转移时：dp[i+1][j+sum][s|ss] += dp[i][j][s];
首先要预处理一下每个a[k]所有可能情况，也就是根据可能包含的Div[i]的数目，算出和sum，状态s，dfs处理一下。
代码:
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 #define in freopen("data.txt", "r", stdin); 5 #define bug(x) printf("Line : %u >>>>>>\n", (x)); 6 7 using namespace std; 8 typedef long long LL; 9 typedef unsigned long long ULL;10 const int M = (int)1e9 + 7;11 const int maxn = 1111;12 LL dp[111][maxn][1<<4];13 int p[maxn], vis[maxn], prime;14 15 void getPrime(int n) {16 for(int i = 2; i < n; i++) {17 if(vis[i] == 0) {18 p[prime++] = i;19 for(int j = i*i; j < n; j+=i)20 vis[j] = 1;21 }22 }23 }24 vector<int> Div;25 int cnt[maxn];26 27 void getDiv(int n) {28 Div.clear();29 for(int i = 0; i < prime; i++) {30 if(n%p[i] == 0) {31 Div.pb(p[i]);32 int sz = Div.size()-1;33 cnt[sz] = 0;34 while(n%p[i] == 0) {35 cnt[sz]++;36 n /= p[i];37 }38 if(n == 1) break;39 }40 }41 if(n != 1) {42 Div.pb(n);43 cnt[Div.size()-1] = 1;44 }45 }46 vector<pair<int, int> > State;47 void getState(int pos, int sum, int s) {48 if(pos == 0) {49 State.pb(make_pair(sum, s));50 return;51 }52 int tmp = 1;53 for(int i = 0; i <= cnt[pos-1]; i++, tmp *= Div[pos-1]) {54 getState(pos-1, sum*tmp, s|(i == cnt[pos-1] ? (1<<(pos-1)) : 0));55 }56 }57 int main() {58 59 int n, m, k;60 getPrime(maxn);61 while(scanf("%d%d%d", &n, &m, &k) == 3) {62 getDiv(m);63 memset(dp, 0, sizeof dp);64 int sz = Div.size();65 State.clear();66 getState(Div.size(), 1, 0);67 dp[0][0][0] = 1;68 for(int i = 0; i < k; i++)69 for(int j = 0; j < n; j++) for(int s = 0; s < (1<<sz); s++) {70 for(int kk = 0; kk < State.size(); kk++) {71 int sum = State[kk].first;72 int ss = State[kk].second;73 if(j+sum <= n)74 dp[i+1][j+sum][ss|s] = (dp[i+1][j+sum][ss|s] + dp[i][j][s])%M;75 }76 }77 cout<<dp[k][n][(1<<sz)-1]<<endl;78 }79 return 0;80 }
2012长春赛区题解（部分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。