正文

gym-101147j.whistle'snewcar(代码片段)

Pneuis  Pneuis  2022-11-05  787

关键词：

题意：

　　给出一颗有点权和边权的树。求每一个点u的子树中有多少点v，使得点v到点u的距离小于等于点v的权值。

题解：

　　对于每一个点，倍增的预处理出他的祖宗节点及距离。根据预处理的结果求出每个点能到的最远的祖宗节点。

　　设点u能到的最远祖宗节点为v。利用差分的思想在点tree[u]+1，点tree[v]-1。

　　最后每个点的答案就是子树的tree[]和。

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int maxn = 5e5+10;
int t, n, u, v, tree[maxn], ans[maxn];
ll c, x[maxn];
struct node 
    ll val; int nod;
;
node fa[32][maxn], tmp;
vector<node> g[maxn];
void dfs(int u, int pre) 
    fa[0][u].nod = pre;
    int len = g[u].size();
    for(int i = 0; i < len; i++) 
        int v = g[u][i].nod;
        if(v==pre) 
            fa[0][u].val = g[u][i].val;
            continue;
        
        dfs(v, u);
    

void dfs_double(int u, int pre) 
    int len = g[u].size();
    for(int i = 0; i < len; i++) 
        int v = g[u][i].nod;
        if(v==pre) continue;
        dfs_double(v, u);
    
    tree[u]++;
    ll tv = x[u];
    for(int k = 31; k >= 0; k--) 
        if(fa[k][u].val <= tv) 
            tv -= fa[k][u].val;
            u = fa[k][u].nod;
        
    
    tree[u]--;

void solve(int u, int pre) 
    int len = g[u].size();
    for(int i = 0; i < len; i++) 
        int v = g[u][i].nod;
        if(v==pre) continue;
        solve(v, u);
    
    for(int i = 0; i < len; i++) 
        int v = g[u][i].nod;
        if(v==pre) continue;
        ans[u] += tree[v]+ans[v];
    

int main() 
    freopen("car.in","r",stdin);
    scanf("%d", &t);
    while(t--) 
        scanf("%d", &n);
        memset(tree, 0, sizeof(tree));
        memset(ans, 0, sizeof(ans));
        for(int i = 1; i <= n; i++) g[i].clear();
        for(int i = 1; i <= n; i++) scanf("%lld", &x[i]);
        for(int i = 1; i < n; i++) 
            scanf("%d%d%lld", &u, &v, &tmp.val);
            tmp.nod = v;
            g[u].push_back(tmp);
            tmp.nod = u;
            g[v].push_back(tmp);
        
        dfs(1, 1);
        for(int k = 0; k < 31; k++) 
            for(int v = 1; v <= n; v++)  
                fa[k+1][v].nod = fa[k][fa[k][v].nod].nod;
                fa[k+1][v].val = fa[k][v].val+fa[k][fa[k][v].nod].val;
            
        
        dfs_double(1, 0);
        solve(1, 0);
        for(int i = 1; i <= n; i++) 
            printf("%d", ans[i]);
            if(i==n) puts("");
            else printf(" ");

View Code

gym-101147b.street(代码片段)

题意：　　大矩形代表市场，大矩形当中有很多小矩形样式的伞。这些小矩形都贴着大矩形的左边或者右边且互不相交。小矩形以外的地方都是阳光。求经过大矩形时在阳光下的最短时间。题解：　　最短路的做法。起点和终点... 查看详情

gym101147g第二类斯特林数

大致题意：n个孩子，k场比赛，每个孩子至少参加一场比赛，且每场比赛只能由一个孩子参加。问有多少种分配方式。分析：k>n，就无法分配了。k<=n。把n分成k堆的方案数乘以n的阶乘。N分成k堆得方案数即第二类斯特林数http... 查看详情

gym-101147a.thegameofosho(代码片段)

题意：　　一共有G个子游戏，一个子游戏有Bi,Ni两个数字。两名玩家开始玩游戏，每名玩家从N中减去B的任意幂次的数，直到不能操作判定为输。问谁最终能赢。题解：　　当Bi为奇数的时候，显然Bi的所有次幂都是奇数，那么答... 查看详情

gym-101147c.thewall(代码片段)

题意：　　长和宽分别为M+N/2，N的矩形中。有很多敌人的点。有两种方法消灭敌人。　　1.N个桶，第i个桶可以消灭i-1<=x<i中的敌人。2.M个摆（半圆）每个摆可以消灭距离他前面不超过1以内的敌人。第i个摆的圆心在（N/2，i-1... 查看详情

gymgym101147g第二类斯特林数

题目链接：http://codeforces.com/gym/101147/problem/G题意：n个人，去参加k个游戏，k个游戏必须非空，有多少种放法?分析：第二类斯特林数，划分好k个集合后乘以阶乘； 1#include<bits/stdc++.h>23usingnamespacestd;45constintmaxn=1010;6const... 查看详情

