當(dāng)前位置：首頁(yè) > 运维知识 > windows >内容正文

windows

模拟赛好题分享

發(fā)布時(shí)間：2023/11/16 windows 35 coder

生活随笔收集整理的這篇文章主要介紹了模拟赛好题分享小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

山茶花
- 100pts
T1區(qū)間逆序?qū)?ul>
60pts
100pts 區(qū)間操作固定套路，轉(zhuǎn)化為前綴操作

dream

20pts 神奇分塊

杭州:轉(zhuǎn)化題意，正難則反

正難則反(或者對(duì)于這種有刪邊操作的題)，我們看成反向加邊

看題：構(gòu)造

坐飛機(jī):斜率優(yōu)化DP

抓頹 : 啟發(fā)式合并 + stl大雜燴

討厭的線段樹

Foo Fighters ：構(gòu)造

亂搞一：大膽隨機(jī)化
正解:位運(yùn)算 -> 基本套路按位考慮

Hack it! ：構(gòu)造

光之劍：計(jì)數(shù)DP

正解:正難則反，取補(bǔ)集

Divide

正解:科技-Stern-Brocot樹法里樹

Stern-Brocot樹
- 性質(zhì)1 單調(diào)性
- 性質(zhì)2 SB Tree的所產(chǎn)生的分?jǐn)?shù)都是最簡(jiǎn)分?jǐn)?shù)
- 證明
法里樹

醒幸：正難則反

相似題目:杭州
正解:轉(zhuǎn)化題意, 二分

ABC321F :退背包

正解:性質(zhì)題

農(nóng)場(chǎng)道路修建 : 問(wèn)題轉(zhuǎn)化

正解：問(wèn)題轉(zhuǎn)化
方法一 :
方法二 :

密碼鎖：優(yōu)化DP

25pts:DP
55pts：區(qū)間DP+線段樹優(yōu)化

100pts：?jiǎn)栴}轉(zhuǎn)化+性質(zhì)

魔法是變化之神

60pts:背包,求補(bǔ)集
100pts：考慮隨機(jī)數(shù)據(jù)

奶牛的數(shù)學(xué)題:單位貢獻(xiàn)

正解

路遇矩陣

奶牛的括號(hào)匹配:狀壓

潤(rùn)不掉了：轉(zhuǎn)化點(diǎn)對(duì)問(wèn)題

40pts
100pts 子樹貢獻(xiàn)轉(zhuǎn)化

美好的查詢:神奇主席樹

80pts：分塊+并查集
100pts:神奇主席樹，多看看

新涂色游戲:操作反做

新-滑動(dòng)窗口簡(jiǎn)單差分

小明去旅游鍋

Heavy and Frail：分治優(yōu)化重復(fù)操作

- 35pts，二進(jìn)制分組背包暴力跑
- 80pts 背包合并
- 100pts

chess：根據(jù)題意分析

glass：簡(jiǎn)單裝呀

card：組合意義的DP

godnumber:鍋

meirin：暴力化簡(jiǎn)式子

sakuya:期望樹形DP好題

交換消消樂:簡(jiǎn)單性質(zhì)題

[ABC232H] King's Tour：構(gòu)造，鍋

Road of the King：神奇DP

醉醉瘋瘋渺渺空空換根dp

F - Robot Rotation 不能隨機(jī)化的折半搜索

E - Revenge of "The Salary of AtCoder Inc." 期望

A. 1031模擬賽-A進(jìn)步科學(xué) 狀壓DP

B. 1031模擬賽-B吉吉沒急差分約束

C. 1031模擬賽-C老杰克噠動(dòng)態(tài)DP

排座位 - 題目 - Daimayuan Online Judge] DP

A. 方塊游戲 - 題目 - 多校信息學(xué)訓(xùn)練題庫(kù)

B. 雪球 - 題目 - 多校信息學(xué)訓(xùn)練題庫(kù)

D. 不要FQ - 題目 - 多校信息學(xué)訓(xùn)練題庫(kù) 動(dòng)態(tài)DP

23zr提高day9-美人魚 - 題目 - Zhengrui Online Judge (zhengruioi.com)

山茶花

性質(zhì)推導(dǎo)題：如果沒有+1操作，那么最后的答案一定為恒定的ans

考慮+1操作對(duì)什么時(shí)候會(huì)產(chǎn)生影響

不難發(fā)現(xiàn)，如果后綴為k個(gè)1, 則+1操作等效于 $ans ^ (1 << (k + 1) )$

那么問(wèn)題就轉(zhuǎn)化為了由這n任意順序異或，是否可以異或出后綴為k個(gè)1的數(shù)

如果第0位的1都沒有拼湊成功，那么后綴1再長(zhǎng)也沒有意義，所以如果要想異或出k個(gè)1，必須要保證前$k - 1$個(gè)1異或出來(lái)且不能因?yàn)榈趉位1的異或影響

思考線性基異或最大值時(shí)，保證了優(yōu)先異或出高位1且高位1不會(huì)被低位1影響

所以可以構(gòu)造低位線性基進(jìn)行判斷復(fù)雜度$n * log_{2}n$

100pts

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
const int MAX = 2e6 + 70;
int n;
LL a[MAX], b[MAX], SUM = 0, ans = 0;
void add(LL X) {
	for(int i = 0; i <= 61; i++) if(X >> i & 1) {
		if(b[i]) X ^= b[i];	
		else {
			b[i] = X;
//			printf("b[%d] %lld\n", i, b[i]);
			return ; 
		}
	}
}
bool check(int X) {
	LL NOW = 0;
	for(int i = 0; i <= X; i++) {
//		printf("X %d NOW %lld\n", X, NOW);
		if((NOW >> i & 1) != (i != X)) {
			if(b[i]) NOW ^= b[i];
			else return 0;	
		}
	}
	return 1;
}
int main() {
//	freopen("shuju.in","r",stdin);
//	freopen("mine.out","w",stdout); 
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		SUM ^= a[i];
		add(a[i]);	
	}
//	cout<<SUM<<endl;
	for(int i = 0; i <= 61; i++) { // 使末尾有i個(gè)1
		if(check(i)) {
			ans = max(ans, SUM ^ (1ll << (i + 1)) - 1);
//			printf("i %d %lld\n",i, ans);	
		} 
	}
	cout<<ans<<endl;
	return 0;
}

60pts

1e5莫隊(duì)即可，主要復(fù)習(xí)一下回滾莫隊(duì)

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
const int MAX = 1e6 + 70;
int n, m, a[MAX], bl[MAX], blen;
int t1[52], t2[52], k[52];
LL ANS[MAX];
struct made {
	int l, r, id;
}ask[MAX];
bool mycmp(made X, made Y) { return (bl[X.l] < bl[Y.l]) || (bl[X.l] == bl[Y.l] && X.r < Y.r); }
int lowbit(int x) { return (x & (-x)); }
void add1(int x) { for(int i = x; i; i -= lowbit(i)) t1[i] += 1; }
LL Find1(int x)  { LL res = 0; for(int i = x; i <= 50; i += lowbit(i)) res += t1[i]; return res;}
void add2(int x) { for(int i = x; i; i -= lowbit(i)) t2[i] += 1; }
LL Find2(int x) { LL res = 0; for(int i = x; i <= 50; i += lowbit(i)) res += t2[i]; return res;}
int main() {
	scanf("%d%d", &n, &m);
	blen = pow(n, 2.0 / 3.0);
//	printf("blen %d\n", blen);
	for(int i = 1; i <= n; i++) bl[i] = (i / blen) + 1;	
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= m; i++) {
		scanf("%d%d",&ask[i].l, &ask[i].r);
		ask[i].id = i;
	}
	sort(ask + 1, ask + 1 + m, mycmp);
	int LST = 0, L = 0, R = 0;
	LL ans = 0;
	for(int i = 1; i <= m; i++) {
		if(bl[ask[i].l] == bl[ask[i].r]) { //同一塊中，暴力求解 
			memset(t1, 0, sizeof(t1)); LL res = 0;
			for(int j = ask[i].l; j <= ask[i].r; j++) {
				res += Find1(a[j] + 1);
				add1(a[j]);
			}
			ANS[ask[i].id] = res;
		} else {
//			printf("ask[%d].id %d l %d r %d\n", i, ask[i].id, ask[i].l, ask[i].r); 
			if(bl[ask[i].l] != LST) { //不在一個(gè)塊中 
				memset(t2, 0, sizeof(t2));
				L = (blen * bl[ask[i].l]);
				R = L - 1;
				ans = 0;			
				LST = bl[ask[i].l];
			}
//			printf("L %d R %d\n", L, R);
			while(R < ask[i].r) {
				ans += Find2(a[++R] + 1);
				add2(a[R]);
			}
			LL res = ans; //儲(chǔ)存 
			for(int j = 1; j <= 50; j++) k[j] = t2[j];
			while(L > ask[i].l) {
				L--;
				ans += (R - L - Find2(a[L]));
				add2(a[L]);
			}
			ANS[ask[i].id] = ans;
			ans = res;
			L = (blen * bl[ask[i].l]);
			for(int j = 1; j <= 50; j++) t2[j] = k[j]; //撤銷 
		}
		
	}
	for(int i = 1; i <= m; i++) printf("%lld\n", ANS[i]);
	return 0;
}

100pts 區(qū)間操作固定套路，轉(zhuǎn)化為前綴操作

觀察數(shù)據(jù)范圍， a的數(shù)值都小于等于50，而每次查詢都是一個(gè)區(qū)間，面對(duì)區(qū)間問(wèn)題，最常用的套路就是預(yù)處理出前綴數(shù)組，O(常數(shù))查詢
思考前綴逆序?qū)性質(zhì)，對(duì)于區(qū)間L,R而言，前綴F[R] 包含了 $L < l < r < R,l < r < L, l < L < r < R$ 三種逆序?qū)?/strong>

對(duì)于前兩種逆序?qū)Γ現(xiàn)[R] - F[L] 即可，主要需要撤銷l不在[L,R]中， r在[L, R]中的逆序?qū)Γ?這里就需要利用$a <= 50$, 看[L, R]中每種1-50出現(xiàn)了多少次即可

#include<bits/stdc++.h> using namespace std; #define LL long long const LL MAX = 1e6 + 70; int tree_g[MAX]; int tree_n[MAX]; int a[MAX]; LL n, m; int sum[MAX][52]; LL NINI[MAX]; int num[MAX][52]; int lowbit(int x) { return (x & (-x)); } int Find_g(int x) { int res = 0; for(int i = x; i <= 50; i += lowbit(i)) res += tree_g[i]; return res; } void ADD_g(int x) { for(int i = x; i; i -= lowbit(i)) tree_g[i] += 1; } int Find_n(int x) { int res = 0; for(int i = x; i <= 50; i += lowbit(i)) res += tree_n[i]; return res; } void ADD_n(int x) { for(int i = x; i; i -= lowbit(i)) tree_n[i] += 1; } signed main() { // freopen("ex_data3.in","r",stdin); // freopen("mine.out","w",stdout); scanf("%lld%lld", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++) { for(int j = 1; j <= 50; j++) { sum[i][j] = sum[i - 1][j]; } sum[i][a[i]] += 1; } for(int i = 1; i <= n; i++) { //處理前綴中比j大的個(gè)數(shù) ADD_g(a[i]); for(int j = 1; j <= 50; j++) { num[i][j] = Find_g(j + 1); } } for(int i = 1; i <= n; i++) { NINI[i] = NINI[i - 1]; LL res = Find_n(a[i] + 1); NINI[i] += res; ADD_n(a[i]); } // printf("%lld\n", num[2][2]); for(int i = 1; i <= m; i++) { int l, r; scanf("%d%d", &l, &r); LL ans = NINI[r] - NINI[l - 1]; for(int j = 1; j <= 50; j++) { ans = ans - ((LL)num[l - 1][j] * (LL)(sum[r][j] - sum[l - 1][j])); } printf("%lld\n", ans); } return 0; }

dream

20pts 神奇分塊

對(duì)于$n * m <= 5e7$的數(shù)據(jù)考慮分塊做法，發(fā)現(xiàn)如果沒有回歸操作，那么僅需要樹狀數(shù)組即可維護(hù)，但是我們發(fā)現(xiàn)對(duì)于序列(l, r)而言，盡管它們的標(biāo)記點(diǎn)不同，但是通過(guò)一次回歸將所有標(biāo)記清空后對(duì)于它們整體的操作所帶來(lái)的偏移量一樣！那么就可以分塊解決了

沒調(diào)過(guò)的代碼

杭州:轉(zhuǎn)化題意，正難則反

數(shù)據(jù)范圍 $n,m <= 200000$,首先很明顯的事情，在一顆樹中距離$x$最遠(yuǎn)的點(diǎn)一定是該直徑的其中一個(gè)端點(diǎn)

那么題目要求我們求得就是在原樹中任一子樹的直徑端點(diǎn)分別是什么，但是我們無(wú)法維護(hù)任一形態(tài)的子樹

正難則反(或者對(duì)于這種有刪邊操作的題)，我們看成反向加邊

那么現(xiàn)在我們要求的就是合并兩個(gè)聯(lián)通塊后直徑端點(diǎn)是什么

假設(shè)兩個(gè)聯(lián)通塊分別為S1,S2, 直徑端點(diǎn)分別$S1.L, S1.R S2.L, S2.R$, 連通塊交點(diǎn)為X, 在兩個(gè)連通塊中距離X的最遠(yuǎn)的端點(diǎn)都在直徑端點(diǎn)上

X將兩個(gè)連通塊聯(lián)通，若直徑?jīng)]變，則應(yīng)該為S1,S2中直徑更大值，若發(fā)生改變，則一定經(jīng)過(guò)X，所以發(fā)生更改的最遠(yuǎn)直徑的端點(diǎn)一定為$S1.L,S1.R,S2.L,S2.R$

現(xiàn)在我們可以維護(hù)出連通塊的最長(zhǎng)直徑和直徑端點(diǎn)，因?yàn)檫@兩個(gè)聯(lián)通塊合并后再在原樹(假定1為根)中形態(tài)不變

所以用(DEP[X] + DEP[Y] - DEP[LCA(X,Y)])維護(hù)即可

