HDU 4507 恨7不成妻

思路

裸的要死的数位 DP 题目

一眼看过去,平方和,有点懵

但是维护平方和也是老套路了

维护 $sum$, $cnt$, $pow_sum$ 就可以了

代码

代码写的着急,会有一些不太好看

#include <cstdio>

const int mod = 1e9 + 7;

inline int add( int a, int b ) { return ( a + b ) % mod; }
inline int mul( int a, int b ) { return ( 1LL * a * b ) % mod; }
inline int power( int a ) { return mul( a, a ); }

int T, max_len;
long long left, rig;
int _count[110][2][10][10][10], _sum[110][2][10][10][10], _pow[110][2][10][10][10];
int max_count[110][2][10][10][10], max_sum[110][2][10][10][10], max_pow[110][2][10][10][10];
bool _vis[110][2][10][10][10];
int a[110];

inline int length( int cur, int len ) {
	int res = cur;
	while( len > 0 ) {
		res = mul( 10, res );
		len --;
	}
	return res;
}

struct node {
	int len, cur, seven, rem, base_rem;
	bool max;
	int& count() {
		if( max ) 
			return max_count[len][seven][rem][cur][base_rem];
		return _count[len][seven][rem][cur][base_rem];
	}
	int& sum() {
		if( max )
			return max_sum[len][seven][rem][cur][base_rem];
		return _sum[len][seven][rem][cur][base_rem];
	}
	int& pow() {
		if( max ) 
			return max_pow[len][seven][rem][cur][base_rem];
		return _pow[len][seven][rem][cur][base_rem];
	}
	bool& vis() {
		return _vis[len][seven][rem][cur][base_rem];
	}
	void print() {
//		printf( "%d %d %d %d %d %d\n", len, cur, seven, rem, base_rem, max );
//		printf( "%d %d %d\n", count(), sum(), pow() );
	}
};

int dfs( node cur ) {
	if( ( ! cur.max ) && cur.vis() )
		return cur.pow();
	if( cur.len == 0 ) {
		if( cur.seven || cur.rem == 0 || cur.base_rem == 0 ) {
			cur.count() = cur.sum() = cur.pow() = 0;
			return cur.pow();
		}
		cur.count() = 1; cur.sum() = cur.cur; cur.pow() = power( cur.cur );
		return cur.pow();
	}
	int &cur_count = cur.count();
	int &cur_sum = cur.sum();
	int &cur_pow = cur.pow();
	if( cur.max ) 
		cur_count = cur_sum = cur_pow = 0;
	for( int i = 0; i <= ( cur.max? a[cur.len]: 9 ); i ++ ) {
		node nxt = cur;
		nxt.len -= 1; nxt.seven = ( cur.seven || ( i == 7 ) ); nxt.cur = i; nxt.max = ( cur.max && i == a[cur.len] );
		nxt.rem = ( cur.rem * 10 + i ) % 7; nxt.base_rem = ( cur.base_rem + i ) % 7;
		dfs( nxt );
		cur_count = add( cur_count, nxt.count() );
		cur_sum = add( cur_sum, add( mul( length( cur.cur, cur.len ), nxt.count() ), nxt.sum() ) );
		cur_pow = add( cur_pow, add( nxt.pow(), add( mul( nxt.count(), power( length( cur.cur, cur.len ) ) ), 
						mul( mul( 2, length( cur.cur, cur.len ) ), nxt.sum() ) ) ) );
	}
	if( cur.max == false )
		cur.vis() = true;
	cur.print();
	return cur_pow;
}

int sum( long long _a ) {
	if( _a == 0 ) 
		return 0;
	if( _a < 0 )
		return 0;
	max_len = 0;
	while( _a ) { 
		a[ ++ max_len ] = _a % 10;
		_a /= 10;
	}
//	printf( "ans: %d\n", dfs( (node){ max_len, 0, 0, 0, 0, true } ) );
	return dfs( (node){ max_len, 0, 0, 0, 0, true } );
}

