A
设S是两地的总距离， x是从west方向过来的车的速度， y是east方向过来的车的速度，根据题意有
S = 60 / y (x + y)
2S = (S - 90 + 60) / y (x + y)
比一下就出来了
B
这题挺有意思的、
题意：就说一颗n个节点，n-1条边，有m种颜色，然后给出每一个节点能涂上的颜色，现在要求相邻的两个节点之间颜色不能相同，问一共有多少种涂色方案
思路：dp1[i][j] 代表以点i为节点的子树在节点i涂上颜色j时候的总方案数，dp2[i]代表以节点i为子树的方案数
#include <cstdio> #include <cmath> #include <cstring> #include <cctype> #include <sstream> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <string> #include <stack> #include <map> #include <set> #include <utility> using namespace std; #define LL long long #define pb push_back #define mk make_pair #define pill pair<int, int> #define mst(Arr, x) memset(Arr, x, sizeof(Arr)) #define REP(i, x, n) for(int i = x; i < n; ++i) const int qq = 1e4 + 10; const int MOD = 1e7 + 9; vector<int> G[qq]; LL dp1[qq][23], dp2[qq]; int color[qq][23]; int n, m; void Init(){ REP(i, 0, n + 1){ G[i].clear(); } mst(dp2, 0); } void Dfs(int u, int fa){ for(int i = 1; i <= m; ++i) dp1[u][i] = color[u][i]; for(int v : G[u]){ if(v == fa) continue; Dfs(v, u); for(int i = 1; i <= m; ++i){ dp1[u][i] *= (dp2[v] - dp1[v][i] + MOD) % MOD; dp1[u][i] %= MOD; } } for(int i = 1; i <= m; ++i) dp2[u] += dp1[u][i]; dp2[u] %= MOD; } int main(){ while(scanf("%d%d", &n, &m) != EOF){ Init(); REP(i, 1, n){ int a, b; scanf("%d%d", &a, &b); G[a].pb(b), G[b].pb(a); } REP(i, 0, n) REP(j, 0, m){ scanf("%d", &color[i + 1][j + 1]); } Dfs(1, -1); printf("%lld\n", dp2[1]); } return 0; }C
题意：你可以删除一些数，要求剩下组成的数可以被6整除，并且不含前导零，问最多可以剩下多少位数
思路：dp[i][j]代表前i位在余数为j的时候的最大位数，注意0存在的情况
#include <cstdio> #include <cmath> #include <cstring> #include <cctype> #include <sstream> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <string> #include <stack> #include <map> #include <set> #include <utility> using namespace std; #define LL long long #define pb push_back #define mk make_pair #define pill pair<int, int> #define mst(Arr, x) memset(Arr, x, sizeof(Arr)) #define REP(i, x, n) for(int i = x; i < n; ++i) const int qq = 1e5 + 10; const int INF = 1e9 + 10; char st[qq]; int dp[qq][7]; int main(){ while(scanf("%s", st + 1) != EOF){ int n = strlen(st + 1); for(int i = 0; i <= n; ++i) for(int j = 0; j < 6; ++j) dp[i][j] = -INF; int ans = -INF; for(int i = 1; i <= n; ++i) if(st[i] == '0') ans = 1; for(int i = 1; i <= n; ++i){ int t = st[i] - '0'; if(t != 0) dp[i][t % 6] = 1; for(int j = 0; j < 6; ++j) dp[i][j] = max(dp[i][j], dp[i - 1][j]); for(int j = 0; j < 6; ++j) dp[i][(j * 10 + t) % 6] = max(dp[i][(j * 10 + t) % 6], dp[i - 1][j] + 1); ans = max(ans, dp[i][0]); } if(ans > 0) printf("%d\n", ans); else printf("-1s\n"); } return 0; }
E
矩阵快速幂的裸题
令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。
只是这里是在k步内达到就可以了，也就是你到达n点后就可以了，但是快速幂还要继续下去，所以mar[n][n] = 1
#include <cstdio> #include <cmath> #include <cstring> #include <cctype> #include <sstream> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <string> #include <stack> #include <map> #include <set> #include <utility> using namespace std; #define LL long long #define pb push_back #define mk make_pair #define pill pair<int, int> #define mst(Arr, x) memset(Arr, x, sizeof(Arr)) #define REP(i, x, n) for(int i = x; i <= n; ++i) const int qq = 105; const int MOD = 1e9 + 7; int n, m, p; struct Rec{ LL mar[qq][qq]; Rec(){ mst(mar, 0); } Rec operator * (const Rec &a)const{ Rec tmp; REP(i, 1, n) REP(j, 1, n){ tmp.mar[i][j] = 0; REP(k, 1, n){ tmp.mar[i][j] = (tmp.mar[i][j] + mar[i][k] * a.mar[k][j] + MOD) % MOD; tmp.mar[i][j] = (tmp.mar[i][j] + MOD) % MOD; } } return tmp; } }ans; Rec Quick(){ Rec tmp; for(int i = 1; i <= n; ++i) tmp.mar[i][i] = 1; while(p){ if(p & 1) tmp = tmp * ans; p >>= 1; ans = ans * ans; } return tmp; } int main(){ scanf("%d%d", &n, &m); REP(i, 1, m){ int a, b; scanf("%d%d", &a, &b); if(a != n) ans.mar[a][b] = 1; if(b != n) ans.mar[b][a] = 1; } ans.mar[n][n] = 1; scanf("%d", &p); Rec t; t = Quick(); printf("%lld\n", (t.mar[1][n] + MOD) % MOD); return 0; }
G
这题就是个求逆序数。
#include <cstdio> #include <cmath> #include <cstring> #include <cctype> #include <sstream> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <string> #include <stack> #include <map> #include <set> #include <utility> using namespace std; #define LL long long #define pb push_back #define mk make_pair #define pill pair<int, int> #define mst(Arr, x) memset(Arr, x, sizeof(Arr)) #define REP(i, x, n) for(int i = x; i < n; ++i) const int qq = 1e6 + 10; int sum[qq], num[qq]; int n; int lowbit(int x){ return x&(-x); } int GetSum(int x){ int ans = 0; while(x > 0){ ans += sum[x]; x -= lowbit(x); } return ans; } void UpDate(int x){ while(x <= qq){ sum[x] += 1; x += lowbit(x); } } int main(){ while(scanf("%d", &n) != EOF){ mst(sum, 0); REP(i, 0, n){ scanf("%d", num + i); } LL ans = 0; for(int i = n - 1; i >= 0; --i){ ans += GetSum(num[i] - 1); UpDate(num[i]); } printf("%lld\n", ans); } return 0; }
