1 咖啡店老板娘

尚未进行身份认证

厉害的人可真多啊

等级
TA的排名 7w+

CodeForces - 1118F1 Tree Cutting (Easy Version)(DFS)

????‍♀️ ????‍♀️ ????‍♀️//目的:找到一个这样的结点,他的子树包含所有的蓝色/红色,且不包含另一种颜色//所以记录下每个节点的子树的蓝色,红蓝结点分别有多少//然后枚举每条边检验int n,ans;int a,b;//一共有多少蓝/红色int tag[MAXN];//某点的颜色int col[3][MAXN];//某点的子树的颜色个数int dep[MAXN];//深度vec...

2020-02-29 17:05:05

CodeForces - 1118C Palindromic Matrix (模拟,STL,排序)

????‍♀️ ????‍♀️ ????‍♀️重点在想清楚次数多的优先安排4,不会出现次数大的多次安排在2的地方。//先把多的安排在需要四个的//因为2是4的约数,不会出现次数大于等于四次还必须安排在2的情况int num[MAXN];int ans[22][22];bool solve(){ int n;cin>>n; vector<pii>v; rp...

2020-02-29 12:20:34

2020 . 02 . 26~2020 . 02 . 28总结

开学前的焦虑,三天就写了俩题,给跪了。

2020-02-29 11:40:12

HDU - 1540 Tunnel Warfare (STL,思维)