int main() {
#ifdef woshiluo
	freopen( "hdu.4507.in", "r", stdin );
	freopen( "hdu.4507.out", "w", stdout );
#endif
	scanf( "%d", &T );
	while( T -- ) {
		scanf( "%lld%lld", &left, &rig );
		if( left == 0 ) 
			printf( "%d\n", ( sum(rig) + mod ) % mod );
		else 
			printf( "%d\n", ( add( sum(rig), - sum( left - 1 ) ) + mod ) % mod );
	}
}

Luogu P3177 [HAOI 2015] 树上染色

题目链接: https://www.luogu.com.cn/problem/P3177

0 说在之前

树形 DP 要么模板题,要么神仙题

这个题就属于不太正常的

1 思路

$f_{i,j}$

其中 $i$ 代表当前节点

$j$ 代表子树中选择 $j$ 个黑点,所能对答案产生的贡献

有了这个思路,后面的东西就是标准的树上背包了

2 Code

#include <cstdio>
#include <cstring>

inline int Min(int a, int b) { return a < b? a : b; }
inline long long Max(long long a, long long b) { return a > b? a : b; }

const int N = 2100;

int n, m;
int size[N];

// Edge Start
struct edge {
    int to, val, next;
} e[N << 1];
int ehead[N], ecnt;

inline void add_edge(int now, int to, int val) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].val = val;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// Edge End

// DP Start
long long f[N][N];
void dp(int now, int la) {
    size[now] = 1;
    f[now][0] = f[now][1] = 0;
    for(int i = ehead[now]; i; i = e[i].next) {
        if( e[i].to == la )
            continue;
        dp(e[i].to, now);
        size[now] += size[ e[i].to ];
        for(int j = Min(size[now], m); j >= 0; j--) {
            for(int k = 0; k <= Min(size[ e[i].to ], j); k++) {
                if( f[now][ j - k ] == -1 )
                    continue;
                long long val = 1LL * ( 1LL * k * ( m - k ) + 1LL * ( size[ e[i].to ] - k ) * ( n - m - size[ e[i].to ] + k ) ) * e[i].val;
                f[now][j] = Max( f[now][j], f[now][j - k] + f[ e[i].to ][k] + val);
            }
        }
    }
}
// DP End

