2 zzulihrs

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 17w+

acwing 97. 约数之和

传送门以下定理参考博客#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll mod = 9901;ll a, b;ll ksm(ll x, ll y){ ll ans = 1; x%=mod; while(y) { if(y&1) ans = (ans*x)%mod; x = (x*x)%mod;

2020-07-03 16:13:20

acwing 95. 费解的开关

传送门枚举第一行的状态,然后向下进行递推,假设我们枚举的每个答案都是正确的,那就不可能从第一行进行翻转,此时如果第一行还有0那么就必须是第二行对应位置进行翻转,然后就依次向下进行递推。还有一种写法是从全1的情况逆向翻转找到所有合法情况进行hash,本题数据小也能过。#include<bits/stdc++.h>using namespace std;char mp[10][10], g[10][10];int n = 5;int dx[4] = {1, 0, -1, 0}, d

2020-07-02 19:06:29

acwing 291. 蒙德里安的梦想

状压dp板题#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N =12, M = 1<<12;ll f[N][M]; ///代表前i-1列都被填满,j代表第i列的状态bool st[M]; ///预处理每一种状态是否合法int n, m;int main(){ while(scanf("%d%d", &n, &m)&&(

2020-06-23 22:26:23

acwing 91. 最短Hamilton路径(哈密尔顿)

传送门状压dp#include<bits/stdc++.h>using namespace std;const int N =20, M = 1<<20;int f[M][N], d[N][N], n;///f[i][j]代表经过状态i,终点在j的点,i代表状态,转成二进制就代表经过那些点int main(){ scanf("%d", &n); for(int i = 0; i < n; ++i) for(int j = 0;

2020-06-23 00:18:45

acwing 784. 强盗团伙

传送门经典并查集问题#include<bits/stdc++.h>using namespace std;const int N = 1010;int n, m;vector<int> e[N]; ///记录敌人int f[N];int Find(int x){ return f[x] = (x==f[x])?x:Find(f[x]);}void merge(int x, int y){ x = Find(x), y = Find(y);

2020-06-22 23:50:45

acwing 238. 银河英雄传说

传送门带边权的并查集#include<bits/stdc++.h>using namespace std;const int N = 1e6+10;int f[N], num[N], d[N];///d[i]表示i到祖宗的距离,num[i]表示以i为祖宗的队列的长度,是否清零都可以,因为合并后就用不到了int Find(int x){ if(x == f[x]) return x; int root = Find(f[x]); d[x] += d[f

2020-06-22 23:49:31

zzuli 2631: B(树链剖分)

传送门题目描述小p很早就听说,在古老的埃及,想要从斯芬克斯守护的地方经过,需要回答对它的一个问题。小p自命不凡,来到了斯芬克斯面前。斯芬克斯每天都望向远处(很远很远)的森林,看着一棵树,树上时不时会有一些小鸟落下,它每天的乐趣就是,当树上的小鸟的数量变化的时候,统计现在树上从一个树叶到另一个树叶上有多少个小鸟,它费尽心思没有搞懂,恰好小p来了,于是它将问题丢给小p,并说到:“我每天望向对面的森林,每天凌晨的时候,树上没有一只小鸟,每当有小鸟来的时候,我就记录 2 x y z,表示这个时候,从x号树叶到y

2020-06-17 17:02:04

树链剖分板题acwing 917. 树上操作

传送门某大佬有趣的视频讲解大佬博客#include<cstdio>#include<stdlib.h>#include<algorithm>#include<iostream>#include<string>#include<cstring>#include<map>#include<vector>#include<queue>#include<math.h>#i

2020-06-17 16:54:50

acwing 18. 重建二叉树

经典题目/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: map<int, int> hash;

2020-06-15 22:24:09

AcWing 12. 背包问题求具体方案

传送门#include<cstdio>#include<stdlib.h>#include<algorithm>#include<iostream>#include<string>#include<cstring>#include<map>#include<vector>#include<queue>#include<math.h>#include<climit

2020-06-13 22:09:10

AcWing 11. 背包问题求方案数

题意:有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。第 ii 件物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出 最优选法的方案数。注意答案可能很大,请输出答案模 1e9+7 的结果。f[j] 表示背包容积”恰好”为j时的最大价值和 ———— 最优解dpg[j] 表示背包容积”恰好”为j时取最优解的方案数 ———— 方案数dp#include<cstdio>#include<stdlib.h