//查詢距離x最遠(yuǎn)的點(diǎn)，一定為樹上直徑端點(diǎn)之一，刪邊樹的直徑不好維護(hù) //考慮轉(zhuǎn)化為加邊維護(hù)聯(lián)通塊中的樹的直徑，那么需要對(duì)于每次加邊操作就重新跑一遍lca嗎？ //顯然不需要，如果我們處理出整顆樹，那么我們只需要確定那兩個(gè)點(diǎn)是樹的直徑, 在原樹中確定即可 //不關(guān)心樹的形態(tài)，只關(guān)心直徑的端點(diǎn) #include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 2e5 + 70; int n, m, cut[MAX], dep[MAX], tot, head[MAX]; int father[MAX], ANS[MAX], fa[MAX][22]; struct NODE {int x, y, dis;} p[MAX]; //分別表示這個(gè)點(diǎn)所處的聯(lián)通塊的直徑端點(diǎn)和直徑長(zhǎng)度 struct made { int l, t, id;}edge[MAX * 2], E[MAX]; struct ASK{ int op, x; }ask[MAX]; void add(int u, int v, int id) { edge[++tot].l = head[u]; edge[tot].t = v; edge[tot].id = id; head[u] = tot; } void dfs(int x, int FA, int DEP) { //預(yù)處理整顆樹的fa fa[x][0] = FA; dep[x] = DEP; for(int i = 1; i <= 20; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1]; for(int i = head[x]; i; i = edge[i].l) { int t = edge[i].t; if(t == FA) continue; dfs(t, x, DEP + 1); } } int Find(int x) { return father[x] == x ? x : Find(father[x]); } LL LCA(int x, int y) { if(dep[x] < dep[y]) swap(x, y); for(int i = 20; i >= 0; i--) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i]; //往上跳 if(x == y) return y; for(int i = 20; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; return fa[y][0]; } int check(int x, int y) { return (dep[x] + dep[y]) - 2 * dep[LCA(x, y)]; } NODE mrg(NODE X, NODE Y) { NODE NOW = (X.dis > Y.dis) ? X : Y; // printf("NOW %d X.x %d X.y %d Y.x %d Y.y %d \n",NOW.dis, X.x, X.y, Y.x, Y.y); if(check(X.x, Y.x) > NOW.dis) { NOW = {(NODE){X.x, Y.x, check(X.x, Y.x)}}; // printf("FIRST NOW.x %d NOW.y %d NOW.dis %d\n", NOW.x, NOW.y, NOW.dis); } if(check(X.x, Y.y) > NOW.dis) { NOW = {(NODE){X.x, Y.y, check(X.x, Y.y)}}; // printf("SECOND NOW.x %d NOW.y %d NOW.dis %d\n", NOW.x, NOW.y, NOW.dis); } if(check(X.y, Y.x) > NOW.dis) { NOW = {(NODE){X.y, Y.x, check(X.y, Y.x)}}; // printf("THIRD NOW.x %d NOW.y %d NOW.dis %d\n", NOW.x, NOW.y, NOW.dis); } if(check(X.y, Y.y) > NOW.dis) { // printf("FORTH NOW.x %d NOW.y %d NOW.dis %d\n", NOW.x, NOW.y, NOW.dis); NOW = {(NODE){X.y, Y.y, check(X.y, Y.y)}}; } return NOW; } void merge(int x, int y) { int fx = Find(x), fy = Find(y); father[fx] = fy; // printf("fx %d fy %d\n", fx, fy); p[fy] = mrg(p[fx], p[fy]); //直徑 } void work() { dfs(1, 0, 0); for(int i = 1; i <= n; i++) father[i] = i, p[i] = {i, i, 0}; for(int i = 1; i < n; i++) { if(cut[i] == 0) { // printf("E[%d] u %d v %d\n", i, E[i].l, E[i].t); merge(E[i].l, E[i].t); //合并兩個(gè)聯(lián)通塊 } } for(int i = 1; i <= n; i++) { int fx = Find(i); // printf("i %d fa %d l %d r %d\n", i, fx, p[fx].x, p[fx].y); } for(int i = m; i >= 1; i--) { if(ask[i].op == 1) merge(E[ask[i].x].l, E[ask[i].x].t); else { int fx = Find(ask[i].x); ANS[i] = max(check(ask[i].x, p[fx].x), check(ask[i].x, p[fx].y)); } } } int main() { scanf("%d%d", &n, &m); for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); add(u, v, i); add(v, u, i); E[i] = {(made){u, v, i}}; } for(int i = 1; i <= m; i++) { scanf("%d%d", &ask[i].op, &ask[i].x); if(ask[i].op == 1) cut[ask[i].x] = 1; } memset(ANS, -1, sizeof(ANS)); work(); // for(int i = 1; i <= m; i++) { if(ANS[i] != -1) printf("%d\n", ANS[i]); } return 0; }

看題：構(gòu)造

坐飛機(jī):斜率優(yōu)化DP

抓頹 : 啟發(fā)式合并 + stl大雜燴

討厭的線段樹

Foo Fighters ：構(gòu)造

亂搞一：大膽隨機(jī)化

只需要輸出一個(gè)S即可，直接隨機(jī)化，如果不捆綁的話應(yīng)該可以取得不少的分?jǐn)?shù)

正解:位運(yùn)算 -> 基本套路按位考慮

&運(yùn)算有一個(gè)性質(zhì) 只有(1 & 1) =1 所以最高有效位數(shù)低的數(shù)字的1的個(gè)數(shù)的奇偶性不會(huì)被較高位1的&運(yùn)算影響（更自然）

所以我們?nèi)绻凑瘴粩?shù)低向高進(jìn)行枚舉這樣可以保證對(duì)較高位的運(yùn)算不會(huì)對(duì)較低位的答案產(chǎn)生影響

這時(shí)候我們發(fā)現(xiàn)一個(gè)問(wèn)題，什么是較高位的答案，什么是較低位的答案，明確下個(gè)定義:最高位1位置的大小

這樣我們將數(shù)進(jìn)行分組，按照最高位進(jìn)行分組，從低到高枚舉，最高位低組的答案一定不會(huì)被最高位高組影響

但是僅有這個(gè)性質(zhì)是不夠的，會(huì)不會(huì)較低位的&運(yùn)算會(huì)影響較高位的答案？

但是讓我們回想每組的答案跟什么有關(guān)系

只跟奇偶性有關(guān)系，所以最高位的一個(gè)1就可以將這一組分成兩組奇數(shù)組與偶數(shù)組，通過(guò)改變最高位1，就可以交換奇數(shù)組和偶數(shù)組

Hack it! ：構(gòu)造

光之劍：計(jì)數(shù)DP

正解:正難則反，取補(bǔ)集

我們從數(shù)據(jù)入手，一步一步分析，如果$n,k <= 10$的話顯然直接搜索即可

但是第2檔分與爆搜差距過(guò)大，所以這檔分顯然需要我們給出一個(gè)$n^2$的做法
肯定可以想到這應(yīng)該是一個(gè)計(jì)數(shù)類的DP，如何設(shè)計(jì)狀態(tài)
如果我們正向去做設(shè)$f[i]$表示以$i$為錯(cuò)誤答案的貢獻(xiàn)
我們發(fā)現(xiàn)有兩個(gè)限制
$1.保證不是n的數(shù)能夠有后k個(gè)比它小的數(shù)$
$2.保證它前面沒有出現(xiàn)比他大的數(shù) 并且沒有出現(xiàn)錯(cuò)誤答案$
如果嘗試過(guò)發(fā)現(xiàn)$f[i]$ 與 $f[j]$的聯(lián)系過(guò)小, 細(xì)節(jié)非常難處理
這時(shí)候我們要不斷調(diào)整狀態(tài)的設(shè)計(jì)，將一個(gè)大問(wèn)題轉(zhuǎn)成一個(gè)子問(wèn)題
這時(shí)候我們反向思考，如果知道了返回最大值為$n$的數(shù)量$res$，$(n! - res)$即為答案
那么什么時(shí)候會(huì)出現(xiàn)返回值為n？
兩種情況
1.n個(gè)數(shù)沒有出現(xiàn)返回值
2.讓n后面有j個(gè)數(shù)，且前面的數(shù)沒有返回值
這時(shí)候我們發(fā)現(xiàn)第二種情況需要用到第一種情況，那么我們思考如何解決第一種即可
設(shè)$f[x]$表示$x$個(gè)數(shù)且沒有返回值，$f[j] = j!(j∈[0,k])$，如何轉(zhuǎn)移?
這時(shí)候其實(shí)就非常簡(jiǎn)單了，如果我們將第$i$個(gè)數(shù)放在$j$的位置上，我們需要保證前$j - 1$個(gè)數(shù)沒有出現(xiàn)返回值，且$i$后面不能有$k$個(gè)數(shù)

$f[i] = f[j-1] * C_{i - 1}^{j-1} * A_{i -j}^{i -j}(j∈[i - k+1,i])$
這樣就能拿到$60pts$考慮化簡(jiǎn)發(fā)現(xiàn)隨著$i$的增加$1$,$j$的左邊界少1，右邊界大1，將組合數(shù)化簡(jiǎn)$f[i] = f[j - 1] * (i-1)!/(j-1)!$這樣雙指針即可!

/* 發(fā)現(xiàn)正著做非常困難，正難則反考慮如果n個(gè)數(shù)的排列最大值能夠選到n的情況那么分為兩種，一種是可以選到的，一種是沒有選出來(lái)來(lái)的如果n在前k個(gè)則一定能取到，如果在k + 1個(gè)之后需要保證前k個(gè)沒有產(chǎn)生最大值 (即沒有選出來(lái)的) 問(wèn)題轉(zhuǎn)化為了子問(wèn)題，前i個(gè)數(shù)選不出來(lái) */ #include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 1e6 + 70; const int MOD = 1e9 + 7; int n, k; LL A[MAX], f[MAX], INV[MAX]; LL quick_mi(LL x, LL y) { LL xx = x, res = 1; while(y) { if(y % 2) res = res * xx % MOD; xx = xx * xx % MOD; y /= 2; } return res; } LL C(int x, int y) { return (A[x] * INV[y] % MOD * INV[x - y] % MOD); } void prework() { A[0] = 1; for(int i = 1; i <= n; i++) A[i] = (A[i - 1] * i) % MOD; for(int i = 0; i <= k; i++) f[i] = A[i]; //隨便放 for(int i = 0; i <= n; i++) INV[i] = quick_mi(A[i], MOD - 2); //預(yù)處理，少log！！！！！ LL ANS = 0; for(int i = k + 1; i >= 2; i--) ANS = (ANS + (f[i - 1] * A[k] % MOD * INV[i - 1] % MOD) ) % MOD; f[k + 1] = ANS; int l = 1; for(int i = k + 2; i <= n; i++) { //前i個(gè)位置 ANS = (ANS - (f[l] * A[i - 1 - 1] % MOD * INV[l] % MOD) + MOD) % MOD; ANS = ANS * (i - 1) % MOD; ANS = ANS + (f[i - 1] * A[i - 1] % MOD * INV[i - 1] % MOD); f[i] = ANS; l++; // for(int j = i; j >= i - k + 1; j--) { //i放的位置 // f[i] = (f[i] + (f[j - 1] * C(i - 1, j - 1) % MOD * A[i - j] % MOD) )% MOD; //可以化簡(jiǎn) ****** //// printf("j %d f[%d] %lld\n",j, i, f[i]); // } // printf("f[%d] %lld\n", i, f[i]); } } int main() { freopen("arisu.in","r",stdin); freopen("arisu.out","w",stdout); scanf("%d%d", &n, &k); prework(); //預(yù)處理前i個(gè)數(shù)選不出來(lái)的數(shù)量 LL res = f[n]; // cout<<f[n]<<endl; for(int i = 1; i <= n - k; i++) { res = (res + (f[i - 1] * C(n - 1, i - 1) % MOD * A[n - i]) )% MOD; } cout<<(A[n] - res + MOD) % MOD<<endl; return 0; }

Divide

正解:科技-Stern-Brocot樹法里樹

Stern-Brocot樹

我們定義$la = 0,lb=1,ra=1,rb=0$,
令$x=la+ra,y=lb+rb$,顯然得到$\cfrac{la}{lb}<\cfrac{x}{y}<\cfrac{ra}{rb}$將得到的$\cfrac{x}{y}$重新作為$la, lb, ra,rb$ 重新進(jìn)行計(jì)算，即可得到上圖

性質(zhì)1 單調(diào)性

性質(zhì)2 SB Tree的所產(chǎn)生的分?jǐn)?shù)都是最簡(jiǎn)分?jǐn)?shù)

證明

法里樹

將右邊界改為$\cfrac{1}{1}$，所得到的都為<=1的分?jǐn)?shù)

#include<bits/stdc++.h> using namespace std; #define LL long long #define LB long double const int MAX = 1e7 + 7; long double eps = 1e-19; int fa, fb; bool flag = 0; long double val; int main() { // scanf("%d%d", &fa, &fb); fa = 1000000000, fb = 1000000000; scanf("%Lf", &val); int la = 0, lb = 1, ra = 1, rb = 0; long double lc = val; int ansa = 1, ansb = 0; while(1) { int x = la + ra, y = lb + rb; if(x > fa || y > fb) break; LB NOW = ((LB)x / (LB)y); if(fabs(NOW - val) < eps) { ansa = x, ansb = y; break; } else { ansa = x, ansb = y; lc = fabs(NOW - val); if(NOW - val < 0) { la = x, lb = y; } else { ra = x, rb = y; } } } printf("%d %d", ansa, ansb); return 0; }

醒幸：正難則反

相似題目:杭州

簡(jiǎn)概題意:給定一個(gè)圖，每次刪去邊權(quán)和最大的森林(即刪去的圖必須聯(lián)通且沒有環(huán)), 求每條邊是哪次操作刪去的

正解:轉(zhuǎn)化題意, 二分

我們發(fā)現(xiàn)每次刪去一個(gè)最大的森林非常難處理，因?yàn)镸的數(shù)據(jù)范圍是$M<=3e5$需要一個(gè)$log_{m} || \sqrt{m}$復(fù)雜度的算法，非常難維護(hù)

觀察數(shù)據(jù)范圍$K*N<=1e7$也就是說(shuō)，我們?nèi)绻梢詫h去$K$次與$N$產(chǎn)生聯(lián)系即可,刪去的圖聯(lián)通沒有環(huán)，顯然是一個(gè)樹形結(jié)構(gòu)，那么也就是說(shuō)我們要把$M$條邊進(jìn)行分組，生成$K$棵樹，每一顆樹對(duì)應(yīng)了一個(gè)刪除順序

現(xiàn)在問(wèn)題就進(jìn)行了轉(zhuǎn)換，如何向K個(gè)森林里加邊，保證沒有環(huán)且K個(gè)森林的邊權(quán)和從大到小?

對(duì)于K個(gè)森林邊權(quán)和從大到小，類Kruskal, 邊權(quán)從大到小，依次判斷往哪個(gè)森林加邊，如果當(dāng)前森林中兩點(diǎn)不聯(lián)通，加邊，否則，向后判斷

到這里我們發(fā)現(xiàn)時(shí)間復(fù)雜度仍然劣，$MKlog_{n}$,瓶頸出在哪里?顯然是判斷往哪個(gè)森林里加邊，我們顯然想要一個(gè)$log$做法，考慮二分,這樣思考，如果對(duì)于當(dāng)前這個(gè)森林已經(jīng)聯(lián)通，顯然會(huì)在后邊的森林加邊，如果不聯(lián)通，顯然會(huì)在前面的森林中，感性理解，這樣問(wèn)題就得以解決

