2019ccpc女生赛
hdu 6544~6554
1.Ticket
签到题
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int n;
double a[1005];
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &n);
double ans = 0;
for (int i = 1; i <= n; i++){
scanf("%lf", &a[i]);
if(a[i - 1] < 100) ans += a[i];
else if(a[i - 1] < 150) ans += a[i] * 0.8;
else if(a[i - 1] < 400) ans += a[i] * 0.4;
else ans += a[i];
a[i] += a[i - 1];
}
printf("%.2lf\n", ans);
return 0;
}
/**/
2.Gcd
从1~n可以组成[1,(n+1) * n / 2]中的任意一个数，那么把它分成两部分时，正好等分的时候gcd最大，比如和为9时，等分为3，6时gcd最大。那么问题转换为求和((n + 1) * n / 2)的最小因子，直接暴力枚举即可，我潜意识中认为不需要枚举多少个数即可得出答案，但是不会证明。
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
LL n;
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%lld", &n);
LL ans = n * (n + 1) / 2;
for (int i = 2; i <= n; i++){
if(ans % i == 0){
ans /= i;
break;
}
}
printf("%lld\n", ans);
return 0;
}
/**/ 3.Function
首先看假设先取每个二次函数对称轴附近的最小值的点设为xi，如果，那么对于需要对于某些函数的x取值加值，用优先队列维护增量(对于ax^2+bx+c而言,若换成a(x+1)^2+b(x+1)+c,只需要在原来的基础上加上2ax+b即可)，对于和大于m的而言，减去增量最多的可使得ans最小。
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int n, m, num[100005];
int a[100005], b[100005], c[100005];
struct node
{
LL w;
int id, num;
bool operator <(const node &rhs)const{
return w == rhs.w ? a[id] > a[rhs.id] : w > rhs.w;
}
};
LL fun(LL p, int x){
return a[x] * p * p + b[x] * p + c[x];
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(scanf("%d %d", &n, &m) == 2){
for (int i = 1; i <= n; i++){
scanf("%d %d %d", &a[i], &b[i], &c[i]);
}
LL ans = 0;
int sum = 0;
for (int i = 1; i <= n; i++){
int t1 = min(max(1, -b[i] / (2 * a[i])), m - n + 1);
int t2 = t1 + 1;
if(fun(t1, i) < fun(t2, i)) sum += t1, num[i] = t1;
else sum += t2, num[i] = t2;
}
for (int i = 1; i <= n; i++) ans += fun(num[i], i);
if(sum < m){
priority_queue<node> q;
for (int i = 1; i <= n; i++) q.push(node{2 * a[i] * num[i] + a[i] + b[i], i, num[i] + 1});
while(sum < m){
node t = q.top();
q.pop();
ans += t.w;
LL temp = 2 * t.num + 1;
q.push(node{temp * a[t.id] + b[t.id], t.id, t.num + 1});
sum++;
}
}else if(sum > m){
priority_queue<node> q;
for (int i = 1; i <= n; i++){
if(num[i] <= 1) continue;
LL temp = 2 * num[i] - 1;
q.push(node{-temp * a[i] - b[i], i, num[i] - 1});
}
while(sum > m){
node t = q.top();
q.pop();
ans += t.w;
if(t.num > 1){
LL temp = 2 * t.num - 1;
q.push(node{-temp * a[t.id] - b[t.id], t.id, t.num - 1});
}
sum--;
}
}
printf("%lld\n", ans);
}
return 0;
}
/**/ 4.Tree
树链剖分模板题，对于区间修改设置一个num数组统计有多少个1，对于更新操作若num[rt] == tr[rt]，说明区间里都是1或者0，不需要更新。
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
LL n, m, r, v[100005];
int tot, head[100005], size[100005], d[100005], son[100005], top[100005];
int rk[100005], id[100005], cnt, f[100005], num[100005 << 2];
LL tr[100005 << 2];
struct Node
{
int v, next;
}a[100005 << 1];
void read(LL &x){
char ch = getchar();x = 0;
for (; ch < '0' || ch > '9'; ch = getchar());
for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
void read1(int &x){
char ch = getchar();x = 0;
for (; ch < '0' || ch > '9'; ch = getchar());
for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
void dfs1(int x){
d[x] = d[f[x]] + 1, size[x] = 1;
for (int v, i = head[x]; i != -1; i = a[i].next){
v = a[i].v;
if(v == f[x]) continue;
f[v] = x;
dfs1(v);
size[x] = size[x] + size[v];
if(size[v] > size[son[x]]) son[x] = v;
}
}
void dfs2(int x, int tp){
top[x] = tp, id[x] = ++cnt, rk[cnt] = x;
if(son[x]) dfs2(son[x], tp);
for (int v, i = head[x]; i != -1; i = a[i].next){
v = a[i].v;
if(v == f[x] || v == son[x]) continue;
dfs2(v, v);
}
}
void up(int rt){
tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
num[rt] = num[rt << 1] + num[rt << 1 | 1];
}
void build(int l, int r, int rt){
if(l == r){
tr[rt] = v[rk[l]];
if(tr[rt] == 1LL) num[rt] = 1;
return ;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1);
up(rt);
}
void update(int L, int R, int l, int r, int rt){
//printf("%d %d %lld\n", rt, num[rt], tr[rt]);
if(tr[rt] == num[rt]) return ;
if(L <= l && r <= R && l == r){
tr[rt] = sqrt(tr[rt]);
if(tr[rt] == 1) num[rt] = 1;
return ;
}
int mid = (l + r) >> 1;
if(mid >= L) update(L, R, l, mid, rt << 1);
if(mid < R) update(L, R, mid + 1, r, rt << 1 | 1);
up(rt);
}
LL query(int L, int R, int l, int r, int rt){
if(l == L && r == R){
return tr[rt];
}
int mid = (l + r) >> 1;
LL ans = 0;
if(R <= mid) ans = query(L, R, l, mid, rt << 1);
else if(L > mid) ans = query(L, R, mid + 1, r, rt << 1 | 1);
else ans = query(L, mid, l, mid, rt << 1) + query(mid + 1, R, mid + 1, r, rt << 1 | 1);
return ans;
}
void updates(int x, int y){
while(top[x] != top[y]){
if(d[top[x]] < d[top[y]]) swap(x, y);
update(id[top[x]], id[x], 1, n, 1);
x = f[top[x]];
}
if(id[x] > id[y]) swap(x, y);
update(id[x], id[y], 1, n, 1);
}
LL sum(int x, int y){
LL ans = 0;
while(top[x] != top[y]){
if(d[top[x]] < d[top[y]]) swap(x, y);
ans = ans + query(id[top[x]], id[x], 1, n, 1);
x = f[top[x]];
}
if(id[x] > id[y]) swap(x, y);
ans = ans + query(id[x], id[y], 1, n, 1);
return ans;
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
memset(head, -1, sizeof(head));
read(n), read(m);
r = 1;
for (int i = 1; i <= n; i++) read(v[i]);
for (int u, v, i = 1; i < n; i++){
read1(u), read1(v);
a[tot] = Node{v, head[u]}, head[u] = tot++;
a[tot] = Node{u, head[v]}, head[v] = tot++;
}
cnt = 0, dfs1(r), dfs2(r, r);
cnt = 1, build(1, n, 1);
for (int op, x, y, i = 1; i <= m; i++){
read1(op), read1(x), read1(y);
if(op == 0) updates(x, y);
else if(op == 1) printf("%lld\n", sum(x, y));
}
return 0;
}
/**/ 5. Checkout
待补
6. String（已修改，现在正确）
一道莫名AC的dp
dp[i][j][k]表示在当前位置i时，分成j段,当前位置为字母k时最小需要多少次修改次数
num[i]用来记录不同数字个数
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int n, l, K, num[100005];
char s[100005];
int dp[100005][15][28];
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d %d %d", &n, &l, &K);
scanf("%s", s + 1);
// if(K >= n) {printf("0\n"); return 0;}
for (int i = 1; i <= n; i++){
num[i] = num[i - 1] + 1;
if(!i) num[i] = 1;
int j = i + 1;
for (; j <= n; j++){
if(s[j] == s[i]) num[j] = num[i];
else break;
}
i = --j;
}
memset(dp, 0x3f3f3f3f, sizeof(dp));
dp[1][1][s[1] - 'a'] = 0;
for (int i = 0; i < 26; i++) if(i != s[1] - 'a') dp[1][1][i] = 1;
for (int i = 2; i <= n; i++){
for (int j = 0; j <= min(i, K); j++){
int min1 = 0x3f3f3f3f, min2 = 0x3f3f3f3f, tp = max(1, i - l);
for (int k = 0; k < 26; k++) min2 = min(min2, dp[tp][j - 1][k]);
for (int k = 0; k < 26; k++) min1 = min(min1, dp[i - 1][j - 1][k]);
// printf("%d %d %d\n", i, j, min1);
for (int k = 0; k < 26; k++){
if(s[i] - 'a' == k && num[i] - (i - l < 1 ? 0 : num[i - l]) <= 1){
dp[i][j][k] = min1;
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]);
dp[i][j][k] = min(dp[i][j][k], dp[tp][j][k]);
dp[i][j][k] = min(dp[i][j][k], min2 + 1);
}else{
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k] + 1);
dp[i][j][k] = min(dp[i][j][k], min(dp[tp][j][k] + 1, min2 + 1));
}
// printf("%d %d %d %d\n", i, j, k, dp[i][j][k]);
}
}
}
int ans = n;
for (int i = 0; i <= min(K, n); i++) for (int j = 0; j < 26; j++) ans = min(ans, dp[n][i][j]);
printf("%d\n", ans);
return 0;
}
/*
1 1 1
a
3 1 2
abc
9 1 9
abbaaabba
2 1 2
ab
*/
7.Circle
根据数学知道易得当平分两个平分点时面积最大
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
double pi = acos(-1);
int n;
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(scanf("%d", &n) == 1){
double t = 2 * pi / n;
printf("%.6lf\n", 1.0 * (n - 1) / 2 * sin(t) + sin(t / 2));
}
return 0;
}
/**/
8.Clock
把所有时间转化成角度，1s是6度，那么12小时为259200
从小到大排序所有角度
1.对于当前指的时间比a[1]小
2.对于当前指的时间比a[n]大
3.对于当前指的时间在a[1]~a[n]之间
对于每一种情况分别枚举每一个点，考虑顺，逆，先顺再逆，先逆再顺4种情况。
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
const int sum = 259200;
int n, h, m, s, a[86405];
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &n);
scanf("%d %d %d", &h, &m, &s);
int p = (h % 12) * 60 * 360 + m * 360 + 6 * s;
for (int i = 1, A, b, c; i <= n; i++){
scanf("%d %d %d", &A, &b, &c);
a[i] = (A % 12) * 60 * 360 + b * 360 + 6 * c;
}
sort(a + 1, a + 1 + n);
int ans = 0x3f3f3f3f;
if(p <= a[1]){
ans = min(ans, a[n] - p);
ans = min(ans, sum + p - a[1]);
for (int i = 1; i < n; i++){
ans = min(ans, a[i] - p + a[i] + sum - a[i + 1]);
}
for (int i = n; i > 1; i--){
ans = min(ans, p + sum - a[i] + a[i - 1] + sum - a[i]);
}
}else if(p >= a[n]){
ans = min(ans, sum - p + a[n]);
ans = min(ans, p - a[1]);
for (int i = 1; i <= n; i++){
ans = min(ans, a[i] + sum - p + a[i] + sum - a[i + 1]);
}
for (int i = n; i >= 1; i--){
ans = min(ans, p - a[i] + a[i - 1] + sum - a[i]);
}
}else{
int p1 = upper_bound(a + 1, a + 1 + n, p) - a;
int p2 = lower_bound(a + 1, a + 1 + n, p) - a - 1;
if(p1 >= 1 && p1 <= n) ans = min(ans, p + sum - a[p1]);
if(p2 >= 1 && p2 <= n) ans = min(ans, sum - p + a[p2]);
ans = min(ans, p - a[1] + a[n] - a[1]);
ans = min(ans, a[n] - p + a[n] - a[1]);
for (int i = 2; i <= p2; i++){
ans = min(ans, p - a[i] + sum - a[i] + a[i - 1]);
}
for (int i = p1; i <= n; i++){
ans = min(ans, a[i] - p + a[i] + sum - a[i + 1]);
}
}
printf("%.2lf\n", 1.0 * ans);
return 0;
}
/**/
9.Union
待补
10.Tangram
拿笔画画可以看出加一根线时+6，两根线时再+7，三根时再+8.....
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
LL n;
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(scanf("%lld", &n) == 1){
if(!n) printf("7\n");
else printf("%lld\n", 7 + (11 + n) * n / 2);
}
return 0;
}
/**/
11.Tetris
可以发现样例给你的就是最小符合情况，也就是说如果行和列都是4的倍数时才满足，否则no response，然后复制复制复制。。。
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int n, m;
int ans[15][15];
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(scanf("%d %d", &n, &m) == 2){
if(n % 4 || m % 4) printf("no response\n");
else{
ans[1][1] = ans[1][2] = ans[1][3] = ans[2][2] = 1;
ans[2][1] = ans[3][1] = ans[3][2] = ans[4][1] = 2;
ans[1][4] = ans[2][3] = ans[2][4] = ans[3][4] = 3;
ans[3][3] = ans[4][2] = ans[4][3] = ans[4][4] = 4;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if(ans[i][j]) continue;
ans[i][j] = ans[i % 4 ? i % 4 : 4][j % 4 ? j % 4 : 4];
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
printf("%d", ans[i][j]);
}
printf("\n");
}
}
}
return 0;
}
/**/
