2012年浙大7月月赛 源码和部分数据
解题报告请见： http://blog.csdn.net/woshi250hua/article/details/7803599
部分题目代码如下：
A题代码：
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;int dp[1000] = {0,1,2,5,10,20,25,50,100,125,200,250,500,1000,1250,2000,2500,5000,10000,12500,20000,25000,50000,100000,125000,200000,250000,500000,1000000,1250000,2000000,2500000,5000000,10000000,12500000,20000000,25000000,50000000,100000000,125000000,200000000,250000000,500000000,1000000000,1250000000,2000000000};int main(){int i,j,k,cnt = 100;int n,m,tot;cnt = 100;while (scanf("%d%d",&n,&m) != EOF) {tot = 0;for (i = 1;i <= cnt; ++i)if (dp[i] >= n && dp[i] <= m)tot++;printf("%d\n",tot);}} B题代码：
//完全背包写法#include <stdio.h>#include <string.h>#define MIN 40#define MAX 660int n,m,dp[MAX],ans;int time[MIN],power[MIN];int main(){ int i,j,k; while (scanf("%d%d",&n,&m) != EOF) { for (i = 1; i <= n; ++i) scanf("%d%d",&time[i],&power[i]); ans = 2147483647; memset(dp,0,sizeof(dp)); for (i = 1; i <= n; ++i) for (j = 0; j <= m; ++j) if (dp[j+time[i]] < dp[j]+j * power[i]) { dp[j+time[i]] = dp[j] + j * power[i]; if (dp[j+time[i]] >= m && j + time[i] < ans) ans = j + time[i]; } printf("%d\n",ans); }}//2B写法#include <stdio.h>#include <string.h>#include <queue>#include <string.h>#include <stdlib.h>using namespace std;#define MIN 50#define MAX 500#define INF 1000000000#define min(a,b) ((a)<(b)?(a):(b))int n,m,cost[MIN],pow[MIN];int dp[MAX][MAX],ans;int main(){int i,j,k,curpow;int tp2,tpl,cnt;while (scanf("%d%d",&n,&m) != EOF) {for (i = 1; i <= n; ++i)scanf("%d%d",&cost[i],&pow[i]);for (i = 0; i <= m; ++i)for (j = 0; j <= m; ++j)dp[i][j] = INF;dp[0][0] = 0;for (i = 0; i <= m; ++i)for (j = 0; j <= m; ++j)for (k = 1; k <= n; ++k)if (dp[i][j] != INF) {curpow = i + pow[k];tpl = j + i * cost[k];if (tpl >= m) tpl = m;if (curpow >= m) tp2 = m;else tp2 = curpow;if (dp[tp2][tpl] >= dp[i][j] + cost[k])dp[tp2][tpl] = dp[i][j] + cost[k];}ans = INF;for (i = 0; i <= m; ++i)ans = min(ans,dp[i][m]);for (i = 1; i <= m; ++i)for (j = 0; j <= m; ++j) if (dp[i][j] != INF) {tpl = dp[i][j],tp2 = m - j;while (1) {tpl++,tp2 -= i;if (tp2 <= 0) {ans = min(ans,tpl);break;}}}printf("%d\n",ans);}}D题代码：
#include <stdio.h>#include <math.h>#define E 0.57721566490153286060651209int main(){ int i,j,k; double a,x; while (scanf("%lf",&a) != EOF) { x = E; x *= pow(2,a) - 1; printf("%1.12e\n",x); }}E题代码：
#include <stdio.h>#include <string.h>#include <vector>using namespace std;#define MAX 220#define max(a,b) ((a)>(b)?(a):(b))struct node {int v,len;};vector<node> tree[MAX];int n,m,st,cost[MAX];int dp[MAX][MAX];void Initial() {memset(dp,0,sizeof(dp));for (int i = 0; i <= n; ++i)tree[i].clear();}void AddEdge(int x,int y,int z) {node cur;cur.v = y,cur.len = z;tree[x].push_back(cur);}void Tree_DP(int s,int pa) {int i,j,k,size;size = tree[s].size();for (i = 0; i < size; ++i) {node cur = tree[s][i];if (cur.v == pa) continue;Tree_DP(cur.v,s);for (j = m; j >= 0; --j)for (k = 0; k <= m; ++k){//?????if (j >= 2*cur.len + k)dp[s][j] = max(dp[s][j],dp[s][j-2*cur.len-k]+dp[cur.v][k]);}}for (i = 0; i <= m; ++i)dp[s][i] += cost[s];}int main(){int i,j,k,a,b,c;while (scanf("%d",&n) != EOF) {Initial();for (i = 1; i <= n; ++i)scanf("%d",&cost[i]);for (i = 1; i < n; ++i) {scanf("%d%d%d",&a,&b,&c);AddEdge(a,b,c),AddEdge(b,a,c);}scanf("%d%d",&st,&m);Tree_DP(st,-1);int ans = 0;for (i = 0; i <= m; ++i)ans = max(dp[st][i],ans);printf("%d\n",ans);}}F题代码：
#include <stdio.h>#include <string.h>using namespace std;#define MAX 100010#define int64 long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))int n, m, p, time;int64 sum[MAX],ans;int left, right, dis,gold[MAX];int64 Solve_AC() { for (int i = p; i <= n; ++i) { if (i - p > time) break; right = i; dis = max(p - (i - p),1); //i-p时间走到的最远距离 left = max(i - m,1); //要求最远距离不多于m，这两个代表的是一起走的情况 left = max(dis,left); //两个约束条件，最大的那个边界两个条件都符合 left = max(left-(time-(i-p)),1);//这时候右边的人带着左边的人跑 left = min(left,p); ans = max(ans,sum[right]-sum[left-1]); } for (int i = p; i >= 1 && p - i <= time; --i) { if (p - i > time) break; left = i; dis = min(p + (p - i),n); //p-i时间走到的最远距离 right = min(i + m,n); //要求最远距离不多于m，这两个代表的是一起走的情况 right = min(dis,right); //两个约束条件，最大的那个边界两个条件都符合 right = min(right+(time-(p-i)),n); //这时候左边的人带着右边的人跑 right = max(right,p); ans = max(ans,sum[right]-sum[left-1]); }}int main() { int i, j, k; while (scanf("%d%d", &n, &p) != EOF) { for (i = 1; i <= n; ++i) { scanf("%d", &gold[i]); sum[i] = gold[i] + sum[i - 1]; } scanf("%d%d", &m, &time); ans = gold[p]; Solve_AC(); printf("%lld\n", ans); }}H题代码：
#include <stdio.h>#include <string.h>#include <math.h>#define int64 long longint64 Solve_AC(int64 n) {if (n == -1) return 0;int64 x = (int64)sqrt(n);if (x & 1) x--;int64 ans = x * (x - 1) / 2;int64 result = x * x;if (n >= result + x * 2 + 1) ans += x * 2 + 1;else ans += n - x * x + 1;return ans;}int main(){int64 n,m;while (scanf("%lld%lld",&n,&m) != EOF) printf("%lld\n",Solve_AC(m)-Solve_AC(n-1));}I题代码：
#include <stdio.h>#include <vector>#include <string.h>using namespace std;#define MIN 101#define MAX 9010#define min(a,b) ((a)<(b)?(a):(b))#define max(a,b) ((a)>(b)?(a):(b))vector<int> mmap[MIN];int st[MIN],top,vis[MIN];int tot,ans,mmax,Index,n,m;int dfn[MIN],low[MIN],isstack[MIN];void Initial() {top = Index = 1;memset(st,0,sizeof(st));memset(vis,0,sizeof(vis));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(isstack,0,sizeof(isstack));}void Tarjan(int s,int del) {int i,j,v,size,cnt;vis[s] = 1,cnt = 0;dfn[s] = low[s] = ++Index;st[++top] = s,isstack[s] = 1;size = mmap[s].size();for (i = 0; i < size; ++i) {v = mmap[s][i];if (v == del) continue;if (dfn[v] == 0) {Tarjan(v,del);low[s] = min(low[s],low[v]);}else if (isstack[v])low[s] = min(low[s],dfn[v]);}if (dfn[s] == low[s]) {do {cnt++;v = st[top--];isstack[v] = 0;}while (v != s);mmax = max(cnt,mmax);}}int main(){int i,j,k,a,b;while (scanf("%d%d",&n,&m) != EOF) {for (i = 0; i < n; ++i)mmap[i].clear();for (i = 0; i < m; ++i) {scanf("%d%d",&a,&b);mmap[a].push_back(b);}for (ans = n,i = 0; i < n; ++i) {Initial();mmax = 0,vis[i] = 1;for (j = 0; j < n; ++j) if (!vis[j]) Tarjan(j,i);if (mmax < 2) mmax = 0;ans = min(mmax,ans);if (ans == 0) break;}printf("%d\n",ans);}}J题代码：
#include <stdio.h>#include <string.h>#include <queue>#include <string.h>#include <algorithm>using namespace std;#define MIN 50#define INF 1000000000#define int64 intpriority_queue<int> qu1,qu2;int n,m,cost[MIN],sum[MIN];int Solve_1A() {int ans = 0,tp;while (!qu1.empty()) qu1.pop();qu1.push(0);for (int i = n; i >= 1; --i) {if (cost[i] > m) continue;while (!qu2.empty()) qu2.pop();while (!qu1.empty()) {tp = qu1.top(),qu1.pop();qu2.push(tp);if (tp + cost[i] <= m) {if (tp + cost[i] > ans)ans = tp + cost[i];qu2.push(tp + cost[i]);}}int flag = 0;while (!qu2.empty()) {tp = qu2.top(),qu2.pop();if (tp + sum[i-1] <= m && flag == 1)break;if (tp + sum[i-1] <= m)flag = 1;qu1.push(tp);}} return ans;}int main(){ int i,j,t,cas = 0; int u,v,k; while (scanf("%d%d",&n,&m) != EOF) { for (i = 1; i <= n; ++i) scanf("%d",&cost[i]);sort(cost+1,cost+1+n);sum[0] = 0;for (i = 1; i <= n; ++i) {sum[i] = sum[i-1] + cost[i];if (sum[i] > m) sum[i] = m + 1;} int ans = Solve_1A(); printf("%d\n",ans); }}K题代码：
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define MAX 110000#define int64 long long#define INF (0xffffffffffff)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1struct node {int cost,last;}arr[MAX];int64 ans,Min[MAX*3],dp[MAX];int n,m,tot,cnt,dis[MAX*3];inline int64 min(int64 a,int64 b) {return a<b?a:b;}void Push_Up(int rt) {Min[rt] = min(Min[rt<<1],Min[rt<<1|1]);}void Build_Tree(int l,int r,int rt) {if (l == r) {Min[rt] = (l == n+1 ? 0 : INF);return;}int m = (l + r) >> 1;Build_Tree(lson);Build_Tree(rson);Push_Up(rt);}int64 Query_Tree(int L,int R,int l,int r,int rt) {if (L <= l && r <= R) return Min[rt];int m = (l + r) >> 1;int64 temp = INF;if (m >= L) temp = min(temp,Query_Tree(L,R,lson));if (m + 1 <= R) temp = min(temp,Query_Tree(L,R,rson));return temp;}void Update(int L,int64 x,int l,int r,int rt) {if (l == r) {Min[rt] = min(Min[rt],x);return;}int m = (l + r) >> 1;if (L <= m) Update(L,x,lson);else Update(L,x,rson);Push_Up(rt);}int main(){int i,j,k,t,cas = 0; while (scanf("%d",&n) != EOF) {for (i = 1; i <= n; ++i)scanf("%d",&arr[i].cost);for (i = 1; i <= n; ++i)scanf("%d",&arr[i].last);Build_Tree(1,n+1,1);for (i = n; i >= 1; --i) {j = i + arr[i].last;if (j >= n + 1) j = n + 1;dp[i] = Query_Tree(i+1,j,1,n+1,1);dp[i] += arr[i].cost;Update(i,dp[i],1,n+1,1);}printf("%lld\n",dp[1]);}}B题数据1 11 12 101 12 5 3 1001 103 2010 100E题数据21 31 2 11 221 32 1 12 123 31 2 12 523 01 2 22 423 01 2 22 433 3 31 2 22 3 21 533 3 31 2 21 3 31 533 3 31 2 21 3 31 10F题数据1 1120 206 3101 2 3 3 5 40 16 3101 2 3 3 5 41 16 3101 2 3 3 5 41 46 3101 2 3 3 5 42 07 4101 2 3 3 5 4 1014 310 3101 2 3 3 5 4 101 102 103 1044 310 3101 2 3 3 5 4 101 102 103 1044 410 7101 2 3 3 5 4 101 102 103 1044 410 7101 2 3 3 5 4 101 102 103 1044 510 8101 2 3 3 5 4 101 102 103 1044 85 51 2 3 4 56 31 2 3 3 5 42 16 31 2 3 3 5 42 46 31 2 3 3 5 42 56 3101 2 3 3 5 42 56 3101 2 3 3 5 42 46 3101 2 3 3 5 42 11I题数据2 20 11 03 30 11 22 04 80 11 22 33 00 22 01 33 1J题数据3 108 4 53 08 4 53 1008 4 510 100001 2 3 4 5 6 7 8 9 1010 1000010000 10000 10000 10000 10000 10000 10000 1000 1000 10000