2016 China-Final 解题报告

Tips

仅含题解,代码详见github喜欢的话点个star
这几天又把China-Final的题补了一些,比较蛋疼的是为啥根本搜不到题解。。。我觉得我要多加些关键字,2016 ICPC China-Final,codeforces gym101194。题目在cf可以交,因为只有PDF就不每一题都加链接了。

阅读全文

2016 CCPC 合肥站 解题报告

Tips

仅含题解,代码详见github喜欢的话点个star
前几天终于把合肥的题补了一些。。。再往下就是lct了,暂时不学。

阅读全文

hdu 5306 Gorgeous Sequence 线段树

Gorgeous Sequence

读完题,可以知道显然要维护最大值和区间和,可以用线段树。写着写着感觉第一种操作好像不能延迟更新,然后就不会了。。。
查题解的时候发现都是线段树,不过各有各的做法,后来有一种说是吉如一论文中介绍的,可以证明每次操作均摊复杂度为 $O(logN)$ 。这个论文的标题我倒是找到了(吉如一 -《区间最值操作与历史最值问题》)然而论文没找到。。。
做法如下:线段树的每个节点记录最大值a,次大值b,区间和sum,以及最大值个数cnt。当进行第一种操作时,

阅读全文

Piece0

某文,很6 。
昨天在某群看到一个同级同专业的同学解答了折半查找的问题,感觉代码写得挺不错的,而且跟别人争辩的时候也不慌不忙。再一看截图,这环境好像是iPad+vim。。。瞬间吓尿,又想起来他这几次比赛好像都很不错,于是赶紧加了好友。
一加好友他竟然说我银牌大佬,还告诉我是AA说的AA真是看得起我😂。后来又了解到他考过pat乙级和pat甲级,甲级80+,凭我感觉应该还是挺屌的。再后来就问问他日常什么系统啊之类的。。。结果发现他每天晚上的日常是躺在床上拿iPad连接自己桌上的笔记本然后…用vim写代码
Cool!妈的感觉这才是大学生啊!当然,首先我需要一个iPad 。
又问了问有没有搞过Web方面的,他说用python爬过10个G的美女图片。
Cool!妈的感觉这才是大学生啊!当然,首先我需要学会python 。
于是我说我想学python ,他就说我这儿有几本书你要不要看啊 。商量了一下,我就直接去他寝室了。
见面当然还是要聊啊,中学没搞过信息学竞赛,但是自学过C语言,大学还玩过单片机,然后转专业到计算机,现在在看算法导论,还在跟别人一起搞3D玩。相比之下我就很挫了,初中用Pascal搞信息学竞赛,高中用C++搞信息学竞赛,python只会helloworld,从来没看过什么正经书…
轻松转专业,估计还是个学霸。我觉得他就是我想要的那种状态,但是也很难说清楚。不过我现在有事干了:

阅读全文

UVALive 7139 Rotation

Rotation

题意:$N×M$ 的网格图,给定一条网格线连成的闭合路径,计算所有格子转动值的平方和。假设一辆车沿着路径移动,一个人站在某个格子正中间始终对着车,这个人在车开始到停下顺时针转动了 $x$ 度,则他的转动值为 $\frac{x}{360}$ (可以为负数)。
题解:首先,因为起点和终点相同,每个格子的转动值一定为整数。
其次,若路径为简单环,环内的格子转动值均为 $\pm 1$,环外的格子转动值均为 $0$ 。

阅读全文

FJNU 低年级程序设计竞赛

B-捧杯

受力分析。。。贴这题主要是因为看到了向量化简有一个很简洁的作法~

阅读全文

2016 ICPC 大连站解题报告

J. Find Small A

一眼题没看清以为移4位WA了一次

阅读全文

hdu 5093 Battle ships 二分图

Battle ships

做的时候能不能搜索想了半天。。。后来查了一下竟然是二分图经典模型。。。所以觉得应该记下来。。。

阅读全文

hdu 5727 Necklace 全排列+二分图

Necklace

题意:要用n个阳石和n个阴石来串一个项链(环),规定阳石旁边只能是阴石,阴石旁边只能是阳石,现在有 m 对影响关系,x 号阳石与 y 号阴石相邻会使阳石变暗(照样可以用),问串这个项链最少让几个阳石变暗

阅读全文

hdu 5875 Function ST+二分

Function