#include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 2100 + 70; int n, m, k, ans[MAX * MAX]; struct made { int fa[1100]; LL val; int Find(int x) { if(fa[x] == x) return x; return fa[x] = Find(fa[x]); } }P[10002]; struct node { int u, v, val, id; } e[MAX * MAX]; bool mycmp(node X, node Y) { return X.val > Y.val; } bool mycmp2(node X, node Y) { return X.id < Y.id; } bool check(int u, int v, int x) { if(P[x].Find(u) == P[x].Find(v)) return 0; return 1; } int add(int x) { int l = 1, r = k, res = 0; //查詢k個(gè)聯(lián)通塊 while(l <= r) { int mid = (l + r) >> 1; if(check(e[x].u, e[x].v, mid)) { res = mid; r = mid - 1; } else l = mid + 1; } if(res == 0) return 0; int fu = P[res].Find(e[x].u); int fv = P[res].Find(e[x].v); P[res].fa[fu] = fv; return res; } int main() { scanf("%d%d%d", &n, &m, &k); for(int i = 1; i <= m; i++) { scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].val); e[i].id = i; } for(int i = 1; i <= k; i++) for(int j = 1; j <= n; j++) P[i].fa[j] = j; //初始化 sort(e + 1, e + 1 + m, mycmp); for(int i = 1; i <= m; i++) { int now = add(i); //將第i個(gè)邊加入連通塊 ans[e[i].id] = now; } for(int i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0; }

ABC321F :退背包

正解:性質(zhì)題

如果只有$+$我們發(fā)現(xiàn)就是一道背包題，但是如果有$-$操作呢？

但是$+$操作的順序?qū)Υ鸢赣杏绊憜?顯然是沒有的，題目保證不會(huì)出現(xiàn)刪去沒有出現(xiàn)過(guò)的數(shù)，我們不妨讓刪去的數(shù)放在整個(gè)序列的最后一個(gè)，倒著刪一下即可

//若只有+則序列順序無(wú)所謂直接背包 //若有- 則考慮將序列構(gòu)造成 -的數(shù)放在最后一個(gè) //反向-一下即可 #include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 5100; const int MOD = 998244353; int q, k, f[MAX + 10]; int main() { scanf("%d%d", &q, &k); f[0] = 1; while(q, q--) { char ch; int x; scanf("\n%c%d", &ch, &x); if(ch == '+') { for(int i = MAX; i >= x; i--) { f[i] = (f[i - x] + f[i] ) % MOD; } } else { for(int i = x; i <= MAX; i++) { f[i] = (f[i] - f[i - x] + MOD) % MOD; } } printf("%d\n", f[k]); } return 0; }

農(nóng)場(chǎng)道路修建 : 問(wèn)題轉(zhuǎn)化

正解：問(wèn)題轉(zhuǎn)化

題目的大致含義為在$\frac{N * (N - 1)}{2}$的點(diǎn)對(duì)中增加一條邊后的基環(huán)樹的最大點(diǎn)支配集與原樹的大小保持不變

如何思考:
1.我們首先發(fā)現(xiàn)在樹上增加一條新的邊一定不會(huì)讓最大點(diǎn)支配集的個(gè)數(shù)變大，其影響一定只會(huì)變小和保持不變

2. 如果在某一種最大點(diǎn)支配集的選擇方案中,
(選擇點(diǎn)，選擇點(diǎn)) 會(huì)讓方案變小，
(無(wú)，選擇點(diǎn))，(無(wú)，無(wú))不會(huì)讓答案變小

顯然性質(zhì)2很好實(shí)現(xiàn)，但如果一顆樹有多種最大點(diǎn)支配集選擇方案該怎么處理, 這時(shí)候會(huì)出現(xiàn)許多重復(fù)

方法一 :

用總數(shù)減去(必選點(diǎn)，必選點(diǎn)) 的方案

方法二 :

(無(wú))點(diǎn)：在某種最大點(diǎn)支配集的選擇方案中可以不選的點(diǎn)
用(無(wú))點(diǎn)統(tǒng)計(jì)答案，因?yàn)?無(wú))點(diǎn)與其他任意一個(gè)點(diǎn)連都可以，但(無(wú))點(diǎn)之間會(huì)多連，所以答案為$Wu_{sum} (n - 1) -\frac{Wu_{sum}(Wu_{sum}-1)}{2}$

選擇方法2: 具體方法已經(jīng)清楚，如何將多種最大點(diǎn)支配集的(無(wú))點(diǎn)選出來(lái)?
首先對(duì)原樹做一遍最大點(diǎn)支配集，從根向下遍歷
如果$bol ==1$即這個(gè)點(diǎn)選擇，向下遍歷時(shí)選擇$son[x]$,$bol$修改為0
如果$bol == 0$即這個(gè)點(diǎn)不選，向下遍歷時(shí)$bol$修改為$f[][0/1]$較大的，如果一樣同時(shí)遍歷
如果當(dāng)前點(diǎn)的$bol==0$打上標(biāo)記，最后統(tǒng)計(jì)總數(shù)

方法2 #include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 3e5 + 70; int n, tot, head[MAX]; bool flag[MAX]; LL f[MAX][3], ans; // 0 / 1 不選，選 int mp[MAX][2]; vector<int> son[MAX]; struct made { int l, t; }edge[MAX * 2]; void add(int u, int v) { edge[++tot].l = head[u]; edge[tot].t = v; head[u] = tot; } void dfs_pre(int x, int fa) { // printf("x %d fa %d\n", x, fa); for(int i = head[x]; i; i = edge[i].l) { int t = edge[i].t; if(t == fa) continue; son[x].push_back(t); dfs_pre(t, x); } } void dfs(int x) { if(son[x].size() == 0) { f[x][1] = 1; f[x][0] = 0; return ; } int len = son[x].size(); for(int i = 0; i < len; i++) { dfs(son[x][i]); f[x][1] += f[son[x][i]][0]; f[x][0] += max(f[son[x][i]][0], f[son[x][i]][1]); } f[x][1] += 1; return ; } void dfs_work(int now, int bol) { if(mp[now][bol]) return ; mp[now][bol] = 1; if(bol == 0) flag[now] = 1; for(int i = 0; i < son[now].size(); i++) { int to = son[now][i]; if(bol == 0) { if(f[to][0] > f[to][1]) dfs_work(to, 0); else if(f[to][0] == f[to][1]) { dfs_work(to, 0); dfs_work(to, 1); } else dfs_work(to, 1); } else { dfs_work(to, 0); } } } int main() { freopen("road.in","r",stdin); freopen("road.out","w",stdout); scanf("%d", &n); for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); add(u, v); add(v, u); } dfs_pre(1, 0); dfs(1); if(f[1][0] > f[1][1]) { dfs_work(1, 0); } else if(f[1][0] == f[1][1]) { // cout<<"ooo"; dfs_work(1, 0); dfs_work(1, 1); } else dfs_work(1, 1); LL sum1 = 0, sum2 = 0; for(int i = 1; i <= n; i++) { if(flag[i] == 1) sum1++, ans += (n - 1); else sum2++; } // cout<<ans<<" "<<sum1<<endl; cout<<ans - ((sum1 - 1) * sum1 / 2)<<endl; return 0; }

密碼鎖：優(yōu)化DP

25pts:DP

首先排除貪心的思路，對(duì)于前三擋我們希望擁有一個(gè)帶常數(shù)的$N*Q$的算法，考慮設(shè)計(jì)DP狀態(tài)，$f[i][j]$表示填充前$i$位，第$i$為$j$的最小代價(jià)
時(shí)間復(fù)雜度$NQ26*26$ 勉強(qiáng)跑過(guò)?

55pts：區(qū)間DP+線段樹優(yōu)化

發(fā)現(xiàn)上面的狀態(tài)沒有拓展性，希望轉(zhuǎn)化狀態(tài)，然后發(fā)現(xiàn)修改先后順序無(wú)所為，只需要讓兩個(gè)相鄰區(qū)間合并時(shí)滿足$Lr <= Rl$即可，考慮區(qū)間DP$f[L][R][l][r]$表示左右端點(diǎn)為$L,R$左右填充$l, r$的最小代價(jià)
考慮簡(jiǎn)化狀態(tài):我們發(fā)現(xiàn)設(shè)定的DP狀態(tài)中很多都不必要存在，修改符合結(jié)合率，考慮線段樹倍增優(yōu)化這個(gè)狀態(tài)

#include<bits/stdc++.h> // 25 感覺可以優(yōu)化(DP 區(qū)間可合并，線段樹) using namespace std; #define LL long long const int MAX = 1e5 + 70; int fp[MAX][30]; int q, len; char ch[MAX]; int cha(int x, int y) { //x -> y的最小花費(fèi) if(x < y) return y - x; else return x - y; } struct SegmentTree { int l, r; int f[6][6]; //左端點(diǎn)，右端點(diǎn)分別填啥 #define l(x) tree[x].l #define r(x) tree[x].r #define t(x) tree[x] }tree[MAX * 4]; void update(int p) { memset(t(p).f, 0x3f, sizeof(t(p).f)); for(int ll = 1; ll <= 5; ll++) { for(int lr = ll; lr <= 5; lr++) { for(int rl = lr; rl <= 5; rl++) { for(int rr = rl; rr <= 5; rr++) { t(p).f[ll][rr] = min(t(p).f[ll][rr], t(2 * p).f[ll][lr] + t(2 * p + 1).f[rl][rr]); // printf("p %d l %d r %d f[%d][%d] %d\n",p, l(p), r(p), ll, rr, t(p).f[ll][rr]); } } } } return ; } void build(int p, int l, int r) { memset(t(p).f, 0x3f, sizeof(t(p).f)); l(p) = l, r(p) = r; if(l == r) { int val = (int)(ch[l] - 'a' + 1); memset(t(p).f, 0x3f, sizeof(t(p).f)); for(int i = 1; i <= 5; i++) { t(p).f[i][i] = cha(val, i); // printf("l %d r %d .f[%d][%d] %d\n", l, r, i, i, t(p).f[i][i]); } return ; } int mid = (l + r) >> 1; build(2 * p, l, mid); build(2 * p + 1, mid + 1, r); update(p); } void change(int p, int l, int r, int val) { if(l(p) == r(p)) { memset(t(p).f, 0x3f, sizeof(t(p).f)); for(int i = 1; i <= 5; i++) { t(p).f[i][i] = cha(val, i); // printf("l %d r %d .f[%d][%d] %d val %d \n", l, r, i, i, t(p).f[i][i], val); } return ; } int mid = (l(p) + r(p)) / 2; if(l <= mid) change(2 * p, l, r, val); if(r > mid) change(2 * p + 1, l, r, val); update(p); return ; } int GET_ANS() { int ans = 0x3f3f3f3f; for(int i = 1; i <= 5; i++) { for(int j = i; j <= 5; j++) { // printf("f[%d][%d] %d\n", i, j, t(1).f[i][j]); ans = min(ans, t(1).f[i][j]); } } return ans; } void prework() { memset(fp, 0x3f, sizeof(fp)); for(int i = 1; i <= 26; i++) { fp[1][i] = cha(int(ch[1] - 'a' + 1), i); } for(int i = 2; i <= len; i++) { for(int j = 1; j <= 26; j++) { //當(dāng)前這位填啥 for(int k = 1; k <= j; k++) { fp[i][j] = min(fp[i][j], fp[i - 1][k] + cha((int)(ch[i] - 'a' + 1), j)); } } } } int main() { freopen("lock.in","r",stdin); freopen("lock.out","w", stdout); scanf("%s", ch + 1); len = strlen(ch + 1); build(1, 1, len); scanf("%d", &q); if(q <= 10) { prework(); int ans = 0x3f3f3f3f; for(int i = 1; i <= 26; i++) { ans = min(ans, fp[len][i]); } cout<<ans<<endl; for(int i = 1; i <= q; i++) { int id; cin>>id; char chr; cin>>chr; int ans = 0x3f3f3f3f; ch[id] = chr; int now = int(chr - 'a') + 1; prework(); for(int j = 1; j <= 26; j++) { ans = min(ans, fp[len][j]) ; } cout<<ans<<endl; } return 0; } int ans = GET_ANS(); cout<<ans<<endl; for(int i = 1; i <= q; i++) { int id; cin>>id; char chr; cin>>chr; int now = int(chr - 'a') + 1; // cout<<"id "<<id<<" now "<<now<<endl; change(1, id, id, now); int ans = GET_ANS(); cout<<ans<<endl; } return 0; }

100pts：?jiǎn)栴}轉(zhuǎn)化+性質(zhì)

在全部數(shù)據(jù)中如果左右端點(diǎn)都有26種選擇，那么$26 * 262626$的巨大常數(shù)直接爆炸

發(fā)現(xiàn)問(wèn)題可以轉(zhuǎn)化為將序列進(jìn)行26次只含有(0/1)的最小代價(jià)之和，對(duì)于設(shè)$i$∈$[a,z]$分別將序列中的大于等于i的設(shè)為1，小于i的設(shè)為0，將代價(jià)累加起來(lái)即為答案
為什么這樣轉(zhuǎn)化問(wèn)題是正確且保證最小？(不是很懂)
證明:

任務(wù)四的方法對(duì)于26的矩陣可能比較慢，設(shè)b(S,i)為一個(gè)長(zhǎng)度為n的01串，第j個(gè)位置的值表示[S_j>=i]，也就是當(dāng)S_j>=i,該位置是1，否則是0。
那么對(duì)于b(S,i)，可以當(dāng)作只有a,b兩種字符的問(wèn)題的求解。
令F(s)為s串的答案，下面證明：$\sum_{i='a'}^{'z'}F(b(S,i))=F(S)$
對(duì)于原串的一種最優(yōu)解S',考慮對(duì)于一個(gè)位置j，有|S_j-S'j|個(gè)i在j位置是不同的，也就是有這么多i在該位置是有代價(jià)的。因此，對(duì)于任意一種最優(yōu)解都有一種代價(jià)相等的將所有的b(S,i)變?yōu)閎(S',i)的方案。因此$\sum_{i='a'}^{'z'}F(b(S,i))\le F(S)$
考慮對(duì)于每個(gè)i，b(S,i)的最佳答案。設(shè)$Z_i$為該答案中0的個(gè)數(shù)。
如果$Z_i$單調(diào)遞增，那么把i號(hào)字符放在$[Z_i,Z_i+1)$就能構(gòu)造一種恰好答案相等的原串方案。
如果$Z_i$不單調(diào)遞增，假設(shè)$Z_i>Z_{i+1}$，那么交換i和i+1的方案不會(huì)使答案更劣，因?yàn)閷?duì)于每個(gè)位置，b(S,i)和b(S,i+1)的對(duì)位情況只能有(1,0),(0,0),(1,1)。因此如果出現(xiàn)$Z_i>Z_{i+1}$，那么對(duì)位就出現(xiàn)了(0,1),一定是可以交換的。那么通過(guò)交換，可以得到一個(gè)$Z_i$單調(diào)遞增的方案。那么也就說(shuō)明了
$\sum_{i='a'}^{'z'}F(b(S,i))\ge F(S)$
因此
$\sum_{i='a'}^{'z'}F(b(S,i))= F(S)$
對(duì)于每個(gè)01串分開做動(dòng)態(tài)dp，要比26大小的矩陣做動(dòng)態(tài)dp要更快，即可得到滿分**

