3 Rancho__

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 5w+

T114048 [RC-02] yltx数对 (打表)

这题如果全部打表的话,文件大小会有65kb,超了,所以只打出一半,前一半用程序算就可以了,并不会超时。如果算法优化的好,其实可以打的更少。#include <bits/stdc++.h>using namespace std;const int maxn=1e5+10;// const int N=1e4+10;const int N=5e3+10;int vis[ma...

2020-02-06 15:23:50

P1030 求先序排列 (一个非常棒的写法)

理论正确就是真正的正确,误。。。就是找嘛,找到每一个对应字符,然后对应的左右子树的区间,然后就可以了。#include <bits/stdc++.h>using namespace std;char mid[100];char suff[100];void getpre(int ml,int mr,int sl,int sr) { // printf("%d ...

2019-12-25 14:49:27

试题编号: 201803-4 试题名称: 棋局评估 (对抗搜索 博弈)

这题真的是一道很不错的题,首先我对题意的理解有点问题,我以为的最优策略是,用最优的策略取胜,但是题目的意思是用最优的策略取得最好的得分。到哪个人行棋,就暴搜哪个人的可选的每一步,然后比较下一个人行棋所得的结果,取最优。例如当alice行棋时,就让alice下一步棋的得分取bob最优行棋的分数,然后alice有不同的点可以下,就让alice下一步走法的最优解等于alice走完下一步之后,对应的b...

2019-12-23 20:30:21

1022_Digital_Library (30分)

这里提供两种写法, 其实都是一样的,第一种比较快。#include <bits/stdc++.h>using namespace std;map<string,set<string> > mp[6];int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); ...

2019-12-21 20:58:10

1018 Public Bike Management (30分) (迪杰斯特拉+dfs)

思路就是dijkstra找出最短路,dfs比较每一个最短路。dijkstra可以找出每个点的前一个点, 所以dfs搜索比较的时候怎么处理携带和带走的数量就是关键,考虑到这个携带和带走和路径顺序有关,所以可以用下面的写法,看代码就可以了。最开始的时候是想用一个偏动态规划的写法做,但是因为题目的显示,既要带去的车数量最少,又要求从一个点带走的车数量最少,所以如果过动规的话,对于一个点的多个最短路,...

2019-12-21 17:01:55

PAT 1014 Waiting in Line (30分) 一个简单的思路

这题写了有一点时间,最开始想着优化一下时间,用优先队列去做,但是发现有锅,因为忽略了队的长度。然后思考过后,觉得用时间线来模拟最好做,先把窗口前的队列填满,这样保证了队列的长度是统一的,这样的话如果到某个时间,队首的人已经服务完了,这样这个队列的长度就减少一,这就变成了所有队列中长度最短的队列,所以直接向这个队列里面添加一个人就可以了。按照从小到大轮询窗口的话,这样正好符合题中的要求,就是队列...

2019-12-20 09:50:56

1010 Radix (25分)

改了一天也没明白,第7个数据是怎么卡的#include <bits/stdc++.h>using namespace std;const int maxn=1005;typedef long long ll;ll tonum(char c){ if (c>='0'&&c<='9') { return c-'0'; } return c...

2019-12-17 18:26:28

试题编号: 201809-4 试题名称: 再卖菜 记忆化搜索

这题一看就是搜索,然后我不会写,咯咯咯。看了题解发现好简单,这是一个递推式,令d[n] 为第n家第一天的菜价 a[n]为第n家第二天的菜价则 (d[n-1]+d[n]+d[n+1]) / 3 = a[n]d[n+1] = 3 * a[n] - d[n-1] - d[n] + k (k=0,k=1,k=2)递推一下就可以了,但是对于第n天,n-1天的菜价为x,第n天的菜价为y , ...

2019-12-12 17:23:26

试题编号: 201903-3 试题名称: 损坏的RAID5

这题的数据未免也太水了,题目的意思好像默认是每块磁盘装载数据的长度是相等的。我写了判断每次取数据是否会超过每块磁盘存的数据的长度,然而并没有什么卵用。交上去20分,写了个数据测了下,如果要求的块太大的话,这样下面计算得出的对应磁盘号会太大,然后就会runtime error,所以求出最大块号,如果查询的块超过最大块号,就输出错误就可以了。#include <bits/stdc++.h&gt...

2019-12-11 16:37:21

CCF 试题编号: 201909-4 试题名称: 推荐系统

这题是stl的综合应用,map要想快,直接上unordered_map,这样查询接近O(1),是不是很嗨皮。思路其实还是很简单的,type+id做个Hash,由于set.insert的第一个返回值是指向该插入元素的迭代器,所以,对于每一个type+id我们都可以存下它对应的迭代器,这样删除不就很快了吗,省去查找。这题是我第一次用c++11的语法, 原谅我的low,嘻嘻,auto还挺好用。#i...

2019-12-08 17:46:56

洛谷P3809 后缀数组模板

