首页 > 代码库 > 2013 长沙邀请赛 ADEGH 题解
2013 长沙邀请赛 ADEGH 题解
HDU 4565 So Easy!
类似fib的构造
设Fn = x + y*sqrt(b)
啪啦啪啦
#include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <iostream> using namespace std; typedef vector<long long> vec; typedef vector<vec> mat; typedef long long ll; ll a, b, n, MOD; mat mul(mat &A, mat &B) { mat C(A.size(), vec(B[0].size())); for (int i = 0; i < A.size(); ++i) { for (int k = 0; k < B.size(); ++k) { for (int j = 0; j < B[0].size(); ++j) { C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; } } } return C; } mat pow(mat A, ll n) { mat B(A.size(), vec(A.size())); for (int i = 0; i < A.size(); ++i) { B[i][i] = 1; } while (n > 0) { if (n & 1) B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } int main() { while (cin >> a >> b >> n >> MOD) { if (n == 1) { ll ans = a; ll bb = (ll)sqrt(1.0 * b); if (bb * bb != b) ++ans; ans = (ans + bb) % MOD; cout << ans << endl; continue; } mat A(2, vec(2)); A[0][0] = a, A[0][1] = b; A[1][0] = 1, A[1][1] = a; A = pow(A, n - 1); ll ans = A[0][0] * a % MOD; ans = (ans + A[0][1]) % MOD; ans = ans * 2 % MOD; cout << ans << endl; } return 0; }
HDU 4568 Hunter
状压dp,写的麻烦了。
。
#include <iostream> #include <algorithm> #include <cstdio> #include <queue> using namespace std; #define N 205 #define M 14 #define inf 10000000 int val[N][N]; int n,m,k; struct node{ int x,y; }c[M]; int d[N][N]; bool vis[N][N]; int step[4][2] = {0,1,0,-1,1,0,-1,0}; bool inmap(int x,int y){return 1<=x&&x<=n&&1<=y&&y<=m;} void spfa(int x,int y) { memset(vis,0,sizeof vis); for(int i = 0; i <= n; i++) for(int j = 0; j <= m; j++)d[i][j] = inf; d[x][y] = 0; queue<int>qx,qy; qx.push(x), qy.push(y); while(!qx.empty()) { int u = qx.front(); qx.pop(); int v = qy.front(); qy.pop(); vis[u][v] = 0; for(int i = 0; i < 4; i++) { int nx = u+step[i][0], ny = v+step[i][1]; if(!inmap(nx,ny))continue; if(d[nx][ny] > d[u][v] + val[nx][ny]) { d[nx][ny] = d[u][v]+val[nx][ny]; if(vis[nx][ny]==0) vis[nx][ny] = 1, qx.push(nx), qy.push(ny); } } } } void work(){ memset(vis,0,sizeof vis); for(int i = 0; i <= n; i++) for(int j = 0; j <= m; j++)d[i][j] = inf; queue<int>qx,qy; for(int i = 1; i <= n; i++) { qx.push(i); qy.push(1); qx.push(i); qy.push(m); d[i][1] = val[i][1]; d[i][m] = val[i][m]; } for(int i = 1; i <= m; i++) { qx.push(1); qy.push(i); qx.push(n); qy.push(i); d[1][i] = val[1][i]; d[n][i] = val[n][i]; } while(!qx.empty()) { int u = qx.front(); qx.pop(); int v = qy.front(); qy.pop(); vis[u][v] = 0; for(int i = 0; i < 4; i++) { int nx = u+step[i][0], ny = v+step[i][1]; if(!inmap(nx,ny))continue; if(d[nx][ny] > d[u][v] + val[nx][ny]) { d[nx][ny] = d[u][v]+val[nx][ny]; if(vis[nx][ny]==0) vis[nx][ny] = 1, qx.push(nx), qy.push(ny); } } } } int find(){ int ans = inf; for(int i = 1; i <= n; i++)ans = min(ans, min(d[i][1],d[i][m])); for(int i = 1; i <= m; i++)ans = min(ans, min(d[1][i],d[n][i])); return ans; } int dis[20][20]; int dp[1<<M][M]; bool can[M]; int main(){ int i,j,T;scanf("%d",&T); while(T--){ scanf("%d %d",&n,&m); for(i = 1; i <= n; i++) for(j = 1; j <= m; j++) { scanf("%d", &val[i][j]); if(val[i][j]<0)val[i][j] = inf; } scanf("%d",&k); for(i = 0; i < k; i++) {scanf("%d %d",&c[i].x,&c[i].y); c[i].x++; c[i].y++;} c[k].x = c[k].y = 0; for(i = 0; i < k; i++) { spfa(c[i].x, c[i].y); for(int j = 0; j < k; j++) { dis[i][j] = d[c[j].x][c[j].y]; } dis[i][k] = find(); } work(); for(i = 0; i < k; i++) dis[k][i] = d[c[i].x][c[i].y]; bool nothing = true; for(i = 0; i < k; i++) { can[i] = (d[c[i].x][c[i].y])<inf; if(can[i])nothing = false; } if(nothing){ puts("0"); continue; } int all = (1<<k)-1; for(i = 0; i <= all; i++) for(j = 0; j < k; j++) dp[i][j] = inf; for(i = 0; i < k; i++) if(can[i])dp[1<<i][i] = dis[k][i]; for(i = 0; i <= all; i++) { for(j = 0; j < k; j++) if(dp[i][j]<inf && can[j]) { for(int K = 0; K < k; K++) if((i&(1<<K))==0 && can[K]) { dp[i|(1<<K)][K] = min(dp[i][j]+dis[j][K], dp[i|(1<<K)][K]); } } } int ans = inf; all = 0; for(i = 0; i < k; i++) if(can[i]) all |= (1<<i); for(i = 0; i < k; i++) if(can[i]) ans = min(ans, dp[all][i] + dis[i][k]); cout<<ans<<endl; } return 0; }
HDU 4569 Special equations
找循环节
但p*p太大
由于f(x) % (p*p) ==0
所以f(x) % p ==0
所以先找到%p=0的第一个解 x
则让x += p 再找循环节,若找到了循环节还无解,则就是无解了
#include <cstdio> #include <algorithm> #include <cmath> #include <iostream> typedef long long ll; const int N = 100000000; int cas = 0; int a[10], n; int get(int x, int mod) { int re = 0, k = 1; for (int i = 0; i <= n; ++i) { re = ((ll)re + (ll)k *a[i]) % mod; k = (ll)k * x % mod; } return re; } void work() { ++ cas; int m, up; scanf("%d", &n); for (int i = n; i >= 0; --i) scanf("%d", &a[i]); scanf("%d", &m); up = m * m; int x, ans = -1, g; for (int i = 0; i <= m; ++i) { g = 0; x = i; for (int j = 1; j <= n; ++j) { g = ((ll)g + (ll)a[j] * x) % m; x = ((ll)x * i) % m; } if (g == ((-a[0]) % m + m) % m) { //printf("%d\n", i); for (int j = i; j <= up; j += m) { if (get(j, up) == 0) { ans = j; break; } } } if (ans >= 0) break; } printf("Case #%d: ", cas); if (ans == -1) puts("No solution!"); else printf("%d\n", ans); } int main() { int t; scanf("%d", &t); while (t--) work(); return 0; }
HDU 4571Travel in time
01背包。先排个序这样就能不考虑递增的条件了
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; const int Inf = (int)(1e9) + 10; const int N = 100 + 2; const int T = 300 + 2; int n, s, t, lim, tcas = 0; int d[T][N], w[N][N], cos[N], val[N]; int dp(int cur, int u) { if (~d[cur][u]) return d[cur][u]; d[cur][u] = 0; for (int i = 0; i < n; ++i) if (val[i] > val[u] && cur + w[u][i] + cos[i] + w[i][t] <= lim) { d[cur][u] = max(d[cur][u], dp(cur + w[u][i] + cos[i], i) + val[i]); } return d[cur][u]; } void work() { int m, u, v, len; memset(d, -1, sizeof d); scanf("%d%d%d%d%d", &n, &m, &lim, &s, &t); for (int i = 0; i < n; ++i) scanf("%d", &cos[i]); for (int i = 0; i < n; ++i) scanf("%d", &val[i]); for (int i = 0; i <= n; ++i) { for (int j = 0; j <= n; ++j) w[i][j] = Inf; w[i][i] = 0; } while (m -- > 0) { scanf("%d%d%d" ,&u, &v, &len); if (w[u][v] > len) { w[u][v] = len; w[v][u] = len; } } w[n][s] = w[s][n] = 0; for(int k = 0; k <= n; ++k) for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) if (w[i][j] > w[i][k] +w[k][j]) w[i][j] = w[i][k] +w[k][j]; cos[n] = 0; val[n] = -1; printf("Case #%d:\n", ++tcas); if(w[n][t] > lim) puts("0"); else printf("%d\n", dp(0, n)); } int main() { int cas; scanf("%d", &cas); while (cas -- > 0) work(); return 0; }
HDU 4572 Bottles Arrangement
先构造一个矩阵
11223344555544332211
然后后移一位构造出第二行
然后找个规律。事实上就是随便哪一列,反正答案都是一样的
交换行和交换列操作:
交换行操作不影响结果。交换列操作是非法的。。
#include <cstdio> int main() { int n, m; while(scanf("%d%d", &n, &m)!=EOF) { int ans = n + n - 1; int x = n + 1, y = n - 1; for(int i = 3; i <= m; i ++) { if(i&1) { ans += --x; } else ans += --y; } printf("%d\n", ans); } return 0; }
2013 长沙邀请赛 ADEGH 题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。