1 MaJorieL

尚未进行身份认证

我们向右偏左的坠落,琢磨着寻求自我

等级
TA的排名 10w+

HDU1179 Ollivanders: Makers of Fine Wands since 382 BC.【二分图匹配/匈牙利算法】

题目链接:Ollivanders: Makers of Fine Wands since 382 BC.#include<bits/stdc++.h>#define pb push_backusing namespace std;const int maxn=111;vector<int> g[maxn<<2];bool vis[maxn];i...

2020-01-22 23:45:08

HDU1384 Intervals【差分约束】

题目链接:HDU1384 Intervals题意:区间[a,b]至少有c个,问至少多少个能满足n个区间;分析:差分约束建边求最长路;#include<bits/stdc++.h>using namespace std;const int maxn=50007;const int INF=0x3f3f3f3f;int dis[maxn],head[maxn];bo...

2020-01-22 23:07:08

Educational Codeforces Round 77 (Rated for Div. 2)

只会写没水平的题A.尽量平均分最少#include<bits/stdc++.h>using namespace std;const int maxn=1e5+5;typedef long long ll;int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;i++) { ...

2019-11-28 00:39:53

2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest

A.Berstagram题意:起始数列是1,2,3,……,n,给你m个操作x,表示将数字x和前一个位置的数交换,如果已经在第一个则不做操作,求每个数能到达的位置的最大和最小值;分析:扫一遍模拟,更新左右极限;#include<bits/stdc++.h>using namespace std;const int maxn=1e5+7;int a[maxn],pos[...

2019-11-07 16:43:58

2019CCPC哈尔滨 Gym102394

比赛链接:Gym102394E. Exchanging Gifts题意:有n个操作,每个操作决定Si,op==1表示后面Si为当前给出的序列,op==2表示Si是Sx+Sy,由此得到最后的Sn,Sn随意交换得到H,问H与Sn最多有多少个不同;分析:假设我们已经得到Sn,长度为len,出现次数最多的数是x,出现次数为num,如果num*2>len,ans=2*(len-num),否...

2019-11-03 16:14:50

CF1245 F.Daniel and Spring Cleaning【数位DP】

题目链接:CF1245 F.Daniel and Spring Cleaning题意:给你一个区间,问区间内有多少对数满足a^b==a+b;([a,b]和[b,a]是两个答案)分析:由题意知道是求a&b==0的对数,既然是位运算就可以转化成二进制下的数位DP,1e9不到30位;#include<bits/stdc++.h>using namespace std;...

2019-11-02 19:36:05

Codeforces Round #597 (Div.2)

A.判断是否互质;#include<bits/stdc++.h>using namespace std;int gcd(int a,int b){return b==0?a:gcd(b,a%b);}int main(){ int t;scanf("%d",&t); while(t--) { int a,b;scanf("%d...

2019-11-02 19:29:10

HDU5961 Sitting in Line【状压DP】

题目链接:HDU5961 Sitting in Line题意:给你n个数和他们的位置,如果位置为-1表示这个数可以取任意位置,选择一种放置方式,使得相邻两数乘积之和最大;分析:N<=16,考虑状压DP;dp[i][j]表示取状态i中为1的数放在前面且这一位放j时的答案;当dp[i][j]成立时,可以从它向后更新dp[i|(1<<k)][k],要注意更新时需要判断这一位的位...

2019-10-31 11:20:20

HDU1045 Fire Net【DFS】

题目链接:HDU1045 Fire Net【DFS】题意:一个至多4*4的棋盘,棋盘上有一些墙壁,可以阻挡子弹,炮台可以向四个方向发射子弹,问在保证他们不能互相攻击的情况下至多可以放置多少炮台;分析:搜就对了;#include<bits/stdc++.h>using namespace std;char mp[5][5];int n,ans;bool check(...

2019-10-30 17:22:37

HDU3290 The magic apple tree【DFS】

题目链接:HDU3290 The magic apple tree题意:给你一个树,起始叶子结点的值为他的编号本身,开始更新后,如果一个非叶子结点有K个子节点有值,那么他的值更新为这些值中第(k+1)/2小,求根节点的最后值;分析:从根节点向下DFS,到叶子结点之后向上回溯,裸题;#include<bits/stdc++.h>#define pb push_backu...

2019-10-29 20:29:15

Codeforces Round #596 (Div.2)

A.注意判断一下9和1;#include<bits/stdc++.h>using namespace std;int main(){ int a,b;scanf("%d%d",&a,&b); if(a==9 && b==1) printf("9 10\n"); else if(b-a>=2 || a>b) printf("-...