python中列表/字符串切片slice？

...=len(lst[3*3::3])*[0]output:[0,1,2,3,4,5,6,7,8,0,10,11,0,13,14,0](2)、s='0123456789's[::-1]'9876543210's[::-2]'97531's[::-3]'9630's='0123456789's[:2:-1]'9876543's[1:2:-1]''s[2:1:-1]'2's[2::-1]'210's[-1:-2:-1]'9's[-1:-5:... 查看详情

英语——'s和s'和s的区别

举个例子吧，student‘s是表示学生的，名词单数形式的所有格students‘是表示学生们的，名词复数形式的所有格students是表示学生们，名词的复数形式查看详情

关于c语言宏定义输出

#defineTOUPPER(c)('a'<=(c)&&(c)<='z'?(c)-'a'+'A':(c))设s是一个足够大的字符数组，i是int型变量，则以下代码段的输出是：strcpy(s,"abcd");i=0;putchar(TOUPPER(s[++i]));奇怪，不应该是B吗？为何输出了D？？解释下... 查看详情

django之logging配置(代码片段)

....#日志配置BASE_LOG_DIR=os.path.join(BASE_DIR,"log")LOGGING='version':1,#保留字'disable_existing_loggers':False,#是否禁用已经存在的日志实例'formatters':#定义日志的格式'standard':'format':'[%(asctime)s][%(threadName)s:%(t... 查看详情

65.validnumber(代码片段)

...=false,exp=false,sign=false;intn=s.size();for(inti=0;i<n;++i)if(s[i]=='')if(i<n-1&&s[i+1]!=''&&(num||dot||exp||sign))returnfalse;elseif(s[i]=='+'||s[i]=='-')if(i>0&&s[i-1]!='e'&&s[i-1]!='')returnfalse;sign=true;... 查看详情

pandas的简单使用(代码片段)

...#Series可以使用index设置索引，可以重复s=pd.Series(['a','b','c','d','e'],index=[100,200,100,400,500])print(s)#Series可以用字典实例化d='b':1,'a':0,'c':2s=pd.Series(d)print(s)#切片s=pd.Series... 查看详情

c语言char输出乱码

...include<string.h>voidprocess(chars[],chars1[]) inti; for(i=0;s[i]!='\0';i++) if(s[i]>='a'&&s[i]<='w') s1[i]=s[i]-32+3; elseif(s[i]>='x'&&s[i]<='z') s1[i]=s[i]-32-23; elseif(s[i]>='A'&&s[i]<='W') s1[i]=s[i]+3;... 查看详情

sql中case,when,then,else的用法是啥?

...一种写法：复制代码SELECTs.s_id,s.s_name,s.s_sex,CASEWHENs.s_sex='1'THEN'男'WHENs.s_sex='2'THEN'女'ELSE'其他'ENDassex,s.s_age,s.class_idFROMt_b_studentsWHERE1=12、第二种写法SELECTs.s_id,s.s_name,s.s_sex,CASEs.s_sexWHEN'1'THEN'男&... 查看详情

天梯训练赛(代码片段)

...h(),now=1;inta=0,b=0;intfa=1,fb=1,pos;for(inti=0;i<len;++i)if(s[i]<'0'||s[i]>'9')if(now==1)fa=0;elseif(now==2)fb=0;break;if(s[i]==''&&s[i+1]<='9'&&s[i+1]>='0')pos=i+1;now=2;if(s[i]==''&&(s[i+1]>'9'||s[i... 查看详情

java示例代码_使用扫描仪'；在main和#39；s body中定义的方法（'；s body）中的输入（用于main和#39；s body中的swtich情况）

java示例代码_使用扫描仪'；在main和#39；s body中定义的方法（'；s body）中的输入（用于main和#39；s body中的swtich情况）查看详情

python一个列表中元素为元祖，想要根据元祖的第二个值进行排序，怎么做

比如对a=[('s',0,'<pian>'),('s',706,'<pian>'),('e',14,'</pian>'),('s',14,'<pian>'),('e',7,'</pian>'),('s',6,'<pian>')]排序，根据每个元祖中数字大小对列... 查看详情

inferredtype's'fortypeparameter's'isnotwithinitsbound(代码片段)

springboot报错内容：Inferredtype‘S’fortypeparameter‘S’isnotwithinitsbound;shouldextendsxxxxxx/**根据id查询*/@GetMapping("/student/id")publicStudentfindById(@PathVariable("id")Integerid)returnstudentRespository.findOne(id);用以上方法findOne(id);报错，经过网上查询资料... 查看详情

如何用substringsql从字符串中截取数字函数

...2和3截取并转换成数字格式（2*16+3）参考技术Aselectleft('2箱+3部',CHARINDEX('+','2箱+3部')-2)+'*16+'+left(right('2箱+3部',len('2箱+3部')-CHARINDEX('+','2箱+3部')),len(right('2箱+3部',len('2箱+3部... 查看详情