引理:
我们称 $X\ge M$ 时 $X\ mod\ M$ 为一次有效的取模,则 $X$ 在 $\lceil log_{2}X\rceil$ 次有效的取模后一定变为 0 。
简要说明:
考虑最坏情况,取 $M=\lfloor\frac{X}{2}\rfloor+1$ ,$X->\lfloor\frac{X-1}{2}\rfloor$
(当 $M’>M$ 或 $M’<M$ 时,$X$ 都会变得更小)

阅读全文

hdu 5728 PowMod 数论

[PowMod][1]

先贴官方题解

官方题解

阅读全文

hdu 5919 Sequence II 主席树

Sequence II

题意:给出原数列。每次询问一个区间时,把各个数字在这个区间中第一次出现的位置记作 $p_{1},p_{2},\cdots, p_{k}$ ,满足 $p_{1} < p_{2} < \cdots < p_{k}$ ,求 $p_{\lceil \frac{k}{2}\rceil}$ 。询问强制在线。

阅读全文

弱校联盟 2016 四川省赛

。。。反正都不会。。。反正都是抄的。。。

水题。。。刚开始我还写了个判断在不在长方体之内的函数。。。

阅读全文

hdu 5546 Ancient Go 搜索

Ancient Go

题意:给出棋盘,轮到 x 这一方下子,问能不能至少提掉一个 o 方的子。
题解:枚举每一个 o ,bfs 一下看看周围的 . 是不是少于等于 1 个,太简单辣!

阅读全文

hdu 3727 Jewel 主席树

最近在学主席树。。。反正感觉挺神奇的。。。
我高中想学,但是并没有看懂。可能是他们写的太屎了
kuangbin的板子也不太行。
poj 2104 那题入门,程序是没错
但是太耦合了,变量也有点意义不明。。。
于是我又去找了找。。。发现应该给一个比利比利的链接

阅读全文

HHUACM 综合训练2

本次综合训练主要是2013年的大连online的题目,有难有易,其中题意不太清楚和要求非常高的题目就直接剔除了。这样题数少了,于是又加了2题2016年大连online的我觉得挺不错的题目。后来发现知识点有点重叠,不过训练一下也无妨。

Find the maximum

题意:给出 $N$ 求出最小的 $2\leq n\leq N$ 使得 $n/\varphi(n)$ 最大。
题解:做这题首先要知道 $\varphi(n)$ 的计算式(不作证明): $\varphi(n)=n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})…(1-\frac{1}{p_{k}})$
$$\therefore n/\varphi(n)=\frac{1}{(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})…(1-\frac{1}{p_{k}})}$$ $$=\frac{1}{\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}…\frac{p_k-1}{p_k}}$$ $$=\frac{p_1}{p_1-1}\frac{p_2}{p_2-1}…\frac{p_k}{p_k-1}$$ $$=(1+\frac{1}{p_1-1})(1+\frac{1}{p_2-1})…(1+\frac{1}{p_k-1})$$
其中 $p_1,p_2,…p_k$ 为 $n$ 的质因子。(考虑到大家提交的很多代码都是打表,这里我写的比较详细)

阅读全文

hdu 4417 Super Mario

这题很明显离线做比较水。。。

把询问和每块砖都按高度排序
不断向树状数组插入满足条件的砖的位置
对每个询问求在 [L,R] 的区间和
也就是把前缀和减一减
【树状数组不能有0,所以传参之前我都加了1。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=1e5+5;
const int MAX=N;
struct query {
int l,r,h,id;
} q[N];
struct brick {
int h,pos;
} a[N];
int c[MAX],ans[N];

struct cmp {
template<typename T>
bool operator()(const T &a,const T &b)
{
return a.h<b.h;
}
};

void ins(int x,int d)
{
for (;x<MAX;x+=x&(-x)) {
c[x]+=d;
}
}

int query(int x)
{
int res=0;
for (;x;x-=x&(-x)) {
res+=c[x];
}
return res;
}

int main()
{
int T,n,m;
scanf("%d",&T);
for (int t=1;t<=T;t++) {
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++) {
scanf("%d",&a[i].h);
a[i].pos=i;
}
for (int i=0;i<m;i++) {
scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].h);
q[i].id=i;
}
sort(a,a+n,cmp());
sort(q,q+m,cmp());
int k=0;
for (int i=0;i<m;i++) {
for (;k<n&&a[k].h<=q[i].h;k++)
ins(a[k].pos+1,1);
ans[q[i].id]=query(q[i].r+1)-query(q[i].l-1+1);
}
printf("Case %d:\n",t);
for (int i=0;i<m;i++)
printf("%d\n",ans[i]);
memset(c,0,sizeof(c));
}
return 0;
}

阅读全文