???? ???? ????查询某村庄连续未摧毁村庄即查询该村庄左右两次第一个摧毁村庄的距离,这样我们一开始将0,n+1插入即可signed main(){ int n, m; while (cin >> n >> m) { set<int> se; stack<int> st; se.in...

2020-02-26 11:09:16

HDU - 4630 No Pain No Game(离线,树状数组)

????‍♂️ ????‍♂️ ????‍♂️题意:一个长为n的数组,m次查询,询问(l,r)中两个数字之间GCD(l,r中任意一对,只要GCD最大即可)(1)处理出每个数字的约数,GCD一定是在这个区间中出现两次即以上的最大的那个约数(2)对于查询按照l排序之后,我们再从后往前更新最大约数,如果这个约数在该位置之后出现过,我们就在他出现的后一个位置更新他(查询时查询r)(3)杭电数据好像有误,如11...

2020-02-26 10:47:13

CodeForces - 1131D Gourmet choice (拓扑关系,并茶几)

???? ???? ????//(1)相等的归于一个并茶几中//(2)大小关系通过拓扑排序判断//(3)拓扑排序的同时构造答案//小于 < int n,m;int f[MAXN];char s[1111][1111];int ans[MAXN];int deg[MAXN];//入度vector<int>mp[2222];int find(int x) { return x=...

2020-02-25 22:11:13

算法复习---拓扑排序

概念DAG:有向无环图拓扑排序:在一个有向图中,对所有的节点进行排序,要求没有一个节点指向它前面的节点。基本流程利用队列,先安排入度为0的点,把这些点指向的点的度数减一,继续寻找入度为0的点入门博...

2020-02-25 22:09:29

HDU - 1394 Minimum Inversion Number (逆序数)

???? ???? ????(为了方便处理把a[ i ]全都加一处理)注意到每次更改都是从第一个位置挪到最后一个位置,可知每次挪动,减少a[ i ] - 1个逆序对,增加n-a[ i ]个逆序对,所以我们利用树状数组维护出未挪动的时候的答案,对每次挪动直接计算即可。int n,c[MAXN],a[MAXN];void update(int x, int v){while (x <= n) {c[x] ...

2020-02-25 20:42:52

HDU - 2227 Find the nondecreasing subsequences(离散化,树状数组,递推)

???? ???? ????容易得到这样一个式子,假设dp[ i ]表示以i结尾的子序列个数,则:这样我们以ai为下标,维护一个前缀和即可,最后的答案就是所有dp的和(即更新到最后mx的前缀和),但是ai是1e9的,所以还需要离散化一下。最后就是注意多组输入,,,WA了好多次原来错在这里#define int llconst int mod = 1e9 + 7;int mx,w[MAXN], hs[M...

2020-02-25 18:47:49

HDU - 3874 Necklace(离线,前缀和,树状数组)

???? ???? ????(1)考虑维护出一个无重复元素的前缀,例如现在枚举到以 i 结尾的前缀,那么所有以 i 结尾的区间均可以直接查询出。(2)维护前缀的过程中,我们记录下每个数字最后出现的位置,并将之前出现过的贡献清零(因为该元素越靠右的位置越有可能对之后的答案有贡献)int n,w[MAXN];ll c[MAXN],ans[MAXN];void update(int x,int v){ whil...

2020-02-25 17:51:39

POJ - 1456 Supermarket (贪心)

???? ???? ????和这道题一模一样贪心,首先肯定尽量卖出去利润大的,其次每次卖出商品的时候我们尽量在最后期限卖出(为以后卖东西腾地方),这样就和cf那道题目一样了,只不过这道题维护的是-1//CE代码,实在懒得改了。。。int f[MAXN];int find(int x){ return f[x]==-1?x:f[x]=find(f[x]);}signed main(){ ...

2020-02-25 16:30:17

ZOJ 3261 Connections in Galaxy War(逆向并茶几,离线处理)

???? ???? ????q次操作,每次操作删去某边或询问与某点相连的权值最大并且序列最小的点(权值要比该点大)的序号并不会用并茶几处理删边,所以我们记录下每次操作离线处理,倒序增边,最后输出答案即可有一个要注意的地方就是,因为是无向边,为了 保证我们查询的时候能查到某边,我们规定一边中序号小的在前。(刚开始栽在这里了)最后就是两个样例之间有空行。//摧毁边---->倒着加边int n,m,q,...

2020-02-25 15:42:38

HDU - 3461 Code Lock (并茶几,区间合并)

???? ???? ????题读了半天题意:有一个长为n的字符串,同时该字符串上有m 个可以一起翻转的区间,如果两种字符串可以通过翻转相同,则视为一种字符串,问你长为n 的这个字符串有几种情况。比如长为1的时候,如果没有可翻转的字符串,那就有26种情况,如果1这个位置可以翻转,那么a=b=c=d=…一共就是一种字符串。(1)容易发现如果没有可翻转的字符串,答案即为26^n(2)每加入一个区间,方案数就减去...

2020-02-25 14:27:52

Codeforces Round #624 (Div. 3) D - Three Integers (枚举)

???? ???? ????枚举B,这样A就是B的因子,C可以根据常识算出,枚举B的时候记得把范围扩大一点,不然会被hack(指了指自己)void solve(){ int a,b,c;cin>>a>>b>>c; int ans=-1,x=a,y=b,z=c; for(int i=1;i<=20000;++i) { in...

2020-02-25 10:32:04

CodeForces - 1315D Recommendations (集合,贪心)

???? ???? ????题意:每个点两个属性,a[ i ] ,t[ i ](给该点a[ i ] +1的消耗),现在要求ai各不相同,问你最小花费(1)如果某点的t小,只要该点的ai有重叠,肯定优先改变该点,所以排序的时候我们首先按照 t 排序(2)每次选择花费时间最小的改变—>尽量让大的不变,对于t大的点,优先加入并茶几中,以每个集合的父亲结点表示当前集合元素最小可达到位置,枚举元素并更新即可(3...

2020-02-24 17:08:39

CodeForces - 1313C2 Skyscrapers (hard version) (单调栈+DP)

???? ???? ????为什么当时没有静下心多想一步呢,,,哦对因为到饭点了//某点做最高峰,//左边的贡献值:左边第一个小于等于他的点的predp+m[i]*这两点之间的距离//右边的贡献值:右边第一个小于等于他的点的sufdp+m[i]*这两点的距离#define int llint n,a[MAXN];int pre[MAXN],suf[MAXN];int predp[MAXN],suf...

2020-02-24 15:10:16

CodeForces - 1130D2 Toy Train(枚举)

???? ???? ????由于火车运载量无限,所以运送每个车站的糖果是相互独立的,所以求从某点开始运送的最远距离,就是枚举该点到每个车站运送的距离,最后取一个最大值。//从某点离开运送某车站的糖果需要的时间//两点之间的距离+n*(sz-1)+最后一个糖果运送所需要的距离int n,m;int dis(int i,int j){return (j>=i?j-i:(n-(i-j)));}//i到 j...

2020-02-24 11:20:29

CodeForces - 1130B Two Cakes (逆向思维)

???? ???? ????看懂题很重要,,给一个1~n双倍的排列,问两个人买蛋糕走的最少的步数。我们把1~n每个数字出现的位置存下来,贪心的让一组尽量靠左,另一组尽量靠右 。#define int llint pos[2][MAXN];void solve(){ int n;cin>>n; rpp(i,n*2) { int x;cin>&gt...

2020-02-23 20:14:45

Codeforces Round #622 (Div. 2) B - Different Rules (思维)

???? ???? ????做第一个写题解的崽让排名靠前 就选第一场排名的前一位 和第二场的后面第二位 ,让排名靠后就尽量让平的多inline void solve(){ int n, x, y; cin >> n >> x >> y; if (x > y) swap(x, y); int minn = 0, m...

2020-02-23 20:07:00

CodeForces - 1133F2 Spanning Tree with One Fixed Degree (并茶几,生成树)

???? ???? ????题意:是否能从给出的图中得出一个生成树,使树中1的度数为k(1) 若原图中1的度数小于k ,显然不行(2)若原图中1的度数大于k,我们需要删除一部分与1相连的边,先把与1相连的所有边删除,剩下我们要添加的1边就需要将这些连通块连接起来,如果连通块个数大于k显然也不行(3)将所有连接起连通块的1边加入答案,之后再随便选几个边直到满足1的度数为k为止,再次根据已经添加到答案的边做一次...

2020-02-23 15:50:34

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。