shyyhs - 个人主页动态

2021-01-26 15:53

A. Odd Divisor 奇数是没有2的因子,那么我们将他反复除2即可. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+50; int w[N]; int main() { int T; //T=1; cin>>T; while(T--) { ll n; cin>>n; if(n%2==0) while(n%2==0) n/=2; if(n>1) puts("YES"); else puts("NO"); } return 0;...

lpt的小屋

0 点赞评论收藏

2021-01-25 20:30

湖南工业大学 C++

get一个可爱的小孙子～

牛油的日常生活

0 点赞评论收藏

2021-01-25 15:16

湖南工业大学 C++

[IOI2011]Race

前言: 从12点T到下午三点,原本以为ioi是个大毒瘤.1.卡vector.2.卡unordered_map/map.3.卡清空方式.结果!!!什么都不卡,tm find root之后不搜root,直接搜子节点,我真是个大***... 思路: 直接点分治即可..都没啥好讲的,就是个板子. 代码: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5,M=1e6+6; struct node{ int to,val; }; vector<node>g[N]...

lpt的小屋

0 点赞评论收藏

2021-01-24 21:44

湖南工业大学 C++

[HAOI2006]均分数据

随机的次数多了,代码轻松跑过. #include <bits/stdc++.h> using namespace std; int main() { int n,m,a[23],x[23];cin>>n>>m;double tot=0; for(int i=1;i<=n;i++) { cin>>a[i];tot+=a[i]; }int T=1000000;tot/=m;double ans=0x3f; while(T--) { memset(x,0,sizeof x); random_shuffle(a+1,a+1+n); for(int ...

lpt的小屋

0 点赞评论收藏

2021-01-24 18:52

湖南工业大学 C++

Contest 1

A - String Game  这种问最多多少次..不是dp就是二分/三分/贪心.开始以为是检测子串,看了下样例2,结果发现是检测子序列..白写了个哈希.二分答案即可. #include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; const int N=2e5+5; char a[N],b[N],c[N]; int w[N]; int len,sz; bool vis[N]; /*ull h_b,h[N],base=131,k[N]; ull get(int l,int r) { re...

lpt的小屋

0 点赞评论收藏

2021-01-24 11:27

湖南工业大学 C++

加分二叉树

前言: 树的遍历,以前学的时候就很懵逼...  今天就来记录下树的四种遍历.    思路: 这题思路比较简单.区间dp一下即可. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=32; ll w[N]; ll f[N][N];//这个区间的最优答案是多少. int root[N][N];//这一段的根是多少. ll solve(int l,int r) { if(f[l][r]) return f[l][r]; if(l==r) return f[l][r]=w[l]; ...

lpt的小屋

0 点赞评论收藏

2021-01-23 23:42

湖南工业大学 C++

比赛

emmm水题)... #include <bits/stdc++.h> using namespace std; const int N=13; struct ANS{ double a,b,c; }f[N]; int n=12; double ans[N]; void dfs(int u,int num,double res)//做了几个,做对几个,的概率. { if(u==13) {ans[num]+=res;return;} dfs(u+1,num+1,res*(1-(1-f[u].a)*(1-f[u].b)*(1-f[u].c))); dfs(u+1,num,res*(1-...

lpt的小屋

0 点赞评论收藏

2021-01-22 14:49

湖南工业大学 C++

Removal

简单的dp就好了,去重的话,就是记录上一个x所在的位子,把它们全部删除就好了.emmm不难吧 #include <bits/stdc++.h> using namespace std; const int N=1e5+50,M=12; const int mod=1e9+7; typedef long long ll; ll f[N][M]; int last[M]; int main() { int n,m,k; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { for(int i=0;i<=n;i++) for(int ...

lpt的小屋

0 点赞评论收藏

2021-01-22 13:17

湖南工业大学 C++

Alliances

前言: 这个每日一题对我来说稍微复杂了亿点点... 思路: 首先的题目的条件就是所有点的lca到所有点的路径都被标记了.我们要求点V到这些点集的一个最小距离. 假如这个点集的LCA和V的lca不是LCA的话,那么显然的一个结论距离就是V到lca的距离. 假如不是,那么V一定位于LCA的子树中.这是我们将树的dfs序求出,然后就简单了许多.距离就是要么是dfs序大于它的第一个点,要么就是小于它的第一个点.然后求个lca即可. (看上去好像很简单...其实确实不难.) 代码: #include <bits/stdc++.h> using namespace std; const int...