poj 3690 Constellations

最近在翻 ICPC online 的题。。。
终于找到一个能做的水题结果WA了七八次。。。
可能我果然还是不会C/C++语言吧 OTZ

行状压和列状压都行吧。。。
然后我就暴力枚举右下角
感觉写的比能查到的题解好看一点。。。
【差点就全服最短了2333333

阅读全文

hdu 5828 Rikka with Sequence

多校8的一道题。。。 【看标题识出题人 ←_←
非常蛋疼的一道题,官方题解根本不知道在说什么,标程写得跟坨屎一样= =
先贴一份比赛中菊苣AC的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/************************************************
*Author :mathon
*Email :luoxinchen96@gmail.com
*************************************************/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define xx first
#define yy second
#define pr(x) cout << #x << " " << x << " "
#define prln(x) cout << #x << " " << x << endl
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
template<class T> inline T lowbit(T x) { return x & (-x); }
const int MAXN = 1e5 + 5;
int A[MAXN];
struct SegT {
ll sum[MAXN<<2];
ll is_same[MAXN<<2], lazy[MAXN<<2];
void init() {
memset(sum, 0, sizeof(sum));
memset(is_same, 0, sizeof(is_same));
memset(lazy, 0, sizeof(lazy));
}

void push_up(int rt) {
if(is_same[rt << 1] && is_same[rt << 1 | 1] &&
is_same[rt << 1] == is_same[rt << 1 | 1]) {
is_same[rt] = is_same[rt << 1];
} else {
is_same[rt] = 0;
}
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void push_down(int rt, int l, int r) {
int m = (l + r) >> 1;
if(is_same[rt]) {
is_same[rt << 1] = is_same[rt];
is_same[rt << 1 | 1] = is_same[rt];
sum[rt << 1] = is_same[rt] * (m - l + 1);
sum[rt << 1 | 1] = is_same[rt] * (r - m);
} else {
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
sum[rt << 1] += lazy[rt] * (m - l + 1);
sum[rt << 1 | 1] += lazy[rt] * (r - m);
lazy[rt] = 0;
if(is_same[rt << 1]) {
is_same[rt << 1] += lazy[rt << 1];
lazy[rt << 1] = 0;
}
if(is_same[rt << 1 | 1]) {
is_same[rt << 1 | 1] += lazy[rt << 1 | 1];
lazy[rt << 1 | 1] = 0;
}
}
}

void build(int l, int r, int rt) {
if(l == r) {
sum[rt] = A[l];
is_same[rt] = A[l];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
push_up(rt);
}
void update1(int L, int R, int x, int l, int r, int rt) {
if(L <= l && r <= R) {
sum[rt] += (ll)x * (r - l + 1);
if(is_same[rt]) {
is_same[rt] += x;
} else {
lazy[rt] += x;
}
return;
}
int m = (l + r) >> 1;
push_down(rt, l, r);
if(m >= L) update1(L, R, x, lson);
if(m < R) update1(L, R, x, rson);
push_up(rt);
}
void update2(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R && is_same[rt]) {
is_same[rt] = sqrt(is_same[rt]);
sum[rt] = is_same[rt] * (r - l + 1);
return;
}
int m = (l + r) >> 1;
push_down(rt, l, r);
if(m >= L) update2(L, R, lson);
if(m < R) update2(L, R, rson);
push_up(rt);
}
ll query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return sum[rt];
}
int m = (l + r) >> 1;
push_down(rt, l, r);
ll res = 0;
if(m >= L) res += query(L, R, lson);
if(m < R) res += query(L, R, rson);
return res;
}
}seg;
int main(void) {
#ifdef MATHON
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
int T; scanf("%d", &T);
while(T--) {
int n, m;
scanf("%d%d", &n, &m);
seg.init();
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
}
seg.build(1, n, 1);
for (int i = 0; i < m; i++) {
int op;
scanf("%d", &op);
if(op == 1) {
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
seg.update1(l, r, x, 1, n, 1);
} else if(op == 2) {
int l, r;
scanf("%d%d", &l, &r);
seg.update2(l, r, 1, n, 1);
} else if(op == 3) {
int l, r;
scanf("%d%d", &l, &r);
ll res = seg.query(l, r, 1, n, 1);
printf("%lld\n", res);
}
}
}
return 0;
}

阅读全文

NOIP2012 借教室(classroom)

http://codevs.cn/problem/1217/
唉。。。即使是以我四年后的水平也要改一遍。。。
太菜了。。。
应该是目前最常用的线段树写法。。。确实是能过的

阅读全文