#include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 1e5 + 70; int fp[MAX][30]; int q, len; char ch[MAX]; int cha(int x, int y) { //x -> y的最小花費(fèi) if(x < y) return y - x; else return x - y; } struct SegmentTree { int l, r; int f[2][2]; //左端點(diǎn)，右端點(diǎn)分別填啥 #define l(x,y) tree[x][y].l #define r(x,y) tree[x][y].r #define t(x,y) tree[x][y] }tree[30][MAX * 4]; void update(int p) { for(int i = 1; i <= 26; i++) memset(t(i, p).f, 0x3f, sizeof(t(i, p).f)); for(int ro = 1; ro <= 26; ro++) { for(int ll = 0; ll <= 1; ll++) { for(int lr = ll; lr <= 1; lr++) { for(int rl = lr; rl <= 1; rl++) { for(int rr = rl ; rr <= 1; rr++) { t(ro, p).f[ll][rr] = min(t(ro, p).f[ll][rr], t(ro, 2 * p).f[ll][lr] + t(ro, 2 * p + 1).f[rl][rr]); } } } } } return ; } void build(int p, int l, int r) { for(int i = 1; i <= 26; i++) memset(t(i, p).f, 0x3f, sizeof(t(i, p).f)); for(int i = 1; i <= 26; i++) l(i, p) = l, r(i, p) = r; if(l == r) { for(int i = 1; i <= 26; i++) { memset(t(i, p).f, 0x3f, sizeof(t(i, p).f)); int val = (ch[l] - 'a' + 1 >= i ? 1 : 0); for(int j = 0; j <= 1; j++) t(i, p).f[j][j] = cha(val, j); } return ; } int mid = (l + r) >> 1; build(2 * p, l, mid); build(2 * p + 1, mid + 1, r); update(p); } void change(int p, int l, int r, int val) { if(l(1, p) == r(1, p)) { for(int i = 1; i <= 26; i++) { memset(t(i, p).f, 0x3f, sizeof(t(i, p).f)); int V = (val >= i ? 1 : 0); for(int j = 0; j <= 1; j++) t(i, p).f[j][j] = cha(V, j); } return ; } int mid = (l(1, p) + r(1, p)) / 2; if(l <= mid) change(2 * p, l, r, val); if(r > mid) change(2 * p + 1, l, r, val); update(p); return ; } int GET_ANS() { int ans = 0; for(int i = 1; i <= 26; i++) { int sum = 0x3f3f3f3f; for(int l = 0; l <= 1; l++) { for(int r = l; r <= 1; r++) sum = min(sum, t(i, 1).f[l][r]); } ans += sum; } return ans; } int main() { freopen("lock.in","r",stdin); freopen("lock.out","w", stdout); scanf("%s", ch + 1); len = strlen(ch + 1); build(1, 1, len); scanf("%d", &q); int ans = GET_ANS(); cout<<ans<<endl; for(int i = 1; i <= q; i++) { int id; cin>>id; char chr; cin>>chr; int now = int(chr - 'a') + 1; change(1, id, id, now); int ans = GET_ANS(); cout<<ans<<endl; } return 0; }

魔法是變化之神

60pts:背包,求補(bǔ)集

將答案分成兩部分，第一部分為固定答案，第二部分為減少的總數(shù)，將$SIZ[]$看做體積，將減小量看做價(jià)值，背包即可拿到60pts

#include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 110000; int n, m, ANS, siz[MAX], fat[MAX]; int tot, head[MAX], f[MAX]; struct made { int l, t, val; }edge[MAX *2], e[MAX *2]; void add(int u, int v, int val) { edge[++tot].l = head[u]; edge[tot].t = v; edge[tot].val = val; head[u] = tot; } void dfs_pre(int x, int fa) { fat[x] = fa; siz[x] = 1; for(int i = head[x]; i; i = edge[i].l) { int t = edge[i].t; if(t == fa) continue; dfs_pre(t, x); siz[x] += siz[t]; } } int main() { freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); scanf("%d%d", &n, &m); for(int i = 1; i < n; i++) { int u, v, val; scanf("%d%d%d", &u, &v, &val); e[i].l = u, e[i].t = v, e[i].val = val; add(u, v, val); add(v, u, val); } dfs_pre(1, 0); for(int i = 1; i <= n; i++) { int U = e[i].l; if(fat[U] != e[i].t) U = e[i].t; ANS += ((n - siz[U]) * (siz[U]) * e[i].val); for(int j = m; j >= siz[U]; j--) { f[j] = max(f[j], f[j - siz[U]] + (n - siz[U]) * (siz[U] * e[i].val)); } } cout<<ANS - f[m]; return 0; }

100pts：考慮隨機(jī)數(shù)據(jù)

因?yàn)閿?shù)據(jù)隨機(jī)，所以SIZ的期望個(gè)數(shù)有$log_{n}$中，因?yàn)檫叺膬r(jià)值最多為5，將價(jià)值和$SIZ$相同的合并在一起，多重背包即可

#include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 110000; int n, m; LL ANS; int siz[MAX], fat[MAX]; int tot, head[MAX]; LL f[MAX]; int cnt[MAX][10]; struct made { int l, t, val; }edge[MAX *2], e[MAX *2]; void add(int u, int v, int val) { edge[++tot].l = head[u]; edge[tot].t = v; edge[tot].val = val; head[u] = tot; } void dfs_pre(int x, int fa) { fat[x] = fa; siz[x] = 1; for(int i = head[x]; i; i = edge[i].l) { int t = edge[i].t; if(t == fa) continue; dfs_pre(t, x); siz[x] += siz[t]; } } void work() { for(int i = 1; i < n; i++) { int U = e[i].l; if(fat[U] != e[i].t) U = e[i].t; ANS += ((LL)(n - siz[U]) * (LL)(siz[U]) * (LL)e[i].val); cnt[siz[U]][e[i].val]++; } } inline int read() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = (x * 10 + f * (int)(c - '0')); c = getchar(); } return x; } int main() { freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); n = read(), m = read(); // cout<<n<<endl; for(int i = 1; i < n; i++) { int u, v, val; u = read(), v = read(), val = read(); e[i].l = u, e[i].t = v, e[i].val = val; add(u, v, val); add(v, u, val); } dfs_pre(1, 0); work(); for(int j = 100000; j >= 1; j--) { for(int k = 5; k >= 1; k--) { if(cnt[j][k] == 0) continue; int C2 = 1; while(C2 <= cnt[j][k]) { LL W = C2 * (LL)j, val = (LL)C2 * k * j * (n - j); for(int i = m; i >= W; i--) f[i] = max(f[i], f[i - W] + val); cnt[j][k] -= C2; C2 *= 2; } if(cnt[j][k]) { LL W = cnt[j][k] * j, val = (LL)cnt[j][k] * k * j * (n - j); for(int i = m; i >= W; i--) f[i] = max(f[i], f[i - W] + val); } } } cout<<ANS - f[m]; return 0; }

奶牛的數(shù)學(xué)題:單位貢獻(xiàn)

正解

看題看到數(shù)據(jù)范圍就應(yīng)該想到這題是一道數(shù)學(xué)題，或者(矩陣乘法)，但顯然無(wú)法寫出線性遞推式，所以應(yīng)該往數(shù)學(xué)上思考
1.如果一個(gè)數(shù)的$f(x) = i$, 則$x$最小為$lcm(1~i)$, 可得$f(x) <= 50$
2.將$num[i] * i = \sum _{i = 1}^{{i<=50}\sum_{j=i}} num[j]$

所以題目轉(zhuǎn)化為了對(duì)于每一個(gè)$i \in50$ $f(x) \ge i$的個(gè)數(shù)，如何計(jì)算個(gè)數(shù)，通過(guò)1可得，若$f(x) \ge i$則$x$必須為$lcm\left { 1,2,3...(i-1) \right }$的倍數(shù)，計(jì)算即可

#include<bits/stdc++.h> //將貢獻(xiàn)拆為單位貢獻(xiàn) using namespace std; #define LL long long const int MAX = 1e4 + 70; const int MOD = 1e9 + 7; int main() { freopen("math.in","r",stdin); freopen("math.out","w",stdout); int t; scanf("%d", &t); while(t, t--) { LL n; scanf("%lld", &n); LL SUM = 1, ans = n % MOD; for(int i = 2; i <= 50; i++) { if(SUM > n) break; ans = (ans + (n / SUM)) % MOD; SUM = SUM * i / __gcd(SUM, (LL)i); } cout<<ans<<endl; } return 0; }

路遇矩陣

![在這里插入圖片描述](https://img-blog.csdnimg.cn/ebf8c6c09c734061994736bda3de3ef3.png

1.20pts的部分分是一個(gè)很好的切入點(diǎn)，我們發(fā)現(xiàn)只有行和只有列順序無(wú)關(guān)，貪心的選一定最優(yōu)

2.但是行和列放在一起，肯定不能貪心，因?yàn)槿绻x的次數(shù)$k$非常大，行數(shù)小，列數(shù)恰好為$k$,那么選$k$列反而最優(yōu)
如何解決? 枚舉選多少個(gè)行，多少個(gè)列即可

//1. 刪除順序與答案統(tǒng)計(jì)無(wú)關(guān)，答案只與選擇有關(guān) //2. 只刪行與只刪列滿足貪心性質(zhì) #include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 1e3 + 70; int n, m, k, p; int a[MAX][MAX]; LL ans = 0, ANS = -1e18, H[1100000], L[1100000]; multiset<LL> h, l; int main() { freopen("matrix.in","r",stdin); freopen("matrix.out","w",stdout); scanf("%d%d%d%d", &n, &m, &k, &p); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d", &a[i][j]); for(int i = 1; i <= n; i++) { LL sum = 0; for(int j = 1; j <= m; j++) sum += a[i][j]; h.insert(sum); } for(int j = 1; j <= m; j++) { LL sum = 0; for(int i = 1; i <= n; i++) sum += a[i][j]; l.insert(sum); } LL sum = 0; for(int i = 0; i <= k; i++) { //控制刪i個(gè)行 H[i] = sum; sum += *h.rbegin(); LL NOW = *h.rbegin(); set<LL>::iterator it = h.end(); it--; h.erase(it); h.insert(NOW - (LL)p * m); } sum = 0; for(int i = 0; i <= k; i++) { L[i] = sum; sum += *l.rbegin(); LL NOW = *l.rbegin(); set<LL>::iterator it = l.end(); it--; l.erase(it); l.insert(NOW - (1LL * p * n)); } for(int i = 0; i <= k; i++) { ANS = max(ANS, L[i] + (H[k - i] - (1LL * p * i * (k - i)))); } cout<<ANS<<endl; return 0; }

奶牛的括號(hào)匹配:狀壓

一眼狀壓，但是如何設(shè)計(jì)狀態(tài)呢?
首先套路的設(shè)定$f(i)$表示選定集合$i$所能產(chǎn)生的最大前綴匹配個(gè)數(shù)

但是若將$j$加入集合$i$必須滿足當(dāng)前的$i$集合的最大方案是可以拓展的

那我們規(guī)定$f(i)$表示 $i$ 集合的最大答案，且當(dāng)前的排列順序保證可以拓展即 $($ 的個(gè)數(shù) 始終$\ge$ $)$

那么如何計(jì)算$j$對(duì)于集合$i$的貢獻(xiàn)，如果集合$i$的剩余 ${\color{Green} {\LARGE （} }$ 括號(hào)的個(gè)數(shù)為 $k$, 那么$j$所能貢獻(xiàn)的數(shù)量即為$cnt_jk$表示第$j$個(gè)串前綴${\color{Green} {\LARGE ）} }$個(gè)數(shù)為$k$的數(shù)量位置

//狀壓DP，狀態(tài)設(shè)計(jì) // f[i] 表示集合i最大答案，轉(zhuǎn)移 // 往i中添加新的字符串j，考慮j的貢獻(xiàn) // 若集合i匹配完仍剩OP個(gè)( 計(jì)算j的貢獻(xiàn) #include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 22; const int oo = 114514123; int n, ans, cnt[MAX][410000]; //表示第i個(gè)串，出現(xiàn)j的個(gè)數(shù) int f[(1 << MAX)]; int maxx[MAX], END[410000]; //表示第j個(gè)的最大的) 和每個(gè)串最后的值 string s[MAX]; int num[(1 << MAX)]; //表示集合i的剩余(個(gè)數(shù) void prework(int id, string S) { int sum = 0; maxx[id] = -oo; for(int i = 0; i < S.size(); i++) { if(S[i] == '(') sum--; else sum++; maxx[id] = max(maxx[id], sum); if(sum >= maxx[id]) cnt[id][sum]++; } END[id] = sum; } int main() { freopen("seq.in","r",stdin); freopen("seq.out","w",stdout); scanf("%d", &n); for(int i = 0; i < n; i++) cin>>s[i]; // 第i個(gè)串 for(int i = 0; i < n; i++) prework(i, s[i]); //預(yù)處理第i個(gè)串的信息 for(int i = 0; i <= (1 << 21) - 1; i++) f[i] = -oo; f[0] = 0; for(int i = 0; i <= (1 << n) - 1; i++) { //枚舉 i集合 for(int j = 0; j < n; j++) { //選擇第j個(gè)填加 if( (i >> j ) & 1) continue; if(num[i] >= maxx[j]) { //說(shuō)明可以更新下一個(gè)f集合 f[i | (1 << j)] = max(f[i | (1 << j)], f[i] + cnt[j][num[i]]); num[i | (1 << j)] = num[i] - END[j]; ans = max(ans, f[i | (1 << j)]); } else { //不可以更新f集合但是可以統(tǒng)計(jì)答案 ans = max(ans , f[i] + cnt[j][num[i]]); num[i | (1 << j)] = num[i] - END[j]; } } } cout<<ans<<endl; return 0; }

潤(rùn)不掉了：轉(zhuǎn)化點(diǎn)對(duì)問(wèn)題

一步一步分析

20pts:爆搜，但是不好打

40pts

我們分析，如果對(duì)于當(dāng)前的根為$root$

對(duì)于$root$的若干子樹，什么子樹需要貢獻(xiàn)1(被一個(gè)點(diǎn)看守)的答案呢?

那么應(yīng)該是子樹$i$中的葉節(jié)點(diǎn)到$ro_i$的最小距離$\le$$dis(x,roi)$,

我們預(yù)處理葉子節(jié)點(diǎn)到其他點(diǎn)的最小距離，枚舉每一個(gè)點(diǎn)為根，向下遞歸答案即可

