昨天晚上打开CF突然发现有个比赛,激动至极,遂猝不及防地与@llf0703合作了一把
结果评测机锅了,Unrated...(明明是因为把Div.3标成了Div.2)
这次的题面是春节主题的,有意思
A. Lunar New Year and Cross Counting
题意过于显然,自己看吧
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include <algorithm> #include <cassert> #include <cstdio> #include <cstring> #include <fstream> #include <iostream> using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f ;const int MAXN = 510 ;char a[MAXN][MAXN];#include <cctype> #include <cstdio> inline int read () { int X = 0 , w = 0 ; char ch = 0 ; while (!isdigit (ch)) { w |= ch == '-' ; ch = getchar (); } while (isdigit (ch)) { X = (X << 3 ) + (X << 1 ) + (ch ^ 48 ); ch = getchar (); } return w ? -X : X; } int main () { int n = read (); for (int i = 1 ; i <= n; i++) { scanf ("%s" , a[i] + 1 ); } int ans = 0 ; for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= n; j++) { if (a[i][j] == 'X' && a[i][j] == a[i - 1 ][j - 1 ] && a[i][j] == a[i - 1 ][j + 1 ] && a[i][j] == a[i + 1 ][j - 1 ] && a[i][j] == a[i + 1 ][j + 1 ]) { ans++; } } } cout << ans << endl; return 0 ; }
B. Lunar New Year and Food Ordering
十分显然的大模拟,照着题意写就好,稍稍加一个优化,就是记录一下上一次取走的最便宜的菜,不要每次从头枚举,记得开int64
代码是llf0703的,被int64和优化坑了两次罚时
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 #include <algorithm> #include <cassert> #include <cstdio> #include <cstring> #include <fstream> #include <iostream> using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f ;const int MAXN = 1e5 + 10 ;#include <cctype> inline int64 read () { int64 X = 0 , w = 0 ; char ch = 0 ; while (!isdigit (ch)) { w |= ch == '-' ; ch = getchar (); } while (isdigit (ch)) { X = (X << 3 ) + (X << 1 ) + (ch ^ 48 ); ch = getchar (); } return w ? -X : X; } struct node { int64 cnt, price, id; } a[MAXN]; int ord[MAXN];bool cmp (const node& x, const node& y) { return (x.price == y.price) ? x.id < y.id : x.price < y.price; } inline void write (int64 x) { if (x < 0 ) putchar ('-' ), x = -x; if (x > 9 ) write (x / 10 ); putchar (x % 10 + '0' ); } int main () { int n = read (); int m = read (); int64 tot = 0 ; for (int i = 1 ; i <= n; i++) { a[i].cnt = read (); a[i].id = i; tot += a[i].cnt; } for (int i = 1 ; i <= n; i++) { a[i].price = read (); } sort (a + 1 , a + n + 1 , cmp); for (int i = 1 ; i <= n; i++) { ord[a[i].id] = i; } int cheapest = 1 ; for (int i = 1 ; i <= m; i++) { int64 t = read (); int64 d = read (); if (d > tot) { tot = 0 ; puts ("0" ); continue ; } if (a[ord[t]].cnt >= d) { a[ord[t]].cnt -= d; tot -= d; write (a[ord[t]].price * d); putchar ('\n' ); } else { tot -= d; d -= a[ord[t]].cnt; int pos = cheapest; int64 ans = a[ord[t]].cnt * a[ord[t]].price; a[ord[t]].cnt = 0 ; while (true ) { if (d >= a[pos].cnt) { d -= a[pos].cnt; ans += a[pos].price * a[pos].cnt; a[pos].cnt = 0 ; } else { a[pos].cnt -= d; cheapest = pos; ans += a[pos].price * d; break ; } pos++; } write (ans); putchar ('\n' ); } } return 0 ; }
C. Lunar New Year and Number Division
这题第一反应是一大一小直接贪,然鹅并不会证明,比赛时也找不到反例(卡了20分钟找反例,不肯相信这么显然)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include <algorithm> #include <cassert> #include <cstdio> #include <cstring> #include <fstream> #include <iostream> using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f ;const int MAXN = 3e5 + 10 ;int64 a[MAXN]; #include <cctype> #include <cstdio> inline int read () { int X = 0 , w = 0 ; char ch = 0 ; while (!isdigit (ch)) { w |= ch == '-' ; ch = getchar (); } while (isdigit (ch)) { X = (X << 3 ) + (X << 1 ) + (ch ^ 48 ); ch = getchar (); } return w ? -X : X; } int main () { int n = read (); for (int i = 1 ; i <= n; i++) { a[i] = read (); } sort (a + 1 , a + n + 1 ); int64 ans = 0 ; for (int i = 1 ; i <= n / 2 ; i++) { ans += (a[i] + a[n + 1 - i]) * (a[i] + a[n + 1 - i]); } cout << ans << endl; return 0 ; }
D. Lunar New Year and a Wander
类似NOIP2018 D2T1,不过限制条件更少,直接优先队列BFS就行了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 #include <algorithm> #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <vector> using namespace std;const int MAXN = 100010 ;const int INF = 0x3f3f3f3f ;class LFS { public : LFS () { memset (head, -1 , sizeof head); ecnt = 0 ; n = 0 ; } LFS (int N) { memset (head, -1 , sizeof head); ecnt = 0 ; n = N; } void adde (int from, int to, int w) { e[ecnt].to = to; e[ecnt].w = w; e[ecnt].next = head[from]; head[from] = ecnt++; } void addde (int a, int b, int w) { adde (a, b, w); adde (b, a, w); } void solve () { memset (vis, false , sizeof vis); while (!q.empty ()) { q.pop (); } q.push (1 ); while (!q.empty ()) { int u = q.top (); q.pop (); if (vis[u]) { continue ; } cout << u << ' ' ; vis[u] = true ; for (int i = head[u]; i != -1 ; i = e[i].next) { int v = e[i].to; if (!vis[v]) { q.push (v); } } } } protected : struct Edge { int to, next, w; } e[MAXN * 2 ]; int head[MAXN]; int ecnt; int n; bool vis[MAXN]; priority_queue<int , vector<int >, greater<int >> q; private : void dfs (int u, int fa) { for (int i = head[u]; i != -1 ; i = e[i].next) { int v = e[i].to; if (v != fa) { dfs (v, u); } } } }; #include <cctype> #include <cstdio> inline int read () { int X = 0 , w = 0 ; char ch = 0 ; while (!isdigit (ch)) { w |= ch == '-' ; ch = getchar (); } while (isdigit (ch)) { X = (X << 3 ) + (X << 1 ) + (ch ^ 48 ); ch = getchar (); } return w ? -X : X; } int main () { int n = read (); int m = read (); LFS* tree = new LFS (n); for (int i = 1 ; i <= m; i++) { int u = read (); int v = read (); if (u == v) { continue ; } tree->addde (u, v, 1 ); } tree->solve (); delete tree; }
EF
比赛时看到Unrated心头一凉,E题基本想出来了没有写,F题放弃,有空再补上代码吧