把题读清楚,题中的输入是包括数字、大写字母和小写字母的。初始化排名的时候可以把字符的ascii值作为排位,因为排名是可以并列的。但是最后的后缀排名是不可能并列的,因为每一个后缀的长度不一样。基数排序的时候,注意处理并列的情况。下面的代码是复旦大学的程序设计里面的代码,写的挺清晰的,想看的可以直接粘走。#include <bits/stdc++.h>using namespace...

2019-11-26 16:57:45

UVa 400 Unix Is命令

简单题#include <bits/stdc++.h>using namespace std;const int maxn=110;string s[maxn];int main(){ // freopen("data.in","r",stdin); ios::sync_with_stdio(false); int N; while (cin>>N)...

2019-10-27 19:40:20

Uva 136 丑数

n^2暴力就完事,但是上限要高,不然就算不到对应的1500,刘汝佳的写法更好。#include <bits/stdc++.h>using namespace std;const int maxn=10000;int cnt=4;long long a[maxn];map<long long , int> mp;int main(){ // clo...

2019-10-27 19:38:22

The Preliminary Contest for ICPC Asia Xuzhou 2019 K. Center

这题对于能加入最多边缘点的center点,这个点就是最优的center ,对于center点,总共是n^2的,顶多也就1e6,所以直接双重循环就行了, 然后map<pair,set >映射一下,第二个用set是因为虽然同一个中心点,对应的边缘点不会出现两次,但是题目中允许一个点作为边缘点两次 ,所以去重的是自己和自己相同的点。最后输出以下答案就可以了。#include <bi...

2019-10-23 11:27:43

The Preliminary Contest for ICPC Asia Xuzhou 2019 J Random Access Iterator (树形DP)

每次循环向下寻找孩子时,随机选取一个孩子,设dp[u]为从u出发,不能得出正确答案的概率,则从u出发,走一次的情况下不能得出正确答案的概率是 P = (dp[v1]+dp[v2]+dp[v3]+……dp[vk]) / cnt_son[u] ,则从u出发,要走cnt_son[u]次,那么dp[u]=P^cnt_con[u] 。dp的意义也可以改成能得出正确答案的概率,下面的式子稍微改改就行了。...

2019-10-12 11:10:34

The Preliminary Contest for ICPC Asia Xuzhou 2019 G Colorful String(回文自动机+dfs)

这题建立一棵回文树,然后用dfs搜索答案,但是有一点需要注意,就是打vis的标记时,如果标记为1,那么在好几个节点都对同一个字符i打过标记,此时的搜索从字符i点回溯,回到它的父亲节点,搜索其它的字符,回溯的时候把vis[i]标记成0了,之前的vis[i]标记全被清空了,如果该父亲的其它字符节点下,有字符i的孩子,则此时统计就会出错。所以打vis标记的时候让vis++,而不是标记为0。#inclu...

2019-10-02 15:54:05

The Preliminary Contest for ICPC Asia Xuzhou 2019 E XKC's basketball team(排序+二分)

这题其实就是瞎搞,稍微想一想改一改就能过。排序按值的大小排序,之后从后向前更新node节点的loc值,如果后一个节点的loc大于(不会等于)前#include <bits/stdc++.h>using namespace std;const int maxn=5e5+10; struct Node { long long val,loc;}node[maxn];lo...

2019-09-27 10:09:38

The Preliminary Contest for ICPC Asia Xuzhou 2019 M. Longest subsequence(思维+序列自动机)

序列自动机跑s串假设k为s和t相同的长度,初始时相同长度为0取s串中大于t[i]的最左边的位置,用n-tmp+1+i-1更新答案,tmp是最左端的位置然后去t[i]相等的位置,走到下一位,如果下一位的位置不存在或者在tmp的右边,跳出循环即可。最后就是s串中找出了一个和t串相同的串,之后的长度只要不为0,也是可以用来更新答案的。#include <bits/stdc++.h>...

2019-09-24 20:24:57

The Preliminary Contest for ICPC Asia Xuzhou 2019 B. so easy (unordered_map+并查集)

这题单用map过不了,太慢了,所以改用unordered_map,对于前面删除的点,把它的父亲改成,后面一位数的父亲,初始化的时候,map里是零,说明它的父亲就是它本身,最后输出答案的时候,输出每一位数的父亲就好了。#include <bits/stdc++.h>using namespace std;unordered_map<int,int>mp;int f...

2019-09-24 11:11:20

HDU 1237 简单计算器(栈+stringstream)

提供几份代码,这题的输入可以用stringsteam处理,先处理乘除后处理加减,正常思路,但是后面统计加减法的时候,对栈的运用相当于加了几个括号就错了。正确的简单解法就是,加法,就让正数入栈,减法就让该数的相反数入栈,之后的操作也不会影响该数的正负,这样处理最简单。单栈#include <iostream>#include <sstream>#include &l...

2019-09-23 19:33:30

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。