2019-10-28 17:32:02

HDU1011 Starship Troopers【数位DP】

题目链接:HDU1011 Starship Troopers题意:n个房间,m个士兵,给出每个房间的bug数和价值,每个士兵可以消灭20个bug,对于每个房间,只有当前的bug被全部消灭才能进入与它相连的房间,如果当前房间没有bug也要留一个士兵,求最多可以获得的总价值;分析:dp[i][j]表示房间i有j个士兵的价值;#include<bits/stdc++.h>#d...

2019-10-17 16:10:32

HDU1520 Anniversary party【树形DP】

题目链接:HDU1520 Anniversary party题意:给你一棵树,每个点都有价值,父子不可同时选择,问选择的点的最大价值和;分析:找到根,然后向下DFS树形DP,由子节点更新父节点,dp[i][1]表示选择i,dp[i][0]表示不选择i,然后向上回溯更新父节点;#include<bits/stdc++.h>#define pb push_backusin...

2019-10-17 14:11:27

HDU2196 Computer【树形DP】

题目链接:HDU2196 Computer【树形DP】题意:给你一个树,求出所有节点在树中能到达的点的最远距离;分析:dp[i][0],表示顶点为i的子树的,距顶点i的最长距离;dp[i][1],表示Tree(i的父节点)-Tree(i)的最长距离+i跟i的父节点距离;dp[i][0]通过dfs1可以很快求出;dp[i][1]可以通过父节点转移来,要维护一个最长mx1和经过的子节点v1,次...

2019-10-16 21:18:06

HDU3709 Balanced Number【数位DP】

题目链接:HDU3709 Balanced Number题意:问区间[l,r]内平衡数的个数,平衡数是指选某一位作支点,左右两边每一位数值*力矩的和相等;分析:dp[len][pos][sum]表示长度为len的数,当支点为pos时,力矩为sum的数的个数;转移是由长度为len-1的数+第len位转移而来,所以dp[len][pos][sum]+=dp[len-1][pos][sum+i*...

2019-10-16 11:41:06

数电实验真有趣

可以参考的管脚配置https://wenku.baidu.com/view/a94fc49cbe1e650e53ea992f.html实验一 五输入表决器设计程序设计module first(a,b,c,d,e,f); input a,b,c,d,e; output f; wire a,b,c,d,e,f; assign f=(a&b&c)|(a&amp...

2019-10-15 11:28:29

CF1238 E.Keyboard Purchase【状压/子集划分DP】

题目链接:CF1238 E.Keyboard Purchase题意:给你一个由前m个字母组成的长度为n(1e5)的字符串,要求你决定一个前m(20)个字母的排列,每个字母的价值是它在排列中的位置,原字符串的代价是相邻两个字母的价值差,问字符串的最小代价是多少;分析:首先可以预处理出相邻字母组合的出现次数;考虑状态压缩,第i位为1表示第i个字母已经定过了排列的位置,为0表示他的位置没有决定,...

2019-10-14 21:12:28

HDU3555 Bomb【数位DP】

题目链接:HDU3555 Bomb题意:问1~n中含有49的个数;分析:首先用init()找到n位数有多少含有49的数;dp[i[[j]用于存储符合条件的数的个数 i代表目前处理的数长度为i;这里dp[i][j]处理的数可包含前导零;dp[i][0]代表长度为i的数中不含49数的数量;dp[i][1]代表长度为i的数中不含49但是最高位为9的数的数量;dp[i][2]代表长...

2019-10-14 20:54:40

HDU4745 Two Rabbits【区间DP】

题目链接:HDU4745 Two Rabbits题意:有一段环形字符串,两个人相对而行,要使得他们走过的字母序列相同的最长长度是多少;实际上就是求字符串中最长的回文子序列的长度,最终答案是取长度为n的区间里最长的长度 和 长度为n-1的区间里最长的长度+1 的最大值;+1是因为n-1的区间剩下的那个可以被同时当作起点,注意是环形字符串;分析:根据差分,dp[l][r]=max(dp[l][...

2019-10-14 19:35:45

HDU4632 Palindrome subsequence【区间DP】

题目链接:HDU4632 Palindrome subsequence题意:找出字符串里回文子序列的个数;分析:由差分可知dp[l][r]=(dp[l][r-1]+dp[l+1][r]-dp[l+1][r-1]+mod)%mod当s[l]=s[r]时,dp[l][r]=(dp[l][r]+dp[l+1][r-1]+1)%mod,[l,r]可由[l+1,r-1]转移来,并且构成一个新的回...

2019-10-14 19:31:25

查看更多

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