#include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 7e4 + 70; int n, tot, head[MAX], du[MAX], len[MAX]; vector<int> son[MAX]; // queue<int> q; void BFS() { while(!q.empty()) { int now = q.front(); q.pop(); for(auto y : son[now]) { if(len[y] > len[now] + 1) { len[y] = len[now] + 1; q.push(y); } } } } int dfs(int now, int fa, int dis) { if(len[now] <= dis) return 1; if(du[now] == 1) return 1; int sum = 0; for(auto y : son[now]) { if(y == fa) continue; sum = sum + dfs(y, now, dis + 1); } return sum; } int main() { freopen("run.in","r",stdin); freopen("run.out","w",stdout); scanf("%d", &n); for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); son[u].push_back(v); son[v].push_back(u); //存邊 du[u] += 1; du[v] += 1; } memset(len, 0x3f, sizeof(len)); for(int i = 1; i <= n; i++) if(du[i] == 1) len[i] = 0, q.push(i); BFS() ; // 處理 for(int i = 1; i <= n; i++) { int ans = dfs(i, 0, 0) ; // 第i 個(gè)點(diǎn)向子樹跑 printf("%d\n", ans); } return 0; }

100pts 子樹貢獻(xiàn)轉(zhuǎn)化

我們想，40pts沒有拓展性，因?yàn)闊o(wú)論怎樣，枚舉根的操作已經(jīng)限制了整個(gè)算法，如何拓展呢?

我們想對(duì)于$x$有貢獻(xiàn)子樹的每個(gè)點(diǎn)都滿足$g(i) \le dis(i,x))$,

如果我們將整棵子樹的貢獻(xiàn)設(shè)為1的話，那么就是計(jì)算點(diǎn)對(duì)問(wèn)題，顯然淀粉質(zhì)就可以了

下面思考樹的子樹的性質(zhì)

$\sum{du}=2siz-1$
變形
$\sum{du}-2siz=1$
$\sum{du-2}=1$
所以我們將每個(gè)點(diǎn)的val設(shè)為$du -2$對(duì)于點(diǎn)$x$的ans即為滿足

$g(i)\le dis(i,x)$的所有點(diǎn)的val之和
若$ro$為分治重心,統(tǒng)計(jì)過(guò)$ro$的點(diǎn)的答案
則$g(i)\le dis(ro,i)+dis(ro,x)$
則$g(i)-dis(ro,i)<=dis(ro,x)$
樹狀數(shù)組維護(hù)

#include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 7e4 + 70; int n, tot, head[MAX], du[MAX], len[MAX], val[MAX]; bool v[MAX]; vector<int> son[MAX]; // queue<int> q; int ro, maxx_tr, f[MAX], dis[MAX], siz[MAX], g[MAX], NUM; int tree[MAX << 1], ans[MAX]; int lowbit(int x) { return x & (-x); } void add(int x, int val) { for(int i = x; i <= 2 * n; i += lowbit(i)) tree[i] += val; } int Find(int x) { int sum = 0; for(int i = x; i; i -= lowbit(i)) sum += tree[i]; return sum; } void get_root(int x, int fa) { //求重心 siz[x] = 1, f[x] = 0; for(auto To : son[x]) { if(To == fa || v[To]) continue; get_root(To, x); siz[x] += siz[To]; f[x] = max(f[x], siz[To]); } f[x] = max(f[x], NUM - siz[x]); if(f[x] < maxx_tr) { maxx_tr = f[x]; ro = x; } } void Clear() { maxx_tr = n + 1; } void get_size(int x, int fa) { siz[x] = 1; for(auto y : son[x]) { if(y == fa || v[y]) continue; get_size(y, x); siz[x] += siz[y]; } } void calc(int x, int fa) { dis[x] = dis[fa] + 1; ans[x] = ans[x] + Find(dis[x] + n); //加上n的偏移量 for(auto y : son[x]) { if(y == fa || v[y]) continue; calc(y, x); } } void change(int x, int fa, int zf) { add(n + g[x] - dis[x], zf * val[x]); for(auto y : son[x]) { if(y == fa || v[y]) continue; change(y, x, zf); } } void work(int x, int id) { dis[x] = 0; if(id == 1) add(g[x] + n, val[x]); //端點(diǎn)有x，x的影響 for(auto y : son[x]) { if(v[y]) continue; calc(y, x); //統(tǒng)計(jì)當(dāng)前這顆子樹的答案 change(y, x, 1); //將影響加上去 } if(id == 1) ans[x] += Find(n);//計(jì)算端點(diǎn)值 for(auto y : son[x]) { //倒著做一次 if(v[y]) continue; change(y, x, -1); } if(id == 1) add(g[x] + n, -val[x]); } void slove(int x) { //計(jì)算過(guò)x的點(diǎn)對(duì)之間的答案 v[x] = 1; work(x, 1); reverse(son[x].begin(), son[x].end()); work(x, 2); for(auto y :son[x]) { if(v[y]) continue; Clear(); get_size(y, x); NUM = siz[y]; get_root(y, x); //分治下去 slove(ro); } } void BFS() { while(!q.empty()) { int now = q.front(); q.pop(); for(auto y : son[now]) { if(g[y] > g[now] + 1) { g[y] = g[now] + 1; q.push(y); } } } } int main() { // freopen("run.in","r",stdin); // freopen("run.out","w",stdout); scanf("%d", &n); for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); son[u].push_back(v); son[v].push_back(u); du[u] += 1; du[v] += 1; } memset(g, 0x3f, sizeof(g)); for(int i = 1; i <= n; i++) if(du[i] == 1) q.push(i), g[i] = 0; //多源最短路 BFS(); for(int i = 1; i <= n; i++) val[i] = 2 - du[i]; //問(wèn)題轉(zhuǎn)化， Clear(); get_size(1, 0); NUM = siz[1]; get_root(1, 0); slove(ro); for(int i = 1; i <= n; i++) { if(du[i] == 1) printf("1\n"); else printf("%d\n", ans[i]); } return 0; }

美好的查詢:神奇主席樹

80pts：分塊+并查集

~~不是很懂，先鍋著~~

100pts:神奇主席樹，多看看

數(shù)據(jù)范圍為$5e5$，也就是說(shuō)我們希望得到一個(gè)$log$常數(shù)級(jí)別的程序，如何思考?

首先發(fā)現(xiàn)只有區(qū)間修改與區(qū)間查詢，而修改是將某一個(gè)范圍的固定值修改,且值不會(huì)大于$5e5$

如果我們?cè)谝活w線段樹上做的話，點(diǎn)權(quán)值不同無(wú)法統(tǒng)計(jì)且時(shí)間復(fù)雜度不能保證，我們按值分組

構(gòu)建$5e5$棵線段樹，每一顆線段樹對(duì)應(yīng)著一個(gè)值，初始將$ro[0]$的樹的每個(gè)節(jié)點(diǎn)都設(shè)為$1$,如果出現(xiàn)將某段區(qū)間加$1$操作，將$ro[x+1]$區(qū)間指向$ro[x]$的區(qū)間，但是我們會(huì)發(fā)現(xiàn)一個(gè)問(wèn)題，細(xì)看下面的錯(cuò)誤操作

如果我們按照上述數(shù)據(jù)依次操作，我們發(fā)現(xiàn)原本不屬于$ro[2]$的節(jié)點(diǎn)卻被歸到的$ro[2]$,也就是說(shuō)我們對(duì)當(dāng)前某一個(gè)值的修改會(huì)影響到下一個(gè)值，貌似很難處理，但實(shí)際很簡(jiǎn)單，重新開一顆樹

這樣就很好解決了這個(gè)問(wèn)題!為保證空間，采用動(dòng)態(tài)開點(diǎn)

~~總結(jié)不出來(lái)什么啊~~

//在線， 5e5考慮log做法，值域主席樹可維護(hù)，二分查最大值，復(fù)雜度n*log^2 #include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 5e5 + 80; const int logMAX = 170; int n, q, ro[MAX], tot; struct made { int id, l, r, x; }ask[MAX]; struct SegmentTree { int lson, rson, sum; #define lson(x) tree[x].lson #define rson(x) tree[x].rson #define sum(x) tree[x].sum }tree[MAX * logMAX]; int build() { return ++tot; } void update(int p) { sum(p) = sum(lson(p)) + sum(rson(p)); } void pre_build_0(int p, int l, int r) { if(l == r) { sum(p) = 1; return ; } lson(p) = build(); rson(p) = build(); int mid = (l + r) >> 1; pre_build_0(lson(p), l, mid); pre_build_0(rson(p), mid + 1, r); update(p); } int copy(int p, int q, int L, int R, int l, int r) { if(L >= l && R <= r) { return p; } //為什么一定正確，反證法 if(p == 0) return p; int now = build(); tree[now] = tree[q]; //復(fù)制 int mid = (L + R) >> 1; if(mid >= l) lson(now) = copy(lson(p), lson(now), L, mid, l, r); if(r > mid) rson(now) = copy(rson(p), rson(now), mid + 1, R, l, r); update(now); return now; } int qurry(int p, int L, int R, int l, int r) { if(L >= l && R <= r) { return sum(p); } int sum = 0; int mid = (L + R) >> 1; if(l <= mid) sum = sum + qurry(lson(p), L, mid, l, r); if(r > mid) sum = sum + qurry(rson(p), mid + 1, R, l, r); return sum; } int Find(int L, int R) { int l = 0, r = 5e5, ans = 0; while(l <= r) { int mid = (l + r) >> 1; if(qurry(ro[mid],1, n, L, R)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans; } int main() { freopen("Innocent.in","r",stdin); freopen("Innocent.out","w",stdout); scanf("%d%d", &n, &q); ro[0] = build(); pre_build_0(ro[0], 1, n); //建0的樹 for(int i = 1; i <= q; i++) { int op; scanf("%d", &ask[i].id); if(ask[i].id == 1) scanf("%d%d%d", &ask[i].l, &ask[i].r, &ask[i].x); if(ask[i].id == 2) scanf("%d%d",&ask[i].l, &ask[i].r); } for(int i = 1; i <= q; i++) { if(ask[i].id == 1) { int now = copy(ro[ask[i].x], ro[ask[i].x + 1], 1, n, ask[i].l, ask[i].r); //保證空間為log ro[ask[i].x + 1] = now; } else { int ans = Find(ask[i].l, ask[i].r); printf("%d\n", ans); } } return 0; }

新涂色游戲:操作反做

回頭看這道題其實(shí)非常簡(jiǎn)單

對(duì)于涂色,整行或整列，則最后一定有一整行或一整列為一個(gè)顏色，反著做，再將操作reverse就可以了

//正著做不好做，反著刪 #include<bits/stdc++.h> using namespace std; #define LL long long #define PII pair<int, int> const int MAX = 1100; int n, a[MAX][MAX], tot; bool can[2 * MAX]; int num[2 * MAX][2 * MAX], kind[2 * MAX]; PII ans[2 * MAX]; void work(int id) { if(id <= n) { int co; for(int i = 1; i <= n; i++) { if(a[id][i] != 0 && a[id][i] != -1) { co = a[id][i]; num[n + i][a[id][i]]--; if(num[n + i][a[id][i]] == 0) kind[n + i] -= 1; a[id][i] = 0; } } ans[++tot] = {(PII){id, co}}; } else { int co; id = (id % n == 0) ? (n) : (id % n); for(int i = 1; i <= n; i++) { if(a[i][id] != 0 && a[i][id] != -1) { co = a[i][id]; num[i][a[i][id]]--; if(num[i][a[i][id]] == 0) kind[i] -= 1; a[i][id] = 0; } } ans[++tot] = {(PII){id + n, co}}; } } int main() { freopen("game.in","r",stdin); scanf("%d", &n); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { scanf("%d", &a[i][j]); if(a[i][j] == 0) a[i][j] = -1; } for(int i = 1; i <= n; i++) { bool flg = 1; for(int j = 1; j <= n; j++) { if(a[i][j] == -1) { flg = 0; break; } else { if(num[i][a[i][j]] == 0) kind[i]++; num[i][a[i][j]]++; } } can[i] = flg; } for(int j = 1; j <= n; j++) { bool flg = 1; for(int i = 1; i <= n; i++) { if(a[i][j] == -1) { flg = 0; break; } else { if(num[n + j][a[i][j]] == 0) kind[n + j]++; num[n + j][a[i][j]]++; } } can[n + j] = flg; } for(int i = 1; i <= 2 * n; i++) { for(int j = 1; j <= 2 * n; j++) { if(can[j] == 1 && kind[j] == 1) { work(j); can[j] = 0; break; } } } reverse(ans + 1, ans + 1 + tot); printf("%d\n", tot); for(int i = 1; i <= tot; i++) { printf("%d %d\n", ans[i].first, ans[i].second); } return 0; }

新-滑動(dòng)窗口簡(jiǎn)單差分

典中典，$\sum li \le10^{6}$對(duì)于滑塊頂?shù)阶钭筮吪c滑塊頂?shù)阶钣疫呄嘟坏闹苯颖┝ψ觯绻唤唬苯硬罘肿畲笾担?xì)節(jié)較多

#include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 1e6 + 70; int n, w, l[MAX]; LL ans[MAX], cha[MAX]; LL a[MAX],b[MAX]; //統(tǒng)計(jì) deque<LL> q; void work(int h) { LL maxx = 0; vector<LL> Now; Now.clear(); Now.push_back(0); for(int j = 1; j <= l[h]; j++) { LL x; scanf("%lld", &x); b[j] = x; maxx = max(maxx, x); Now.push_back(x); } if(l[h] < w - l[h] + 1) { //不交 LL Max = 0; for(int i = 1; i <= l[h]; i++) { Max = max(Max, Now[i]); ans[i] += Max; } Max = 0; for(int i = w; i >= w - l[h] + 1; i--) { Max = max(Max, Now[l[h] - (w - i)]); ans[i] += Max; } cha[l[h] + 1] += maxx; cha[w - l[h] + 1] -= maxx; } else { //香蕉 memset(a, 0xcf, sizeof(a)); while(!q.empty()) q.pop_back(); int len = w - l[h] + 1; for(int i = 1; i <= l[h]; i++) { while(!q.empty() && i - q.front() + 1 > len) q.pop_front(); while(!q.empty() && Now[q.back()] < Now[i]) q.pop_back(); q.push_back(i); a[i] = max(a[i], Now[q.front()]); } for(int i = 1; i <= w - l[h]; i++) a[i] = max(a[i], 1LL * 0); while(!q.empty()) q.pop_back(); Now.clear(); for(int i = 0; i <= w - l[h]; i++) Now.push_back(0); for(int i = w - l[h] + 1; i <= w; i++) Now.push_back(b[i - (w - l[h])]); for(int i = w; i >= w - l[h] + 1; i--) { while(!q.empty() && q.front() - i + 1 > len) q.pop_front(); while(!q.empty() && Now[q.back()] < Now[i]) q.pop_back(); q.push_back(i); a[i] = max(a[i], Now[q.front()]); } for(int i = l[h] + 1; i <= w; i++) { a[i] = max(a[i], 1LL * 0); } for(int i = 1; i <= w; i++) { ans[i] += a[i]; } } } int main() { freopen("windows.in","r",stdin); scanf("%d%d", &n, &w); for(int i = 1; i <= n; i++) { scanf("%d", &l[i]); work(i); } for(int i = 1; i <= w; i++) { cha[i] += cha[i - 1]; printf("%lld ", ans[i] + cha[i]); } return 0; } /* 1 5 2 -10 10 */

