1 kosf_

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 4w+

[dp] cf 1437C. Chef Monocarp

题目http://codeforces.com/contest/1437/problem/C思路dp[i][j]dp[i][j]dp[i][j]表示第iii分钟前拿了jjj个盘子的最小代价递推式:dp[i][j]=min(dp[i−1][j],dp[i−1][j−1]+abs(a[j]−i))dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+abs(a[j]-i))dp[i][j]=min(dp[i−1][j],dp[i−1][j−1]+abs(a[j]−i))代码#in

2020-10-28 23:55:44

[大数分解板子] 2020ccpc 威海 D

题目应该之后会放gym的吧 大致是求n(n<=1e18)的质因子的积代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include

2020-10-28 23:35:24

[网络流求最大流板子]

代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<queue>#include<stack>#in

2020-10-17 01:02:18

[思维]cf 1417D

题目思路先把所有的东西都转移到位置1(i=1i=1i=1)上,再由1分发给每一位代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#inc

2020-10-17 00:40:38

[ST表板子]luogu P3865

题目题目链接:https://www.luogu.com.cn/problem/P3865代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>

2020-10-16 17:15:37

[并查集板子] luogu P3367 【模板】并查集

题目题目链接:https://www.luogu.com.cn/problem/P5520代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>

2020-10-16 00:59:07

[组合数] luogu 5520

题目题目链接:https://www.luogu.com.cn/problem/P5520思路可以把第一个当成单独的树,从第二个树开始每棵树斗鱼一个空位置绑定。那么现在还剩下n-m+1个格子。因为最后的答案是有序的 所以求得是排列数,即An−m+1mA_{n-m+1}^mAn−m+1m​代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include&lt

2020-10-16 00:46:47

[组合数] luogu P2822 组合数问题

题目题目链接:https://www.luogu.com.cn/problem/P2822v思路根据公式Cji=Cj−1i+Cj−1i−1C_j^i=C_{j-1}^i+C_{j-1}^{i-1}Cji​=Cj−1i​+Cj−1i−1​,C00=C11=C10=1C_0^0=C_1^1=C_1^0=1C00​=C11​=C10​=1可以递推求出组合数 预处理存下n,mn,mn,m对应答案代码#include<cstdio>#include<cstring>#incl

2020-10-16 00:00:03

[贪心] cf1400 B. RPG Protagonist

题目题目链接:http://codeforces.com/contest/1400/problem/B思路枚举s、ws、ws、w中小的数即可代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<stri

2020-10-15 09:33:37

[dij] cf1430D

题目思路离散化一下 对x\y相等的点连边代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#include<iostream>#include<string>#include<map>#include<queue>#i

2020-10-15 00:29:15

[背包dp+容斥定理] luogu 1450 硬币购物

题目题目链接:https://www.luogu.com.cn/problem/P1450思路如果只询问次数很少 可以完全背包不过这个询问次数很多要超时那么就预处理1—1e51—1e51—1e5的背包的值每次带了d[i]枚硬币 那么d[i]+1之后的硬币就不行s−c[i]∗(d[i]+1)s-c[i]*(d[i]+1)s−c[i]∗(d[i]+1)就是第i个硬币能取的最大钱钱dp[s−c[i]∗(d[i]+1)]dp[s-c[i]*(d[i]+1)]dp[s−c[i]∗(d[i]+1)]就

2020-10-14 23:28:20

[错排] luogu 4071

题目思路错排:给定n元素集合X,它的每一个元素都有一个特定的位置,而现在要求求出集合X的排列中没有一个元素在它指定位置上的排列的数目.递推公式:D1=0 D2=1D_1=0 \ D_2=1D1​=0 D2​=1Di=(i−1)∗(Di−1−Di−2)D_i=(i-1)*(D_{i-1}-D_{i-2})Di​=(i−1)∗(Di−1​−Di−2​)这道题要保证mmm个数等于它的下标,即n−mn-mn−m个数不等于下标 答案为Cmn∗D(n−m)C_m^n*D(n-m)

2020-10-14 22:19:54

luogu 5560

题目题目大意:一棵树有n个结点,每个点的值分别是i2−1i^2-1i2−1,每条边的权值是gcd(i2−1,j2−1)gcd(i^2-1,j^2-1)gcd(i2−1,j2−1) 求树边总权值的最小值题目链接:https://www.luogu.com.cn/problem/P5560思路暴力打表可以发现 只有4 10需要特判 其他都是n−1n-1n−1代码#include<cstdio>#include<cstring>#include<cmath>

2020-09-04 11:46:56

[欧拉函数] 仪仗队 2158

题目题目链接:https://www.luogu.com.cn/problem/P2158思路gcd(x,y)=1的就计入考虑 我们可以寻找gcd(x,y)!=1的 用f[i]记录n-1*n-1里面有多少个公约数为i的数 再减去f[i *k] (k>=2)的值 思想与欧拉定理一致 最后加上x=0y=0的两种情况代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib&

2020-09-03 00:50:59

[excrt] luogu 4777

题目题目链接:https://www.luogu.com.cn/problem/P4777代码#include<bits/stdc++.h>#define int long longusing namespace std;const int INF = 0x3f3f3f3f;int a[100010],b[100010];int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1; y=0; return

2020-08-26 14:50:59

【中国剩余定理+快速乘】

题目题目连接:https://www.luogu.com.cn/problem/solution/P3868思路模板题注意快速乘不是提速的 而是减小数据范围的,因为这道题最大的时候会达到10^32 所以要用快速乘代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#include<ctime>#in

2020-08-24 00:45:21

[cf] 1401 D.Maximum Distributed Tree

题目题目链接:https://codeforces.ml/contest/1401/problem/D思路计算每个边的经过次数,然后把最大的p分配给次数最多的即可。不过要讨论 m>n-1 的时候还有如果要sort千万千万千万别取模代码#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<cctype>#incl

2020-08-23 01:13:28

[逆元] luogu 4942

题目题目链接:https://www.luogu.com.cn/problem/P4942思路这道题最后的ans的形式为ans=l∗10a+(l−1)∗10b+.....+r∗100ans=l*10^a+(l-1)*10^b+.....+r*10^0ans=l∗10a+(l−1)∗10b+.....+r∗100,10%1=910\%1=910%1=9因此变为ans=l+l−1+l−2+...+rans=l+l-1+l-2+...+rans=l+l−1+l−2+...+r用等差数列即可代码#inc

2020-08-21 17:29:47

[dp] hdu 6880 Permutation Counting

题目题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6880思路官方题解:注意:5 4 1 2 3 这个数列里的数字并不是数列a的排序方式,而是下图的 数列c 由数列c构造得到数列a由于每一个数列c只对应一个数列a 我们计算数列c存在的次数即可用二维数组来进行状态转移,dp[i][j]dp[i][j]dp[i][j]表示第i位对应的数字是j对应的种类数如果b[i]==1b[i]==1b[i]==1,那么dp[i+1][j]=dp[i+1][

2020-08-21 01:19:51

【线性求逆元板子】 luogu 3811

题目题目链接:https://www.luogu.com.cn/problem/P3811代码#include<bits/stdc++.h>#define int long longusing namespace std;int inv[3000010];inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');

2020-08-20 16:13:57

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。