先說一個事，我成都賽區基本徹底GG了。磊哥因為考試不能去，損失一大站力。
題目連接
http://acm.hdu.edu.cn/search.php?field=problem&key=2012%20Asia%20Tianjin%20Regional%20Contest&source=1&searchmode=source
然后我在今天19:00開始刷了一下天津賽區的題。到現在23:44分做出了5道。還被F怒坑了。
A題 大模擬，看了就不想寫。。。。
B題
枚舉一個數的所有因子
B
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 char cal(int x){
5 if(x < 10) return x + '0';
6 else return x - 10 + 'A';
7 }
8 long long convert(int a,int b) {
9 long long sum = 0;
10 while(a) {
11 int x = a % b;
12 sum += x * x;
13 a /= b;
14 }
15 return sum;
16 }
17 char ch[10005];
18 int main(){
19 int n,m;
20 while(~scanf("%d%d",&n,&m)) {
21 long long ans = 0;
22 for(int i = 1; i*i <= n; i++)
23 if(n % i == 0) {
24 ans += convert(i,m);
25 if(i*i!=n) ans += convert(n/i,m);
26 }
27 int len = 0;
28 while(ans) {
29 ch[len ++] = cal(ans % m);
30 ans /= m;
31 }
32 for(int i = len - 1; i >= 0; i--) printf("%c",ch[i]); puts("");
33 }
34 }
35 C題
貌似可以直接遞推求解的，但是不愿意多想了就直接寫了一個SPFA，還為末尾的情況糾結了好久，其實直接加哨兵就可以的。
C
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstring>
4 #include<cstdio>
5 #include<queue>
6 using namespace std;
7 const int N = 1005;
8 const int M = 1000;
9 const int inf = ~0u>>2;
10 int dp[N][M],vis[N][M],n,xa[N],xb[N];
11 queue<pair<int,int> >Q;
12 inline void shift(int la,int u,int c,int lb,int v){
13 if(dp[la][u] + c < dp[lb][v]) {
14 dp[lb][v] = dp[la][u] + c;
15 // cout<<"v: "<<lb<<" "<<v<<" "<<dp[lb][v]<<endl;
16 if(0 == vis[lb][v]) {
17 vis[lb][v] = 1;
18 Q.push(make_pair(lb,v));
19 }
20 }
21 }
22 int spfa(){
23 for(int i = 0; i <= n; i++)
24 for(int j = 0; j < M; j++)
25 dp[i][j] = inf , vis[i][j] = 0;
26 int s = xa[0] * 100 + xa[1] * 10 + xa[2];
27 int e = xb[0] * 100 + xb[1] * 10 + xb[2];
28 dp[0][s] = 0;
29 Q.push(make_pair(0,s));
30 while(!Q.empty()){
31 int l = Q.front().first;
32 int u = Q.front().second; Q.pop();
33 vis[l][u] = 0;
34 // cout<<"u: "<<l<<" "<<u<<" "<<dp[l][u]<<endl;
35 int a = u / 100, b = u % 100 /10, c = u % 10;
36 if(l == n) continue ;
37 if(a == xb[l]){
38 shift(l,u,0,l+1,b*100 + c*10 + xa[l+3]);
39 }
40 for(int i = 1; i < 10; i ++) {
41 int na = (a + i) % 10;
42 int nb = (b + i) % 10;
43 int nc = (c + i) % 10;
44 int v = 5 - abs(i-5);
45 shift(l,u,v,l,na*100+b*10+c);
46 shift(l,u,v,l,na*100+nb*10+c);
47 shift(l,u,v,l,na*100+nb*10+nc);
48 }
49 }
50 return dp[n][0];
51 }
52 char cha[N],chb[N];
53 int main(){
54 while(~scanf("%s%s",cha,chb)){
55 n = strlen(cha);
56 /*if(n == 1) printf("%d\n",abs((int)cha[0] - chb[0]));
57 else if(n == 2) {
58 int ans = inf, a = cha[0] - '0', b = cha[1] - '0';
59 int ea = chb[0] -'0', eb = chb[1] - '0';
60 for(int i = 0; i < 10; i++){
61 int v = 5 - abs(i - 5);
62 int na = (a + i) % 10;
63 int nb = (b + i) % 10;
64 ans = min(ans, v + abs(na - ea) + abs(na - eb));
65 }
66 printf("%d\n",ans);
67 }*/
68 // else {
69 for(int i = 0; i < n; i++) xa[i] = cha[i] - '0', xb[i] = chb[i] - '0';
70 xa[n] = xa[n+1] = xa[n+2] = 0;
71 xb[n] = xb[n+1] = xb[n+2] = 0;
72 printf("%d\n",spfa());
73 // }
74 }
75 }
76 E題
我一開始看的這題，感覺臥槽這題可做么。多哈密頓路點數還是128個點的歐式圖。。。。。
后來發現并非每個加油站只能去一次。。。。
因為在點i建立加油站的費用是2^i，所以即使前i-1個都建立加油站，也比在i點建立加油站合適。。。。
于是可以從后向前枚舉是否建立加油站。如果前i-1個節點都建立加油站可以保證合法，那么i一定不建立，否則一定建立。
然后問題就是在給出哪些點建立加油站之后，如何判斷方案可行了。。。
首先所有的加油站必須聯通。
其次對于所有非加油站，最好的情況是找一個最近的加油站作為自己的“補充”。
E
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<cmath>
5 #include<queue>
6 using namespace std;
7 const int N = 150;
8 int ans[N],num[N][N],vis[N],d,n;
9 const int inf = ~0u>>2;
10 const int eps = 1e-9;
11 queue<int> Q;
12 bool bfs(){
13 Q.push(0);
14 memset(vis,0,sizeof(vis));
15 vis[0] = 1;
16 while(!Q.empty()){
17 int u = Q.front(); Q.pop();
18 for(int v = 0; v < n; v++) if(ans[v] && !vis[v] && num[v][u] <= d){
19 vis[v] = 1;
20 Q.push(v);
21 }
22 }
23 bool flag = 1;
24 for(int i =0; i < n; i++) if(ans[i] && !vis[i]) flag = 0;
25 return flag;
26 }
27 bool solve() {
28 if(!bfs()) return 0;
29 bool flag = 1;
30 for(int i = 0; i < n; i++) if(!ans[i]){
31 int mn = inf;
32 for(int j = 0; j < n; j++) if(ans[j]){
33 mn=min(mn,2*num[i][j]);
34 }
35 if(mn > d) {flag = 0;break;}
36 }
37 return flag;
38 }
39 int x[N],y[N];
40 int main(){
41 while(~scanf("%d%d",&n,&d)){
42 for(int i = 0; i < n; i++) scanf("%d%d",&x[i],&y[i]);
43 for(int i = 0; i < n; i++)
44 for(int j = 0; j < n; j++){
45 num[i][j] = ceil(sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i] - y[j]) * (y[i] - y[j])) - eps);
46 }
47 for(int i = 0; i < n; i++) ans[i] = 1;
48 if(!bfs()) printf("-1\n");
49 else {
50 for(int i = n-1; i; i--){
51 ans[i] = 0;
52 if(!solve()) ans[i] = 1;
53 }
54 bool flag = 1;
55 for(int i = n-1; i>=0; i--) {
56 if(!ans[i]) {
57 if(!flag) printf("0");
58 } else {
59 flag = 0;
60 printf("1");
61 }
62 }
63 puts("");
64 }
65 }
66 }
67 F
一看到“所有的子串”，就一定會想到后綴自動機來搞了。
連接所有的串建立后綴自動機。不同的串用特殊符連接。
然后對這個DAG進行DP。轉移非常明顯。不要走特殊符的邊和第一個零邊。
拓撲排序的時候我到了深搜然后hdoj就爆棧了。。。。。。。。。
F
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 #define tm t_tim
7 const int N = 120005;
8 const int M = 10;
9 typedef long long ll;
10 int G[N<<1][11],par[N<<1],val[N<<1],sz,last;
11 void ins(int x) {
12 int p = last, np = sz ++;
13 memset(G[np],0,sizeof(G[np]));
14 val[np] = val[p] + 1;
15 while(p != -1 && G[p][x] == 0) { //if(x==4) cout<<p<<endl;
16 G[p][x] = np, p = par[p]; }
17 if(-1 == p) {
18 par[np] = 0;
19 } else {
20 int q = G[p][x];
21 if(val[q] == val[p]+1) {
22 par[np] = q;
23 } else {
24 int nq = sz ++;
25 memcpy(G[nq],G[q],sizeof(G[q]));
26 val[nq] = val[p] + 1;
27 par[nq] = par[q];
28 par[q] = par[np] = nq;
29 while(p != -1 && G[p][x] == q) G[p][x] = nq, p = par[p];
30 }
31 }
32 last = np;
33 }
34 char ch[N];
35 int num[N];
36 // dp && sort
37 const int mod = 2012;
38 int cnt[N<<1] , dp[N<<1];
39 int vis[N<<1];
40 int tm;
41 struct node{
42 int id, v;
43 node(){id=v=0;}
44 node(int _id,int _v) :id(_id),v(_v){}
45 bool operator < (const node &a) const{
46 return v > a.v;
47 }
48 } flag[N<<1];
49 int tp,stp;
50 int stk[N<<1][2];
51 void dfs(int u){
52 stk[0][0] = stk[0][1] = 0;
53 stp = 1;
54 vis[u] = 1;
55 int v;
56 while(stp) {
57 int s= stk[stp-1][1],f = 0;
58 int u = stk[stp-1][0];
59 //cout<<"u: "<<u<<endl;
60 for(;s<M;s++) if((v=G[u][s])&&!vis[v]){
61 f = 1;
62 vis[v] = 1; stk[stp-1][1] = s+1;
63 //cout<<"v: "<<v<<endl;
64 stk[stp][0] = v;
65 stk[stp][1] = 0;
66 stp++;
67 u = v;
68 break;
69 }
70 if(!f) {
71 stp --;
72 flag[tp++] = node(u,++tm);
73 }
74 }
75 }
76 int main(){
77 int n;
78 while(~scanf("%d",&n)){
79 int m = 0;
80 for(int i = 0; i < n; i++){
81 scanf("%s",ch);
82 int len = strlen(ch);
83 for(int j = 0; j < len; j++)
84 num[m++] = ch[j] - '0';
85 num[m++] = 10;
86 }
87 m --;
88 par[0] = -1;
89 tm = tp = last =0; sz = 1;
90 memset(G[0],0,sizeof(G[0]));
91 for(int i = 0; i < m; i++)
92 ins(num[i]);
93 G[0][0] = 0;
94 for(int i = 0; i < sz; i++) dp[i] = 0, cnt[i] = 0, vis[i] = 0;
95 dfs(0);
96 sort(flag,flag+tp);
97 cnt[0] = 1;
98 int ans = 0;
99 for(int p = 0; p < tp; p++){
100 int u = flag[p].id,v;
101 // cout<<"u: "<<u<<" "<<dp[u]<<" "<<cnt[u]<<endl;
102 ans = (ans+ dp[u])%mod;
103 for(int i = 0;i < M; i++) if(v = G[u][i]) {
104 dp[v] += dp[u] * 10 + cnt[u] * i;
105 cnt[v] += cnt[u];
106 dp[v] %= mod;
107 cnt[v] %= mod;
108 }
109 }
110 cout << ans << endl;
111 }
112 }
113 H
上過高中的都會吧。。。
H
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int main(){
5 int x,y,t;
6 double p,q; cin >> t;
7 while(t--&&~scanf("%d%d%lf%lf",&x,&y,&p,&q)){
8 double tiger = (1-q)*x + q*p*(x+y);
9 double wolf = q*y + p*(1-q)*(x+y);
10 if(tiger>wolf) printf("tiger %.4lf\n",tiger);
11 else printf("wolf %.4lf\n",wolf);
12 }
13 }
14 K splay可以做，但是連敲5個小時體力不支了。。。以后還要多練習啊
posted on 2012-10-30 00:07
西月弦 閱讀(1019)
評論(8) 編輯 收藏 引用 所屬分類:
解題報告