小明去旅游鍋

目前還不會(huì)，先鍋著

Heavy and Frail：分治優(yōu)化重復(fù)操作

35pts，二進(jìn)制分組背包暴力跑

80pts 背包合并

發(fā)現(xiàn)只有單點(diǎn)修改，其他不變，跑一個(gè)前綴背包，跑一個(gè)后綴背包，對(duì)于查詢，將前后兩個(gè)背包合并，再插入**

//根據(jù)m非常小的性質(zhì)，且是單點(diǎn)修改，完全可以維護(hù)前i個(gè)數(shù)的背包，與后i個(gè)數(shù)的背包，查詢時(shí)暴力合并，復(fù)雜度 m*m*q * logc #include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 5100; int n, m, q; LL val[MAX], v[MAX], num[MAX]; LL f_pre[MAX][810], f_back[MAX][810]; //表示前i個(gè)數(shù)的背包，后i個(gè)數(shù)的背包 LL f[810], ans[MAX * 10]; struct made { int id; LL x, y, z; int whr; }ask[MAX * 10]; bool mycmp(made X, made Y) { return X.id < Y.id; } int main() { freopen("reflect.in","r",stdin); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%lld",&val[i]); for(int i = 1; i <= n; i++) scanf("%lld", &v[i]); for(int i = 1; i <= n; i++) scanf("%lld", &num[i]); scanf("%d", &q); for(int i = 1; i <= q; i++) { scanf("%d%lld%lld%lld", &ask[i].id, &ask[i].x, &ask[i].y, &ask[i].z); ask[i].whr = i; } sort(ask + 1, ask + 1 + q, mycmp); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) f_pre[i][j] = f_pre[i - 1][j]; int Num = num[i], k = 1; while(k <= Num) { LL V = k * v[i]; LL VAL = k * val[i]; for(int j = m; j >= V; j--) f_pre[i][j] = max(f_pre[i][j], f_pre[i][j - V] + VAL); Num -= k; k *= 2; } if(Num != 0) { LL V = Num * v[i]; LL VAL = Num * val[i]; for(int j = m; j >= V; j--) f_pre[i][j] = max(f_pre[i][j], f_pre[i][j - V] + VAL); } } for(int i = n; i >= 1; i--) { for(int j = 1; j <= m; j++) f_back[i][j] = f_back[i + 1][j]; int Num = num[i], k = 1; while(k <= Num) { LL V = k * v[i]; LL VAL = k * val[i]; for(int j = m; j >= V; j--) f_back[i][j] = max(f_back[i][j], f_back[i][j - V] + VAL); Num -= k; k *= 2; } if(Num != 0) { LL V = Num * v[i]; LL VAL = Num * val[i]; for(int j = m; j >= V; j--) f_back[i][j] = max(f_back[i][j], f_back[i][j - V] + VAL); } } for(int i = 1; i <= q; i++) { for(int j = 1; j <= m; j++) f[j] = 0; for(int j = 1; j <= m; j++) { for(int k = 0; k <= j; k++) { f[j] = max(f[j], f_pre[ask[i].id - 1][j - k] + f_back[ask[i].id + 1][k]); } } int Num = ask[i].z, k = 1; while(Num >= k) { LL V = ask[i].y * k; LL VAL = ask[i].x * k; for(int j = m; j >= V; j--) f[j] = max(f[j], f[j - V] + VAL); Num -= k; k *= 2; } if(Num) { LL V = ask[i].y * Num; LL VAL = ask[i].x * Num; for(int j = m; j >= V; j--) f[j] = max(f[j], f[j - V] + VAL); } ans[ask[i].whr] = f[m]; } for(int i = 1; i <= q; i++) printf("%lld\n", ans[i]); return 0; }

100pts

只有單點(diǎn)修改，前后綴的合并$m^2$沒有拓展性，思考如果分治去做，$(l, r)$代表到$(l,r)$區(qū)間內(nèi)除了$(l,r)$都已經(jīng)被加入背包，到$(x, x)$時(shí)便統(tǒng)計(jì)答案，時(shí)間復(fù)雜度$O(nmlog_n^2+mq)$
重復(fù)計(jì)算，分治

#include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 5010; int n, m, q; LL val[MAX], v[MAX], num[MAX], ans[MAX * 10]; LL f[900]; struct made { int id; LL num, v, val; }; vector<made> ask[MAX]; void Nowwork(int l, int r) { for(int j = l; j <= r; j++) { int Num = num[j], k = 1; while(k <= Num) { LL V = k * v[j], VAL = val[j] * k; for(int j = m; j >= V; j--) f[j] = max(f[j], f[j - V] + VAL); Num -= k; k *= 2; } if(Num) { LL V = Num * v[j], VAL = val[j] * Num; for(int j = m; j >= V; j--) f[j] = max(f[j], f[j - V] + VAL); } } } void work(int x) { LL fnow[802]; for(auto y : ask[x]) { int Num = y.num, k = 1; for(int i = 0; i <= m; i++) fnow[i] = f[i]; while(k <= Num) { LL V = k * y.v, VAL = k * y.val; for(int i = m; i >= V; i--) f[i] = max(f[i - V] + VAL, f[i]); Num -= k; k *= 2; } if(Num) { LL V = Num * y.v, VAL = Num * y.val; for(int i = m; i >= V; i--) f[i] = max(f[i - V] + VAL, f[i]); } ans[y.id] = f[m]; for(int i = 0; i <= m; i++) f[i] = fnow[i]; } } void slove(int l, int r) { if(l == r) { work(l); return ; } int mid = (l + r) >> 1; LL fnow[810]; for(int i = 0; i <= m; i++) fnow[i] = f[i]; Nowwork(mid + 1, r); slove(l, mid); for(int i = 0; i <= m; i++) f[i] = fnow[i]; Nowwork(l, mid); slove(mid + 1, r); } int main() { freopen("reflect.in","r",stdin); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%lld", &val[i]); for(int i = 1; i <= n; i++) scanf("%lld", &v[i]); for(int i = 1; i <= n; i++) scanf("%lld", &num[i]); scanf("%d", &q); for(int i = 1; i <= q; i++) { int t; LL x, y, z; scanf("%d%lld%lld%lld", &t, &x, &y, &z); made Now; Now.id = i, Now.num = z, Now.v = y, Now.val = x; ask[t].push_back(Now); } slove(1, n); for(int i = 1; i <= q; i++) { printf("%lld\n", ans[i]); } return 0; }

chess：根據(jù)題意分析

如果暴力DP，發(fā)現(xiàn)字符串比較在最劣情況下為$O(n)$,顯然過(guò)不了，考慮轉(zhuǎn)化問(wèn)題，如果在第$1$步就不是最優(yōu)的策略一定不會(huì)被用到第$2$步，所以基于這個(gè)性質(zhì)，我們可以考慮每一步最優(yōu)為什么，將可以跑到最優(yōu)的存入set，只用set里面的元素更新下一步的最優(yōu)，這樣的時(shí)間復(fù)雜度就轉(zhuǎn)化為了$O((n + m)log)$

#include<bits/stdc++.h> using namespace std; const int MAX = 2100; #define PII pair<int, int> char ch[MAX][MAX]; char minn[MAX + MAX]; queue<PII> q; set<PII> s[MAX + MAX]; int n, m; int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin>>ch[i][j]; for(int i = 1; i <= n + m + 10; i++) minn[i] = 'z'; minn[1] = ch[1][1]; s[1].insert((PII){1, 1}); for(int i = 2; i <= n + m; i++) { for(auto lst : s[i - 1]) { int x = lst.first, y = lst.second; if(x < n && minn[i] >= ch[x + 1][y]) { if(minn[i] > ch[x + 1][y]) s[i].clear(); minn[i] = ch[x + 1][y]; s[i].insert((PII){x + 1, y}); } if(y < m && minn[i] >= ch[x][y + 1]) { if(minn[i] > ch[x][y + 1]) s[i].clear(); if(minn[i] > ch[x][y + 1]) minn[i] = ch[x][y + 1]; s[i].insert((PII){x, y + 1}); } } } for(int i = 1; i <= n + m - 1; i++) { cout<<minn[i]; } return 0; }

glass：簡(jiǎn)單裝呀

數(shù)據(jù)范圍，一眼狀壓，壓什么? 我們發(fā)現(xiàn)一個(gè)瓶子只會(huì)被轉(zhuǎn)移一次，且轉(zhuǎn)移后一定不會(huì)再次轉(zhuǎn)移，所以我們就壓一個(gè)瓶子是否轉(zhuǎn)移過(guò)即可，時(shí)間復(fù)雜度$O(2^nnn)$跑不滿，所以能過(guò)

//一個(gè)瓶子只會(huì)被轉(zhuǎn)移 #include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = (1 << 21); int n, k, ANS = 1e9; int f[MAX], c[25][25]; int Minn[MAX][21]; int main() { freopen("b.in","r",stdin); freopen("b.out","w",stdout); scanf("%d%d", &n, &k); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cin>>c[i][j]; } } memset(Minn, 0x3f, sizeof(Minn)); for(int i = 0; i <= (1 << n) - 1; i++) { for(int j = 0; j < n; j++) { if(i >> j & 1) continue; for(int k = 0; k < n; k++) { if(k != j) if((i >> k & 1) == 0) Minn[i][j] = min(Minn[i][j], c[j][k]); } } } memset(f, 0x3f, sizeof(f)); f[0] = 0; for(int i = 0; i <= (1 << n) - 1; i++) { for(int j = 0; j < n; j++) { if((i >> j & 1) == 0) { f[i | (1 << j)] = min(f[i | (1 << j)], f[i] + Minn[i][j]); } } } int ans = 1e9; for(int i = 0; i <= (1 << n); i++) { int sum = 0; for(int j = 0; j < n; j++) { if((i >> j & 1) == 0) sum++; } if(sum == k) ans = min(ans, f[i]); } cout<<ans<<endl; return 0; }

card：組合意義的DP

原題，但是之前沒做，考場(chǎng)上也是一籌莫展
因?yàn)?mark>一個(gè)序列不同是操作順序有一位不同即可，所以一定有組合意義，考慮如何將一個(gè)問(wèn)題轉(zhuǎn)化為一個(gè)組合問(wèn)題

隨意構(gòu)造一個(gè)序列，我們發(fā)現(xiàn)根據(jù)題意操作

在$1$左側(cè)的數(shù)下標(biāo)一定遞減，在$1$右側(cè)的數(shù)下標(biāo)遞增
那么最大值是怎么統(tǒng)計(jì)的呢? 一定為左側(cè)數(shù)的單調(diào)遞增加上右側(cè)數(shù)的單調(diào)遞增的個(gè)數(shù)

但是要規(guī)定左側(cè)的最大值，小于右側(cè)單調(diào)遞增的最小值

左側(cè)單調(diào)遞增在原序列中為以某個(gè)數(shù)(x)的單調(diào)遞減序列

為了保證上述規(guī)定，右側(cè)的單調(diào)遞增的數(shù)也由x為起點(diǎn)，這樣的話將總數(shù)減1即為最大嚴(yán)格遞增子序列的長(zhǎng)度
而總數(shù)如何計(jì)算，假設(shè)對(duì)于$x$而言由若干個(gè)組合可以構(gòu)成最大嚴(yán)格遞增子序列，對(duì)于其它的數(shù)除了1以外，往左放，往右放都無(wú)所謂，所以答案$+=sum*(2^{n-len+1}/2)1$

而求最長(zhǎng)上升子序列，最長(zhǎng)下降子序列需要一個(gè)$(log)$做法，離散化后值域線段樹即可

//一個(gè)序列不同，當(dāng)且僅當(dāng)操作序列不同，具有計(jì)數(shù)優(yōu)勢(shì) //在1左邊的下標(biāo)遞減，值遞增，在1右邊的下標(biāo)遞增，值遞增 //考慮用一個(gè)數(shù)劃分階段 #include<bits/stdc++.h> using namespace std; #define LL long long //#define int long long const int MOD = 1e9 + 7; const int MAX = 2e5 + 70; int n, a[MAX], b[MAX], tot; LL num_up[MAX], num_down[MAX]; LL f_up[MAX], f_down[MAX]; int lsh[MAX]; struct node { int f, num; }; struct SegmentTree { int l, r; LL f, num; #define l(x) tree[x].l #define r(x) tree[x].r #define f(x) tree[x].f #define num(x) tree[x].num }tree[MAX * 4]; LL quick_mi(int x, int y) { LL xx = x, res = 1; while(y) { if(y & 1) res = res * xx % MOD; xx = xx * xx % MOD; y = y / 2; } return res; } void update(int p) { if(f(2 * p) > f(2 * p + 1)) { f(p) = f(2 * p); num(p) = num(2 * p) % MOD; } else if(f(2 * p + 1) > f(2 * p)) { f(p) = f(2 * p + 1); num(p) = num(2 * p + 1) % MOD; } else if(f(2 * p + 1) == f(2 * p)) { f(p) = f(2 * p); num(p) = (num(2 * p) + num(2 * p + 1)) % MOD; } return ; } void build(int p, int l, int r) { l(p) = l, r(p) = r, f(p) = num(p) = 0; if(l == r) { return ; } int mid = (l + r) >> 1; build(2 * p, l, mid); build(2 * p + 1, mid + 1, r); } node New(node x, node y) { if(x.f > y.f) return x; else if(y.f > x.f) return y; node NOW; NOW.f = x.f; NOW.num = (x.num + y.num) % MOD; return NOW; } node Find(int p, int l, int r) { if(l(p) >= l && r(p) <= r) { node NOW; NOW.f = f(p); NOW.num = num(p); return NOW; } node NOW; NOW.f = 0, NOW.num = 0; int mid = (l(p) + r(p)) >> 1; if(l <= mid) NOW = New(NOW, Find(2 * p, l, r)); if(r > mid) NOW = New(NOW, Find(2 * p + 1, l, r)); return NOW; } void change(int p, int l, int r, int ff, int num) { if(l(p) == r(p)) { if(ff > f(p)) { f(p) = ff; num(p) = num % MOD; } else if(ff == f(p)) { num(p) = (num(p) + num) % MOD; } return ; } int mid = (l(p) + r(p)) >> 1; if(mid >= l) change(2 * p, l, r, ff, num); if(r > mid) change(2 * p + 1, l, r, ff, num); update(p); } void Clear() { for(int i = 0; i <= 8e5 + 1; i++) tree[i].f = tree[i].num = 0; } signed main() { freopen("c.in","r",stdin); scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = a[i]; } sort(b + 1, b + 1 + n); for(int i = 1; i <= n; i++) if(b[i] != b[i - 1]) lsh[++tot] = b[i]; for(int i = 1; i <= n; i++) a[i] = lower_bound(lsh + 1, lsh + 1 + tot, a[i]) - lsh; reverse(a + 1, a + 1 + n); build(1, 0, 2e5 + 1); change(1, 2e5 + 1, 2e5 + 1, 0, 1); for(int i = 1; i <= n; i++) { node NOW = Find(1, a[i] + 1, 2e5 + 1); f_up[i] = NOW.f + 1; num_up[i] = NOW.num % MOD; change(1, a[i], a[i], f_up[i], num_up[i]); } Clear(); change(1, 0, 0, 0, 1); for(int i = 1; i <= n; i++) { node NOW = Find(1, 0, a[i] - 1); f_down[i] = NOW.f + 1; num_down[i] = NOW.num % MOD; change(1, a[i], a[i], f_down[i], num_down[i]); } LL maxx = 0, NUM = 0; for(int i = 1; i <= n; i++) { if(f_up[i] + f_down[i] - 1 > maxx) { maxx = f_up[i] + f_down[i] - 1; NUM = 0; } if(f_up[i] + f_down[i] - 1 == maxx) NUM = (NUM + (1LL * num_up[i] * num_down[i] % MOD * quick_mi(2, n - f_up[i] - f_down[i] + 1) % MOD) ) % MOD; } cout<<maxx<<' '<<NUM<<endl; return 0; }

