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;
}
};
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++) ans += a[i] + b[i] + c[i];
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{3 * a[i] + b[i], i, num[i] + 1});
while(sum < m){
node t = q.top();
q.pop();
ans += t.w;
int 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;
int 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){
int 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]表示在当前位置i时，分成j段最小需要多少次修改
1.对于i-l+1~i进行一次更新时表示这段长度修改成相同的颜色或者修改成和前面相同的颜色的最小次数
2.如果i-l+1 ~ i这段上颜色相同那么dp[i][j] = min(dp[i][j], dp[i - l][j - 1]);
3.如果i-l+1~i这段上的颜色和前面的相同那么dp[i][j] = min(dp[i][j], dp[i - l][j]);
代码有点乱。。
/**/
#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];
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d %d %d", &n, &l, &k);
scanf("%s", s);
int len = strlen(s);
for (int i = 0; i < len; i++){
num[i] = num[i - 1] + 1;
int j = i + 1;
for (; j < len; j++){
if(s[j] == s[i]) num[j] = num[i];
else break;
}
i = --j;
}
memset(dp, 0x3f3f3f3f, sizeof(dp));
dp[0][0] = 1, dp[0][1] = 0;
for (int i = 1; i < len; i++){
for (int j = 1; j <= min(i + 1, k); j++){
int t = max(0, i - l);
dp[i][j] = min(dp[t][j - 1] + 1, dp[t][j] + 1);
if(num[i] - num[t] <= 1){
dp[i][j] = min(dp[i][j], dp[t][j - 1]);
if(s[max(t - 1, 0)] == s[i]) dp[i][j] = min(dp[i][j], dp[t][j]);
}
}
}
printf("%d\n", dp[n - 1][min(k, len)]);
return 0;
}
/**/
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;
}
/**/
查看7道真题和解析
投递牛客等公司10个岗位 >