lpt的小屋

0 点赞评论收藏

2021-01-21 21:15

湖南工业大学 C++

换个角度思考

前言: 这题假如用树状数组的话,还是很不错的一个题的. 思路: 直接把两个序列都按权值排序,把查询的以及原序列,这样做的好处就是保证我插入的一定是合法的,然后直接查询即可. 代码: #include <bits/stdc++.h> using namespace std; const int N=1e5+50; struct Query{ int l,r,k,id,ans;//询问区间[l,r]小于等于k的个数.存下查询时间轴以及答案. }q[N],w[N]; int n,m,c[N]; int lowbit(int x) { return x&(-x); } void a...

庄旭东：在计算出所有的q[q[i].id].ans后，不能进行sort(q+1,q+1+m,cmp);这个排序，因为你在存储ans时是按原来坐标的位置存储的，如果再对坐标排序会打乱原本正确的顺序，把sort(q+1,q+1+m,cmp);去掉应该就没问题了

lpt的小屋

0 点赞评论收藏

2021-01-22 13:25

已编辑

湖南工业大学 C++

明天任务--因为要学的算法有点多/我看了没思路的题/代码较长的题.

·Color ·边的染色 ·Jamie and Tree ·[HNOI2017]礼物+cf上场的题,虽然只有四个题目和几个思维题,但是这五个题估计不好写哦= =.(虽说明天不需要浪费时间)今天继续写些不是太难的题!加油.

lpt的小屋

0 点赞评论收藏

2021-01-21 20:01

湖南工业大学 C++

Paint Box

一直不是很懂容斥原理的原因,学二分图的时候再看看!我们很容易知道,求给n个位子上色,可以最多使用k种颜色的方案数是.由容斥原理想到可以把最多->等于.那么就是最多使用k种颜色-最多使用k-1种颜色+最多使用k-2种颜***r>那么直接这样做就好了.(值得注意的是:因为取模了,所以会存在负数的情况,记得对负数取模~)代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; const int N=1e6+5; ll qp(ll a,ll b)...

lpt的小屋

0 点赞评论收藏

2021-01-21 14:10

湖南工业大学 C++

MMSet2

将求树的直径的过程进行模拟即可~ #include <bits/stdc++.h> using namespace std; const int N=3e5+50,M=20; vector<int>v[N]; int dep[N],w[N],f[N][M]; void dfs(int u,int fa) { dep[u]+=dep[fa]+1; f[u][0]=fa; for(int i=1;i<20;i++) f[u][i]=f[f[u][i-1]][i-1]; for(int x:v[u]) { if(x!=fa) dfs(x,u); } } int lca(...

lpt的小屋

0 点赞评论收藏

2021-01-20 23:13

已编辑

湖南工业大学 C++

树的直径

之前一个题目求树的直径,我是暴力树形dp的..但是其实是有个性质的,树的直径一定是含有一个深度最深的点.反证法:假如我当前树的直径不含深度最深的点,那么我一定存在一条路径从深度最深的点到另外一个点的距离比当前dis更大,因为树上任意两点都是有路径的.而树上路径的距离公式是.那么假设我现在最深的点到其中两个点的距离最大值最小,假如我现在这个点和这两个点都没有重叠部分,必定是大于的.假如有重叠部分且是两个部分的公共重叠部分,也必定大于,假如不止公共部分,那么和另外一个距离减少的同时,另外一个在增大.同时也可以证明,任意一个距离最远的点都可以.证毕.

lpt的小屋

0 点赞评论收藏

2021-01-20 21:41

湖南工业大学 C++

「火」皇家烈焰

直接按题意模拟dp即可.. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5,M=2; const int mod=1e9+7; char s[N]; ll f[N][M][M];//到了第i个位子,i这个位子有无火,i+1这个位子有无火. int main() { scanf("%s",s+1); int n=strlen(s+1); f[0][0][1]=f[0][0][0]=1; for(int i=1;i<=n;i++) { if(s[i]=='0...

lpt的小屋

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：