godnumber:鍋

ACAM套數(shù)位DP，還沒打

meirin：暴力化簡(jiǎn)式子

簡(jiǎn)單數(shù)學(xué)題?
首先不考慮增加操作，如果單求
$\sum_{l=1}^{n} \sum_{r=l}^{{n}(\sum_{j=l}}a_i)(\sum_{j=l}^{r}b_i)$

考慮將里面的式子用前綴和表示出來(lái)即

$\sum_{l=1}^{n} \sum_{r=l}^{n}(Sa_r-Sa_{l-1})(Sb_r-Sb_{l-1})$

展開
$\sum_{l=1}^{n} \sum_{r=l}^{n}(Sa_rSb_r+Sa_{l-1}Sb_{l-1}-Sa_rSb_{l-1}-Sb{r}Sa_{l-1})$
令$S_{ab_i}$表示$Sa_i*Sb_i$,$SSa$表示$Sa$的前綴和，$SSb$表示$Sb$的前綴和

將式子中的$r$累加起來(lái) 化簡(jiǎn)為$\sum_{i=1}^{n}S_{ab_i}n-Sa_{i-1}(SSb_{n}-SSb_{i-1})-Sb_{i-1}*(SSa_{n}-SSa_{i-1})$
這樣就得到了一個(gè)$NQ$ 時(shí)間復(fù)雜的的代碼，考慮如果有修改，考慮修改的貢獻(xiàn)
顯然題目中只對(duì)$b$進(jìn)行操作，考慮每個(gè)$b$對(duì)應(yīng)的$a$區(qū)間和
$\sum_{l=1}^{{i}\sum_{r=i}}\sum_{j=l}^{r}a_i$
前綴優(yōu)化一維
$\sum_{l=i}^{{i}\sum_{r=i}}S_{a_r}-S_{a_{l-1}}$
將式子拆開，分別積掉一個(gè)$\sum$后再相加

$\sum_{i=1}^{n}i*(SS_{a_n}-SS_{a_{i-1}})-(n-i+1)(SS_{a_{i-1}})$
再對(duì)這個(gè)式子求前綴和即可$O1$計(jì)算貢獻(xiàn),總時(shí)間復(fù)雜度$O(n+q)$

#include<bits/stdc++.h> using namespace std; #define LL long long #define lll 1LL const int MAX = 5e5 + 70; const int MOD = 1e9 + 7; int n, q; int a[MAX], b[MAX], sa[MAX], ssa[MAX]; int g[MAX], sg[MAX]; LL ans; int main() { scanf("%d%d", &n, &q); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++) scanf("%d", &b[i]); for(int i = 1; i <= n; i++) sa[i] = (1LL * sa[i - 1] + 1LL * a[i] ) %MOD; for(int i = 1; i <= n; i++) ssa[i] = (1LL * ssa[i - 1] + 1LL * sa[i]) % MOD; for(int i = 1; i <= n; i++) { g[i] = ((1LL * i * ((1LL * ssa[n] - 1LL * ssa[i - 1] + MOD) % MOD) - (1LL * (n - i + 1) * (1LL * ssa[i - 1])) ) + MOD ) % MOD; } for(int i = 1; i <= n; i++) sg[i] = (1LL * sg[i - 1] + g[i] + MOD) % MOD; for(int i = 1; i <= n; i++) ans = (ans + (1LL * g[i] * b[i] % MOD) ) % MOD; for(int i = 1; i <= q; i++) { int l, r, k; scanf("%d%d%d", &l, &r, &k); ans = (ans + ((1LL * sg[r] - sg[l - 1] + MOD) % MOD * 1LL * k) % MOD + MOD) % MOD; printf("%lld\n", ans); } return 0; }

sakuya:期望樹形DP好題

~~最討厭期望什么的了~~

首先不考慮修改

分析題意，要求期望難走程度，期望=概率*值

將值的貢獻(xiàn)拆分成若干點(diǎn)對(duì)的貢獻(xiàn)，發(fā)現(xiàn)每個(gè)點(diǎn)對(duì)在序列中相鄰的概率是相同的

題意變?yōu)?$\sum_{l=1}^{{m}\sum_{r=1}}dis(l,r)(l \ne r)*P$

首先考慮$P$怎么計(jì)算，發(fā)現(xiàn)$P$實(shí)際等于$\frac{2*(m-1)A_{m-2}^{m-2}}{A_{m}{m}}$

接下來(lái)問(wèn)題轉(zhuǎn)化為點(diǎn)對(duì)之間的貢獻(xiàn)如何計(jì)算,發(fā)現(xiàn)不好處理，考慮與上面相同的處理方式，將點(diǎn)對(duì)貢獻(xiàn)轉(zhuǎn)化為邊權(quán)*出現(xiàn)次數(shù)

發(fā)現(xiàn)出現(xiàn)次數(shù)可以用$f[v]*(m-f[v])$計(jì)算得出($f[i]表示以i為根的子樹中特殊點(diǎn)的個(gè)數(shù)$)
重新加回修改的限制

考慮對(duì)一個(gè)點(diǎn)的相連邊增加$k$對(duì)答案的增量為什么?為相連邊出現(xiàn)次數(shù)$num$×$k$

上述所有操作都可以在一次樹形DP中處理，時(shí)間復(fù)雜度$O(N+Q)$

#include<bits/stdc++.h> using namespace std; #define int long long #define LL long long const int MAX = 5e5 + 70; const int MOD = 998244353; int tot, head[MAX], n, m, q, p[MAX], fa[MAX], f[MAX]; //表示以i為子樹的特殊點(diǎn)的個(gè)數(shù) LL ans = 0; int Num[MAX], sum[MAX]; vector<int> son[MAX]; vector<int> ce[MAX]; struct node { int u, v, val; }E[2 * MAX]; struct made { int l, t, id, val; }edge[MAX * 2]; void add(int u, int v, int id, int val) { edge[++tot].l = head[u]; edge[tot].t = v; edge[tot].val = val; edge[tot].id = id; head[u] = tot; } void dfs_pre(int x, int Fa) { fa[x] = Fa; f[x] = p[x]; for(int i = head[x]; i; i = edge[i].l) { int to = edge[i].t; if(to == Fa) continue; ce[x].push_back(to); son[x].push_back(to); dfs_pre(to, x); f[x] += f[to]; } } LL quick_mi(int x, int y) { LL xx = x, res = 1; while(y) { if(y % 2) res = res * xx % MOD; xx = xx * xx % MOD; y /= 2; } return res % MOD; } signed main() { scanf("%lld%lld", &n, &m); for(int i = 1; i < n; i++) { int u, v, val; scanf("%lld%lld%lld", &u, &v, &val); E[i].u = u, E[i].v = v; E[i].val = val; add(u, v, i, val); add(v, u, i, val); } for(int i = 1; i <= m; i++) { int x; scanf("%lld", &x); p[x] = 1; } LL P_up = 1, P_down = 1, P; for(int i = 1; i <= m - 2; i++) P_up = (P_up * 1LL * i )% MOD; for(int i = 1; i <= m; i++) P_down = (P_down * 1LL * i) % MOD; P = 2LL * (m - 1) * P_up % MOD * quick_mi(P_down, MOD - 2) % MOD; dfs_pre(1, 0); //兒子節(jié)點(diǎn)，父親節(jié)點(diǎn)，相鄰的邊 for(int i = 1; i < n; i++) { if(E[i].u != fa[E[i].v]) swap(E[i].u, E[i].v); Num[E[i].v] = (f[E[i].v] * (m - f[E[i].v])) % MOD; } for(int i = 1; i < n; i++) { if(E[i].u != fa[E[i].v]) swap(E[i].u, E[i].v); ans = (ans + (E[i].val * Num[E[i].v] % MOD) ) % MOD; } for(int i = 1; i <= n; i++) { sum[i] = (sum[i] + Num[i]) % MOD; for(int j = 0; j < ce[i].size(); j++) sum[i] = (sum[i] + Num[ce[i][j]]) % MOD; } scanf("%lld", &q); for(int i = 1; i <= q; i++) { int x, k; scanf("%lld%lld", &x, &k); ans = (ans + (1LL * sum[x] * k)) % MOD; printf("%lld\n", (ans * P) % MOD); } return 0; }

交換消消樂:簡(jiǎn)單性質(zhì)題

將貢獻(xiàn)拆成兩部分，一部分為消除貢獻(xiàn)顯然為$n$,另一部分為移動(dòng)貢獻(xiàn)

考慮對(duì)于一個(gè)元素$i$,把$i$消掉需要多少步

設(shè)$i$左右端點(diǎn)分別為$l_i,r_i$

若只將$[l_i,r_i]$中元素移除區(qū)間，不考慮移動(dòng)左右端點(diǎn)

如果將$i$這個(gè)元素消掉，則需要$[l_i,r_i]$中的出現(xiàn)次數(shù)為奇數(shù)的元素離開$[l_i,r_i]$的區(qū)間

通過(guò)打表或手玩發(fā)現(xiàn)，移動(dòng)次數(shù)為所有$[l_i,r_i]$中出現(xiàn)奇數(shù)次的數(shù)的個(gè)數(shù)之和

這樣我們就得到了一個(gè)$n ^ 2$做法，發(fā)現(xiàn)統(tǒng)計(jì)奇數(shù)次出現(xiàn)數(shù)目不好統(tǒng)計(jì)，正難則反

用$r_i-l_i+1-2num_{mod2=0}$含義是區(qū)間長(zhǎng)度減去出現(xiàn)偶數(shù)次的數(shù)的個(gè)數(shù)$2$即為出現(xiàn)奇數(shù)次個(gè)數(shù)

發(fā)現(xiàn)滿足$l_i<=l_j$和$r_i>=r_j$二維數(shù)點(diǎn)問(wèn)題，樹狀數(shù)組維護(hù)即可

#include<bits/stdc++.h> using namespace std; #define LL long long const int MAX = 5e5 + 70; int n,val[2 * MAX]; LL ans = 0, tree[MAX * 2]; bool bol[MAX]; struct made { int l, r; }a[MAX]; bool mycmp(made X, made Y) { return X.l > Y.l; } int lowbit(int x) { return x & (-x); } LL Find(int x) { LL res = 0; for(int i = x; i; i -= lowbit(i)) res += tree[i]; return res; } void add(int x) { for(int i = x; i <= 2 * n; i += lowbit(i)) tree[i] += 1; } int main() { scanf("%d", &n); for(int i = 1; i <= 2 * n; i++) { scanf("%d", &val[i]); if(bol[val[i]] == 0) { a[val[i]].l = i; bol[val[i]] = 1; } else a[val[i]].r = i; } sort(a + 1, a + 1 + n, mycmp); for(int i = 1; i <= n; i++) { LL res = Find(a[i].r); ans = ans + (a[i].r - a[i].l - 1 - 2 * res); add(a[i].r); } ans = ans / 2; ans = ans + n; printf("%lld\n", ans); return 0; }

[ABC232H] King's Tour：構(gòu)造，鍋

Road of the King：神奇DP

神奇$DP$,希望得到一個(gè)$n^3$的做法

首先發(fā)現(xiàn)$1$能到達(dá)所有點(diǎn), 所以若一個(gè)圖為強(qiáng)聯(lián)通分量，當(dāng)且僅當(dāng)所有點(diǎn)都能到達(dá)$1$

不妨設(shè)計(jì)$DP$狀態(tài)為$f[i][j][k]$表示已經(jīng)走了$i$步，且經(jīng)過(guò)了$j$個(gè)點(diǎn)，能夠到達(dá)$1$點(diǎn)的個(gè)數(shù)為$k$的方案數(shù)

我們想初始值如何賦,根據(jù)狀態(tài)可得$f[0][1][1] = 1$

轉(zhuǎn)移分三種情況

*1.若下一步前往了一個(gè)新的節(jié)點(diǎn)，得到轉(zhuǎn)移 : $f[i + 1][j + 1][k] += f[i][j][k] (n-j)$
2.若下一步重新去往了無(wú)法到達(dá)$1$的節(jié)點(diǎn), 得到轉(zhuǎn)移 $f[i + 1][j][k]=f[i][j][k]*(j-k)$
3.若下一步去往了任意一個(gè)可以到達(dá)$1$的節(jié)點(diǎn)，則可以使所有不能到達(dá)$1$的節(jié)點(diǎn)全部變?yōu)榭梢缘竭_(dá), 得到轉(zhuǎn)移$f[i+1][j][j]=f[i][j][k]*k$
綜上即可解決問(wèn)題

題目的分析其實(shí)非常巧妙，為何這樣設(shè)計(jì)狀態(tài)，為何這樣轉(zhuǎn)移一定是正確的

都可以從題目要求每次都從當(dāng)前節(jié)點(diǎn)指向下一節(jié)點(diǎn),起點(diǎn)為$1$ 這兩個(gè)限制條件，或者關(guān)鍵性質(zhì)得出，所以要多注意題目的限制條件，設(shè)計(jì)與限制條件有關(guān)的$DP$狀態(tài)去解決問(wèn)題

醉醉瘋瘋渺渺空空換根dp

經(jīng)典題，考慮如何計(jì)數(shù)
兩點(diǎn)不在一條鏈上，發(fā)現(xiàn)如果能統(tǒng)計(jì)每個(gè)點(diǎn)子樹距離它的$\sum 2^{dis}$，此題就可做了
兩點(diǎn)在一條鏈上，發(fā)現(xiàn)需要統(tǒng)計(jì)$v$子樹外的點(diǎn)距離它的$\sum2^{dis}$$(dep[v]<dep[u])$,考慮求全集，然后減去$v$子樹中的$dis$之和即為子樹外的，然后全集就是換根求即可

F - Robot Rotation 不能隨機(jī)化的折半搜索

數(shù)據(jù)范圍提醒我們一定是一個(gè)優(yōu)化后的指數(shù)級(jí)算法，考慮如何搜索.
根據(jù)題目的要求
我們發(fā)現(xiàn)$x$軸上移動(dòng)只與奇數(shù)位的數(shù)字有關(guān)
$y$軸上的移動(dòng)只與偶數(shù)位的數(shù)值大小有關(guān)
考慮$x$軸與$y$軸分離開,折半搜索可過(guò)

