2018期初考标准程序
pantw
2018-03-18 18:04:27
# D1T1 song
```cpp
#include <cstdio>
int h = 17, m = 56, s = 0;
int main() {
freopen("song.in", "r", stdin);
freopen("song.out", "wb", stdout);
int n;
scanf("%d", &n);
m += n * 4;
s += n * 4;
m += s / 60;
s %= 60;
h += m / 60;
m %= 60;
h %= 24;
printf("%d %d", h, m);
fclose(stdin);
fclose(stdout);
return 0;
}
```
------------
# D1T2 equation
```cpp
#include <cstdio>
#include <cstring>
#define Lovelive long long
int T, n, k, s[100100];
inline int lb(int x) { return x & -x; }
inline void add(int p, Lovelive x) { for(++p; p <= k + 10; p += lb(p)) s[p] += x; }
inline Lovelive sum(int p) { Lovelive ret = 0; for(++p; p; p -= lb(p)) ret += s[p]; return ret;}
void inter(int l, int r, Lovelive x) { if(l <= r) add(l, x), add(r + 1, -x); else inter(0, r, x), inter(l, k - 1, x); }
int main() {
freopen("equation.in", "r", stdin), freopen("equation.out", "wb", stdout);
scanf("%d", &T);
for(int tt = 1; tt <= T; ++tt) {
Lovelive ans = 0, cnt = 0;
scanf("%d%d", &n, &k);
memset(s, 0, sizeof s);
for(int i = 1; i <= n; ++i) {
Lovelive sq = (Lovelive) i * i;
cnt += i / k;
if(i % k) inter((sq + 1) % k, (sq + i) % k, 1);
ans += sum(sq * i % k) + cnt;
}
printf("Case #%d: %lld\n", tt, ans);
}
return fclose(stdin), fclose(stdout), 0;
}
```
------------
# D2T1 water
```cpp
#include <cstdio>
#define maxn 1000010
int f[maxn], n, ans = 0;
int main() {
freopen("water.in", "r", stdin);
freopen("water.out", "wb", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", f + i);
for(int i = 1; i <= n; i++) if(f[f[f[i]]] == i) ++ans;
printf("%d", ans / 3);
fclose(stdin);
fclose(stdout);
return 0;
}
```
------------
# D2T2 string
```cpp
#include <cstdio>
#define Lovelive long long
char s[333333], x[233];
int cnt[233], n;
Lovelive ans;
inline Lovelive max(Lovelive a, Lovelive b) { return a > b ? a : b; }
Lovelive calc(int len) {
Lovelive match = 0;
for(int i = 0, j = 1; i < n; i++) {
if(s[i] == x[j]) j++;
if(j > len) match++, j = 1;
}
return (Lovelive) match * match * len;
}
void dfs(int len) {
for(int i = 0; i < 3; i++) {
x[len] = 'a' + i;
cnt[i]++;
if(cnt[i] <= 2) {
ans = max(ans, calc(len));
dfs(len + 1);
}
x[len] = 0;
cnt[i]--;
}
}
int main() {
freopen("string.in", "r", stdin);
freopen("string.out", "wb", stdout);
scanf("%d%s", &n, s);
ans = n;
dfs(1);
printf("%lld", ans);
fclose(stdin);
fclose(stdout);
}
```
------------
# D3T1 plant
```cpp
#include <cstdio>
#define Lovelive long long
#define INF 0x3F3F3F3F
int main() {
freopen("plant.in", "r", stdin);
freopen("plant.out", "wb", stdout);
Lovelive n, k, a, besta, besti;
scanf("%lld%lld%lld", &n, &k, &a);
besta = a, besti = 1;
for(int i = 2; i <= k; i++) {
scanf("%lld", &a);
if(n % a < n % besta || (n % a == n % besta && a > besta)) besta = a, besti = i;
}
printf("%lld %lld", besti, n / besta);
fclose(stdin);
fclose(stdout);
}
```
------------
# D3T1 game
```cpp
#include <cstdio>
#include <algorithm>
#include <functional>
#define maxn 200010
#define Lovelive long long
int head[maxn], nxt[maxn], to[maxn], ec;
int v[maxn];
Lovelive val[maxn], leaf[maxn], ln = 0, ans = 0;
inline void add(int u, int v) {
nxt[++ec] = head[u], head[u] = ec, to[ec] = v;
}
void dfs(int x) {
if(!head[x]) leaf[++ln] = val[x];
else for(int e = head[x]; e; e = nxt[e]) {
val[to[e]] = val[x] + v[to[e]];
dfs(to[e]);
}
}
int main() {
freopen("game.in", "r", stdin);
freopen("game.out", "wb", stdout);
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) scanf("%d", v + i);
for(int i = 1; i < n; i++) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
val[1] = v[1];
dfs(1);
std::sort(leaf + 1, leaf + n + 1, std::greater<Lovelive>());
for(int i = 1; i <= k; i++) ans += leaf[i];
printf("%lld", ans);
fclose(stdin);
fclose(stdout);
return 0;
}
```