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;
}
/**/

 

全部评论

相关推荐

11-22 16:58
天津大学 数据采集
点赞 评论 收藏
分享
11-21 15:28
远景_HRBP
入职远景一年了，说说上班感受
入职远景一年了，说说上班感受，毕竟如果我自己都感受不好，也没啥动力推荐大家来了平时上班还是有点交付压力，但是据我和其他公司人了解后感觉大家都差不多，这个时候就体现出高薪和福利的重要性了，平时运动日，桌游，团建活动非常多，茶歇点心随便吃，来这里都学会了控制自己的饮食公司是处于新能源(风电储能)赛道的头部公司，并且三个业务板块能源动力和智能都入围了新一期的独角兽榜单;在众所周知的就业大环境下(多家知名光伏/新能源车企裁员或毁约)，远景基本上不会出现裁员的情况，且离职率大大低于知名友商;远景的薪资待遇在同行业中也处于顶级;4.同事都是高学历的，且逐渐年轻化（其实这点也有点卷了）出差...
远景公司福利 157人发布
点赞 评论 收藏
分享
10-10 18:54
北京航空航天大学 机械设计/制造
感谢信+1
不回我，我直接给你感谢信有了满意offer也是硬气起来了
无情咸鱼王的秋招日记之薛定谔的Offer：好拒信，偷了，希望有机会用到
点赞 评论 收藏
分享
10-18 00:17
第一拖拉机制造厂拖拉机学院 Java
又来了哈
hr天天给我发消息😅
牛客279957775号：铁暗恋
点赞 评论 收藏
分享
头像
11-26 16:16
山东大学 嵌入式软件工程师
提前预习，Leader的PUA话术
实习er：“你表现得很好，部门领导给你打分都很高，转正希望很大”“过两天新来几个实习生，他们简历很优秀，在XX大厂实习过”“这个项目单独给你做，挤一挤时间完成他，其他实习生我没给，对转正有用”“就你这工作态度，以后哪个公司敢要你？”“这么简单的任务都完成不好，你还想不想转正了？”“你别觉得自己了不起，你离我的要求还差得远呢。”“别人怎么都能做好，就你不行？你是不是能力有问题？”“你要是再这样下去，实习评价肯定好不了。”“我对你很失望，你根本没有发挥出你的潜力。”“你怎么这么笨啊？教了你多少次了还不会，我都怀疑你是不是根本没用心。”“你看看你做的这点事儿，就这水平还大学生呢？我随便找个高中生都比...
你觉得哪一届的校招最难？ 上班苦还是上学苦呢？
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
362857次浏览 3576人参与
# 如果再来一次，你还会选择这个工作吗？ #
94033次浏览 914人参与
# 阿里云管培生offer #
43977次浏览 1018人参与
# 地方国企笔面经互助 #
5575次浏览 13人参与
# ai智能作图 #
6516次浏览 110人参与
# 发工资后，你做的第一件事是什么 #
2868次浏览 9人参与
# 百度开奖 #
220492次浏览 1408人参与
# 我的实习求职记录 #
6094189次浏览 83755人参与
# 上班到公司第一件事做什么？ #
14316次浏览 162人参与
# 听到哪句话就代表面试稳了or挂了？ #
95730次浏览 807人参与
# 华为工作体验 #
108566次浏览 850人参与
# 网易求职进展汇总 #
38647次浏览 298人参与
# 如何写一份好简历 #
614620次浏览 8690人参与
# 如果有时光机，你最想去到哪个年纪？ #
26091次浏览 540人参与
# 面试体验感最好的是哪家？ #
91064次浏览 879人参与
# 牛客租房专区 #
996次浏览 64人参与
# 如何一边实习一边秋招 #
1001216次浏览 12707人参与
# 实习中的菜狗时刻 #
279407次浏览 2750人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
38340次浏览 346人参与
# 国央企薪资爆料 #
15601次浏览 118人参与
# 腾讯求职进展汇总 #
202808次浏览 1676人参与
# 阿里求职进展汇总 #
71116次浏览 764人参与
牛客网
牛客企业服务