int main() {
#ifdef woshiluo
    freopen("luogu.3177.in", "r", stdin);
    freopen("luogu.3177.out", "w", stdout);
#endif
    scanf("%d%d", &n, &m);
    for(int i = 1, u, v, w; i < n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    memset(f, -1, sizeof(f));
    dp(1, 0);

    printf("%lld", f[1][m]);
    fclose(stdin);
    fclose(stdout);
}

PKUWC 2020(2019) 游记

0 序

晚上十一点半的机房,Woshiluo 正悠闲地考虑着第二天该做的题目

说着他一瞬想起来自己似乎报名过 PKUWC

「过去几年都没有人通过的,今年夏令营整个新疆都没过,果然还是白忙活吧」

话虽这么说,Woshiluo 还是打开了报名网站

「喵喵喵,过了?」

1 Day -2 出发

在经过严密的安检过后

我终于到达了乌鲁木齐站三层

比较有意思是,我的检票口貌似是 A1

然而 A1 前面的人都已经坐满了

我走到夹层,和绝大多数高铁站一样,这个地方是用来骗钱的

不过也就意味着,这里的人会少一点

稍作调整之后,车站广播也响起来了

随着缓慢的人群,我通过了检票口,到达了火车上

2 Day -1 火车上的短暂时光

乌鲁木齐铁路局所销售物品的昂贵已经是有很久历史的事情了

所以如果上车的时候犯懒没有买足吃的东西的话

可以到大站下去购买以尽可能的减少损失

这趟列车绝大部分地区都是没有信号的地方

所以基于手机的娱乐基本上是没有了

Kindel 和随身携带的纸制书可能是最有效的消磨时间方式

所以我在火车上过了一遍绿书,并读完了「樱花庄的宠物女孩」的本篇及番外

我的上铺和下铺都是年轻人,一个考研,一个去内地学习技术

总而言之,大家也都有自己的前途

3 Day 0 慌忙的首都一天

在早上十点,火车到达了北京西站

我从地铁口出来,联系上了 sbr,我从北京西站到国家图书馆再换乘到海淀黄庄

两个人见面稍微寒暄了一小阵,就到星巴克里谈人生

到了快要报道的时间,我们从海淀黄庄坐到北京大学东门 D 出口,从 D 口出来后约 5min 就可以到达报道的地方

我前面比没有几个人,进去之后签到的一栏旁边还有一个 是否使用 NOI Linux

看到这一栏时,就体会到了 PKU 的良心,更不要提后面还有 PKU 食堂 150 CNY 的饭卡

和 sbr 打车到国贸大厦,惊奇的发下自己把一些东西落在了报到处…

算了不重要

然后在和 sbr 吃完午饭后,我坐地铁从国贸到东大桥

经过 5min 的第六感导航,我顺利的到达了 Animate

这里的 Animate 和广东店装修风格好像啊

不过比广东店大了不少

时间超级紧迫,因为很明显,我需要在报道时间结束前回到报道处,拿回自己的东西

所以我就一目十行,随便扫了点 LoveLive! 和 碧蓝航线 的东西就飞速离开了

不过最意外的收获就是搞到了一本 「LoveLive! School idol diary」还是日文原版的

然后一路 Rush 到北京大学的报道处,偷偷的拿到了自己的东西

接着到了自己的酒店,真的离 PKU 好远啊…

稍微整理了一下在 Animate 的战果后跑去和 杨老师 — 我们的教练 会面

然后发现自己这边里所有地铁站都好远啊…

选了个最近的地铁站 — 上地站,然后惊奇的发现 13 号线几乎全是在地表的,我一开始以为这是轻轨,后来发现这东西叫城铁

从上地站出发,换乘两次到鼓楼,然后杨老师告诉我她到雍和宫了

于是从鼓楼出发,换乘一次到雍和宫

后面和老师吃了顿饭,然后和地铁关闭时间赛跑,换乘两次回到上地站

待我再回到酒店的时候,我人已经完全坏掉了

4 Day 1 稍有秩序的开幕

早上在酒店滴滴了 10min +,终与打到了车…

匆匆忙忙,到达开幕式所在场所

认识了几位大佬

开幕式大约介绍了一下北大,然后就散了

然后发现,没有地方休息的说

在经历了一阵混乱后,最后反正是在中关新园定了一间房

嘛,虽然贵的要死,不过明天也算是有地方休息了

反正今天是没有时间了

和教练一起在食堂吃了顿饭

在吃完 PKU 食堂的饭后,真的让人想上 PKU (不是

食堂饭又便宜又好吃,感谢 PKU 给的饭卡

然后跑到考场,Windows 考生使用 Windows 10,具体配置也不清楚

NOI Linux 考生使用的是 Dell 的笔记本,Intel i7,16G DDR4

多余的也没看,毕竟体验很优秀

T1

  • 离谱玩意儿,Subtask 1 随便搞搞就出来了
  • Subtask 2 推了好长时间…没有出来

T2

  • 全肝 T1 和 T3 了
  • 这道题目 Subtask 很多,认真写的花应该有至少 20pts

T3

  • Subtask 1 不用带脑子
  • Subtask 2 离线查分即可,没来的及写
  • 后面的 Subtask 不是我这种人该碰的

告辞 28pts 跑路

在 T1 莽的太久了, T2 T3 好多暴力没拿

中关新园离 pku 是真的近(

回去没有什么事情,就一直在颓废

5 Day 2 PKU 旅游日

面试

据说面试还有紧张到说不出话的

基本上面试文的问题都挺普通的

面试的时候会有一个预定的时间表

我想着我还没到时间,就去食堂买了个面包当早餐

结果回来发现已经到下一个了

无限尴尬

不过还好,面试老师并没有说什么

和一个天津大佬面基成功w

测试

T1

  • 跟着 Subtask 一步步走,基本上都能过
  • 说白了就是人口普查题
  • 我随便在考场上胡了个 $O(n\log^2(n))$ 的,反正过了

T2

  • 神仙,Subtask 1 跑路

T3

  • 最小割?
  • 有一说一,我上次敲网络流应该还是在中山
  • 弃了

最后 100 + 32 + 0 = 132pts

还算可以,基本上算是我的最大能力了(

晚上

回到酒店后,想起今天是冬至,便外卖了份饺子

然而是真的贵

吃完虽然没有吃饱,不过就这样子吧

然后颓废

6 Day 3

早早的就起来了

和 lk 爷爷面基,一起在楼下的包子铺吃了招行

两个人扯皮了好久

Orz lk 太强了

后来两个人打车去 PKU,中间 LK 在 THU 下了

我到了之后刚好开幕

我们教练家女儿生病了,于是我又双是一个人了

闭幕式

一开始大概就是领导讲话

然后就开始讲题

讲下来感觉自己还是很有希望 200 + 的

不过 Day 1 的时候智商下线了w

题倒是都还好,除了 Day 1 T3 完全没搞懂

剩下的都是能听懂但是不会写的(

然后颁奖

我觉得和我没什么关系,就把衣服拉链来开了,毕竟很热

然后惊奇的发现有个三等奖,结果上去的时候拉链没拉上www

晚上

后面发现闭幕式结束才 15 点

直接冲出去坐地铁到搜秀城w

然后再采购

然后就是回宾馆睡觉

晚上和 sbr 再面基

6 Day +1

上午和 Galaxy 见面

(或许是我这次唯一一个面基的成年人?)

然后带我逛了下 THU,顺便在 THU 吃了顿饭

和他聊了一阵子天,受益匪浅

正准备去机场

然后飞机延误了

7 Day +2

意外之喜

于是再去了趟 Animate,好好逛了一把

发现了好多之前没有发现的东西

大收获的说

8 Day +3

飞机又双延误了

告辞,火车真香

CSP 2019 游记

0 序

今年感觉相比较以往还是难了一些的

不过没有大家说的那么夸张倒是真的

不过自己貌似真的变菜了

0.1 吐槽

笔者考完 CSP 就会初中部回了一天

然后周二病到周五

一直在不发烧和低烧徘徊

但是一直咳嗽

咳得人 头疼 + 胸口疼 + 嗓子疼

新疆地邪啊

1 Day 0

今年七十中并不给试机子(注:也有可能是 CCF/科协 不让)

罢了,也没什么看头,每年 11 月都会在七十中冻一下

中午大家一起吃饭

虽然想学习,最后还是放弃了

晚上翻来覆去睡不着,迷迷糊糊最后还是睡了

2 Day 1

2.0 序 – 清晨

早上一开门,哇,下雪了

无论这个比赛怎么改名下雪还是避免不了的

在寒冷的凌晨,我们又拿起武器,向着熟悉的战场再次走去

2.1 CSP – S2 Day 1

T3 是个啥啊?

一中学长们的校车因为各种各样的原因,8:25 才到

遇见了不少以前的熟人,SpinMry,dyf 大家好久不见了,一起加油吧!

匆匆忙忙赶进考场,熟练的敲下 .vimrc,慌的一批

到了时间,准点发题

一直很想问都 9102 年,新疆为什么还是不用压缩包加密这种可靠性高的多的方法

非要用电子教师软件传输,然后再匆匆忙忙断网

罢了,有人愿意举办就不错了

  • T1
    • 属实不带脑子的题目,上来一看基本上就知道从上往下模拟即可 $O(64)$
      不过确实有一种更为简单的办法,参见 Oi-wiki – 格雷码
      最后看数据范围注意到 unsigned long long,出题人太毒瘤了吧
  • T2
    • 随便一看就是瞎搞累计贡献,道理我都懂,这代码怎么写?
      考场上一顿胡写,树上瞎跳,然后写点优化
      写完一开样例3,114514 太臭了,一跑,爆栈了,手写递归去了
      这么一套下来,感觉要出事 $\text{flag}_1$
  • T3
    • 一看,神仙题,10pts 告辞
      等一下这个 10pts 为什么这么难调,时间到了,完蛋

2.2 午休

考完心态小崩,找 dyf 一起快乐

两个人一起吃了饭,然后开始互相吐槽各自的学校

聊完天,两个人有一起走到七十中,路上还在吐槽某大佬的的迷路属性,结果到了七十中校门口就碰到了某大佬

2.3 CSP – J2

先在二楼和 dyf 与 caq 一起聊天 CSP 本质面基大会无疑

然后快考试了才去了三楼,运气可以抽到了比较暖和的位置

  • T1
    • 哇这么水的题目真的有出的必要吗…
  • T2
    • 一开始没看懂在搞什么,还想着 CSP – J2 都考平衡树了?
      后来一看 $price_i \leq 1000$ ,那没事了,多队列维护开溜
  • T3
    • 一眼背包,倒是不知道怎么搞
      弃了
  • T4
    • 最短路题目,怎么搞随缘

一出考场发现 2 道原题过分了啊

T3 我竟然做过,傻了

3 Day 2

3.1 CSP – S2 Day 2

又见熟人,不过因为 Day1 的心态,所以就没有过多闲聊

遇到郭老师,问他 Day 1 爆栈的问题

满口都是什么

「机子环境不重要的啊」
「全国只有两个省份提供了 NOI Linux,还都是虚拟机,别的都是 Windows 」

我看加个「七十中断电和七十中无关」都可以郭老师三连了

顺带一提,Day2 T2 内存 1GB 我们考试环境总共就 1GB 内存,可把我给整乐了

算了,XJ 这个占全国 $\frac{1}{6}$ 领土的小省份还是不要想别的了吧

  • T1
    • 什么玩意儿,神仙,跳
  • T2
    • $O(n^3)$ 是很显然了,就 $f_{i,j}$ 为以 $i$ 结束,向前 $j$ 位的最优答案就行了
      然后对 $i$ 考虑优化,考虑 $i$ 相等的情况下有两种状态 $j,k$,若 $j < k$ 且 $f_{i,j} < f_{i,k}$ 那么 $k$ 状态显然可以舍去
      不就是个弱化版斜率优化吗
  • T3
    • $O(n^2)$ 的点不用带脑子,敲就完事了
      链的点是不带脑子,可是我又双没时间了

3.2 下午

随便在一中食堂买了桶泡面

然后就会机房和大家一起聊天

高二的学长们很大一部分都要退役了,说不好真的是最后一次见了…

祝各位安好

After

一点 CSP 过后的小记

Day +2

选手程序出了

找了几个数据在 NOI Linux 上测试了一下

顺带一提,是远程测试,是真的延迟高…

最后基本上都是

$100 + 55 + 0 + 0 + 64 + 40 = 259$

也不知道官方数据怎么样…

Day +5

斗胆看了下 Day1 T2

发现自己把

st[ st_cnt ] 

写成了

st_cnt

离谱

Day +14

正在去市一中的路上,突然看到有个群里说成绩出了

CCF 又写 Bug了(当然不排除故意的可能性)

一路狂奔跑到机房

拿到数据正准备测试,结果机房 DNS 锅了

看了一下发现 php-fpm 服务挂了

修复了之后开始评测,然后在大屏上直播

感觉还可以,评测期间基本上就是在骂测了 1min + 但是却 0 pts 的憨憨

Day +16

想了想,还是有想停课冲冬令营的想法

稍作思考也许就会出结果了吧…

回去文化课实际上感觉还可以,基本上也都听得懂

勉强在班里还算可以,不过在这个学校里想要上一中必须得很靠前啊…

一点小小的总结

今年可能比较去年可能会更加迷茫一些

去年的问题有一条今年还有的

  • 时间规划有一定问题

除此之外,能察觉到的主观问题还有

  • 思想方向有些许问题
  • 过于追梦,导致检查和部分暴力点未能做到

以下是一些客观原因

  • 提高组和入门组一起考太痛苦了,敲到最后在考场上不想写 值得一提的是,相似问题也在第一轮认证时有出现
  • 某名的感觉体力不太行…考试到最后手一直在冷(也有可能是七十中实在是太冷了)

顺带一提,我和同省大爷 StudyingFather 的意见一样

个人感觉我们今年的培训题目还是太偏了,考试虽然一直都在考,但是留于改题与总结的时间并不算长

不过我们也确实做不到跟上出题趋势这个大方向

希望我们会走的更好吧

「Jump up HIGH!!」

– Aqours

今年已经是我第三年学习 Oi 了

也许自己真的在实现最初的梦想

当时刚学 Oi 的时候,就一直在想,要是我能拿到 XJ 的第二块 Au 就好了

后来目标渐渐变了,变成很多奇奇怪怪的东西

回过头来,却发现自己也无意识中接近了最初的目标

不过还是很遥远就是了

不过人好歹还是要有梦想的,毕竟自己文化课也不算优秀

所以说,就当是有梦想了吧

虽然自己菜的真实

「私たち、 輝きたい!」

「LoveLive!SunShine!!」

Woshiluo
2019/12/04
乌鲁木齐市第一中学 小机房

CSP – S/J 2019 第一轮 游记

0 序

又开始了啊,新的一轮

大家或多或少的开始了新的旅程了呢

这两天和一位内地的 CSPer 聊了一些和 CSP 无关的东西,感觉想通了不少事情

今年到考场都跟咸鱼一样了

依稀记得去年监考老师不讲理过了 3min 还不发卷子

「老师,已经过去了三分钟了,怎么还不发卷子」 xqmmcqs 大佬突然站起来询问道

感觉自己就是从这个时候开始,老师这个概念已经从我心中的神坛跌了下去

我只会去尊重有理有据教育我们的老师的

或许是 Oi 学久了,某些思想竟以变得如此激进了

前文说的有点杂了,还是开始正题吧

注:为了笔者和大家的习惯,下文统称 CSPer 和 Oier 为 Oier

注:文中出现人物多使用其常见 id 称呼,没有或我不知道常见 id 的使用姓名拼音首字母简称,您可以在评论去提出更改或者匿名请求,请求处理完后会删除相应评论

Continue reading “CSP – S/J 2019 第一轮 游记”

平面向量学习笔记(大概?)

这篇文章咕了好久了,鬼知道为什么

本篇文章的目的只是为了更方便的学习 P2742 【模板】二维凸包 这道题目,如果有不详细或者错误之处,往各位大佬们多多指出

1 定义

向量:有大小,有方向 的量是向量,然而数学中研究的向量通常是 自由向量,即起点终点并不重要

向量的模:向量的长度被称为向量的模

零向量:模为 $0$ 的向量,零向量方向任意,记为 $\vec 0$ 或 $\mathbf 0$

单位向量:模为 $1$ 的向量是其在该方向的单位向量

Continue reading “平面向量学习笔记(大概?)”

中山纪念中学 Day 21 2019.08.21 解题报告 & 题解

T1 数字 Number

1 记录

考场上疯狂肝这道题目,结果少个特判

2 Solution

很明显,$n$ 只有三种情况

  1. $n$ 就是结尾
  2. 中间有一段是一个数字,这个情况 $O(\log^3(n))$ 枚举即可
  3. 中间切一刀,左边是一个不完整的数字,右边也是一个不完整的数字,枚举中间即可

所以直接暴力即可

所以这是一道毒瘤模拟题目

Continue reading “中山纪念中学 Day 21 2019.08.21 解题报告 & 题解”

中山纪念中学 Day 10 2019.08.10 解题报告 & 题解

T1 数学题 Math

1 记录

真就数学题目呗

考场企图推正解,结果最后只推出了 60 分的,哭了

正解参见 欧几里得算法的应用.pdf

这是真的类欧几里得算法

Continue reading “中山纪念中学 Day 10 2019.08.10 解题报告 & 题解”