算秒数,算角度,注意180以内,所以大于180之后拿360减
#include#include #include using namespace std; int h, m, s, t; int main(){ //freopen("in.txt", "r", stdin); int _; scanf("%d", &_); for (; _--;){ scanf("%d%d%d%d", &h, &m, &s, &t); t += h * 3600 + m * 60 + s; t %= 3600 * 12; m = t % 3600; double ans = fabs(1.0 * t / 120 - 1.0 * m / 10); if (ans > 180) ans = 360 - ans; //printf("t = %d\n", t); //double ans = 1.0 * t / 120; printf("%.4lf\n", ans); } return 0; }
没想到这题居然是最难的一题,卡了一万年
hint: 中位数,前缀和
#include#include #include #include using namespace std; const int MAXN = 1e6 + 5; int a[MAXN]; int Getc[MAXN]; int Sum[MAXN]; int main(){ //freopen("in.txt", "r", stdin); int N, M; cin >> N >> M; for(int i = 1; i <= N; i++) { scanf("%d", Getc + i); } int cnt = 0; for(int i = 1; i <= N; i++) { if(Getc[i] == 0) { a[cnt++] = i; } } for(int i = 0; i < cnt; i++) { a[cnt + i] = a[i] + N; } Sum[0] = a[0]; for(int i = 1; i < cnt * 2; i++) { Sum[i] = Sum[i - 1] + a[i]; } if(cnt < M) { printf("-1\n"); return 0; } int ans = a[M / 2] * (M / 2) - Sum[M / 2 - 1] + Sum[M - 1] - Sum[M / 2] - (M - 1 - M / 2) * a[M / 2]; for(int i = 1; i < cnt; i++) { ans = min(ans, a[(i + i + M) / 2] * (M / 2) - Sum[(i + i + M) / 2 - 1] + Sum[i - 1] + Sum[M + i - 1] - Sum[(i + i + M) / 2] - (M - 1 - M / 2) * a[(i + i + M) / 2]); } printf("%d\n", ans); return 0; }
树形DP,统计每个点到叶子的最大距离,让每个子树都是一个“相等”、“平衡”状态
尽量修改靠上的节点,这样最后修改结果最小
#include#include #include using namespace std; typedef long long LL; const int N = 1e5 + 7; LL a[N], ans; int n; bool NotRoot[N]; int FindRoot(){ for (int i = 1; i <= n; i++) if (!NotRoot[i]) return i; return -1; } struct Edge{ int from, to, nxt; Edge(){} Edge(int u, int v, int n):from(u), to(v), nxt(n){} } edges[N * 2]; int E, head[N]; LL dist[N]; inline void AddEdge(int f, int t){ edges[++E] = Edge(f, t, head[f]); head[f] = E; } inline void Init(){ E = -1; for (int i = 0; i <= n; i++) head[i] = -1; for (int i = 0; i <= n; i++) dist[i] = 0; } int dfs(int u, int pre){ //printf("dfs(%d, %d)\n", u, pre); LL Max = 0; for (int i = head[u]; i != -1; i = edges[i].nxt){ Edge &e = edges[i]; dfs(e.to, u); Max = max(Max, dist[e.to]); } dist[u] = Max + a[u]; for (int i = head[u]; i != -1; i = edges[i].nxt){ Edge &e = edges[i]; ans += Max - dist[e.to]; } } int main(){ //freopen("in.txt", "r", stdin); int u, v; for (; ~scanf("%d", &n);){ a[0] = 0; for (int i = 1; i <= n; i++) scanf("%d", &a[i]); Init(); for (int i = 1; i < n; i++) { scanf("%d%d", &u, &v); AddEdge(u, v); NotRoot[v] = 1; } int root = FindRoot(); ans = 0; dfs(root, -1); printf("%lld\n", ans); } return 0; }
本以为是个压轴题,以为要线段树什么各种数据结构来维护
然后一看过的人多的不正常,想,先拿30分再说,然后就莫名其妙过了
标算应该不是这么粗暴的,加强数据应该还是过不了
这里就是根据题意模拟
#include#include #include #include using namespace std; const int MAXN = 1e6 + 5; int a[MAXN]; int N; int Find(int x) { if(x > N) return 0; return 1 + Find(x + a[x]); } int main(){ cin >> N; for(int i = 1; i <= N; i++) { scanf("%d", a + i); } int Q; cin >> Q; while(Q--) { int x; scanf("%d", &x); if(x == 1) { int y; scanf("%d", &y); printf("%d\n", Find(y)); } else { int u, v; scanf("%d%d", &u, &v); a[u] = v; } } return 0; }
复杂度1e5*26*26
#include#include #include #include using namespace std; const int N = 1e5 + 7; char st[N]; int Hash[222], n; int getMax(char ch){ int ans = 0; for (char i = 'a'; i <= 'z'; i++){ if (i == ch) ans = max(ans, Hash[i]-1); else ans = max(ans, Hash[i]); } return ans; } char FindChar(char last){ n--; for (char i = 'a'; i <= 'z'; i++){ if (!Hash[i]) continue; if (i == last) continue; int Max = getMax(i); if (Max * 2 > n + 1) continue; Hash[i]--; return i; } return '0'; } int main(){ //freopen("in.txt", "r", stdin); scanf("%s", st); int len = strlen(st); n = len; memset(Hash, 0, sizeof(Hash)); for (int i = 0; i < len; i++) Hash[st[i]]++; int Max = getMax('0'); if (Max * 2 > len + 1) puts("INVALID"); else { char last = ' '; for (int i = 0; i < len; i++){ last = FindChar(last); printf("%c", last); } puts(""); } return 0; }