E - Revenge of "The Salary of AtCoder Inc." 期望

期望DP,感覺這塊太薄弱了
期望一般都是倒著做的
考慮設(shè)計(jì)狀態(tài)$f[i]$表示從第$i$天為起點(diǎn)，直到結(jié)束的期望收益
發(fā)現(xiàn)$f[i]是由\sum f_j (j >i)$，然后發(fā)現(xiàn)可以前綴和優(yōu)化，然后就做完了？

A. 1031模擬賽-A進(jìn)步科學(xué) 狀壓DP

貌似可以稱作狀壓經(jīng)典套路題

如果一次操作結(jié)束前不能使用其他的操作，我們發(fā)現(xiàn)一位狀態(tài)$f[S]$表示狀態(tài)為$S$的最小時(shí)間即可解決

目前唯一的難點(diǎn)在于在一次操作結(jié)束前可以使用其他操作，這也就表示了可能會(huì)有多種操作在同一時(shí)間同時(shí)進(jìn)行

那么最直觀的感受當(dāng)然是$f[S][T]$表示當(dāng)前狀態(tài)為 $S$還有的操作序列為$T$的最小時(shí)間，但是我們發(fā)現(xiàn)時(shí)間仍然不對(duì)

首先我們發(fā)現(xiàn)總時(shí)間不會(huì)超過(guò)$2n$

那么上面竟然也說(shuō)了時(shí)間很關(guān)鍵，考慮將操作序列抽象為一個(gè)關(guān)于時(shí)間的排列，若第$i$位為$0$即代表這一秒沒有操作，若第$i$秒為$j$,則代表對(duì)$j$進(jìn)行操作

考慮將某一個(gè)時(shí)刻的操作抽象成一個(gè)二進(jìn)制數(shù)，每次異或這個(gè)數(shù)即為影響，但這樣的時(shí)間復(fù)雜度為$20^{20}$

我們接著考慮優(yōu)化，如果我們只記錄相同狀態(tài)的最小值就可以刪去很多無(wú)用信息

那么我們結(jié)合上面的，大膽設(shè)計(jì)狀態(tài)$f[t][S]$表示在$t$秒狀態(tài)為$S$是否合法，但是如果我們考慮向序列后面加數(shù)的話，無(wú)法保證結(jié)束時(shí)間，不妨往操作序列前面加數(shù)，這樣就類似枚舉了一個(gè)終止時(shí)間，然后就可以轉(zhuǎn)移了

時(shí)間復(fù)雜度$O(n2^n)$

B. 1031模擬賽-B吉吉沒急差分約束

是一道轉(zhuǎn)換很巧妙的題

首先考慮用$-1$和$1$增加限制

先考慮$-1$,首先用若設(shè)計(jì)$f[x]$表示$x$最早什么時(shí)候可以學(xué)會(huì)

那么$-1$的點(diǎn)的$f[x]$都為正無(wú)窮

如果其他點(diǎn)和$-1$的點(diǎn)有連邊的話，那么最早只能在$L + 1$的時(shí)間連邊

那么如果我們發(fā)現(xiàn)$f[0]$比$0$大的話說(shuō)明不合法

然后用$1$考慮增加限制,然后判斷每一個(gè)$1$是否合法

C. 1031模擬賽-C老杰克噠動(dòng)態(tài)DP

首先我們寫出轉(zhuǎn)移式

$a[i] = 0$

$\qquad$$f[i][1] = min(f[i - 1][0] + 1, f[i - 1][1] + 1);$

$\qquad f[i][0] = min(f[i - 1][0], f[i - 1][1] + 2);$

$a[i] = 1$

$\qquad f[i][1] = min(f[i - 1][0], f[i - 1][1]);$

$\qquad f[i][0] = min(f[i - 1][0] + 1, f[i - 1][1] + 2);$

我們發(fā)現(xiàn)轉(zhuǎn)移式是線性的且有修改，那么就是動(dòng)態(tài)DP無(wú)疑了

動(dòng)態(tài)DP構(gòu)造矩陣時(shí)可以把行看成輸入值，把列看成輸出值

線段樹+矩陣維護(hù)一下

排座位 - 題目 - Daimayuan Online Judge] DP

如果沒有不能相鄰的限制的話，那么按照大小從小到大排序，兩兩配對(duì)即可得到最小值

接下來(lái)我們加入限制

下方黑色字代表的時(shí)排完序后的編號(hào)，上方綠色和紅色字體是排序前的編號(hào)，紫色數(shù)字是空的下標(biāo)

首先我們發(fā)現(xiàn)，如果有一對(duì)數(shù)$(fis,sed)$它們排完序后仍然互斥，我們考慮把它們倆拆開，

當(dāng)然最優(yōu)方案是和$fis$前一個(gè)換一換，或者$sed$和后一個(gè)換一換

那么我們自然的設(shè)計(jì)$dp$狀態(tài)$f[i][0/1/2]$分別代表這一對(duì)數(shù)不換，前一個(gè)數(shù)換，后一個(gè)數(shù)換

那么轉(zhuǎn)移如下

$if(AT same organize(a[i],a[i-1]))$

$\qquad f[i][0] = 0x3f3f3f3f3f3f3f$

$\qquad f[i][1] = f[i-2][2]+abs(a[i]-a[i-2])$

$\qquad f[i][0] = 0x3f3f3f3f3f3f3f$

$\qquad f[i][2] = min(f[i - 2][2] + abs(a[i - 2].val - a[i + 1].val), min(f[i - 2][0], f[i - 2][1])+ abs(a[i - 1].val - a[i + 1].val));$

$else$

$\qquad f[i][0] = min(min(f[i - 2][0], f[i - 2][1]) + abs(a[i - 1].val a[i].val), f[i - 2][2] + abs(a[i - 2].val - a[i].val));$

A. 方塊游戲 - 題目 - 多校信息學(xué)訓(xùn)練題庫(kù)

普及題場(chǎng)上切不掉，真是個(gè)菜狗啊

首先考慮套路，差分一下區(qū)間修改變?yōu)榱藛吸c(diǎn)修改

這時(shí)候我們發(fā)現(xiàn)題目的要求就變成了將差分序列變?yōu)橐欢芜B續(xù)$>1$的段和一段$<0$的段

維護(hù)一下就行了

B. 雪球 - 題目 - 多校信息學(xué)訓(xùn)練題庫(kù)

細(xì)節(jié)題，想不出來(lái)真菜啊??

首先我們發(fā)現(xiàn)一個(gè)雪球最多能收集到的雪就是$r[i]-l[i]+1$,$r[i].l[i]$分別表示它左右兩個(gè)雪球

但是實(shí)際能收集多少呢?

對(duì)與左邊的雪，應(yīng)該是它向左與$l[i]$向右的長(zhǎng)度恰好相接的長(zhǎng)度，

對(duì)于右邊的雪也是同理

然后我們發(fā)現(xiàn)每個(gè)雪球的移動(dòng)的距離相同，不妨維護(hù)前$i$個(gè)時(shí)刻向左最長(zhǎng)距離，向右最長(zhǎng)距離

然后二分一下就行了，但是要注意細(xì)節(jié)，

因?yàn)橛锌赡軟]有相切的時(shí)刻，那我們只能找下一次恰好交的位置

這時(shí)候統(tǒng)計(jì)雪的量的時(shí)候，我們還要看一看下一次實(shí)際有效移動(dòng)，是向哪個(gè)方向，統(tǒng)計(jì)的量不同

D. 不要FQ - 題目 - 多校信息學(xué)訓(xùn)練題庫(kù) 動(dòng)態(tài)DP

因?yàn)榭梢韵蛏舷蛳屡埽园凑樟袨殡A段

首先應(yīng)該能夠想出基本的$DP$

$f[1][i]=f[1][i-1]a[1][i]+(f[0][i-1]a[0][i]*a[1][i])$

$f[0][i]=f[0][i-1]a[0][i]+(f[1][i-1]a[0][i]*a[1][i])$

如果對(duì)于$T>0$的情況，我們選擇直接構(gòu)造一個(gè)$2*2$的矩陣

但是對(duì)于$T=0$的情況呢

我們不妨枚舉左端點(diǎn)

然后考慮前$i$個(gè)的 $sum$

得到轉(zhuǎn)移

$sum[i] = sum[i-1]+f[i-1][0]+f[i-1][1]$ (這里求的不包含第$i$位)

然后發(fā)現(xiàn)也是線性的，可以將矩陣變成$3*3$的就行了

23zr提高day9-美人魚 - 題目 - Zhengrui Online Judge (zhengruioi.com)

看完題解直接就懂了，非常套路

將區(qū)間排序

首先，如果區(qū)間互不交的話

顯然我們每次單點(diǎn)修改只會(huì)對(duì)一個(gè)區(qū)間有影響，這樣的話二分一下就行了

考慮區(qū)間有交

會(huì)對(duì)一些區(qū)間有影響，我們畫一些情況觀察一下，如果沒有區(qū)間被包含的情況下，修改的應(yīng)該是一段連續(xù)的下標(biāo)

但是如果區(qū)間有包含呢?

顯然被包含的區(qū)間沒有用，把它們刪除就可以了

然后區(qū)間修改線段樹維護(hù)即可

總結(jié)

以上是生活随笔為你收集整理的模拟赛好题分享的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

赛好题

歡迎分享！

轉(zhuǎn)載請(qǐng)說(shuō)明來(lái)源于"生活随笔"，并保留原作者的名字。

本文地址：模拟赛好题分享

上一篇：【调度算法】并行机调度问题遗传算法

下一篇： Python 机器学习入门：数据集、数据

最新發(fā)布

java信息管理系统总结_java实现科研信息管理系统

金融行业信息系统信息安全等级保护实施指引_中国人民银行发布金融行业网络安全等级保护实施指引...

ultraedit中文粘贴出去乱码_Windows系统-怎么搞定乱码

如何读emmc里的引导程序_自制操作系统学习1 引导程序

windows7专业版_windows7专业版和旗舰版的区别

熱門推薦

鸿蒙系统激活炼妖壶设备管理员实现应用双开（微信，QQ三开）以及常见问题解决

启动时检测不到u盘启动-(启动时检测不到u盘启动怎么办)

uu盘如何制作pe系统教程-(如何制作U盘PE系统)

acer如何在u盘启动不系统还原-(acer电脑u盘启动不了)

华硕笔记本开机进u盘-(华硕笔记本开机进u盘快捷键)

標(biāo)簽云

连接数据库

单元格

蓝牙耳机

程序语言

微信游戏

软件安装

双系统

游戏开发者

设计理念

计算机资源

理工科

长老

任丘

毁了

焦躁

大赢家

李商隐代赠中

平板电脑

纺织品

emotnui

3atv精品不卡视频,97人人超碰国产精品最新,中文字幕av一区二区三区人妻少妇,久久久精品波多野结衣,日韩一区二区三区精品

windows

模拟赛好题分享

山茶花

100pts

60pts

100pts 區(qū)間操作固定套路，轉(zhuǎn)化為前綴操作

dream

20pts 神奇分塊

杭州:轉(zhuǎn)化題意，正難則反

正難則反(或者對(duì)于這種有刪邊操作的題)， 我們看成反向加邊

看題：構(gòu)造

坐飛機(jī):斜率優(yōu)化DP

抓頹 : 啟發(fā)式合并 + stl大雜燴

討厭的線段樹

Foo Fighters ：構(gòu)造

亂搞一：大膽隨機(jī)化

正解:位運(yùn)算 -> 基本套路 按位考慮

Hack it! ： 構(gòu)造

光之劍：計(jì)數(shù)DP

正解:正難則反，取補(bǔ)集

Divide

正解:科技-Stern-Brocot樹 法里樹

Stern-Brocot樹

性質(zhì)1 單調(diào)性

性質(zhì)2 SB Tree的所產(chǎn)生的分?jǐn)?shù)都是最簡(jiǎn)分?jǐn)?shù)

證明

法里樹

醒幸：正難則反

相似題目:杭州

正解:轉(zhuǎn)化題意, 二分

ABC321F :退背包

正解:性質(zhì)題

農(nóng)場(chǎng)道路修建 : 問(wèn)題轉(zhuǎn)化

正解 ：問(wèn)題轉(zhuǎn)化

方法一 :

方法二 :

密碼鎖：優(yōu)化DP

25pts:DP

55pts：區(qū)間DP+線段樹優(yōu)化

100pts：?jiǎn)栴}轉(zhuǎn)化+性質(zhì)

魔法是變化之神

60pts:背包,求補(bǔ)集

100pts：考慮隨機(jī)數(shù)據(jù)

奶牛的數(shù)學(xué)題:單位貢獻(xiàn)

正解

路遇矩陣

奶牛的括號(hào)匹配:狀壓

潤(rùn)不掉了：轉(zhuǎn)化點(diǎn)對(duì)問(wèn)題

40pts

100pts 子樹貢獻(xiàn)轉(zhuǎn)化

美好的查詢:神奇主席樹

80pts：分塊+并查集

100pts:神奇主席樹，多看看

新涂色游戲:操作反做

新-滑動(dòng)窗口簡(jiǎn)單差分

小明去旅游 鍋

Heavy and Frail：分治優(yōu)化重復(fù)操作

35pts，二進(jìn)制分組背包暴力跑

80pts 背包合并

100pts

chess：根據(jù)題意分析

glass：簡(jiǎn)單裝呀

card：組合意義的DP

godnumber:鍋

meirin：暴力化簡(jiǎn)式子

sakuya:期望樹形DP好題

交換消消樂:簡(jiǎn)單性質(zhì)題

[ABC232H] King's Tour：構(gòu)造，鍋

Road of the King：神奇DP

醉醉瘋瘋渺渺空空換根dp

F - Robot Rotation 不能隨機(jī)化的折半搜索

E - Revenge of "The Salary of AtCoder Inc." 期望

A. 1031模擬賽-A進(jìn)步科學(xué) 狀壓DP

B. 1031模擬賽-B吉吉沒急 差分約束

C. 1031模擬賽-C老杰克噠 動(dòng)態(tài)DP

排座位 - 題目 - Daimayuan Online Judge] DP

A. 方塊游戲 - 題目 - 多校信息學(xué)訓(xùn)練題庫(kù)

B. 雪球 - 題目 - 多校信息學(xué)訓(xùn)練題庫(kù)

D. 不要FQ - 題目 - 多校信息學(xué)訓(xùn)練題庫(kù) 動(dòng)態(tài)DP

正難則反(或者對(duì)于這種有刪邊操作的題)，我們看成反向加邊

正解:位運(yùn)算 -> 基本套路按位考慮

Hack it! ：構(gòu)造

正解:科技-Stern-Brocot樹法里樹

正解：問(wèn)題轉(zhuǎn)化

小明去旅游鍋

B. 1031模擬賽-B吉吉沒急差分約束

C. 1031模擬賽-C老杰克噠動(dòng)態(tài)DP