2020-06-13 20:57:01

牛客练习赛65(C)

传送门这是用的是一个记录斜率的方法,基本有斜率都是通分,毕竟浮点数会有误差。这个题很容易发现只有0,1,2,3,-1这几种答案,-1就是所有点都在同一直线且没有点与当前点的斜率相同, 0就是在原点,特判一下,3就是n为2, 然后四个点组成平行四边形。1的话就是x, y和其中的一个点的斜率相同(这里的斜率指的是点与原点之间的斜率),2的话就是其他情况都考虑完就剩2了。比赛时写的太乱,分的情况太杂,最后也是没过。还有些大佬用的是奇角排序加二分判断斜率相同,不过总体思路都相同。大佬的题解#include

2020-06-12 23:36:40

AcWing 178. 第K短路

传送门第k短路的裸题,第k短路涉及到A算法。遇到问题我们先思考暴力的解法,这道题暴力的解法就是把其放到队列里,并查看点的出队次数,出队次数就代表了从起始点到当前点的第出队次短路。然后就是用A算法进行优化,主要就是利用一个估价函数,估价函数要求估计值一定是小于等于真实值,这个真实值就是从当前点到终点的权值。估价函数求法是反向建边,求终点到其他点的最短路。注意一下,题目要求至少包含一条边,也就是说如果起点和终点相同,就是求第k+1条路,第1条为0的路就不算是最短路。#include<cstdio

2020-06-11 22:02:42

洛谷 P4568 [JLOI2011]飞行路线(分层图最短路)

很容易理解的一个算法,只要把图画出来看看就行,感觉也很实用。#include<cstdio>#include<stdlib.h>#include<algorithm>#include<iostream>#include<string>#include<cstring>#include<map>#include<vector>#include<queue>#include<ma

2020-06-10 23:18:56

zzulioj 2634: E(spfa限制边权+二分)

这道题是对这个全局最优的边权进行二分,我们知道这条路上的其他边的容量肯定都大于等于这个值。所以,就可以根据这个来限制当前的图,然后再判断当前图的可行性进行二分。#include<cstdio>#include<stdlib.h>#include<algorithm>#include<iostream>#include<string>#include<cstring>#include<map>#include&

2020-06-10 22:17:57

zzulioj 2636: G(二分图)

传送门经典二分图,经常用于解决这种覆盖问题。原理是把二维变成一维,把相邻的块当成边,然后进行二分图求最大匹配,单向边就可以。#include<cstdio>#include<stdlib.h>#include<algorithm>#include<iostream>#include<string>#include<cstring>#include<map>#include<vector>#in

2020-06-10 22:12:15

pta 郑州轻工业大学2020年数据结构练习集

6-1 顺序表操作集/*#include <stdio.h>#include <stdlib.h>#define MAXSIZE 5#define ERROR -1//typedef enum {false, true} bool;typedef int ElementType;typedef int Position;typedef struct LNo...

2020-02-26 15:02:21

HDU - 618(暴搜+递推+矩阵快速幂)

一种找规律的方法,先暴搜找出前几个值,再多次循环找表达式系数,流批https://www.cnblogs.com/yzm10/p/9313916.html//#pragma comment(linker, "/STACK:10240000000000,10240000000000")#include<bits/stdc++.h>#define debug(x) cout &l...

2020-02-08 14:49:36

Codeforces Round #616 (Div. 2)

A - Even But Not EvenB - Array SharpeningC - Mind ControlA - Even But Not Even题意:给长度为n的一个数字串,求其子串符合子串每个数字和为偶数但子串是奇数。答案不唯一思路:其实根本不用考虑偶数,符合条件的串一定是奇数为偶数个数,且最后一位是奇数。由于答案不唯一,我们只考虑一种情况,有两个奇数的子串。只要够两个奇...

2020-02-03 17:42:25

Codeforces Round #615 (Div. 3)

传送门A Collecting CoinsB Collecting PackagesC Product of Three NumbersD MEX maximizingA Collecting Coins题意:有3孩子,分別有a,b,c个糖果,现有n个糖果给他们,最后能否让三个人拥有的糖果数量相同。思路:找出糖果最多的孩子,先让三个孩子的糖果数量都等于最多的那个,然后看是否能平分剩...

2020-01-23 23:24:46

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv1
    阅读者勋章Lv1
    授予在CSDN APP累计阅读博文达到3天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。